Reliable multistage interconnection network design

High-performance supercomputers generally comprise millions of CPUs in which interconnection networks play an important role to achieve high performance. New design paradigms of dynamic on-chip interconnection network involve a) topology b) synthesis, modeling and evaluation c) quality of service, fault tolerance and reliability d) routing procedures. To construct a dynamic highly fault tolerant interconnection networks requires more disjoint paths from each source-destination node pair at each stage and dynamic rerouting capability to use the various available paths effectively. Fast routing and rerouting strategy is needed to provide reliable performance on switch/link failures. This paper proposes two new architecture designs of fault tolerant interconnection networks named as reliable interconnection networks (RIN-1 and RIN-2). The proposed layouts are multipath multi-stage interconnection networks providing four disjoint paths for all the source-destination node pairs with dynamic rerouting capability. The designs can withstand switch failures in all the stages (including input and output stages) and provide more reliability. Reliability analysis of various MIN architectures is evaluated. On comparing the results with some existing MINs it is evident that the proposed designs provides higher reliability values and fault tolerance.     

The composite banyan network

A new multipath multistage interconnection network called the composite banyan network is proposed. The network incorporates both the banyan and the reverse banyan networks and is constructed by superimposing the two. The basic building blocks in the composite banyan network are 3×3 switching elements with log₂N stages. A major advantage of the composite banyan network over existing networks with 3×3 SEs is an efficient and fast control algorithm that sets up a path between any source and destination pair. Instead of complex numerical calculations, the network can easily generate a primary routing tag and alternate tags through simple binary operations. Also, the network has a lot of favorable features, including regularity, symmetry, and easy rerouting capability under faults and conflicts. It is shown that at least two totally disjoint paths exist between any source and destination pair, which increase the degree of fault-tolerance. A deterministic permutation routing algorithm is also developed for the 8×8 composite banyan network, Using a simple tabular method, it is shown that the algorithm always finds a set of conflict-free tags     

Fault-tolerant routing methodology for hypercube and cube-connected cycles interconnection networks

This paper presents a fault-tolerant routing methodology for both injured hypercube and cube-connected cycles interconnection topologies. The proposed routing methodology efficiently tolerates any pattern of faulty regions with any number of faulty nodes in the network which is based on the best-first search and backtracking strategy. Deadlock freedom of the proposed routing methodology is obtained by only one virtual channel per physical channel. In order to evaluate the proposed routing methodology, a 7-dimensional hypercube network is simulated in various conditions, i.e., different traffic rates, different number of faulty nodes and different message lengths. Simulation results confirm that the proposed routing methodology in comparison with the previous methods provides acceptable performance while it significantly increases the reliability of the network. It also guarantees delivery of messages between any pair of source and destination while the network is connected.     

Design of 4-disjoint gamma interconnection network layouts and reliability analysis of gamma interconnection Networks

Multistage interconnection networks (MINs) are widely used for reliable data communication in a tightly coupled large-scale multiprocessor system. High reliability of MINs can be achieved using fault tolerance techniques. The fault tolerance is generally achieved by disjoint paths available through multiple connectivity options. The gamma interconnection network (GIN) is a class of fault tolerant MINs providing alternate paths for source–destination node pairs. Various 2-disjoint and 3-disjoint GIN architectures have been presented in the literature. In this paper, two new designs of 4-disjoint paths multistage interconnection networks, called 4-disjoint gamma interconnection networks (4DGIN-1 and 4DGIN-2) are proposed. The proposed 4DGINs provide four disjoint paths for each source–destination pair and can tolerate three switches/link failures in intermediate interconnection layers. Proposed designs are highly reliable GIN with higher fault-tolerant capability than other gamma networks at low cost. Terminal pair reliabilities of proposed designs and various other 2-disjoint and 3-disjoint GINs are evaluated, analyzed and compared. Reliability values of proposed designs are found higher.     

直线引导的Torus结构路由算法

为了提高片上网络在Torus拓扑结构下的路由通信效率,提出了一种基于直线引导思想的路由算法Tline。该路由算法将Torus拓扑结构的片上网络拓展为类似Mesh结构的坐标平面,以数据包的源节点和目的节点构成的直线为路由转发方向,并根据周围邻近节点的拥塞状况选择传输路径方向实现部分自适应路由。实验结果表明,与XY、OE路由算法相比,在热点流量模式下Tline路由算法具有较好的路由性能,且平均能耗降低约8%。     

Design schemes of dynamic rerouting networks with destination tag routing for tolerating faults and preventing collisions

In fault-tolerant multistage interconnection design, the method of providing disjoint paths can tolerate faults, but it is complicated and hard to choose a collision-free path in disjoint paths networks. A network with disjoint paths can concurrently send more identical packets from the source node to increase the arrival ratio or backtrack a packet to the source and take the other disjoint path, but these two methods might increase the collision ratio. In contrast, a dynamic rerouting method finds an alternative path that tolerates faults or prevents collisions. In this paper, we present methods of designing dynamic rerouting networks. This paper presents (1) three design schemes of dynamic rerouting networks to tolerate faults and prevent collisions; (2) design schemes that enable a dynamic rerouting network to use destination tag routing to save hardware cost in switches for computing rerouting tags; (3) a method to prevent a packet from re-encountering the faulty element again after rerouting to reduce the number of rerouting hops and improve the arrival ratio; and (4) simulation results of related dynamic rerouting networks to realize the factors which influence the arrival ratio including the fault tolerant capability and the number of rerouting hops. According to our proposed design schemes and according to our analysis and simulation results, a designer can choose an applicable dynamic rerouting network by using cost-efficient considerations. This paper was partially supported by the National Science Council NSC-92-2213-E-324-006- and NSC-94-2213-E-035-050-; and the partial part of the preliminary version of this paper was published by the conference ISPA 2005 [5].     

自动布局布线程序

功述描述了用于规划芯片的自动布局布线程序。其特点是在单元电路版图实现之前进行布局布线以及布线是在单元内部进行，不存在专门的布线通道。这种布图模式，以多端网连接模型作为布局布线的连接模型，并以布线均匀作为主要的目标函数。 整个程序模块分为矩阵网格规划和布局，总体布线，端口分配三部分。在布局中采用最小切割算法。初始布线以布线均匀，连线长度最短为目标，并采用一个基于布线均匀的“重心“算法。通过再布线和通     

一种无虚通道NoC负载均衡容错路由算法

随着芯片复杂度的不断增大,设计一个高效的片上网络容错路由算法面临着巨大的挑战。由于芯片面积开销的限制,拥有低面积开销的无虚通道片上网络路由器受到学术界的广泛关注。但目前对无虚通道片上网络容错路由算法的研究却停留在容错性能上,而忽略了容错路由算法的路由路径过于单一所造成的负载不均、数据包平均延迟较大等问题。文章在借鉴已有的奇偶转向容错路由算法的基础上,对算法的故障模型和故障绕行策略进行优化,并在算法中融入负载均衡策略,以形成新的容错算法缓解上述问题。在9x9的2D mesh网络中对新提出的算法和参考算法的仿真结果表明：与参考算法相比,新算法在降低数据延迟和吞吐量方面有着明显的优势,在最优情况下能减少8.92%数据延迟和增加10.46%的吞吐量。     

Rerouting schemes for dynamic traffic grooming in optical WDM networks

Traffic grooming in optical WDM mesh networks is a two-layer routing problem to effectively pack low-rate connections onto high-rate lightpaths, which, in turn, are established on wavelength links. The objective of traffic grooming is to improve resource efficiency. However, resource contention between lightpaths and connections may result in inefficient resource usage or even the blocking of some connections. In this work, we employ a rerouting approach to alleviate resource inefficiency and improve the network throughput under a dynamic traffic model. We propose two rerouting schemes, rerouting at lightpath level (RRLP) and rerouting at connection level (RRCON) and a qualitative comparison is made between the two. We also propose two heuristic rerouting algorithms, namely the critical-wavelength-avoiding one-lightpath-limited (CWA-1L) rerouting algorithm and the critical-lightpath-avoiding one-connection-limited (CLA-1C) rerouting algorithm, which are based on the two rerouting schemes. Simulation results show that rerouting reduces the blocking probability of connections significantly.     

Depth-first search approach for fault-tolerant routing in hypercubemulticomputers

Using depth-first search, the authors develop and analyze the performance of a routing scheme for hypercube multicomputers in the presence of an arbitrary number of faulty components. They derive an exact expression for the probability of routing messages by way of optimal paths (of length equal to the Hamming distance between the corresponding pair of nodes) from the source node to an obstructed node. The obstructed node is defined as the first node encountered by the message that finds no optimal path to the destination node. It is noted that the probability of routing messages over an optimal path between any two nodes is a special case of the present results and can be obtained by replacing the obstructed node with the destination node. Numerical examples are given to illustrate the results, and they show that, in the presence of component failures, depth-first search routing can route a message to its destination by means of an optimal path with a very high probability     

一种基于扩散机制的LEO卫星网络多径路由协议

提出一种适用于LEO卫星网络的动态多径路由协议——DMRP（Diffusion—based Multi—path Routing Protocol）。协议按需运行,且具有在源、目的之间建立多条路由的能力。按需协议仅当节点发送数据时才启动路由过程,寻找到达目的节点的路由,不要求节点实时维护网络拓扑信息,从而降低了协议运行时间与拓扑存储开销;多径路由则提高了网络的可靠性及协议的健壮性。仿真结果表明,DMRP在协议收敛时间、丢包率等方面都有良好的性能。     

TRABPT:一种移动P2P网络可信路由选择算法*

针对移动P2P网络中源节点与目标节点之间如何从多条可选路径中选择可信路由的问题,基于前景理论（PT）提出了一种新的移动P2P网络可信路由选择算法TRABPT（trusted mobile P2P network routing algorithm based on prospect theory）。利用PT中的权重函数对路由过程中下一跳节点进行选择,提高了路由选择的灵活度和可信度。理论分析和仿真实验表明,本算法与DSR和Flooding算法相比在任务完成效率、平均查找时间及抵制恶意节点等方面有一定程度的改     

Dynamic rerouting of guaranteed Quality-of-Service connections

To support the widespread demands for integrated services various solutions have been proposed to provide guaranteed Quality-of-Service (QoS) services in packetswitched networks. These solutions usually require fixed route selection and resource reservation on a per connection basis. The routing and reservation decisions, combined with load fluctuations, introduce the problems of network unavailability and loss of network management flexibility. We believe that these problems can be alleviated by transparently rerouting connections to properly balance the network load. In this paper, we present a solution that supportstransparent route modification ofguaranteed QoS connections during the life time of the connections. As the emphasis of this work is to support transparency we must ensure that during and after the rerouting, the QoS guarantees made to the client are preserved, and the interface instances at both the sender and receiver are unaltered. Our solution includes the mechanisms that support the transparent rerouting of connections, and a routing algorithm that is based on the traffic characteristics, the delay, and the jitter requirements of a connection. This routing algorithm can also use various administrative constraints and facilitate the reuse of resources currently reserved by the connection. To optimize the solution, additional mechanisms have been introduced to reduce the time needed to reroute a connection and to support rerouting of segments of a connection. The solution has been implemented in the context of the Tenet scheme and route changes can be observed and controlled by using the Simple Network Management Protocol (SNMPv 1). Simulation experiments and some initial measurements of the implementation demonstrate that such a scheme is useful, practical, and can be achieved with load overhead.     

蛀洞路由机制及其芯片设计

蛀洞路由技术是“曙光１０００”大规模并行计算机所采用的一面关键技术。本文讨论了蛀洞路由机制，详细介绍了“曙光１０００”的蛀洞路由算法、芯片结构设计，以及由该芯片构成的处理机互连网络。     

Architecture and operating system support for two-dimensional runtime partial reconfiguration

Reconfigurable machines based on field programmable gate array (FPGA) chips adapt to applications’ needs through hardware reconfiguration. Partial reconfiguration allows the configuration of a portion of a chip while the rest of the chip is busy working on tasks. This paper considers a two-dimensional partially reconfigurable FPGA chip that allows the dynamic swap in and out of circuit modules. Such a chip supports the concurrent execution of multiple applications or an application that is otherwise too large to fit. A challenging issue for 2-D runtime partial reconfiguration is how to support the efficient connection, or routing, between circuit modules or between modules and I/O pins, when those modules may be placed on any area of a chip. Because commercial chips are not efficient in 2-D runtime routing, a new FPGA architecture is proposed based on an array of clusters of configurable logic blocks and a mesh of segmented buses. To evaluate the runtime performance of the architecture, an operating system is specified and implemented which takes care of the scheduling, placement, and routing of circuits on the architecture. Simulation is used to evaluate the efficiency of the OS kernel and to determine the optimal cluster size of the architecture.     

Ad hoc网络中基于QoS约束的AOMDV路由协议设计

多数Ad hoc网络路由研究聚焦于找到一条连接源和目的节点的路由,而没有考虑网络的QoS需求,一旦数据流量超过了网络所能承受的限度,数据流的传输质量将无从保证。提出了一种AOMDVQ（AOMDV Based on QoS）路由协议,在AOMDV基础上增加了带宽、时延、跳数和优先级等约束条件,使得在路由发起和路由维护阶段满足一定的QoS需求。仿真结果显示,AOMDVQ协议在高速移动状态下其数据包发送成功率、端到端时延等较AOMDV、MP-AOMDV协议有明显改进。     

一种链路不相交的多约束QoS路由算法

为提高网络路由可靠性,改善网络资源利用率,提出一种满足多个QoS约束的基于链路保护机制的路由算法.该算法首先通过图论的有关性质找到满足给定约束条件的节点对间的全部路径,并在此基础上利用邻接矩阵的方法得到其最短链路不相交相似路径,最后赋以算例分析.结果证明,该算法在减小网路传输时延方面有一定的优势,对于高实时性网络应用有更好的优化作用.     

基于服务质量的多媒体通信初始路由建立算法的研究

基于服务质量的路由选择机制是从根本上提供分布式多媒体应用所需的服务质量保证的重要手段之一。该文提出了两种基于服务质量的多媒体通信初始路由建立算法。一种算法支持在两个通信方之间建立基于服务质量的初始路由,既可以作为点对点多媒体通信的基于服务质量的路由选择／初始路由建立算法,也可以作为初始成员为两个的多媒体动态组通信的基于服务质量的初始路由建立算法,另一种算法支持在多个通信方之间建立基于服务质量的初始路由,既可以作为多媒体静态组通信的基于服务质量的路由选择／初始路由建立算法,也可以作为初始成员为多个的多媒体动态组通信的基于服务质量的初始路由建立算法,文中还探讨了这两种算法的正确性。     

Unicast-based fault-tolerant multicasting in wormhole-routed hypercubes

A unicast-based fault-tolerant multicasting method is proposed for hypercubes, which can still work well when the system contains enough faults. A multicast message may be unable to reach a destination if Hamming distance between the destination and the multicast source is large enough. A multicast message fails if any one of the destinations is unreachable from the source. An effective destination ordering scheme of the destinations is proposed for one-port systems first, it is extended to all-port systems for unicast-based fault-tolerant multicasting. Unreachable destinations from the source based on the local safety information are forwarded to a reachable destination, where the multicast message can be routed reliably. Destination ordering is completed based on Hamming distance. A multiple round p-cube routing scheme is presented for a deadlock-free fault-tolerant routing for each unicast step in hypercubes, where the same virtual channel is used for each round of p-cube routing. Sufficient simulation results are presented by comparing with the previous methods.     

二维网格中基于最小通路区的自适应和最小容错路由算法

网格结构是并行与分布式处理中最流行的一种网络拓扑结构。在存在故障的情况下，如何设计具有最优性的容错路由算法一直是研究的热，点问题。本文研究了采用故障块模型的二维网格的最小路由问题，提出存在最小通路的一个充分必要条件。基于最小通路区（RMP）的概念，提出一种自适应的最小容错路由算法。如果源节点和目的节点之间存在最小通路区，则在最小通路区中进行自适应最小容错路由；反之，则采用多阶段最小容错路由。主要思想就是在存在故障的情况下，尽量保证路由算法能走最短路径。因为只要求知道每个节点的局部信息，故算法是分布式的。