双层二维网格结构间的Wromhole路由算法

二维网格结构由于其较好的可扩展性而被越来越广泛地应用，因此对于二维网格结构多处理机间的数据通信，寻找一个好的路由算法也越来越重要。以Intel公司的Option Red机器为背景，分析了双层二维网格结构多处理机间的通信机制，并且针对该实际结构，根据单层二维网格结构中以Wormhole原理为基础的Unicast自适应路由算法，提出了适用于双层二维网格结构的无死锁的Wormhole路由算法。根据该算法得出的数据传输路径是无死锁的最短传输路径。     

蜂窝网格的单播路由算法

六角形蜂窝网格是一种具有良好网络拓扑性质的并行多处理机互连网络.蜂窝网格在某些特性上优于二维网格.不过,这种网络不存在单信道最短路径无死锁路由算法.文中针对该网络设计了两个部分自适应无死锁虫孔路由算法.一个是基于转弯模型单信道非最短路径路由算法,另一个则是采用了虚拟双信道的最短路径路由算法.对第二个算法,还进一步使用转弯模型对其改进.通过仿真实验,结果显示这两个路由算法都具有较好的性能.     

二维mesh上的自适应容错路由算法

基于故障块模型提出了二维ｍｅｓｈ上的自适应无死锁容错路由算法。该算法将网络分为两个虚拟网络ＶＩＮ０和ＶＩＮ１。消息根据源与目的节点的相对位置判断进入哪一个虚拟网络。消息在没有遇上故障时经由最短路径路由。算法的容错技术是基于故障环和故障链的概念。最后,将该算法与另一个二维ｍｅｓｈ上的容错路由算法ｆ－ｃｕｂｃ２进行性能比较。     

蜂窝网络上的路由算法*

主要研究蜂窝网络上的无死锁单播路由算法和一对全的广播路由算法。基于蜂窝网络的砖形画法,利用二维网络维序路由的基本思想和两个虚拟网络实现了无死锁的最短单播路由算法,并证明了算法的无死锁性。然后基于这个单播路由算法和线列上的广播算法,用软件实现了蜂窝网络上一对全的广播路由算法,经过简单比较得出该广播算法比以往的算法在通信效率上有了极大的提高。     

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

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

二维网格片上网络中的新型自适应路由算法

本文针对二维网格的片上网络设计了一种称为维度气泡流控(DBFC)的新型流控策略。利用虚跨步切换技术中消息的依存关系只与相邻缓冲区队列相关的特点,设计实现了维度气泡流控。该流控策略建立在虚跨步(VCT)切换和信约流控机制之上,通过分析端口信约值和路由信息实现点点间的流控。在二维网格的片上网络中采用DBFC流控策略,即使网络中存在环相关,本文设计的自适应维度气泡路由(ADBR)算法仍可实现无死锁、最短距离的路由。对于以上结论,本文提供了详细证明。最后,通过修改通用的片上网络模拟工具-NOXIM的代码,实现了DBFC流控策略和ADBR算法。在NOXIM上分析了ADBR算法的性能,结果显示ADBR算法拥有较好的性能。     

基于对角互连网格拓扑结构的片上网络

对二维网格拓扑结构进行改进,给出对角互连的DMesh结构和对角互连且边界节点互连的DTorus结构,针对2种拓扑结构分别提出DXY路由算法和TDXY路由算法。仿真实验结果表明,DMesh和DTorus结构可以节省网络节点间的路由通道数,减少平均传输延迟,增加吞吐量,使路由路径更加多样化。     

一种邻节点状态感知的NoC可重构容错路由

芯片特征尺寸的减小导致NoC的故障发生率越来越高.针对传统NoC容错算法中容错路由路径过长的问题,提出了一种可重构容错路由算法.该算法基于扩展的细粒度功能故障模型,对邻节点的故障情况及时掌握,并结合新的路由端口优先级策略和奇偶转向模型,实现了数据包的无死锁最优化容错路由.实验表明,该算法的路由路径更接近于最短路由路径,同时以增加较少的硬件开销为代价,获得了更优的容错性能,并具有更低的延迟和更高的吞吐量.     

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

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

一种二维网格中最小路径区的构建模型

矩形故障块模型可用来解决二维网格中的容错路由问题.本文基于最小路径区(RMP)概念,提出了一种最小路径区的分布式构建模型.该模型首先将带有矩形故障块的网格划分成若干个不同大小的矩形块,通过矩形块的不同组合来构成相应两点之间的最小路径区.最后对该构建模型进行了扩展讨论,指出其在特殊二维网格和容错路由算法中的应用.     

ASCI Option Red Supercomputer中MRC的选路问题

对Optional Red的Solit2-D网孔拓扑结构的虫孔路由问题进行了简单探讨,尤其对死锁问题和执行过程以及容错等几个突出问题进行了分析,最后给出了单一信包一到一的无死锁虫孔路由选择算法.     

Adaptive and deadlock-free routing for irregular faulty patterns inmesh multicomputer

Message routing achieves the internode communication in parallel computers. A reliable routing is supposed to be deadlock-free and fault-tolerant. While many routing algorithms are able to tolerate a large number of faults enclosed by rectangular faulty blocks, there is no existing algorithm that is capable of handling irregular faulty patterns for wormhole networks. In this paper, a two-staged adaptive and deadlock-free routing algorithm called “Routing for Irregular Faulty Patterns” (RIFP) is proposed. It can tolerate irregular faulty patterns by transmitting messages from sources or to destinations within faulty blocks via multiple “intermediate nodes.” A method employed by RIFP is first introduced to generate intermediate nodes using the local failure information. By its aid, two communicating nodes can always exchange their data or intermediate results if there is at least one path between them. RIFP needs two virtual channels per physical link in meshes     

星形图上最小无死锁受限条件及无死锁路径算法

针对是形图中台能产生死锁的问题，对星形图上无无线锁的路径算法进行了研究，得到了星形图上的两类最小无死锁受限条件，并给出了一个满足该两类最小无死锁受限条件的无死锁路径算法。同时还证明了文献中提出的两个死锁受限条件分别只是该文所提出的两类最小无死锁受限条件的一个特例。     

一种对片上网络中Mesh结构的改进策略及路由算法

Mesh结构以其简单、规整、易于实现与扩展的特性而成为现在广泛应用的片上网络拓扑模型。对2D-Mesh结构进行了改进,给出了顶点互连的Vertices interconnect Mesh(VMesh)结构;同时,提出了在此结构上的无死锁路由算法。最后,通过详细的计算证明,此结构可以减小网络直径和平均延迟,增加吞吐量;并用gpNoCsim模拟器对此结构及算法进行了仿真,结果表明,此结构具有较小的平均延迟和平均距离。     

Deadlock-free multicast wormhole routing in 2-D mesh multicomputers

Multicast communication services, in which the same message is delivered from a source node to an arbitrary number of destination nodes, are being provided in new-generation multicomputers. Broadcast is a special case of multicast in which a message is delivered to all nodes in the network. The nCUBE-2, a wormhole-routed hypercube multicomputer, provides hardware support for broadcast and a restricted form of multicast in which the destinations form a subcube. However, the broadcast routing algorithm adopted in the nCUBE-2 is not deadlock-free. In this paper, four multicast wormhole routing strategies for 2-D mesh multicomputers are proposed and studied. All of the algorithms are shown to be deadlock-free. These are the first deadlock-free multicast wormhole routing algorithms ever proposed. A simulation study has been conducted that compares the performance of these multicast algorithms under dynamic network traffic conditions in a 2-D mesh. The results indicate that a dual-path routing algorithm offers performance advantages over tree-based, multipath, and fixed-path algorithms     

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.     

基于2D Mesh的NoC路由算法设计与仿真

在研究Turn Model模型的基础上,提出一种基于2D Mesh结构的XY-YX路由算法,是一种确定性的无死锁的最短路径路由算法。给出无死锁的证明,通过片上网络（NoC）模拟仿真实验平台NIRGAM,将该算法在一个4×4的2D Mesh网络中进行仿真,并与XY路由算     

A theory of deadlock-free adaptive multicast routing in wormholenetworks

A theory for the design of deadlock-free adaptive routing algorithms for wormhole networks, proposed by the author (1991, 1993), supplies sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies were proposed. Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. A tree-like routing scheme is not suitable for hardware-supported multicast in wormhole networks because it produces many headers for each message, drastically increasing the probability of a message being blocked. A path-based multicast routing model was proposed by Lin and Ni (1991) for multicomputers with 2D-mesh and hypercube topologies. In this model, messages are not replicated at intermediate nodes. This paper develops the theoretical background for the design of deadlock-free adaptive multicast routing algorithms. This theory is valid for wormhole networks using the path-based routing model. It is also valid when messages with a single destination and multiple destinations are mixed together. The new channel dependencies produced by messages with several destinations are studied. Also, two theorems are proposed, developing conditions to verify that an adaptive multicast routing algorithm is deadlock-free, even when there are cyclic dependencies between channels. As an example, the multicast routing algorithms of Lin and Ni are extended, so that they can take advantage of the alternative paths offered by the network     

一种避免拥塞的片上网络通信协议

为了平衡通信协议的自适应性和性能,提出一种避免拥塞的片上网络通信协议.该通信协议采用区分服务和自适应路由算法,区分服务提供不同等级数据流的质量保证型服务,自适应路由算法是一种避免拥塞的无死锁路由算法.通过OPNETM odeler建模仿真,结果表明该协议极大地改善了网络的平均链路利用率和端到端延迟.     

LEO卫星通信网的鲁棒路由算法

针对使用星际链路ISL的LEO卫星系统,许多学者提出基于面向连接结构的路由算法,但这些算法的性能很大程度上依赖于初始路径的建立,健壮性差。该文提出一种基于面向连接结构的增强路由算法,只要源卫星与目的卫星之间存在一条通路,源卫星便可以与目的卫星通信。若源卫星与目的卫星之间存在多条路径,通过该算法一定能在线找到其中的最佳路径。通过仿真实验评价了算法的性能,证明算法比已有的基于面向连接结构的路由算法具有更高的鲁棒性。