不规则网络拓扑结构下的多棵树路由算法研究

为了提高不规则网络拓扑结构的路由效率,提出了一种新型路由算法-多棵树路由算法.考虑了原始路由算法的不足,平均了网络中各个通道的利用率,降低路由表的平均路径长度,同时在死锁发生时能够及时有效的进行死锁恢复,解决了先前路由算法中通道负载集中、通道利用率低、路由表平均路径长度过长的问题.通过模拟真实硬件环境的模拟器软件,表明了在不同规模、不同负载下的不规则网络下多棵树路由算法具有更高的效率.     

基于PRDT的16节点NoC路由算法

网络结构对于片上网络系统的性能和功耗发挥着重要作用，PRDT(2,1)有着较低的网络直径和平均距离、常数的节点度以及良好的可扩展性，这些特点使其非常适于NoC。为了提高小规模PRDT的路由性能，该文提出了一种binary路由算法，当网络规模不大于16时，该算法无须使用虚拟通道即可实现无死锁路由，通过增加少量虚拟通道，可改进为完全自适应路由算法。对所提出的路由算法与原有的向量路由算法进行仿真比较，结果显示binary算法在硬件成本较低的同时，性能更为优异，完全可以应用于基于PRDT的小规模NoC网络。     

支持确定性/自适应路由的低延迟片上路由器设计

自适应路由可以有效地提高片上网络性能,却导致网络中的数据传输乱序.设计了一个两级流水虚拟通道虫孔交换路由器,通过修改数据包的标记位和路由计算单元,使路由器支持确定性和自适应路由算法,简化了数据传输乱序问题;同时,将流经路由器的数据流分为东西和南北2个部分;在此基础上从经典的部分自适应路由出发,增加虚拟通道允许原本禁止的转向,实现了无死锁的自适应路由,并降低了网络延迟与硬件开销.     

ORA——一种负载平衡的虚通道分配算法

MPP互联网中通常使用虚通病来防止死锁和提高网络吞吐率。但通常的虚通道分配算法会导致通道的负载不平衡,从而降低网络的性能。针对采用虫孔路由技术和维序路由算法下的Torus互联网,提出了ORA虚通道负载平衡分配算法。与Naive分配算法和Scott分配算法的比较表明,ORA能够较好地实现负载平衡,能够较好地提高网络的性能。     

不规则网络中基于拐弯模型的路由算法的设计

由虫孔路由交换器连接而成的不规则拓扑网络，越来越多地用于构建工作站机群系统（NOWs），以实现高性能价格比的并行处理．采用虫孔路由技术，网络中容易发生死锁．交换器之间连接的不规则性，使路由避免死锁问题变得更加复杂．本文给出了在不规则网络中，设计基于拐弯模型的无死锁路由算法的一般方法，并采用扩展链路方向的方法得到多种路由策略，确定了up-first与down-last两种性能较优的路由算法．最后通过模拟实验，评价了算法的性能．     

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

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

基于局部扭曲立方体的多播路由算法

局部扭曲立方体是一种新提出来用于并行计算的互联网络。经研究发现,局部扭曲立方体中已有最小路由算法存在着死锁。因此,在原有算法的基础上,提出了一种新的无死锁路由算法并给出了无死锁证明。利用将物理通道分成两条虚拟通道进而形成两个不相交的虚拟网络,将不同的点对之间的路由限定在某一个虚拟网络中,从而有效地避免了死锁的产生。同时,利用一个局部扭曲立方体可由两个低维子立文体和2-扭曲立方体构成这一性质,在局部的低维子立方体和2-扭曲立方体中均采用自适应路由,从而提高了算法的自适应性。在此基础上提出了一种多播路由算法。     

LCFAA:一个低代价的完全自适应路由算法

大规模并行处理机系统（ＭＰＰ）中路由算法对互联网络通信性能和系统性能起着重要作用。自适应路由算法具有灵活性好、网络的通道利用率高和网络容错能力强等优点,但其实现难度较大,因而目前仅在少数ＭＰＰ系统中得以实现。文中在ｍｅｓｈ结构上提出了一个低代价无死锁的安全自适应最短虫孔路由算法ＬＣＦＡＡ,该算法所需虚通道数少,具有代价低、自适应性强的特点。文中证明了算法的无死锁、无活锁性和完全自适应性,并模拟验证     

基于虚拟通道非均匀分布的路由算法

随着片上系统(systems on chip,SoC)集成度的提高,IP核之间的通信成为SoC急需解决的问题。近年来提出的片上网络(network on chip,NoC)是解决SoC通信问题的一种有效方法。虚拟通道和路由算法是NoC设计中的关键技术,对NoC的延时、吞吐量等性能有重要的影响。根据NoC负载分布特点,提出一种新的虚拟通道非均匀分布技术VCND。该技术在Mesh内部使用虚拟通道,在边界上使用非虚拟通道,从而减少缓冲单元的数量。同时提出一种改进的无死锁路由算法CXY(combination XY)。仿真结果表明,与XY路由算法和XY-YX路由算法相比,CXY路由算法提高了网络吞吐量,并降低了网络平均延时;相比虚拟通道均匀分布技术,VCND技术能够以较小的吞吐量和网络延时损失获得可观的缓冲单元利用率提升,并减少了路由器的面积。     

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

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