检索结果-内蒙古大学图书馆

parallel routing in regular networks with faults

INFORMATION PROCESSING LETTERS 2019年 142卷 84-89页

作者： Sabir, Eminjan Meng, Jixiang Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Peoples R China

With the continuous increasing the scale of networks, routing in networks with faulty processors has become inevitable. Motivated by parallel routing in networks with faults, we investigate the fault-tolerant maximally local connectivity of regular networks. A network G is (fault-tolerant maximally local-connected if each pair of nodes x and y of G F are connected by min{dG_F (x), (Y)} parallel (node-disjoint) paths for any node subset F of G with WI < f, where dG_F (x) and do-F(y) are the degrees of x and y in G F, respectively. In this paper, we give a sufficient condition for regular networks to be f-fault-tolerant maximally local-connected. Furthermore, we apply this result on some well-known networks. In addition, several known results about other interconnection networks are straight consequence of our result. (C) 2018 Elsevier B.V. All rights reserved.

关键词： parallel routing Fault tolerance Regular networks

来源：评论

学校读者我要写书评

暂无评论

Optimal parallel routing in star networks

引用

IEEE TRANSACTIONS ON COMPUTERS 1997年第12期46卷 1293-1303页

作者： Chen, CC Chen, J Tatung Inst Technol Dept Comp Sci Taipei 10451 Taiwan Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

Star networks have recently been proposed as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. In this paper, we present an efficient algorithm that constructs an ... 详细信息

关键词： network routing star network parallel routing partition matching graph container shortest path

来源：评论

学校读者我要写书评

暂无评论

Nearly optimal one-to-many parallel routing in star networks

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 1997年第12期8卷 1196-1202页

作者： Chen, CC Chen, J Tatung Inst Technol Dept Comp Engn & Sci Taipei 10451 Taiwan Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

Star networks were proposed recently as an attractive alternative to the well-known hypercube models for interconnection networks. Extensive research has been performed that shows that star networks are as versatile as hypercubes. This paper is an effort in the same direction. Based on the well-known paradigms, we study the one-to-many parallel routing problem on star networks and develop an improved routing algorithm that finds n - 1 node-disjoint paths between one node and a set of other n - 1 nodes in the n-star network. These parallel paths are proven of minimum length within a small additive constant, and the running time of our algorithm is bounded by O(n(2)). More specifically, given a node s and n - 1 other nodes {t(1), t(2),..., t(n-1)} in the n-star network, our algorithm constructs n - 1 node-disjoint paths P-1, P-2..., Pn-1, where P-i is a path from s to t(i) of length at most dist(s, t(i)) + 6 and dist(s, t(i)) is the distance, i.e., the length of a shortest path, from s to t(i), for i = 1,2,..., n - 1. The best bound on the path length by previously known algorithms for the same problem is 5(n - 2) approximate to 10 Delta(n)/3, where Delta(n) = max{dist(s, t)} is the diameter of the n-star network.

关键词： interconnection network node-disjoint paths parallel routing routing algorithm shortest path star network

来源：评论

学校读者我要写书评

暂无评论

Serial-Equivalent Static and Dynamic parallel routing for FPGAs

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2020年第2期39卷 411-423页

作者： Shen, Minghua Zhang, Wentai Luo, Guojie Xiao, Nong Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou 510275 Peoples R China Sun Yat Sen Univ Key Lab Machine Intelligence & Adv Comp Minist Educ Guangzhou 510275 Peoples R China Peking Univ Ctr Energy Efficient Comp & Applicat Sch Elect Engn & Comp Sci Beijing 100871 Peoples R China

Serial equivalency enables easier regression testing and customer support in production-grade parallel CAD tools. While existing parallel routing techniques have become sufficiently advanced to provide good speedup, support for serial equivalency still has been very limited or ignored because it was considered costly. In this paper, we present a serial-equivalent parallel router that not only provides significant speedup but also produces the same result as the serial router. This parallel router primarily leverages a dependency-aware scheduling algorithm to facilitate the serial equivalency. Moreover, regardless of how many processor cores are used, this scheduling algorithm also enables parallel router to have the same result as the serial router. In scheduling algorithm, according to the original net order of serial router, all of the nets are scheduled to a series of different stages. Specifically, the independent nets are scheduled to the same stage and they can be routed in parallel while the dependent nets are scheduled in different stages and they are processed in serial. Note that the parallel routing of independent nets can be explored in static and dynamic fashions, and the data synchronization between dependent stages is implemented in MPI-based message queue. Experimental evaluations using ten large designs from the academic VTR benchmark suite show that our parallel router can scale to 32 processor cores at least to provide an average 19.13x speedup compared to the state-ofthe-art academic VPR router. And most importantly, our parallel router can maintain the serial equivalency which achieves the same results as the serial router. To the best of our knowledge, it is the first parallel router that provides significant speedup with a serial equivalency guarantee.

关键词： Field-programmable gate array (FPGA) FPGA CAD parallel routing routing serial equivalency

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel routing Algorithms for Cartesian and Composition Networks

引用

13th International-Computer-Society-of-Iran-Computer Conference

作者： Bakhshi, Marzieh Bakhshi, Saeedeh Sarbazi-Azad, Hamid Sharif Univ Technol Tehran Iran

ISBN: (纸本)9783540899846

The Cartesian and Composition products are two well known graph products, also applied to interconnection networks area. The Cartesian and Composition network products possess great characteristics of fault resilience according to their high connectivity. In this paper. we study the existence and construction of parallel routing paths in these two well-known product networks. To prove the existence of certain number of parallel paths in these product networks, we need to compute their connectivity. By assuming the availability of certain number of faulty nodes, we propose some new shortest-path parallel routing algorithms. These algorithms can be used both in faulty networks and to route different data from different paths to a specified target node. We also study the concept of container length and wide diameter of the two mentioned product networks. Comparison between wide diameters and diameters of the two networks exhibit the efficiency of these product networks in constructing node disjoint paths.

关键词： parallel routing Cartesian product Composition product Fault tolerant routing Connectivity

来源：评论

学校读者我要写书评

暂无评论

Fine-Grained parallel routing for FPGAs with Selective Expansion 36

Fine-Grained Parallel Routing for FPGAs with Selective Expan...

引用

36th IEEE International Conference on Computer Design (ICCD)

作者： Shen, Minghua Xiao, Nong Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou Guangdong Peoples R China

ISBN: (纸本)9781538684771

FPGAs are reconfigurable architectures that can offer large performance and energy improvements over general purpose processors. However, compiling an application design onto the underlying FPGA device takes commonly too much time to allow efficient design turnaround times, significantly hindering designer productivity. routing is always a very timing-consuming and critical process in FPGA compilation flow. To reduce FPGA routing time, parallel techniques have become more popular in recent years. In this paper, we propose a line-grained GPU-based parallel routing approach that enables high concurrent single-net parallel routing for large-scale FPGAs. The proposed approach is novel in three ways. The first is Scheme-I. We route a single net only on its own hounding box rather than entire routing resource graph and then selectively expand its hounding box to make sure that single-net routing has a feasible solution. The second is Scheme-2. We impose a GPU thread to each node and perform path searching in dynamic programming algorithm on all the nodes simultaneously for single-net parallel routing on a single GPU. Note that these nodes are distributed in the bounding box of single net. The third is optimized Scheme-2. We attempt to partition single-net routing box into several sub-boxes, each of which is processed in a shared memory of GPU to enable high scalability and parallelism. Our evaluation with ten large designs from the academic VTR benchmark suite shows that our approach of combining the approximation of VPR 7.0 router (Scheme-1) and its parallelization (optimized Scheme-2) provides a 1.57x speedup improvement compared to the best parallelization-only approach of the original VP.R 7.0 router, though at a small quality deterioration.

关键词： FPGA FPGA CAD routing parallel routing Selective Expansion

来源：评论

学校读者我要写书评

暂无评论

A Novel Fault Tolerance parallel routing Mechanism with Network Coding in Hybrid Wireless-Optical Broadband Access Network

A Novel Fault Tolerance Parallel Routing Mechanism with Netw...

引用

International Conference on Computing, Networking and Communications (ICNC)

作者： Zhang, Hong Wang, Ruyan Wang, Honggang Wu, Guangkai Chongqing Univ Posts & Telecommun Sch Commun & Informat Engn Chongqing Peoples R China Univ Massachusetts Dartmouth Elect & Comp Engn Dept N Dartmouth MA USA

ISBN: (纸本)9781538636527

Survivability is the critical issue in the wirelessoptical broadband access network (WOBAN) since that any failure of network components would resulted in a large amount of traffic interrupted. The previous mechanisms suffer from two key issues. First, they must reroute the interrupted traffic to the backup resources which caused a long recovery time. Second, the deployment of backup fiber could increase the recovery cost. To address these problems, a novel fault tolerance parallel routing mechanism with network coding (FTPR-NC) is proposed in this paper to enhance the survivability. In FTPR-NC mechanism, the original packets are coded to the optimal number of encoded packets which results in the minimum cost of recovery. Then the encoded packet is transferred to the destination node in accordance with the packet allocation scheme which results in the minimum number of encoded packet when recover the original packets by parallel routings. Numerical results show that the proposed FTPR-NC mechanism outperforms the previous mechanism significantly on the performance of average delay. Meanwhile, the FTPR-NC mechanism dramatically decrease the recovery time when a failure occurs.

关键词： parallel routing network coding survivability hybrid wireless-optical broadband access network (WOBAN)

来源：评论

学校读者我要写书评

暂无评论

CHIRPS - A GENERAL-AREA parallel MULTILAYER routing SYSTEM

引用

IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES 1995年第3期142卷 208-214页

作者： VENKATESWARAN, R MAZUMDER, P Dept. of Electr. Eng. & Comput. Sci. Michigan Univ. Ann Arbor USA

A new highly parallel model for concurrent multilayer routing, called CHiRPS, is presented. The nucleus of CHiRPS is a very flexible pathfinder that can be easily configured, even in the presence of obstacles, to generate various commonly used pattern-based routes, such as Steiner trees with single trunk, comb trees, contour-based routes, etc., that span multiple layers simultaneously. The authors employ the concept of a total grid-graph to capture the state of the routing region. The main steps of the pathfinder are based on new parallel algorithms for cycle detection, cycle elimination and tree reduction. The proposed algorithms scale well with increased problem sizes since they require only O(log(N)) time when given a grid-graph with up to N-2 nodes. As such they are good candidates for massively data-parallel machines.

关键词： parallel routing CYCLE-ELIMINATION GRID-GRAPHS COTERIE ARRAY

来源：评论

学校读者我要写书评

暂无评论

Node-to-Set Disjoint Paths in Biswapped Networks

引用

COMPUTER JOURNAL 2014年第7期57卷 953-967页

作者： Ling, Shan Chen, Weidong S China Normal Univ Dept Comp Sci Guangzhou 510631 Guangdong Peoples R China

The node-to-set disjoint paths problem in a k-connected network Omega is defined as follows: given a node s and a set of k other nodes t(1), t(2), aEuro broken vertical bar , t(k) in Omega, find k node-disjoint paths connecting s and t(i), with 1 acurrency sign i acurrency sign k. It is known that such disjoint paths must exist since Omega is k-connected. However, building them, and ensuring that they are as short as possible are non-trivial problems. An efficient solution to the node-to-set disjoint paths problem in a network, with short paths, can be used as a building block in synthesizing collective communication operations that achieve high performance or are highly resilient to node or link failures. Recently proposed Biswapped networks, improved versions of well-known Optical Transpose Interconnection System networks or swapped networks, are a family of interconnection architectures applicable to constructing massive parallel computers. It has been known that any Biswapped network built of a connected factor network is maximally fault-tolerant, implying that such a Biswapped network has maximal connectivity. In this paper, we propose a general algorithm for the node-to-set disjoint paths problem in an arbitrary Biswapped network with a connected factor network that yields paths of length at most 1.5D + 3 in time, where D, Delta and N represent, respectively, the diameter, maximum degree and order of the Biswapped network, and O(f(n)) is the time complexity of a shortest-path routing algorithm for the n-node factor network. The algorithm is time-optimal for certain Biswapped networks of practical interest, including those built of meshes and hypercubes.

关键词： Biswapped network connectivity fault tolerance disjoint paths parallel routing

来源：评论

学校读者我要写书评

暂无评论

A fast and high-performance global router with enhanced congestion control

引用

INTEGRATION-THE VLSI JOURNAL 2024年 99卷

作者： Bai, Xiqiong Chen, Yilu Lin, Zhifeng Wei, Min Cai, Zhijie Zhu, Ziran Chen, Jianli Nanjing Univ Posts & Telecommun Sch Integrated Circuit Sci & Engn Nanjing 210023 Peoples R China Fuzhou Univ Sch Math & Stat Fuzhou 350116 Peoples R China Fudan Univ State Key Lab ASIC & Syst Shanghai 200433 Peoples R China Southeast Univ Natl ASIC Syst Engn Ctr Nanjing 211189 Peoples R China

In global routing, congestion and running time are the key factors that affect the quality of the solution. With the rapid growth of integrated chip scale, striking a balance between running time and congestion has become a bottleneck in improving design quality. In this paper, we propose a highly efficient and effective global router to address this challenge. We first propose an efficient R-tree-based compatible routing region partitioning algorithm for collecting routable regions, which offers robust support for ideal parallel routing scheduling. Then, taking into account the effect of the barrel effect on congestion evaluation and the detrimental impact of loops, a congestion-driven initial parallel routing scheme is proposed to enhance routability in the triaxial pattern routing structure. After that, we develop an accurate congestion estimation model and an optimized path-searching scheme, which are instrumental in effectively managing smaller congestion gradient variations and guiding efficient congestion reduction. We evaluate the performance of our algorithm on the ISPD 2018 and ISPD 2019 contest benchmark suites and compare it with the state-of-the-art work. Experimental results show that our proposed algorithm significantly reduces 71% overflows, improving 65% running time, and the total wirelength is even smaller.

关键词： Physical design Global routing Congestion Wirelength parallel routing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：