虚网叠加构造自适应路由算法的有效框架

大规模并行处理机系统中路由算法对互联网络通信性能和系统性起着重要作用。     

超立方体网络下的自适应容错路由研究*

针对超立方体结构的多处理机系统出现故障的问题,对容错超立方体网络的局部连通性进行了研究。根据局部连通性的特点定义了相邻节点集合类的概念,提出并证明了求解两类相邻节点集合的公式。给出了满足任意子连通性条件的超立方体网络的自适应容错路由算法。该算法是分布式和基于局部信息的,可以预防死锁。仿真实验的结果表明算法是高效的,且构建的路径长度接近于最优路径长度。     

Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions

The simplicity of regular mesh topology Network on Chip (NoC) architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A proposed way in literature to deal with this is to utilize the region concept, which helps to accommodate cores larger than the tile size in mesh topology NoC architectures. Region concept offers many new opportunities for NoC design, as well as provides new design issues and challenges. One of the most important among these is the design of an efficient deadlock free routing algorithm. Available adaptive routing algorithms developed for regular mesh topology cannot ensure freedom from deadlocks. In this paper, we list and discuss many new design issues which need to be handled for designing NoC systems incorporating cores larger than the tile size. We also present and compare two deadlock free routing algorithms for mesh topology NoC with regions. The idea of the first algorithm is borrowed from the area of fault tolerant networks, where a network topology is rendered irregular due to faults in routers or links, and is adapted for the new context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. The application specific routing algorithm tries to maximize adaptivity by using static and dynamic communication requirements of the application. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases. But this higher performance for the second algorithm comes at a higher area cost for implementing network routers.     

Enhanced fault tolerant routing algorithms using a concept of “balanced ring”

Fault rings can be used to guide messages bypass faulty nodes/links in a fault tolerant interconnection network. However, nodes on the fault ring become hot spots, thus causing uneven distribution of the traffic loads. To avoid such traffic congestion, a concept of the balanced ring is proposed in this paper. The proposed balanced ring, defined as concentric rings of a given fault ring, can be applied to the fault tolerant routing algorithms for mesh and torus topologies. By properly guiding messages to route on the balanced ring and the fault ring, more balanced link utilization and greatly reduced traffic congestion can be achieved on a fault tolerant network. Methods of applying the balanced ring concept to some published fault tolerant routing algorithms are discussed. Proof of deadlock and livelock freedom is also presented. The use of balanced ring does not need to add new virtual channels. The performance of two routing algorithms with and without the balanced ring is simulated and evaluated. The results indicate that routing algorithms with the balanced rings constantly yield larger throughput and smaller latency than those without.     

Fault-tolerant wormhole routing for hypercube networks

We present an adaptive fault-tolerant wormhole routing algorithm for hypercubes by using 3 virtual networks. The routing algorithm can tolerate at least n−1 faulty nodes and can route a message via a path of length no more than the shortest path plus four. Previous algorithms which achieve the same fault tolerant ability need 5 virtual networks. Simulation results are also given in this paper.     

A performance model of compressionless routing in k-ary n-cube networks

Several analytical models of fully adaptive routing in wormhole-routed networks have recently been reported in the literature. All these models, however, have been discussed for routing algorithms with deadlock avoidance. Recent studies have revealed that deadlocks are quite rare in the network, especially when enough routing freedom is provided. Thus, the hardware resources, e.g. virtual channels, dedicated for deadlock avoidance are not utilised most of the time. This consideration has motivated researchers to introduce fully adaptive routing algorithms with deadlock-recovery. This paper proposes a new analytical model to predict message latency in k-ary n-cubes with compressionless routing, a fully adaptive algorithm that uses deadlock-recovery. The proposed model uses results from queueing systems with impatient customers to capture the effects of the timeout mechanism used in this routing algorithm to deal with message deadlock. The validity of the model is demonstrated by comparing results predicted by the analytical model against those obtained through simulation experiments.     

The message flow model for routing in wormhole-routed networks

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. This method may be used to develop deterministic, partially-adaptive, and fully-adaptive routing algorithms for wormhole-routed networks with arbitrary topologies. We first establish the necessary and sufficient condition for deadlock free routing, based on the analysis of the message flow on each channel. We then use the model to develop new adaptive routing algorithms for 2D meshes     

基于GCC的容错编译器的研究与实现

在COTS微处理器上实现面向硬件故障的软件容错技术,与硬件容错技术相比,其性能、成本、功耗和灵活性上都拥有巨大的优势。其中容错编译技术通过在编译的时候自动地插入指令实现容错,实现简单、高效,不需要重写源代码,减轻了程序员的负担,有利于利用已有的大量程序,是软件容错研究中较为活跃的分支。本文以GNU开源编译器GCC为平台,结合现有容错编译算法,讨论一款初步具有容错编译能力的编译器的设计与实现。     

交换超立方体网络容错路由研究

为了研究交换超立方体网络容错路由问题,引入了相邻结点集合类的概念,提出了相邻结点集的求解公式。对于满足任意子连通性条件的交换超立方体网络,给出了基于相邻结点集合类的自适应容错路由算法及算法的步长上界。仿真实验结果表明算法是有效的。     

具有原路返回特征的改进OSRM胖树路由算法研究

胖树是最重要的互连网络拓扑结构之一。针对胖树拓扑结构,已经提出了多种路由算法,其中OSRM被证明是一种最优化的路由算法,但是所有算法都忽略了网络链路故障的易诊断性。为此,提出一种对OSRM改进的新型路由算法BT-OSRM。该算法定义了节点间的大小关系并通过比较节点大小而从OSRM路由路径与其反向路径中选择路由路径。此外,还针对常用的2级和3级胖树结构,分别详细给出了BT-OSRM2和BT-OSRM3路由算法。理论分析表明,BT OSRM路由算法不但继承了OSRM路由算法无死锁、负载均衡和性能最优等优点,而且保证了任意两节点间的路由路径具有原路返回特性,从而提高了网络故障链路的易诊断性。     

A framework for designing deadlock-free wormhole routing algorithms

This paper presents a framework to design fully-adaptive, deadlock-free wormhole algorithms for a variety of network topologies. The main theoretical contributions are: (a) design of new wormhole algorithms using store-and-forward algorithms, (b) a sufficient condition for deadlock free routing by the wormhole algorithms so designed, and (c) a sufficient condition for deadlock free routing by these wormhole algorithms with centralized flit buffers shared among multiple channels. To illustrate the theory, several wormhole algorithms based on store-and-forward hop schemes are designed. The hop-based wormhole algorithms can be applied to a variety of networks including torus, mesh, de Brujin, and a class of Cayley networks, with the best known bounds on virtual channels for minimal routing on the last two classes of networks. An analysis of the resource requirements and performances of a proposed algorithm, called negative-hop algorithm, with some of the previously proposed algorithms for torus and mesh networks is presented     

Compressionless wormhole routing: an analysis for hypercube with virtual channels

Several recent studies have shown that adaptive routing algorithms based on deadlock recovery have superior performance characteristics than those based on deadlock avoidance. Most of these studies, however, have relied on software simulation due to the lack of analytical modelling tools. In an effort towards filling this gap, this paper presents a new analytical model of compressionless routing in wormhole-routed hypercubes. This routing algorithm exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. The advantages of compressionless routing include deadlock-free adaptive routing with no extra virtual channels, simple router design, and order-preserving message transmission. The proposed analytical model computes message latency by determining the message transmission time, blocking delay at each router, multiplexing delay at each network channel, and waiting time in the source before entering the network. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.     

对角网格中的无死锁自适应路由算法

网格是多计算机中应用广泛的互连结构,提出了一种新的互连结构－对角网格。并在这种结构上提出了一类自适应无死锁的路由算法－负优先算法,证明了此算法的无死锁性。对角网格是可平面图,其结构简单,可扩充性非常好。负优先自适应路由算法的突出优点是对硬件逻辑要求简单,无须增加虚拟通道即可达 死锁和自适应。     

Adaptive wormhole routing in k-ary n-cubes

Distributed memory multiprocessor (DMMP) systems have gained much attention because their performance can be easily scaled up by increasing the number of processor-memory modules. The k-ary n-cube is the most popular interconnection network topology currently used in DMMPs. Wormhole routing is one of the most promising switching technology and has been used in many new generation multicomputers. Wormhole routing makes the communication latency insensitive to the network diameter and reduces the size of the channel buffer of each router. The concept of virtual channels and virtual networks are widely invented for deadlock-free design. A fully adaptive wormhole routing method for k-ary n-cubes has been proposed by Linder in 1991 [10]. Unfortunately, the need of 2^{n − 1} virtual networks makes it unreasonable. In this paper, we propose a virtual network system to support an adaptive, minimal and deadlock free routing in k-ary n-cubes. It uses only four virtual networks but can get a higher degree of adaptability and higher traffic capacity. Simulation results are presented to verify the performance.     

Torus网络自适应容错路由算法

在应用于大规模并行计算机的互连网络的设计中,容错问题是其中的一个关键问题和难点问题。提出了一种基于Torus虫孔交换网络的容错路由算法,这一算法使用了矩形故障模型,无论故障区域大小多少和如何分布,算法始终是无死锁的,而且具有足够的自适应性,只要故障节点没有断开网络的连接,算法就能够通过选路使消息绕过故障区域,保持路由的连通性。同时,算法仅需要使用3个额外的虚拟通道。最后算法在不同故障率的Torus网络中进行了仿真实验,结果显示这一算法具有良好的平滑降级使用的特性。     

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.     

无线传感器网络中网络层故障容错技术研究进展

故障容错能提高无线传感器网络的稳定性和可靠性, 是无线传感器网络的一项关键技术。网络层容错及跨层协同优化设计是网络故障容错的重要研究内容, 主要对网络层容错技术研究进行了归纳和总结。网络层容错控制技术主要分为多路由传输、纠删编码/网络编码、数据重传机制、跨层协同优化与复合容错和仿生智能容错等, 并对网络层容错控制技术研究趋势作了探讨。     

系统互连网络的容错策略研究

本文研究了互连网路由算法的容错问题,分析了各种切换技术下多种容错路由和错误恢复策略的特点及适用情况,研究了典型算法的优缺点。     

无虚拟通道的3D NoC ZoneDefense容错路由算法*

3D片上网络能有效解决片上系统的通信问题。本文针对3D Mesh NoC中的节点故障,提出了一种无虚拟通道容错路由算法,称为3D ZoneDefense容错路由算法(3D-ZDFT)。该算法建立在3D防御区域基础之上,3D防御区域能够提供故障体的位置信息。根据防御区域提供的故障体位置信息,3D-ZDFT可提前发现故障位置并改变转发端口,实现容错的同时避免引入死锁。实验结果表明,与HamFA相比,3D-ZDFT有较低的网络延迟和更高的可靠性。面积开销分析显示,3D-ZDFT比HamFA的面积开销高约3.1%。     

A general theory for deadlock-free adaptive routing using a mixedset of resources

This paper presents a theoretical framework for the design of deadlock-free fully adaptive routing algorithms for a general class of network topologies and switching techniques in a single, unified theory. A general theory is proposed that allows the design of deadlock avoidance-based as well as deadlock recovery-based wormhole and virtual cut-through adaptive routing algorithms that use a homogeneous or a heterogeneous (mixed) set of resources. The theory also allows channel queues to be allocated nonatomically, utilizing resources efficiently. A general methodology for the design of fully adaptive routing algorithms applicable to arbitrary network topologies is also proposed. The proposed theory and methodology allow the design of efficient network routers that require minimal resources for handling infrequent deadlocks