一种片上网络容错路由算法

赵巍，才华，吴剑飞

（长春理工大学，长春　130022）

一种片上网络容错路由算法

赵巍，才华，吴剑飞

（长春理工大学，长春130022）

为解决片上网络的可靠性问题，以2D-Mesh拓扑结构为基础，将片上网络中的节点划分为边缘节点和内部节点两大类，并分别针对这两大类节点的各自特征有针对性地提出相对快捷的路径决策模型和转弯模型，从而帮助路由节点更为快捷地确定符合自身特征的当前任务最佳传送路径，算法大幅缩减了重复运算时间，并减少了数据计算量。通过容错偏转路由算法进行仿真实验，应用本文算法和XY路由算法、Flooding路由算法进行比较分析，实验结果证明算法可以有效的避免产生死锁和拥塞，具有很好的传输效率。

片上网络；容错方法；转弯模型

随着集成电路工艺的不断进步，系统芯片的规模不断增大，基于片上系统（SoC）［1，2］的芯片设计非常复杂，而且传统的SoC体系结构及其设计方法在多知识产权（IP）核的超复杂系统中遇到了技术瓶颈。从2000年开始，业界提出一种全新系统芯片设计模型—片上网络（NoC）［3，4］，将计算机网络技术移植到芯片设计中来，彻底解决多IP模块体系结构中的问题。

本文基于2D-Mesh拓扑结构提出一种新的算法，展现一个可以在二维网络拓扑结构容错的路由算法。

1　基于2D-Mesh拓扑结构的片上网络偏转容错路由算法

片上网络是有冗余特性的一种结构，在传递信息的过程，节点间信息传递都有很多不同路径，这为研究路由容错算法提供了条件。本算法所要解决的技术问题是提供一种结构简单、功耗低、占用内存小的可重构容错路由算法。

2D-Mesh片上网络的容错路由算法需要满足以下特点：

低成本：硬件成本产生的可重构性必须占总路由器硅面积很小的百分比。

通用性：可重构路由算法必须可以应用在任何出现故障的路由（或出现故障的区域）拓扑结构中。

可拓展：重构的硬件必须是独立的二维网格大小。

无死锁：任何可重构的路由算法必须无死锁。确定性：确保按次序发送属性，数据是否可顺利从起始点发送到终点。

1.1容错偏转路由算法相关定义

定义一：相邻节点

在二维网格上，一个节点（X，Y）有四个直接相邻节点（东，南，西，北方向各一个），和四个间接相邻节点（东北，西北，东南，西南方向各一个）。本文认为这8个节点是相邻节点。

定义二：内部路由节点

在2D-Mesh网络结构中，如果与一个节点相邻的节点有4个，则该节点叫做内部路由节点（如图1），6、7、10、11即为内部路由节点。

定义三：边缘路由节点

在2D-Mesh网络结构中，如果与一个节点相邻的节点不大于三个，则将这种最多有三个相邻路由节点的节点叫做边缘路由节点（如图1），1、2、3、4等即为边缘路由节点。

图14　*4 2D-Mesh结构

定义四：ping命令的测试超时时间

定义计量时间的确定常数T，设置当前路由节点对其相临节点发送ping命令测试包。若在T时间范围内，测试包发送回源节点，则当前路由器传送的路径是通路，否则是非通路。

1.2容错偏转路由算法实现具体描述

该方法的具体步骤如下所示：

步骤一：为本容错偏转路由算法定义基础信息，分别定义变量，包括：内部路由节点、边缘路由节点和ping命令的测试超时时间并定义基础X-Y传输规则；

步骤二：2D-mesh拓扑片上网络的初始化；

步骤三：当m×n的2D-mesh拓扑片上网络开始一个以任意一个路由节点A为起点并以另外一个任意路由节点B为终点的数据传送任务时，将路由节点A称为数据源节点，并将目标路由节点B称为目标节点；

步骤四：内部路由节点的数据传输过程；

步骤五：边缘路由节点的数据传输过程。

具体应用的总体流程如图2所示。若路由节点X未故障或拥塞，则以内部数据源节点M为起点数据传送任务将顺次经过路由节点C、D和X，并最终完成整个传送任务过程，其传送路径遵循基础X-Y传输规则，在图3中以实线的折线箭头示意。

图2　算法总体流程图

图3　当前的内部数据源节点M至目标节点B的绕行原理示意图

图4　数据包结构

若节点X为非通节点，则由本算法确定的数据传送绕行路径由图3中的虚线的折线箭头示意。

2　仿真分析

2.1仿真数据设置

在片上网络中传输的数据有发送端发送的数据包和接收端接收后发送的反馈包。发送端中将发送的数据包拆分为两种微片，分别是包头微片和数据微片。报头微片、数据微片以及反馈包的具体结构如图4所示。

实验应用这种数据包结构，将数据包分成一个个微片，组包传输数据，对微片进行计数，将地址等相关信息按照规定的包头微片格式组装到包头微片中，然后将有效数据按规定的数据微片格式组装到数据微片中，最后将所有的微片进行编码存储。

2.2仿真环境设置

主要参数配置如表1所示。

表1　仿真平台参数设置

实验构造了10×10的2D-Mesh拓扑结构，为设置虚拟通道，有100个通信节点，数据可通过这些节点达到传输目的。并采用XY路由算法，Flooding路由算法和本文的DTM容错路由算法进行比较。每一种仿真实验运行10次，以减少偏差，使结果更精确。实验前需设置源节点和目的节点所在位置。

分组数据根据字节数和占全部分组的百分比确定。据统计结果：30字节长度的数据包占30%，40字节的占40%，500字节的占20%，2000字节的占的10%。失效率是指失效路由占所有路由的百分比。根据不同失效率状态下的比较，可清晰地知道哪一种算法更有利于路由器的容错性能。

仿真流量模型采用低负载条件下的（即均匀分布）流量模型和高负载（即集中分布）条件下的流量模型来判断。低负载流量模型是指：输入较少的数据包流量，网络中每一个节点传递信息的数据包都比较小，传递完信息后，每个节点有空闲时间等待下一节点传输过来的信息。高负载流量模型是指：数据运行传输过程中，所有的节点向一个节点传输信息，以检查每一个节点是否能够顺利到达目的节点，有故障路由的情况下，是否可以绕过故障节点同样达到可靠传输。实验采用平均时延和网络吞吐量来判断整体的网络数据传输性能。

2.3实验结果分析

仿真结果如图5至图8所示。采用不同容错路由算法时，随路由器失效率的增加，网络负载情况的改变，网络延时（cycles）和网络吞吐量（flits/wireless router/cycle）方面各自有变化。图中各曲线分别代表对应的容错路由算法。

图5　低负载情况相同的失效率下不同算法延时的比较

失效率为0时，三种情况延时均为0。随失效率增加，XY路由算法的延时增加比较快，失效率达到3%时达到最高值，失效率为4%时，出现拥塞，由于信息停止传输，所以也就没有所谓的延时。Flooding路由算法在有一定的失效率情况下同样能将信息有效的传输，但当失效率达到4%时，延时随之增加很快，所以Flooding路由算法对于延时控制不佳。DTM路由算法在低负载的情况下优势明显，当失效率在3%时，DTM算法还是能够稳步的传递可靠信息，当失效率达到6%的时候，DTM路由算法还是在一定延时状态下将信息顺利的从源节点传递到目的节点。

图6　高负载情况下相同的失效率下不同算法延时的比较

相对于低负载情况，XY路由算法在失效率为2%的时候就已经达到饱和状态，信息无法继续传递。Flooding路由算法在失效率为3%时延时开始迅速增加，最终每一个路由节点均达到饱和无法传输信息。而DTM路由算法在高负载的情况下只是比低负载时在失效率相同的情况增加了一些延时，每一个数据包都能达到有效的传输目的。

图7　低负载情况相同的失效率下不同算法吞吐量的比较

在失效率为0的情况下，三种算法网络吞吐量差不多。随失效率的增加，XY路由算法的网络吞吐量在失效率达到3%时明显下降很快，网络吞吐量快速降低。Flooding路由算法在达到3%时网络吞吐量还算正常，但随着网络继续传递信息，当失效率达到4%时，网络吞吐量也急剧下降。DTM路由算法无论是在失效率达到3%、4%或以上的情况都有相对其他两种算法较高的网络吞吐量，能在容错的基础上实现信息的有效传输。

图8　高负载情况相同的失效率下不同算法吞吐量的比较

由于负载较高，开始时XY路由的网络吞吐量就相对较低。Flooding路由算法相对DTM路由算法较低，说明高负载失效率为零的情况下Flooding路由算法也会受到影响，同时，Flooding路由算法和DTM路由算法与低负载的情况比较相同，区别就是Flooding路由算法在失效率和时间逐渐增强的时候吞吐量会达到饱和，信息也就不会继续传输。而DTM路由算法在一般情况下能够满足有效传输信息。

2.4性能比较

2.4.1延时比较

在相同网络负载环境下，3个数据传输算法均有不同的表现，在三种不同的网络环境下设定相同的源节点和目的节点，开始的时候三种路由算法的延时大体相同，但随着网络负载的增加，可看出偏转容错路由算法时延明显比其他两种方法低很多。

2.4.2网络吞吐量比较

在相同网络负载和失效率情况下，三种数据传输算法也有不同的网络吞吐量，在低负载时开始相同，随着失效率增加，DTM路由算法有明显的优势。在高负载的情况下，DTM路由算法在一开始的网络吞吐量就比其他两种要高。综上所述，在网络吞吐量方面，DTM路由算法是一种比较有优势的容错偏转路由算法。

图5至图8显示，在不同网络负载情况下，最开始无失效率的情况下，三种算法在延迟和吞吐量方面的差异不大。随着失效率不断增加，网络负载的提高，各种路由算法对网络性能都会产生不同的影响，2D-Mesh拓扑结构下的片上网络偏转容错路由算法优势明显。上述对比结果表示，DTM路由算法在不同的数据流量模式，在性能上都有比较明显的优势。能够更好地解决网络中出现的拥塞、死锁等问题，在路由器出现故障的情况下，都会将信息传递到位，使网络性能维持在一个良好的状态。

通过上述实验，证明了2D-Mesh拓扑结构下的片上网络偏转容错路由算法可以实现数据的有效传输，当网络中出现故障路由的时候，容错路由算法可以通过绕过故障的方式传递信息，即2D-Mesh拓扑结构下的片上网络偏转容错路由算法具有容错功能。

3　结论

2D-Mesh网络拓扑结构在设计中具有实现简单、规则性、设计成本低、便于操控等优势，所以在片上网络中应用这一结构很有优势。基于2D-Mesh网络拓扑结构提出了一种新的容错算法。利用转弯模型和边缘路由的路由表信息实现了一种低成本、结构简单、功耗消耗低、占用内存小的可重构容错路由算法。该算法实用性强、容错性能高、硬件开销少。在网络性能需求上，能够满足路由器之间的可靠性连接的需求。

［1］Ditomaso D，Kodi A，Kaya S，et al.IWise：Inter-router wireless scalable egress channels for Network-on-Chips（NoCs）architecture［C］.The 19th Annual System on High Performance Interconnects. IEEE，2011：11-18.

［2］ Chen X，Lu Z，Jantsch A，et al.Supporting distributedsharedmemoryonmulticorenetwork-onchips using a dual microcode controller［C］.ProceedingsofDesign，AutomationandTestinEurope Conference and Exhibition，2010：39-44.

［3］AisoposK，ChenCHO，PehLS.EnablingSystem-levelmodelingofvariation-inducedfaultsin networks-on-chips［C］.IEEEDesignAutomation Conference，2011：930-935.

［4］Ditomaso D，aha S，Kodi A，et al.Evaluation and performanceanalysisofenergyefficientwireless NoC architecture［C］.Midwest Symposium on Circuits&Systems，2012，59（5）：798-801.

［5］ Dumitras T，Marculescu R.On-chip stochastic communication［SoCapplications］［DB］.InProceedings of the Design，Automation and Test in Europe Conference and Exhibition（DATE’03）.2003：790-795.

［6］Tang M，Lin X.Network-on-chip routing algorithmsbybreakingcycles［C］.ICA3PP2010：163-173.

［7］Ganguly A，Pande PP，Belzer B.Crosstalk-aware channel coding schemes for energy efficient and reliable NOC interconnects［J］.IEEE Transactions on VeryLargeScaleIntegration（VLSI） Systems，2009，17（11）：1626-1639.

［8］ 张媛緩.片上互连网络关键问题研究［D］.北京：清华大学，2012.

［9］Murali S，Theocharides T，Vijaykrishnan N，et al. Analysis of error recovery schemes for networks on chips［J］.IEEE Design Test of Computers 2005，22 （5）：434-442.

A Fault Tolerant Routing Algorithm for Network on Chip

ZHAO Wei，CAI Hua，WU Jianfei
（Changchun University of Science and Technology，Changchun 130022）

In order to solve the reliability of the on-chip network problems，the nodes of Network-on-Chip will be divided into two types which are edge node and internal nodes on the basis of 2D-Mesh topology structure，and according to the respective characteristics of two kinds of nodes puts forward relatively fast path decision-making model and turning model，helping routing node to determine the best way which is the current task and accordes with its own characteristics more quickly.This algorithm greatly reduces the repeated operation time，and reduces the amount of data calculation.By using fault-tolerant deflection routing algorithm to do simulation experiment，and proposed algorithm and the XY routing algorithm，flooding routing algorithm to do comparative analysis，the experimental results show that the proposed algorithm can avoid deadlock and congestion effectively and has great transmission efficiency.

Network-on-Chip；fault-tolerance approach；turning model

TN47

A

1672-9870（2015）06-0145-05

2015-12-21

赵巍（1980-），男，博士研究生，工程师，E-mail：zhaowei@cust.edu.cn