2DMesh片上网络分区容错路由算法

胡哲琨 杨升春 陈杰

Abstract： In order to reduce the entries of routing tables and avoid using large numbers of Virtual Channels （VC）， a Regionbased Fault Tolerant Routing （RFTR） algorithm was proposed for wormhole switching 2D Mesh Network on Chip （NoC） to reduce the amount of hardware resources. According to the positions of faulty nodes and links， the 2D Mesh network was divided into several rectangular regions. Within each region the packet could be routed by deterministic or adaptive routing algorithms， while among these regions the routing path was determined by up*/down* routing algorithm. Besides， with the Channel Dependency Graph （CDG） model， the proposed algorithm was proved to be deadlockfree using only two VCs. In a 6×6 Mesh network， the RFTR algorithm can reduce the amount of routing table resources by 25%. Simulation results show that， with the same amount of buffer resources， the RFTR algorithm can achieve an equivalent or even higher performance compared to up*/down* and segmentbased routing algorithms.

Key words：Network on Chip （NoC）； fault tolerant routing； deadlock avoidance； routing table； Channel Dependency Graph （CDG）

0 引言

随着集成电路工艺技术的发展，芯片内部可集成的IP核数目不断增加，出于对可扩展性、连线延时和功耗等因素的考虑，片上网络（Network on Chip， NoC）逐渐成为多核间通信的主流方式。2D Mesh是一种常用的片上网络结构，具有规则的平面布局，且易于实现高效无死锁的数据包路由。然而，集成电路制造过程中产生的缺陷和工艺变化等因素可能导致芯片中的部分节点或链路不能正常工作，从而打破了Mesh结构的规则性，且随着工艺尺寸的进一步缩小，该现象会更加明显。为了有效利用芯片中剩余的资源进行计算，片上网络需具有一定的容错特性，而其中一个重要方面就是容错路由算法的设计。

目前针对2D Mesh网络已存在多种容错算法。传统的基于故障块模型的容错路由算法[1-2]需要3至4个虚通道（Virtual Channels， VC）才能避免死锁，然而在片上网络中，较多的虚通道不仅会占用大量的缓存资源，还会导致路由器工作频率降低，因此这类算法并不适用于片上网络。拓扑无关的路由算法[3]也能用于容错路由，如up*/down*路由算法[4-5]和segment路由算法[6]。这些算法在不使用虚通道的情况下就能避免死锁，但需依赖路由表才能实现路由计算，而路由表的总项数与网络节点数的平方成正比，当片上网络的规模增大时，会导致芯片面积和功耗的急剧增加，因此这类算法缺乏良好的可扩展性。文献[7]提出了一种基于逻辑运算的分布式容错路由机制，无需虚通道就能避免死锁，但只能针对某些特定的拓扑结构（如“P”型、“+”型网络）适用。此外，文献[8-9]也分别针对2D Mesh片上网络提出了容错路由算法。

为了减小路由表的规模，同时避免使用较多虚通道，本文针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由（Regionbased Fault Tolerant Routing， RFTR）算法。该算法根据故障节点和链路的分布，将整个网络划分为若干个相连的矩形区域，数据包在区域内可按照确定性路由算法（如XY算法[4]）或自适应路由算法（如westfirst算法）进行路由，而在区域之间则按照up*/down*算法确定路由路径。该算法仅需2个虚通道就能避免死锁，且能显著减少路由表的使用。6×6 Mesh网络中的仿真结果表明，在路由器缓存资源相同的情况下，本文提出的RFTR算法能达到与up*/down*算法和segment算法相当甚至更优的性能。

1 分区容错模型

本文对片上网络采用静态故障模型，即已通过故障检测手段事先获得了故障节点和链路的位置，然后在此基础上计算路由表并对片上网络进行配置。一旦配置完成，数据包在网络中即可实现高效无死锁的传输。

图1示意了在一个6×6的Mesh网络中，节点N（8）、N（22）及链路C（9，15）发生故障时的情况。根据故障节点和链路的分布，整个网络被划分为若干个相连的矩形区域，每个矩形区域均为一个完整的子Mesh网络，且这些区域之间互不相交。每个节点除了记录自身的（x， y）坐标以外，还用一个区域寄存器记录其所属的区域。未被划分进矩形区域的节点则被设置为连接节点，如节点N（2）和N（16），这些节点根据路由表的配置进行区域间的数据包传递，但不参与网络中的并行计算。此外，如果一个区域中的节点与另一区域的节点相连（直接相连或通过连接节点相连），则称该节点为边界节点。因此通过矩形区域的划分和连接节点的设置，2D Mesh网络中的容错路由问题就转换为多个子Mesh网络间的路由问题。

2 分区容错路由算法设计

本文使用一种查表与逻辑运算相结合的方法来实现容错路由（RFTR），以使数据包在区域内可以按照确定性或自适应路由算法进行路由，而在区域之间则能绕过故障节点和故障链路实现无死锁的传输。本章首先给出矩形区域间的路由方法，继而描述路由表的结构，然后给出虚通道的使用规则及具体的路由算法，最后分析该算法的死锁特性。

2.1 区域间路由

与图1所示的矩形区域对应，图2（a）给出了其区域连接图，其中每个顶点都代表一个矩形区域，且两个顶点之间存在一条边当且仅当在2D Mesh网络中存在一对相连的节点分别位于这两个顶点所对应的矩形区域中。然后在区域连接图中按照up*/down*路由算法确定各条边的方向，其步骤[4]为：选取某个顶点作为树根，求得该区域连接图的一棵生成树，并将属于原图但不属于生成树的边（也称余边）添加到树中；如果一条边所关联的两个顶点位于生成树的不同层中，则靠近树根的方向为向上的（up），否则，靠近编号较小的顶点的方向为向上的，而与向上方向相反的方向则被称为向下的（down）。如果用箭头表示向上方向，那么根据以上规则所得到的有向图中不存在环，或者说从任意一个顶点出发，要再回到该顶点，至少需要经过一条向上的边和一条向下的边，这一性质对于保证RFTR算法不会发生死锁十分重要。

依据区域连接图中边的方向，数据包在区域间的传输规则为：禁止从向下的边到向上的边的转向，即数据包的传输应经过零次或多次向上的边，再经过零次或多次向下的边（因此算法取名为up*/down*，其中*表示重复0次或1次以上）。图2（b）所示的是选取顶点0作为树根时得到的有向图，例如数据包由区域3到达区域2后可以再转发给区域4，但是到达区域4后不能再向区域1传输。将区域连接图中所确定的边的方向映射到2D Mesh网络后，则得到图1所示的区域间连接的方向，数据包在网络中的传输应满足同样的规则，图1中示意了从N（20）到N（17）的数据包的传输路径。

2.2 路由表结构

为了使数据包在矩形区域间的传输符合上述规则，每个路由器中均使用一个路由表来指定数据包的传输路径，并利用标志位来区分表项的含义，如图3（a）所示。在执行路由计算时，用数据包的目的区域号对该表进行索引，如果其标志位为N（Node），则表项指定了数据包应该首先到达的边界节点的坐标；如果其标志位为D（Direction），则表明当前节点是一个边界节点，其表项指示了数据包应使用的输出端口（东/南/西/北）及其对应的up/down方向，该方向将用来指定虚通道的使用。图3（a）以节点N（20）为例示意了路由表的结构，其中目的节点位于区域0或区域1中的数据包应使用向南的输出端口，且其对应的区域间连接的方向是向上的，而目的节点位于区域4的数据包应该先到达节点N（15），其对应的坐标为（3，2）。

此外，为了表示连接节点的连接状态，每个路由器中还需提供一个连接表，该表可以是分布在各个输入端口的，也可以是集中式的。图3（b）以连接节点N（16）为例示意了连接表的结构，其中西、北两个端口相互连接。在计算路由表的内容时，应确保数据包不会从未指定连接关系的端口进入连接节点，如在图1中，数据包到达节点N（17）后不能向西传输。

2.3 RFTR算法

路由表和连接表仅指示了数据包在区域间的路由路径，而数据包在矩形区域内则可按照已有的确定性或自适应路由算法进行路由，如XY路由算法或westfirst路由算法。由于每个矩形区域均为完整的子Mesh网络，因此区域内的路由计算可以采用逻辑运算的方式实现。这样，路由表的项数仅与矩形区域的数目有关，而与每个区域内节点的数目并无关系，因此这种查表与逻辑运算相结合的路由计算方式为矩形区域的划分提供了灵活性，且有助于减少路由表的资源用量。

然而当数据包在多个矩形区域之间路由时，网络中可能会发生死锁[10]，其原因为：针对某一矩形区域而言，从进入该区域的连接到离开该区域的连接之间，可能会存在由通道依赖关系形成的通路，因此当两个或多个区域之间存在连接时，其通道依赖关系就可能形成回路。为了避免死锁的发生，本文对文献[11]的死锁避免方案进行了扩展，具体为：网络中使用两个虚通道VC0和VC1，如果数据包的目的节点与源节点位于同一矩形区域内，则数据包可以选择任何一个虚通道进入网络，且一直使用该虚通道进行路由，直到被目的节点接收；而当数据包的目的节点与源节点不在同一区域时，数据包通过VC0进入网络，仅当数据包穿过向下方向的区域间连接时，才切换到VC1中，并继续使用VC1进行路由，直到被目的节点接收。由于一个数据包通过向下方向的连接后，不能再使用向上方向的连接，因此不会发生从VC1到VC0的切换。最后，注意到只有边界节点的路由表才指定了区域间连接的方向，因此只有在边界节点中才能发生虚通道的切换，而在矩形区域内和连接节点上的传输均不改变数据包所占用的虚通道。

RFTR算法首先检查当前端口是否处于连接状态，如果是则选择与其相连的输出端口作为路由结果。否则，如果当前区域就是目的区域，则使用westfirst算法路由到目的节点；而如果当前区域不是目的区域，则使用目的区域号对路由表进行索引，如果得到的标志位为N，则使用westfirst算法路由到其所指定的边界节点，否则，直接使用表项所指定的输出端口作为路由结果，并根据其方向使用相应的虚通道。

2.4 RFTR算法的死锁特性

为了说明RFTR算法是无死锁的，本节首先引入通道依赖图（Channel Dependency Graph， CDG）的概念及路由算法无死锁的充分条件[12]，继而证明RFTR算法的死锁特性。

定义1 在一个由非空节点集N和非空通道集C组成的网络I=G（N， C）中，给定一个路由算法R，如果数据包在路由过程中会连续地使用通道cij和cjk，则存在从cij到cjk的通道依赖关系。

定义2 网络I和路由算法R所对应的通道依赖图是一个有向图D=G（V， E），该图中的顶点vij对应网络I中的通道cij，该图中的边e（vij， vjk）则对应从cij到cjk的通道依赖关系。如果在网络I中一条物理通道对应了多个虚通道，则在通道依赖图D中对每个虚通道均用一个顶点来表示。

引理1 在网络I中，对一个给定的路由算法R，如果其对应的通道依赖图D中不存在回路，则该路由算法不会发生死锁[12]。

图4给出了在2×3 Mesh网络中使用westfirst路由算法时的通道依赖图，可以看出该图中不存在回路，其原因为任何一个回路都必须包含由南向西或者由北向西的边，而westfirst算法禁止这两种类型的路由转向。

定理1 对于RFTR算法，如果矩形区域内使用的路由算法所对应的通道依赖图不存在回路，则该算法不会发生死锁。

证明 由于矩形区域内的通道依赖图不存在回路，因此如果要形成回路，则必须通过多个矩形区域。为此，任意选择一个矩形区域，考虑如下两种情况：

1）数据包通过向下方向的区域间连接传输到另一矩形区域，由虚通道的使用规则可知，数据包离开该区域后一定位于VC1中，而根据up*/down*路由算法的规则可知，所有处于VC1中的数据包均不能使用向上方向的连接，因此在通道依赖图中沿着其通道依赖关系不能再返回到该区域，所以不能构成回路；

2）数据包通过向上方向的区域间连接传输到另一矩形区域，则该数据包一定位于VC0中，而在其所构成的通道依赖图中，为了能沿着通道依赖关系返回该区域，则一定需要使用向下方向的连接，那么返回该区域的通道依赖关系一定是针对VC1的依赖关系，如图5所示，而由于VC1中的数据包不能切换到VC0中，所以其通道依赖关系不能再回到VC0构成回路。

综合以上情况，RFTR算法对应的通道依赖图中不存在回路，所以该算法无死锁。

注意到在以上证明过程中，如果所考虑的区域为树根区域，则所有离开该区域的连接均为向下方向的连接，因此对该区域不会发生上述的第二种情况，所以数据包在树根区域中路由时可在VC0和VC1间随意切换，而不必担心发生死锁，其唯一需保证的就是数据包离开该区域后使用VC1进行路由。由于在up*/down*路由算法中，树根节点通常会承受更多的数据包负载，因此使用该优化措施可提高对树根区域的带宽利用率，缓解因树根区域负载过重而使网络过早达到饱和的情况。最后，各矩形区域内的路由算法仅需保证其对应的通道依赖图中不存在回路，而不同区域内使用的路由算法可以不同。

3 路由表硬件开销

在系统设计阶段，由于故障节点和链路的位置和数目是未知的，因此对路由表项的数目，或者说网络中可划分出的矩形区域的数目，就存在一定的权衡：更多的路由表项能容纳更多的故障，然而也需要消耗更多的硬件资源。本文对一个n×n（其中n∈{4，6，8，10}）的2D Mesh网络，分别按照5%和10%的比例随机生成了一系列的故障节点，然后在此基础上计算矩形区域和连接节点的数目，表1给出了其统计平均值。

从表1可以看出，在一个n×n的2D Mesh网络中使用n个路由表项即可覆盖大多数的故障情况，在这种情况下，RFTR算法中路由表和连接表的比特数总和为：

[（1+2「lb n）×n+3×4]×n2

而传统的路由表所需的比特数为2n4。当n等于6时，RFTR算法能节省25%的路由表资源，而当n增加到8时，其所节省的路由表资源能达到46%以上。

需要指出的是，矩形区域的划分方式会对连接节点的数量产生影响，由于连接节点仅作为区域间通信的通道，并不参与并行计算，因此在划分矩形区域时应在路由表项允许的范围内尽量覆盖较多的非故障节点。

4 仿真结果及分析

为了对RFTR算法进行性能验证，本文用SystemC搭建了周期精确的片上网络仿真平台。该平台中的路由器采用虫孔交换策略，具有5级流水，且为了保证数据包传输的公平性，对虚通道分配和交叉开关分配均采用基于延时（agebased）优先策略，即先进入网络的数据包拥有较高优先级。此外，本文还设计了基于传统路由表的路由器，用于对up*/down*算法和segment算法进行仿真，并将其结果与RFTR算法比较。

在配置路由表时，数据包均按照最短路径路由。在RFTR算法中，数据包在区域内采用westfirst路由算法，而在区域间如果有多个边界节点可用，则选择离当前路由器最近的边界节点进行路由；对于up*/down*路由算法，其生成树的计算方式对网络性能具有重要影响，而本文使用的则是基于深度优先搜索生成树的算法[5]，该算法对比基于广度优先搜索生成树的算法[4]在性能上有很大提高；此外，在对segment路由算法进行仿真时，对其路由转向的限制也从负载均衡的角度进行了优化。

本文在6×6 Mesh网络中，分别按照5%和10%的比例随机产生故障节点，并在此基础上生成路由表进行仿真。对RFTR算法而言，其路由器具有2个虚通道，每个虚通道的缓存队列容量为6个微片；而由于up*/down*算法和segment算法无需使用虚通道，为了保证各算法使用相同的缓存资源，其路由器缓存队列的容量被设置为12个微片。在仿真过程中，每个节点均按照均匀分布的概率r随机选取一个有效目的节点发送数据包，且数据包的长度均匀分布在区间[2，10]内。

图6和图7分别给出了故障节点率为5%和10%时，四种随机故障模式下的数据包延时。从图中可以看出，当数据包注入率较小时，这三种算法所提供的数据包传输延时基本一致；然而随着注入率的增大，各算法逐渐呈现出性能上的差异：up*/down*算法最先达到饱和，其次是segment算法，最后是RFTR算法。但根据故障节点位置的不同，这种差异并不是一定的，如在图7（c）中，这三种算法的饱和注入率就非常接近，其原因为，故障节点的具体位置对矩形区域的划分方式会产生影响，当区域间连接的数目较少，或者大量数据包的传输集中在少数边界节点时，这些连接和边界节点会成为瓶颈而限制网络吞吐率。因此从整体来看，RFTR算法能达到与up*/down*算法和segment算法相当甚至更优的性能。

5 结语

本文针对2D Mesh片上网络提出了一种分区容错路由算法，通过划分矩形区域和设置连接节点，将2D Mesh中的容错路由问题转换成多个子Mesh网络间的路由问题。该算法仅需2个虚通道就能避免死锁，且通过查表与逻辑运算相结合的路由计算方式，减少了路由表资源的用量。仿真结果表明，在路由器缓存资源相同的情况下，本文算法能达到与up*/down*算法和segment算法相当甚至更优的性能。考虑到矩形区域的划分方式对RFTR算法的性能会产生影响，因此在给定故障节点和链路的具体位置的情况下，寻求优化的区域划分方法是下一步工作的重点。

参考文献：

[1] CHEN C L， CHIU G M. A faulttolerant routing scheme for meshes with nonconvex faults[J]. IEEE Transactions on Parallel and Distributed Systems， 2001， 12（5）： 467-475.

[2] ZHOU J P， LAU F C M. Multiphase minimal faulttolerant wormhole routing in meshes[J]. Parallel Computing， 2004， 30（3）：423-442.

[3] FLICH J， SKEIE T， MEJIA A， et al. A survey and evaluation of topologyagnostic deterministic routing algorithms[J]. IEEE Transactions on Parallel and Distributed Systems， 2012， 23（3）： 405-423.

[4] DUATO J， YALAMANCHILI S， NI L. Interconnection Networks： An Engineering Approach[M]. San Francisco： Morgan Kaufmann Publishers， 2003： 190-194.

[5] SANCHO J， ROBLES A， DUATO J. An effective methodology to improve the performance of the up*/down* routing algorithm[J]. IEEE Transactions on Parallel and Distributed Systems， 2004， 15（8）： 740-753.

[6] MEJIA A， FLICH J， DUATO J， et al. Segmentbased routing： an efficient faulttolerant routing algorithm for meshes and tori[C]// Proceedings of the 20th International Parallel and Distributed Processing Symposium. Washington， DC： IEEE Computer Society， 2006： 10-19.

[7] FLICH J， RODRIGO S， DUATO J. An efficient implementation of distributed routing algorithms for NoCs[C]// Proceedings of the 2nd ACM/IEEE International Symposium on NetworksonChip. Washington， DC： IEEE Computer Society， 2008： 87-96.

[8] 姚磊， 蔡觉平， 李赞， 等. 2DMesh结构片上网络无虚通道容错路由算法[J]. 西安电子科技大学学报（自然科学版）， 2012， 39（6）： 26-33. （YAO L， CAI J P， LI Z， el al. Faulttolerant routing algorithm for the 2DMesh networkonchip without using virtual channels[J]. Journal of Xidian University（Natural Science）， 2012， 39（6）： 26-33.）

[9] 周磊， 吴宁， 李云. 一种基于2Dmesh的片上网络无死锁容错路由算法[J]. 上海交通大学学报， 2013， 47（1）： 18-22. （ZHOU L， WU N， LI Y. A faulttolerant and deadlockfree routing algorithm in 2Dmesh for network on chip[J]. Journal of Shanghai Jiaotong University， 2013， 47（1）： 18-22.）

[10] HOLSMARK R， KUMAR S， PALESI M， et al. HiRA： a methodology for deadlock free routing in hierarchical networks on chip[C]// Proceedings of the 3rd ACM/IEEE International Symposium on NetworksonChip. Washington， DC： IEEE Computer Society， 2009：2-11.

[11] DUBOIS F， SHEIBANYRAD A， PETROT F， et al. Elevatorfirst： a deadlockfree distributed routing algorithm for vertically partially connected 3DNoCs[J]. IEEE Transactions on Computers， 2013， 62（3）： 609-615.

[12] DALLY W J， SEITZ C L. Deadlockfree message routing in multiprocessor interconnection networks[J]. IEEE Transactions on Computers， 1987， 36（5）：547-553.