一种高吞吐低延时NoC容错路由算法

韦良芬，张佑生，王勇

(1.安徽三联学院计算机科学与技术系，安徽合肥230601；2.合肥工业大学计算机与信息学院，安徽合肥230092；3.安徽工程大学计算机与信息学院，安徽芜湖241000)

一种高吞吐低延时NoC容错路由算法

韦良芬1,2，张佑生2，王勇3

(1.安徽三联学院计算机科学与技术系，安徽合肥230601；2.合肥工业大学计算机与信息学院，安徽合肥230092；3.安徽工程大学计算机与信息学院，安徽芜湖241000)

为了提高片上网络（Network-on-Chip，NoC）系统的可靠性及故障情况下的网络性能，基于转弯模型（Turn Model）的思想对现有的XY路由算法进行了改进,提出了一种容错路径短，且在故障情况下具有信息均衡能力的无虚通道容错路由算法（T-XY路由算法）。OPNET仿真结果表明，该算法与同类算法相比具有较好的吞吐及时延性能。

片上网络；容错路由；2Dmesh

随着芯片制造技术的不断发展，芯片系统制造工艺不断升级，如元器件设计的精简、电路集成方式密集度增加、电路工作频率的提高以及电路工作电压的降低等，导致芯片故障的因素亦随之增多[1]；另外，芯片规模不断扩大，特征尺寸减小、IP核的增多等也将增加片上网络（Network-on-Chip，NoC）系统出现故障的概率[2]。因此，增加系统的容错能力，提高系统的可靠性成为片上网络系统的重点研究内容之一。现有的容错方案中，通常存在容错开销较大、网络流量不均衡等问题。

NoC容错路由算法分为有虚通道技术和无虚通道技术2种类型。增加了虚通道技术的路由节点比无虚通道的路由节点需要多增加1至2个逻辑门，建立时延将近增加了1倍[3]。而NoC对功耗、面积及成本要求均非常严格，所以无虚通道技术更适合NoC要求。文献[4]提出了一种无虚通道容错路由算法，该算法可以用于解决单故障节点时的容错问题，但却存在绕行规律不强，网络负载不均等问题；文献[5]中无虚通道单故障节点的容错路由算法复杂度较低，绕行规律性较强，但绕行环路上网络负载较重；文献[6]提出利用内建自测机制（Built-in Self Test,BIST）获取故障位置信息的一种适用于多故障节点的无虚通道容错路由算法，但BIST所需的电路增加了NoC的面积，同时建立测试也需要时间。

本文利用XY路由算法在中低网络流量情况下的高效性特点以及转弯模型（Turn Model）的自适应能力，在不增加额外硬件的情况下，提出了一种无虚通道容错路由算法（T-XY路由算法）。

1 T-XY路由算法

本文T-XY路由算法是适用于2D_Mesh拓扑结构的一种容错路由算法。在网络没有故障的情况下采用传统的XY路由算法进行路由，一旦遇到故障，则向离目标节点近的垂直方向转弯路由，若相对于目标节点有2个相同距离的垂直节点，则根据不同方向优先选择指定的垂直节点进行路由。

1.1 算法原理

T-XY路由方向标示见图1。路由算法中每个节点拥有一张实时记录邻居节点故障状态的路由表。数据包的传输在路由过程中，若某个路由表记录了下一个节点存在故障，则根据源节点和目的节点的位置关系，分为以下几种情况避开故障。

1)源目的节点Y维坐标相等时，若向东或向西路由时遇到故障，则向其垂直方向拐弯路由一个节点（具有两个垂直节点的情况下，向东路由时优先判断Y+，向西路由时优先判断Y-），再应用XY路由算法路由到目标节点。

2)源目的节点X维坐标相等时，故障情况下，若具有两个垂直节点，向北路由时优先判断X+，向南路由时优先判断X-，再使用先Y后X的路由方式（即YX路由）路由到目标节点。

3)目的节点位于源节点的东北方向时，若X维东向路由时遇到故障，则转为YX路由；Y维北向再次遇到故障，则有转为XY路由；路由到X维坐标相同时遇到故障，则转向2；路由到Y维坐标相同遇到故障，则转向1。

当目的节点位于源节点的东南、西北、西南等方向时，故障的处理情况与3原理基本相同。若(XS,YS)表示源节点的坐标，(XD,YD)表示目的节点的坐标，ΔX=XD-XS表示目的节点和源节点X轴方向相对偏移量，ΔY=YD-YS表示目的节点和源节点Y轴方向相对偏移量。则T-XY路由算法故障时的拐弯方法可用表1所示。

图1 路由方向标示Fig.1 Route direction flag

表1 T-XY算法故障避让方法Tab.1 Faultavoidancemethodsof T-XY algorithm

1.2 算法描述

算法描述中的相关参数说明：

1）布尔值good、bad表示邻居状态。good表示邻居节点及链路状态正常。bad表示邻居节点及链路出现故障。

2）check（）函数用于判断邻居故障状态，返回值为good或bad。

3）channel为所选择的通道方向，其值的集合为{X+，X-，Y+,Y-}。具体方向设置如图1所示。

4）TTL表示一个数据包的生命周期。当TTL递减为0时，表示数据包传送失败。

算法如下：

1）收集相关状态信息，填写路由表;

2）进行XY维序路由;

3）if(TTL＜=0)

{维序路由失败，销毁数据包，释放链路和缓存资源}

4）路由开始

(1)if(△X=0&&△Y=0)到达目的节点，发送数据包到本地处理器，路由结束;

(2)if（△X!=0&&△Y=0），算法伪代码为：

①if（△X＞0&&△Y==0）

if(check(X+)==good)XY路由；

else if(check(Y+)==good)

{channel=Y+;△Y++;XY路由；} else if(check(Y-)==good)

{channel=Y-;△Y--;XY路由；}

else路由失败，转向3；

②if(△X＜0&&△Y==0)

if(check(X-)==good)XY路由；

else if(check(Y-)==good) {channel=Y-;△Y-;XY路由；}

else if(check(Y+)==good)

{channel=Y+;△Y++;XY路由；}

else路由失败，转向3；

(3)if（△X==0&&△Y!=0），与（2）类似，但拐弯一个节点后使用YX算法向目标节点路由。

(4)if（△X＞0&&△Y＞0），算法伪代码为：

if(check(X+)==good)

{channel=X+；进行XY路由；

if(check(Y+)==bad）转向（3）}

else{channel=Y+；YX路由；

if（check(Y+)==bad）

{channel=X+；转向（4）；}

else if（check(X+)==bad）转向（2）；}

△X＞0&&△Y＜0;△X＜0&&△Y＞0;△X＜0&&△Y＜0等几种情况的伪代码与（4）类似。

T-XY路由算法中无故障时采用XY路由算法进行路由，遇到故障时，采用容错方案将数据包正确传送到目的节点。因此，无故障时不会影响网络的性能。而在故障的情况下，除了源目的节点在一条直线上会略微增加数据的传输路径之外，其他情况的容错路径仍然是两节点间的最短路径。另外，该算法不需要增加额外的硬件开销。

图2所示为T-XY路由算法源节点和目的节点在不同位置关系情况下避让故障节点的示例。当源节点S（3,2）向其东北方向的目的节点D1（1,4）发送数据时，意向节点（3,3）为故障节点，则路由意向立即转为其垂直且朝向目标的北向节点（2,2）路由，接着应该向节点（1,2）路由，但节点（1,2）也为故障节点，固又转向其垂直且朝向目标的节点（2,3），并沿着东向继续路由，直到与目标节点Y维坐标相同再转为北向路由。所以源节点（3,2）向其东北方向的目的节点（1,4）发送数据，并遇到（3,3）和（1, 2）两个故障节点的情况下，T-XY路由算法的路由路径为：（3,2）→（2,2）→（2,3）→（2,4）→（1,4）。此路径仍然为源目的节点间的最短路径。从图3可以看出，当源节点和目标节点不在同一直线上时，即使遇到多处故障，T-XY容错路径仍然是最短路径，但当源节点和目标节点在同一直线上时遇到一个故障将会增加2个节点的路径长度。

图2 T-XY路由算法实例Fig.2 T-XY routing algorithm instance

2 T-XY算法性能仿真

延时和吞吐量是衡量片上网络性能的两个重要参数[7]。本文利用OPNET仿真平台对T-XY容错路由算法进行仿真，并与文献[8]提出的容错算法分别进行仿真比较，从而验证T-XY算法故障情况下的吞吐率和延时性能。文献[8]提出的算法是针对2D_Mesh结构中单故障节点的容错路由算法，在无故障区域，该算法也使用XY算法进行路由，但在故障区域，绕行环路上的负载较重。

仿真中搭建了一个包含6×6个节点的2D_Mesh结构的网络。为了验证算法在故障情况下的网络性能，人为设置了多处故障节点。网络仿真在虫孔交换机制和均匀流量模式下进行测试；如图3为文献[8]容错路由算法和T-XY容错路由算法在相同环境下的吞吐量对比曲线，图4为它们相同环境下的时延性能对比曲线。

图3 吞吐量比较曲线Fig.3 Throughput com parison curves

图4 时延比较曲线Fig.4 Latency com parison curves

从图3吞吐量曲线中可以看出在相同的网络环境下，T-XY容错路由算法故障的情况下具有较好吞吐性能，从输入率为0.1开始，T-XY算法相对于文献[8]算法来说，能实现更多的数据传输，因为T-XY算法在容错的时候不仅不会增加网络的拥塞程度，而且对网络的拥塞状况还具有一定的调节作用；从图4的时延曲线中可以看出，T-XY相对于文献[8]的算法来说具有更好的时延特性，因为T-XY算法除了源目的节点同在一条直线时容错具有绕道现象外，其他容错路径仍然为两节点间的最短路径。

T-XY容错路由算法不仅弥补了XY路由缺乏容错能力的不足，而且容错时根据源目的节点的相对位置采用不同的拐弯方式，对网络的拥塞状况也具有一定调节作用。同时容错带来的能耗和开销也相对较低。

3 结语

本文结合XY路由算法及转弯模型的思想，基于2D_Mesh拓扑结构，提出了一种新的容错路由算法——T-XY路由算法。该算法设计简单，基本没有额外的硬件开销。通过OPNET的仿真结果表明该算法具有高吞吐、低时延的特点，完全适合NoC的设计需求。

[1]葛芬.专用片上网络设计关键技术研究[D].南京：南京航空航天大学,2010.

[2]SeyrafiM,Asad A,ZonouzA E,etal.A new low cost fault tolerantsolution formesh based NoCs[C]//2010 InternationalConference on Electronicsand Information Engineering.Piscataway:IEEE,2010:207-213.

[3]林世俊,苏厉,金德鹏,等.虚通道数和时钟比率对片上网络的影响[J].清华大学学报：自然科学版,2009,49(1):86-89.

[4]Duan X M,Sun X M.Fault-tolerant routing in A PRDT(2,1)-based NoC[C]//2010 2nd International Conference on Computer Engineering and Technology.Piscataway:IEEE,2010：506-510.

[5]Zhang Z,GreinerA,Taktak S.A reconfigurable routing algorithm fora fault-tolerant2D-mesh network-on-chip[C]//45th ACM/IEEE Design Automation Conference.Piscataway:IEEE,2008:441-446.

[6]姚磊,蔡觉平,李赞,等.基于内建自测技术的Mesh结构NoC无虚通道容错路由算法[J].电子学报,2012,40(5):983-989.

[7]Cai JP,Huang G,Wang S,etal.OPNEC-sim:an efficientsimulation tool fornetwork-on-chip communication and energy performance analysis[J]//InternationalConference on Solid-State and Integrated CircuitTechnology 2010.Piscataway:IEEE,2010:1892-1894.

[8]Yusuke F,Masaru F.A fault-tolerant routing algorithm for network on chip withoutvirtual channels[C]//2009 IEEE International Symposium on Defectand FaultTolerance in VLSISystems.Piscataway:IEEE,2009:313-321.

责任编辑：丁吉海

AHigh-Throughputand Low-Latency TolerantRouting Algorithm for NoC

WEILiangfen1,2,ZHANG Yousheng2,WANG Yong3
(1.Departmentof Computer Science and Technology,Anhui Sanlian University,Hefei230601,China;2.School of Computer and Information,Hefei University of Technology,Hefei 230092,China;3.School of Computer and Information,AnhuiPolytechnic University,Wuhu 241000,China)

To improve reliability and network performance under fault conditions for the Network-on-Chip (Network-on-Chip,NoC)system,the idea based on Turn Modelmakes improvement of the current XY routing algorithm and puts forward a no virtual channel fault-tolerant routing algorithm(T-XY Routing A lgorithm).The algorithm has the short fault-tolerantpath and theability to balance the information.TheOPNET simulation results show that thisalgorithm hasbetterperformanceof throughputand latency compared with the sim ilaralgorithms.

network-on-chip;fault-tolerant routing;2Dmesh

TP302

A

10.3969/j.issn.1671-7872.2014.02.019

1671-7872(2014)02-0195-04

2013-06-13

国家自然科学基金项目(61106037)；安徽高校自然科学重点项目（KJ2013A040）；安徽省质量工程项目（2012jyxm589）

韦良芬（1975-），女，安徽舒城人，讲师，研究方向为片上网络、容错技术。