一种无虚通道NoC负载均衡容错路由算法

，徐海，，

(1.上海大学 微电子研究与开发中心，上海 200072；2.吉林大学 软件学院，长春 130012)

一种无虚通道NoC负载均衡容错路由算法

刘鹏1，徐海鹏1，崇云锋1，赵倩倩2

(1.上海大学微电子研究与开发中心，上海200072；2.吉林大学软件学院，长春130012)

随着芯片复杂度的不断增大，设计一个高效的片上网络容错路由算法面临着巨大的挑战；由于芯片面积开销的限制，拥有低面积开销的无虚通道片上网络路由器受到学术界的广泛关注；但目前对无虚通道片上网络容错路由算法的研究却停留在容错性能上，而忽略了容错路由算法的路由路径过于单一所造成的负载不均、数据包平均延迟较大等问题；文章在借鉴已有的奇偶转向容错路由算法的基础上，对算法的故障模型和故障绕行策略进行优化，并在算法中融入负载均衡策略，以形成新的容错算法缓解上述问题；在9x9的2D mesh网络中对新提出的算法和参考算法的仿真结果表明：与参考算法相比，新算法在降低数据延迟和吞吐量方面有着明显的优势，在最优情况下能减少8.92%数据延迟和增加10.46%的吞吐量。

虚通道；容错；故障模型；负载均衡

0 引言

在集成电路设计中，将多个物理核集成在同一个芯片中用于提升计算性能已成为一个重要的发展趋势。随着多核芯片的发展，各物理核之间的通信量迅速增长，分时复用的片上总线互连结构已不能满足多核芯片在扩展性、并行性和功耗等方面的要求。为了解决多核互联所面临的上述问题，专家和学者们提出了一种以通信为中心、采用全局异步局部同步的片上互连结构，片上网络(network on chip, NoC)[1]。

然而，伴随着多核芯片的密集度和复杂度的不断增大，以NoC为互联结构的多核芯片对制造工艺偏差和外界干扰也变得越来越敏感，发生故障的概率也越来越大。这些故障可能会使NoC的性能急剧下降或直接瘫痪[2]。为确保芯片的可靠性，设计一种高效的容错路由算法是非常有必要的[3]。

当前，由于芯片面积开销的限制，拥有低面积开销的无虚通道片上路由器受到学术界的广泛关注。对无虚通道NoC容错路由器的设计主要可以分为硬件容错和算法容错。硬件容错需要在NoC路由器中添加备份单元，以保证故障发生时，NoC路由器仍能正常运作[4]。然而增加备份单元将增大芯片面积开销。因此算法容错方案逐渐在无虚通道NoC路由器的容错设计中成为主流。

1 无虚通道容错算法的相关研究

当前无虚通道NoC容错路由算法可大致分为基于泛洪机制的容错路由算法[5]、基于查找表的容错路由算法[6]和基于转向模型的容错路由算法[7-9]。基于泛洪机制的容错路由算法会向网络中发送大量的冗余数据包，随着网络负载的增大，网络性能将急剧下降。采用查找表的容错路由算法，需要在NoC路由器中增加一张路由表，以确定数据包的路由路径。然而，随着NoC尺寸的扩大，路由表的尺寸也随之增大，造成面积开销、功耗和数据包延迟迅速增加。而基于转向模型的容错路由算法在硬件开销和性能上均优于上述两类容错算法，因此基于转向模型的容错路由算法已成为NoC容错的一个重要研究方向。

基于转向模型的NoC容错方案主要面临网络死锁和故障绕行这两个问题。为了解决这两个问题的，基于转向模型的容错算法将在遵守已有的无死锁转向规则基础之上，对基于该转向规则的路由算法进行扩展，使之具备故障绕行功能，以达到容错的要求。死锁是数据包在传输过程中所形成的循环等待队列引发的。基于转向模型的无死锁转向规则[10]最早是由Glass和Ni提出，它是通过禁用部分90度转向以破坏循环等待队列的形成条件来杜绝死锁的发生。目前，大部分基于转向模型的无虚通道容错路由算法都是基于Glass和Ni的转向规则扩展设计的，典型的有Yusuke借鉴Glass和Ni的无死锁转向模型，提出一种Message-based容错路由算法[7]。这种算法使用矩形故障模型对故障节点进行扩展，并在不同路由方向的数据包上施加不同的转向限制，通过这些方法在赋予算法容错能力的同时避免死锁的发生。Fu也基于Glass和Ni的转向模型提出一种ZoneDefense的容错路由算法[8]。此算法在每个节点中增加Ceiling 和Floor寄存器，分别记录着该节点南、北方向上故障区的位置信息。并利用Ceiling 和Floor中矩形故障区的位置信息在故障区之间构成了叫做ZoneDefense的区域。当数据包在ZoneDefense区域路由时，算法会禁用那些使数据包垂直撞向故障区而引发死锁的转向，从而避免了死锁的发生。

Glass和Ni的路由算法存在有路径分配不均的问题，在某个方向上仅能提供一条路由路径，而基于它的容错算法也存在这样的问题。因此Chiu对Glass和Ni的转向规则进行改进，提出奇偶(Odd-Even, OE)转向模型[11]。它将不同的转向限制分别施加在奇数和偶数列节点，并通过这种方式将路径均匀分配到各个方向路由的数据包。具体的OE转向规则如Rule1：

1) 任何数据包在偶数列不允许使用由东向北转向(EN)和由东向南转向(ES)。

2) 任何数据包在奇数列不允许使用由北向西转向(NW)和由南向西转向(SW)。

Wu提出一种典型的基于OE转向规则的容错路由算法[9]。为了使算法能够容忍更多的故障节点，Wu的算法需要禁用一些无故障节点，以形成矩形的故障区，并且在故障区的东、西方向上需要预留两条故障边界。

然而无论是基于Glass和Ni还是Chiu的转向规则的容错算法都存在一个共同的问题：他们把工作过多的集中在容错上，而忽略了各个节点的负载不均所导致的网络局部拥塞、数据包平均延迟较大等问题。为了缓解这些问题，将对Wu的故障绕行策略和故障模型进行优化和改进，然后在此基础上融入负载均衡策略，最终形成一种无虚通道NoC负载均衡容错路由算法，它可以借助负载策略把数据负载分配到各个节点上，使得空闲的带宽资源能被充分的利用，以缓解局部拥塞和关键路径上数据包延迟较大等问题，提升了NoC的性能。

2 基于转向规则的负载均衡容错算法

新提出的无虚通道NoC负载均衡容错路由算法是基于路径分配均匀的OE转向规则扩展而来，它主要包含三部分内容：故障模型、故障绕行策略、负载均衡策略。这里将对算法的这3个部分进行具体的展开说明。

2.1 故障模型

目前大部分基于转向模型的无虚通道容错路由算法采用的是矩形故障模型，这种故障模型在形成过程中需要牺牲大量的安全节点，并且不适用于新算法的负载均衡策略。因此新算法将对 Wu的矩形故障模型[9]进行优化和改进，以形成适用于新算法的故障模型。

为简化算法的复杂度、容忍更多的故障节点，Wu在故障模型中定义了安全节点、危险节点和活动节点以形成矩形故障区和适用于故障绕行的故障边界。其中，危险节点是由网络中的无故障节点转化而来，它的转化方案如Rule2。

Rule2：在初始状态下所有的无故障节点都是安全节点，一个安全节点只要满足下列任意一个条件时，则转变成危险节点：

1) 相邻位置上至少有两个危险节点或故障节点。

2) 东方向或西方向的相邻位置上有一个危险节点或者故障节点，且这个节的西方向或东方向相邻节点的南、北方向上有相邻的危险节点或者故障节点。

重复1)、2)过程直到无新的危险节点生成，最终把危险节点和故障节点统称为禁用节点，然后由这些禁用节点形成矩形的故障区。

然而，形成上述矩形故障区将牺牲过多的安全节点。针对这个问题，新的故障模型将在上述规则之上增加一条规则，以激活矩形故障区西边缘上部分险节点，减少安全节点损失的数量。危险节点激活规则如Rule3。

Rule3：当一个危险节点在西方向上和南、北方向上有一个相邻的安全节点，这个危险节点将被激活成安全节点。

重复上述过程直到没有新的危险节点被激活，最终形成左凸多边形故障区。由于OE转向规则是通过破坏循环等待队列右边界的形成条件以杜绝死锁的发生，在Wu的故障绕行策略下，激活故障区右边缘上的危险节点可能会导致数据包在故障绕行时形成循环等待队列的右边界。因此新算法仅对故障区的西边缘进行优化。

图1 故障模型应用实例

图1是新故障模型的应用实例。在初始状态下所有的无故障节点都是安全节点，执行Rule2后，网络中牺牲了大量安全节点。新算法将会采用Rule3激活故障区西边缘的部分危险节点。在执行完Rule3后，危险节点的数量将明显的下降。

新算法使用的故障绕行策略和负载均衡策略都是基于OE转向规则扩展而来，为了给东向、西向故障绕行的数据包提供足够多的转向许可，在故障区的东、西方向上会有一条由活动节点相互连接所形成奇数列和偶数列故障边。而这里的活动节点是由与禁用节点相邻的安全节点转化而来，它的具体的生成方案如Rule4。

Rule4：故障区形成之后，网络中只有禁用节点和安全节点，一个安全节点满足以下任意一种条件时，则变为边界节点。

1) 以该安全节点为原点，在其南、北方向相邻位置上存在禁用节点。

2) 以该安全节点为原点，在其东、西方向上相距两跳之内存在禁用节点。

重复执行Rule4，直到不再产生活动节点，然后这些活动节点将相互连接形成故障边。

由于新算法借鉴了Wu的故障绕行策略对需要进行故障绕行的数据包进行故障路由。而按照Wu的故障绕行规则，南、北方向故障路由的数据包需要优先沿南、北方向路由，以确定数据包是否要进行故障路由，且只能沿着故障区的西边界进行绕行。为了在容错算法中融入负载均衡策略，在新故障模型中将故障区南、北两个方向上的安全节点称为临界节点，其转化方案如Rule5。

Rule5：在故障边界形成之后网络将有禁用节点、活动节点和安全节点，其中部分处于故障区南、北方向上的安全节点在满足以下任一条件时，将转化为临界节点，其转化规则如下。

1) 在南向上与活动节点或者临界点相邻的安全节点。

2) 在北向上与活动节点或者临界节点相邻的安全节。

重复Rule5直到不再有临界节点生成。临界节点位于故障区的南、北方向上，算法将对数据包是否需要故障绕行进行预判，以确定数据包是否能施行负载均衡策略。

2.2 故障绕行策略

故障模型的主要作用在于简化容错路由算法的复杂度、容忍更多故障节点。而故障绕行策略则是容错路由算法中至关重要的部分，它直接决定算法的容错能力。新算法将在Wu的故障绕行策略中融入网络边界故障绕行规则，以形成具有能容忍网络边界故障区的故障绕行策略。在Wu的故障绕行策略中，南、北向故障路由的数据包将一律沿着故障区西边界进行故障绕行，因此Wu的故障绕行策略不支持无故障西边界的网络西边界故障区的故障容错。为解决网络西边界故障区的容错问题，新算法规定网络边界故障区南、北故障边界与内侧东边界的交界节点为辅助节点，且允许辅助节点使用OE转向规则所禁用的转向。下面将对改进后的绕行策略的绕行规则Rule6进行介绍。

Rule6：在叙述故障绕行规则之前，先对部分字母符号做以下定义：dx为数据包的目的节点横坐标与当前节点横坐标的差值，dy为数据包的目的节点纵坐标与当前节点纵坐标的差值，S为源节点，E代表偶数列、O代表奇数列。算法将根据不同的故障边界、节点的类型和路由方向为数据包选择不同的路由路径：

1) 如果dx、dy为零，当前节点为目的节点，数据包则被本地节点吸收。dx或dy不为0时转向2)。

2) 如果dy不为零，当前节点为安全节点或临界节点，数据包则优先向西路由到最近的偶数节点，然后沿着南、北方向路由，直到dy为零或遇到故障边界。当前节点为活动节点则转向3)。

3) 如果dx或dy不为零，当前节点为活动节点，且路由方向与所处的故障边平行，数据包则沿着原来方向继续路由。路由方向与故障边垂直时则转向4)。

4) 如果dx不为零，当前节点为故障东边界上的活动节点，且路由方向与所处的故障边界垂直，数据包则优先向西路由到最近的偶数列活动节点，然后沿着靠近目的节点的故障边界向目的节点路由。当前节点在故障西边界上则转5)。

5) 如果dx不为零，当前节点为故障西边界上的活动节点，且路由方向与所处的故障边界垂直，数据包则优先向东路由到最近的奇数列活动节点，然后沿着靠近目的节点的故障边界向目的节点路由。当前节点在故障南、北边界上则转6)。

6) 如果dy不为零，当前节点为网络边界故障区南、北边界上的活动节点，且数据包的路由方向与所处的故障边界垂直，路由算法需要根据东、西故障边界的存在情况为数据包选择不同的路由方向。当故障区只有东边界或西边界时，数据包将分别向东或向西发送，经过辅助节点或故障边的交界点，沿着故障东边界或西边界进行故障绕行；当故障区既有东边界又有西边界时，数据包则沿着靠近目的节点的方向路由。网络内部故障区的故障绕行转向7)。

7) 如果dy不为零，当前节点为网络内部故障区南、北边界上的活动节点，且数据包的路由方向与所处的故障边界垂直，数据包将向西发送，沿故障区西边界绕行。其他情况转8)。

8) 当数据包所处节点的状态、dx，dy的值、路由方向不满足上述条件时，数据包优先沿南、北方向路由，直到dy为0或遇到活动节点，然后沿着东、西方向路由。

2.3 负载均衡策略

在奇偶转向规则和最短路径的限制下，dx、dy都不为零的数据包可能存在多个输出端口，负载均衡策略则根据输出端口上一时段的输出情况为数据包选择输出端口，以实现负载均衡。为了施行均衡策略，在每个路由节点中会有一个4 bit的寄存器balac_bit[x](x=0,1,2,3)用于决定负载均衡模式下的数据的输出端口。表1为数据包在负载均衡模式下的输出端口，balac_bit[x](x=0,1,2,3)分别决定了数据包dxgt;0amp;amp;dygt;0、dxgt;0amp;amp;dylt;0、dxlt;0amp;amp;dygt;0和dxlt;0amp;amp;dylt;0时端口的输出情况。

表1 负载均衡模式下数据包的输出端口

数据包确定输出端口后会把相应的balac_bit[x]位取反，在下一个数据到达这个节点时，会把它分配到另外一条路径上，以实现负载的均衡和空余的带宽资源的充分利用。

2.4 算法的执行步骤

新的容错路由算法主要由一个故障模型和两种路由策略构成，故障模型用于容忍更多的故障节点和简化算法复杂度，两种路由策略则被固化在路由计算单元中为处于不同情况下的数据包选择路由路径，当数据包进入NoC路由节点的缓存单元后，路由计算单元将根据数据包的目的地址坐标、当前节点的地址坐标和当前节点的状态选择不同的路由策略。算法具体执行流程如图3所示。

1)当数据进入NoC路由器的缓存单元后，路由器首先判断当前节点是否为目的节点，如果当前节点为目的节点，数据包则被本地节点吸收，否则转向步骤2) 。

2)当前节点为安全节点时，算法将根据负载均衡策略为数据包选择输出端口。如果当前节点不是安全节点则转向步骤3)。

3)当前节点为临界节点或活动节点，路由算法则会先根据数据包的目的地址坐标与当前节点坐标对数据包是否要故障绕行进行预判，如果数据包需要进行故障绕行，算法则采用故障绕行策略为数据包选择路由路径。反之则采用负载均衡策略为数据包选择路由路径。

图2 算法的执行流程图

未到达目的节点的数据包将重复上述步骤为数据包选择输出端口，直到到达目的节点，其算法流程如图2所示。数据包在路由过程中可能会交替使用负载均衡策略和故障绕行策略，以应对不同路由环境。图3是南、北向数据包的路由实例，数据包A和B的目的节点被无西故障边界的网络西边界故障区隔断，因此它们将一律向东借助辅助节点沿故障东边界路由；数据包C路由到南边界故障区的边界时，由于故障区既有东边界又有西边界，这时数据将沿着靠近目的节点的方向进行故障绕行；数据包D和E绕行的是网络内部故障区，因此数据包D和E将一律沿着故障西边界进行路由。

图3 南、北向数据包路由实例

图4是东、西向数据包的路由实例，数据包F和G需要沿无北故障边界的网络北边界故障区绕行，它们将被向南发送，沿故障南边界进行故障绕行；而数据包H和I到达网络内部故障区的边界后，它们将沿着靠近目的节点的方向路由。

图4 东、西向数据包路由实例

2.5 无死锁的证明

新算法使用了负载均衡策略和故障绕行策略为数据包选择路由路径，负载均衡策略是在遵循OE转向规则下对多输出端口的数据包进行端口输出选择，南、北向数据包绕行网络西边界故障区的路由策略和东、西向数据包绕行故障区的路由策略都与Wu的路由策略一致，遵循OE转向规则，不会引发死锁。而南、北向数据包沿故障东边界进行绕行时，在辅助节点使用了OE转向规则所禁用的转向，可能会形成循环等待队列的右边界，但却不会引发死锁，具体证明如下：

假设采用辅助节点路由的数据包在网络中形成了循环等待队列的右边界，并且导致网络中发生死锁。那么这个引发死锁的循环等待队列一定要包含该辅助节点和其绕行的网络边界故障区。然而网络边界的故障区不存在完整的故障边界，假设不成立，网络不会出现死锁。因此借助辅助节点绕行网络边界故障区的数据包不满足循环等待队形成的条件，故障绕行策略和新算法都是无死锁的。

3 实验分析与结论

本文将采用NIRGAM[12]仿真器对算法的性能进行仿真与验证，它是一种基于System C的NoC专用模拟器，能对NoC的数据包的延迟和节点的吞吐量进行的仿真。性能仿真实验将在负载不均的热点模式下，向9x9的2D mesh网络中注入4%和8%的故障节点对新提出的算法、Wu的算法[9]和文献[7]的算法进行仿真。通过对比3种算法在热点模式下平均延迟和吞吐量的差距以证明新算法的优越性。在热点模式下将会随机地选取10%的节点作为通信热点，这些通信热点的通信量将比普通节点的通信量高出40%。

3.1 实验结果分析

图5和图6分别为热点模式下数据包平均延迟和节点吞吐量的仿真结果曲线图。在热点模式下，数据负载在网络中负载的分配相对集中，在关键路径上容易引发局部拥塞和数据包延迟较大等问题。而在这种情况下，新算法中的负载均衡策略可以把集中的数据负载分配到其他带宽相对富裕的节点上。因此从曲线图中可以看出，随着网络负载率的增大新算法在数据包

图5 热点模式下数据包的平均延迟

图6 热点模式下节点的平均吞吐量

延迟和节点吞吐量的优势都将逐渐增大，相对Wu的算法，在下最优情况下能降低8.92%的数据包平均延迟和增加10.48%的节点吞吐量；但随着故障注入率增加到8%，能施行均衡策略的节点数量也在不断的减少，在网络带宽利用率到达最大值时，新算法在数据包平均延迟和节点吞吐量的优势将逐渐减小。但由于牺牲的无故障节点较少，新算法的性能仍会优于其他两种算法。

3.2 结论

文章针对当前无虚通道容错路由算法存在的负载分配不均的问题，借鉴Wu的故障绕行策略提出了一种无虚通道NoC负载均衡容错路由算。该算法能将数据负载分配到其他空闲的通信节点上，在保证网络不发生死锁的同时降低了数据包的平均延迟、增加了节点的吞吐量。实验结果表明在故障率适中、负载较大的情况下新算法能取得一个良好的效果。

[1] Benini L, De M G. Networks on chips: a new SoC paradigm [J]. Computer, 2002, 35(1):70-78.

[2] L Xiaowei, Yu H, Lei Z et al. The fault tolerant design of digital IC [M]. Beijing: Science Press, 2011.

[3] Wu M S, Lee L C. Using a periodic square wave test signal to detect crosstalk faults [J]. IEEE Design amp; Test of Computer, 2005, 22(2):160-169.

[4] Feng C C, Lu Z H, Jantsch A, et al. A reconfigurable fault-tolerant deflection routing algorithm basesd on reinforcement learning from network-on-chip [A]. the 3rd International Workshop on Network on Chip Architecture [C]. New York, 2010.

[5] Pirretti M, Link G, Brooks R, et al. Fault tolerant algorithm for network on Chip interconnect [A]. Computer Society Annual Symposium on VLSI [C]. Lafayette, 2004.

[6] Fick D, Deorio A, Chen G, et al. A highly resilient routing algorithm for fault tolerant NoCs [A]. Design, Automation and Test Europe Conference amp; Exhibition [C], Nice, 2009.

[7] Yusuke F, Masaru F, Susumu H. Fault Tolerant Routing Algorithm for Network on Chip without Virtual Channels [A]. International Symposium on Defect and Fault Tolerance in VLSI Systems [C], Chicago, 2009.

[8] F Binzhang, H Yinhe, L Huawei, et al. ZoneDefense: A Fault Tolerant Routing for 2D Meshes Without Virtual Channels [J]. IEEE Transactions on very large scale integration system 2014, 22(1):113-126.

[9] Wu Jie. A Fault-Tolerant and Deadlock-Free Routing Protocol in 2D Meshes Based on Odd-Even Turn Model [J]. IEEE Transactions on computers 2003, 52(9):1154-1169.

[10] Glass C J, Ni L M. The Turn Model for Adaptive Routing [A]. Computer Architecture. Los Alamitos [C], Los Alamitos, 1992.

[11] Chiu Geming.The Odd-Even Turn Model for Adaptive Routing [J]. IEEE transactions on parallel and distributed systems 2000, 11(7):729-738.

[12] Lavina J. A simulator for NoC interconnect routing and application modeling [D]. UK: University of Southampton, 2007.

ALoad-balancingFault-tolerantNoCRoutingAlgorithmBasedonTurnRulesWithoutVirtualChannel

Liu Peng1, Xu Haipeng1, Chong Yunfeng1, Zhao Qianqian2

(1.Microelectronics Ramp;D Center, Shanghai University, Shanghai 200072, China;2.College of software, Jilin University, Changchun 130012, China)

As structure of chip is becoming more complex, an efficient routing algorithm designed for Network on Chip has became increasingly challenging. Currently, the research of fault-tolerant routing algorithm without virtual channels mainly focus on routing around fault, but neglects issues of load-balancing and latency caused by communication hotspot and single path between source and destination. To address the problems, a fault-tolerant routing algorithm based on Odd-Even turn rules with load-balancing strategy is proposed based on existing OE fault-tolerant strategy. The novel algorithm extend Odd-Even fault model and Odd-Even fault-tolerant strategy to enhance capacity of fault-tolerant and also fuse a load-balance strategy to relieve the issues. The simulation results demonstrate that the proposed algorithm outperforms in average package latency and throughout compared to reference algorithms in the 9x9 2D mesh NoC. In the best case, it reduces 8.92% average delay and increase 10.46% throughout.

virtual channel; fault-tolerance; fault model; load-balancing

2017-03-01；

2017-03-24。

刘 鹏(1991-)，男，江西赣州人，硕士，硕士研究生，主要从事集成电路容错设计方向的研究。

1671-4598(2017)09-0126-04

10.16526/j.cnki.11-4762/tp.2017.09.033

TP336

A