Performance analysis of fault-tolerant routing algorithm in wormhole-switched interconnections

With nowadays popularity of large-scale parallel computers, Multiprocessors System-on-Chip (MP-SoCs), multicomputers, cluster computers and peer-to-peer communication networks, fault-tolerant routing becomes an important issue in developing these systems. Fault-tolerant routing algorithms in such systems aim at providing continuous operations in the presence of one or more failures by allowing the graceful degradation of system. The Software-Based fault-tolerant routing scheme has been suggested as an efficient routing algorithm to preserve both communication performance and fault-tolerant demands in parallel computer systems. To study network performance, a number of different analytical models for fault-free routing algorithms have been proposed in the past literature. However, there has not been reported any similar analytical model of fault-tolerant routing in the presence of faulty components. This paper presents a new analytical modeling approach for determining the effects of failures in wormhole-switched 2-D tori using the fault-tolerant Software-Based scheme. More specifically, we describe a general model to derive mathematical expressions to investigate the performance behavior of routing algorithms confronting convex (|-shaped, □-shaped) or concave (U-shaped, +-shaped, T-shaped, H-shaped) faulty regions. The model is validated through comprehensive simulation experiments for different types of failures.

TTPM – An efficient deadlock-free algorithm for multicast communication in 2D torus networks

A torus network has become increasingly important to multicomputer design because of its many features including scalability, low bandwidth and fixed degree of nodes. A multicast communication is a significant operation in multicomputer systems and can be used to support several other collective communication operations. This paper presents an efficient algorithm, TTPM, to find a deadlock-free multicast wormhole routing in two-dimensional torus parallel machines. The introduced algorithm is designed such that messages can be sent to any number of destinations within two start-up communication phases; hence the name Torus Two Phase Multicast (TTPM) algorithm. An efficient routing function is developed and used as a basis for the introduced algorithm. Also, TTPM allows some intermediate nodes that are not in the destination set to perform multicast functions. This feature allows flexibility in multicast path selection and therefore improves the performance. Performance results of a simulation study on torus networks are discussed to compare TTPM algorithm with a previous algorithm.     

Origin-based fault-tolerant routing in the mesh

The ability to tolerate faults is critical in multicomputer employing large numbers of processors. This paper describes a class of fault-tolerant routing algorithms for n-dimensional meshes that can tolerate large numbers of faults without using virtual channels. We show that these routing algorithms prevent livelock and deadlock while remaining highly adaptive.     

An effective routing algorithm in incomplete hypercubes

An incomplete hypercube appears interesting and practical because of its relaxed restriction on the system size and possession of salient properties of complete hypercubes. The performance of incomplete hypercubes can be improved considerably by reducing communication time, which can be achieved by forwarding messages through two parallel paths between a pair of nodes. This paper presents a simple and effective two-parallel-paths routing algorithm for incomplete hypercubes which takes advantage of the flexibility provided by incomplete hypercubes, and yet prevents traffic congestion and deadlock. Simulation results indicate that the mean latency for sending large sized messages is reduced and the degree of reduction becomes larger when the system load grows. This significant reduction in latency could translate to a respectable performance improvement. This algorithm can also tolerate one fault in the system by sending duplicate copies of messages through two parallel paths with little increase in the mean latency under light-traffic load.     

A dynamic fault-tolerant message routing algorithm for double-loop networks

Message routing is a fundamental function of a network, and fault-tolerance is an important tool to ensure the quality of service of a network. Assume that the network contains at most one faulty element and the algorithm does not know the faulty element in advance. We present an optimal fault-tolerant message routing algorithm for double-loop networks. We show that sending at most two messages with different routing strategies can ensure that one of the messages will be sent through a shortest path that avoids the faulty element. At each vertex, for any destination, the algorithm needs only constant time and space to determine the next vertex to which the message is to be sent.     

Adaptive inter-layer message routing in 3D networks-on-chip

Existing routing algorithms for 3D deal with regular mesh/torus 3D topologies. Today 3D NoCs are quite irregular, especially those with heterogeneous layers. In this paper, we present a routing algorithm targeting 3D networks-on-chip (NoCs) with incomplete sets of vertical links between adjacent layers. The routing algorithm tolerates multiple link and node failures, in the case of absence of NoC partitioning. In addition, it deals with congestion. The routing algorithm for 3D NoCs preserves the deadlock-free propriety of the chosen 2D routing algorithms. It is also scalable and supports a local reconfiguration that complements the reconfiguration of the 2D routing algorithms in case of failures of nodes or links. The algorithm incurs a small overhead in terms of exchanged messages for reconfiguration and does not introduce significant additional complexity in the routers. Theoretical analysis of the 3D routing algorithm is provided and validated by simulations for different traffic loads and failure rates.     

交换超立方网的自适应性无死锁路由算法

交换超立方网是一种新提出来的互连网络。首先,利用图论的方法研究了交换超立方网的拓扑性质,引入了相似子网的概念,得出相似子网和超立方体同构的结论;然后,利用将物理通道分成两条虚拟通道的方法,给出了一种交换超立方网的自适应性路由算法,并从理论上证明了该算法的无死锁性。     

三维无线传感器网络寿命和动态路由算法

无线传感器网络(WSNs)寿命受到电池能量的制约,利用无线能量传输技术对传感器节点进行充电,可以解决无线传感器网络的能量问题.以三维无线传感器网络为研究对象,证明三维最短Hamilton回路为无线充电设备遍历网络中节点的最优路径,提出了网络的连续时变模型,并简化复杂度为多项式的离散T+1阶段线性规划模型.仿真结果表明:通过运算离散T+1阶段线性规划模型能够使无线传感器网络持续运行.     

A simple fault-tolerant adaptive and minimal routing approach in 3-D meshes

In this paper we propose a sufficient codition for minimal routing in 3-dimensional (3-D) meshes with faulty nodes,It is based on an early work of the author on minial routing in 2-dimensional(2-D) meshes,Unlike many traditional models that assume all the nodes know global fault distribution or just adjacent fault information,our approach is based on the concept of limited global fault information,First,we propose a fault model called faulty cube in which all faulty nodes in the system are contained in a set of faulty cubes.Fault information is then distributed to limited number of nodes while it is still sufficeint to support minimal routing.The limited fault information collcted at each node is represented by a vector caaled extended safety level.The extended safety level associated with a node can be used to determine the existence of a minimal path from this node to a given destination .Specifically,we study the existence of minimal paths at a given source node,limited distribution of fault information,minimal routing,and deadlock-free and livelock-free routing.our results show that any minimal routing that is partially adaptive can be applied in our model as long as the dstination node meets a certain conditon.We also propose a dynamic planar-adaptive routing scheme that offers better fault tolerance and adaptivity than the planar-adaptive routing scheme in 3-D meshes.Our approach is the first attempt to address adaptive and minimal routing is 3-D meshes with faulty nodes using limited fault information.     

A deadlock-free routing algorithm for dynamically reconfigurable Networks-on-Chip

We address routing in Networks-On-Chip (NoC) architectures that use irregular mesh topologies with Long-Range Links (LRL). These topologies create difficult conditions for routing algorithms, as standard algorithms assume a static, regular link structure and exploit the uniformity of regular meshes to avoid deadlock and maintain routability. We present a novel routing algorithm that can cope with these irregular topologies and adapt to run-time LRL insertion and topology reconfiguration. Our approach to accommodate dynamic topology reconfiguration is to use a new technique that decomposes routing relations into two stages: the calculation of output ports on the current minimal path and the application of routing restrictions designed to prevent deadlock. In addition, we present a selection function that uses local topology data to adaptively select optimal paths.The routing algorithm is shown to be deadlock-free, after which an analysis of all possible routing decisions in the region of an LRL is carried out. We show that the routing algorithm minimises the cost of sub-optimally placed LRL and display the hop savings available. When applied to LRLs of less than seven hops, the overall traffic hop count and associated routing energy cost is reduced. In a simulated 8 × 8 network the total input buffer usage across the network was reduced by 6.5%.     

A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet

Nowadays genetic algorithms stand as a trend to solve NP-complete and NP-hard problems. In this paper, we present a new hybrid metaheuristic which uses parallel genetic algorithms and scatter search coupled with a decomposition-into-petals procedure for solving a class of vehicle routing and scheduling problems. The parallel genetic algorithm presented is based on the island model and its performance is evaluated for a heterogeneous fleet problem, which is considered a problem much harder to solve than the homogeneous vehicle routing problem.     

基于扩展安全级的Torus网络容错路由算法研究

在存在故障结点的网络中如何设计最小容错路由是网络容错研究中的一个热点问题。以存在矩形故障块的二维Torus网络为例,将扩展安全级运用到Torus中,对于网络中任意一对结点,给出存在最小路径的充要条件;并且结合扩展安全级的概念,给出建立最小通路区的方法,并用实验验证了方法的可行性。研究为存在故障结点的Torus网络寻找最小容错路径提供了理论依据。     

The torus routing chip

The torus routing chip (TRC) is a selftimed chip that performs deadlock-freecut-through routing ink-aryn-cube multiprocessor interconnection networks using a new method of deadlock avoidance calledvirtual channels. A prototype TRC with byte wide self-timed communication channels achieved on first silicon a throughput of 64 Mbits/s in each dimension, about an order of magnitude better performance than the communication networks used by machines such as the Caltech Cosmic Cube or Intel iPSC. The latency of the cut-through routing of only 150 ns per routing step largely eliminates message locality considerations in the concurrent programs for such machines. The design and testing of the TRC as a self-timed chip was no more difficult than it would have been for a synchronous chip. Bill Dally received his B. S. degree in Electrical Engineering from the Virginia Polytechnic Institute in 1980 and his M.S. degree in Electrical Engineering from Stanford University in 1981. From 1980 to 1982 he worked at Bell Telephone Laboratories, where he contributed to the design of the BELLMAC-32 microprocessor. From 1982 to 1983 he worked as a consultant in the area of digital systems design. Since 1983 he has been a graduate student in Computer Science at Caltech, and is expected to complete his Ph.D. studies in the spring 1986. His current research interests include computer architecture, computer aided design, VLSI, design, and concurrent systems. Chuck Seitz earned B.S., M.S., and Ph.D. degrees from M.I.T. Before joining the Computer Science faculty at Caltech in 1977, he worked as a member of the technical staff of the Evans & Sutherland Computer Corporation from 1969 to 1971, as an Assistant Professor of Computer Science at the University of Utah from 1970 to 1972, and as a consultant to Burroughs Corporation from 1971 to 1978. He is currently a Professor of Computer Science at Caltech, where his research and teaching activities are in the areas of VLSI architecture and design, concurrent computation, and self-timed systems.The research described in this paper was sponsored in part by the Defense Advanced Research Projects Agency, ARPA Order number 3771, and monitored by the Office, of Naval Research under contract number N 00014-79-C-0597, in part by Intel Corporation, and in part by an AT & T Ph.D. fellowship     

基于三维胞元空间的MA双向并行路由算法

针对传统移动代理(MA)在监测无线传感器网络(WSNs)的感兴趣信息时产生的延迟较大和能耗较多问题,提出了基于三维胞元空间的MA双向并行(3D-BPMA)路由算法.3D-BPMA将MA与传统的客户/服务器(c/S)模式相结合,在胞元内利用C/S模式搜集信息,在单层胞元系统和路由器与路由器之间采用MA双向并行的策略进行传输.仿真结果表明:3D-BPMA与LCF,DSG-MIP算法相比减少了平均响应时间和网络平均能耗,提高了MA发送率.     

Scalable 3D hybrid parallel Delaunay image-to-mesh conversion algorithm for distributed shared memory architectures

In this paper, we present a scalable three-dimensional hybrid parallel Delaunay image-to-mesh conversion algorithm (PDR.PODM) for distributed shared memory architectures. PDR.PODM is able to explore parallelism early in the mesh generation process thanks to the aggressive speculative approach employed by the Parallel Optimistic Delaunay Mesh generation algorithm (PODM). In addition, it decreases the communication overhead and improves data locality by making use of a data partitioning scheme offered by the Parallel Delaunay Refinement algorithm (PDR). PDR.PODM supports fully functional volume grading by creating elements with varying size. Small elements are created near boundary or inside the critical regions in order to capture the fine features while big elements are created in the rest of the mesh. We tested PDR.PODM on Blacklight, a distributed shared memory (DSM) machine in Pittsburgh Supercomputing Center. For the uniform mesh generation, we observed a weak scaling speedup of 163.8 and above for up to 256 cores as opposed to PODM whose weak scaling speedup is only 44.7 on 256 cores. PDR.PODM scales well on uniform refinement cases running on DSM supercomputers. The end result is that PDR.PODM can generate 18 million elements per second as opposed to 14 million per second in our earlier work. The varying size version sharply reduces the number of elements compared to the uniform version and thus reduces the time to generate the mesh while keeping the same fidelity.     

三维无线传感器网络贪婪地理路由协议

针对已有的三维无线传感器网络路由协议均将三维问题转换到二维平面上解决,没有充分利用三维空间的特点,提出了一种基于地理信息的三维无线传感器网络贪婪地理路由(GGR)协议。该协议在通常状况下采用贪婪转发算法,针对基于地理信息的贪婪算法中易出现的路由空洞问题,给出一种三维滚动球边界遍历算法。实验结果表明:该协议具有较高的路由成功率,路由跳数也得到优化,尤其是在节点密度较低的情况下体现出较强的优势。     

Congestion-aware ant colony based routing algorithms for efficient application execution on Network-on-Chip platform

Networks-on-Chip (NoC) is an interesting option in design of communication infrastructures for embedded systems. It provides a scalable structure and balanced communication between the cores. Parallel applications that take advantage of the NoC architectures, are usually are communication-intensive. Thus, a big deal of data packets is transmitted simultaneously through the network. In order to avoid congestion delays that deteriorate the execution time of the implemented applications, an efficient routing strategy must be thought of carefully. In this paper, the ant colony optimization paradigm is explored to find and optimize routes in a mesh-based NoC. The proposed routing algorithms are simple yet efficient. The routing optimization is driven by the minimization of total latency during packets transmission between the tasks that compose the application. The presented performance evaluation is threefold: first, the impact of well-known synthetic traffic patterns is assessed; second, randomly generated applications are mapped into the NoC infrastructure and some synthetic communication traffics, that follow known patterns, are used to simulate real situations; third, sixteen real-world applications of the E3S and one specific application for digital image processing are mapped and their execution time evaluated. In both cases, the obtained results are compared to those obtained with known general purpose algorithms for deadlock free routing. The comparison avers the effectiveness and superiority of the ant colony inspired routing.     

2D Mesh片上网络分区容错路由算法

为了减小路由表的规模且避免使用较多虚通道(VC),从而降低硬件资源用量,针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由(RFTR)算法。该算法根据故障节点和链路的位置将2D Mesh网络划分为若干个相连的矩形区域,数据包在矩形区域内可使用确定性或自适应路由算法进行路由,而在区域间则按照up^*/down^*算法确定路由路径。此外,利用通道依赖图(CDG)模型,证明了该算法仅需两个虚通道就能避免死锁。在6×6 Mesh网络中,RFTR算法能减少25%的路由表资源用量。仿真结果表明,在队列缓存资源相同的情况下,RFTR算法能实现与up^*/down^*算法和segment算法相当甚至更优的性能。     

改进型量子蚁群算法求解QoS单播路由

针对遗传以及蚁群算法在求解QoS单播路由问题时收敛速度慢和易于陷入局部最优的问题。采用量子蚁群算法求解QoS单播路由,采用量子旋转门实现蚂蚁的移动,用量子非门来实现蚂蚁位置的变异,同时为了确保算法不陷于局部最优,对量子蚁群算法做了改进,并进行了对比实验。实验表明该算法不但克服了遗传以及蚁群算法的易限于局部最优解的缺陷,在收敛速度上也优于相关算法,能较好地解决QoS单播路由问题。