韩承浩，陈乃金，胡宇杨，李抗

（1.安徽工程大学 计算机与信息学院，芜湖 241000；2.安徽工程大学 电气工程学院，芜湖 241000）

随着可重构多核处理器的进一步发展，其编译映射工具片上数据传输的容错显得越来越重要[1]，片上网络数据传输拥塞或路由器故障导致可重构多核系统之间的数据传输时延显著增加，目前针对片上网络（network-on-chip，NoC）节点故障国内外学者大多采用路由容错等解决方法。一般而言，片上网络数据传输的容错机制大多从网络传输层找到可以替代的传输路径来避开故障节点位置，因为要改变NoC 原有的数据传输路径，所以需要解决网络死锁的问题，根据不同的解决网络死锁的方法，被分为有虚通道路由[2-3]和无虚通道路由。有虚通道路由将物理信道分为几个逻辑信道，通过切换不同的逻辑信道，来避免信道之间的相互依赖，从而解决死锁问题，然而这样就使得路由节点的逻辑门个数增大，功耗增大。无虚通道路由算法大多采用转向模型来避免死锁，通过禁止一定数量的转向，避免信道之间形成环形依赖[4]。由于有虚通道路由需要消耗额外的硬件达到容错的目的，而无虚通道路由主要依赖在故障节点周围的链路绕行来避开故障节点以达到容错的目的。

1 相关工作

关于故障预测的2D Mesh 单故障节点的无虚通道容错路由相关工作阐述可分为故障位置的检测和无虚通道容错路由算法。

1.1 故障位置的检测

对于故障位置的检测主要依赖于内建自测技术（Built-in Self Test，BIST），将外部检测的工具集成到电路内部，实现对故障类型、故障位置的诊断。Biswajit 等人[5]提出了一种面向在线分布式内建自测试的测试机制，该机制专门检测通信链路上的开放故障，并从NoC 中识别故障链路。随后，提出一种合适的容错策略。内建自测试是实现高可靠性的主要测试方案之一。该方案可对NoC 的基本组件进行故障测试和恢复。Bhowmik 等人[6]提出了一种检测通信介质中短路故障的内建自测试方法，提高了NoC 的产量和性能。

1.2 无虚通道容错路由算法

Zhang 等 人[7]提 出RR 算法 在 无 故 障 时 采 用XY 路由算法，当有故障节点在网络非边界区域时将故障节点相邻的四个节点，以及间接的四个顶点组成绕行环路，在绕行环路的东北角（SW，ES）禁止转向，来避免死锁，因此当故障节点出现在网络中心区域时由于需要考虑避免死锁，导致了某些数据包的长距离绕行，绕行环路负载不均衡等问题。针对此问题，姚磊等人[8]提出了FTR 算法对RR 算法进行了改进，对RR 算法中在绕行环路的东北角无法转向的数据包，在东北角节点的右邻接节点定义为辅助拐点允许数据包由北向西转向。Xie 等人[9]提出了一种具有一定容错能力的转向模型（Fault-Tolerant Odd-Even，FTOE），使得数据包有更多的路径进行传输，从而避开故障节点，可以被用于单故障节点容错，有较好的效果。Bahrebar 等人[10]利用算珠转向模型提出一种可重构无死锁路由方法，通过对算珠的动态调整，赋予数据包高度的适应性。谢瑞莲等人[11]提出一种低开销的无虚通道隔离路由算法，根据凸故障模型的思想划分不规则区域，利用不规则区域的边界传输数据包，来达到容错的目的。Rahaman 等人[12]提出无死锁的自适应容错NoC 路由（F-Route-NoCMesh，FRNM），该方法将NoC 中的多个故障节点，构造成一个正交凸形故障区域，通过自适应路由算法来绕过这个区域，实现容错。路由算法通过当前数据包的位置和目的节点的位置来作出不同的路由策略。通过转向模型来避免死锁，没有使用虚通道。通过虚拟故障块边界路由数据包来平衡流量，减小故障区域负载，通过实验表明网络平均时延、平均吞吐量和功耗均有改善。Sayed 等人[13]提出一种拥塞感知、容错和过程变化感知的自适应路由算法（CFPA），在每个路由器上都有一个路由表，以跟踪所有路由器的排队延迟。在路由决策中考虑到排队延迟，使路由器有能力通过非拥挤路径向目的地转发数据信息。CFPA 通过对数据包路由进行优先排序来避免死锁。因此，长路径的数据包比短路径的数据包有更高的优先权。CFPA 将NoC的吞吐量提高60%，使用CFPA，故障对NoC 吞吐量的影响减轻了48%，减少了网络时延。

通过对上述文献的研究发现，相关路由算法存在数据包传输距离长、网络负载不均衡等问题。本文对此展开深入研究，其研究方案列举如下：

（1）设计一种基于全局容错的转向模型，提出一种单节点故障预测无虚通道（Single-node Fault Prediction without Virtual Channels，SFPVC）路由算法。

（2）利用内建自测机制在X方向和Y方向作出预测，避免数据包垂直或水平方向进入绕行环路，减轻故障节点周围负载，减少数据包传输距离。

2 问题定义

定义1：节点坐标。

方向约定X+方向为东，X-方向为西，Y+方向为北，Y-方向为南；节点类型符号可表示为S、D和F等三种类型，其含义分别为源、目的和故障节点，S、D和F的坐 标 分别表 示为（Sx，Sy）、（Dx，Dy）和（Fx，Fy）。在本文中若无特殊说明则约定为网络规模为N×N。具体如图1 所示。

图1 路由节点坐标相关说明

定义2：故障点信息。

故障点信息可标定为一种特殊的数据包，发送到片上网络内的任意一节点，并且可以存储在路由器故障寄存器中。

定义3：节点数据传输转向模型。

本节点数据传输方向模型规定与文献[4]一致，NE 表示由北向东转向，WS 表示由西向南转向，ES 表示由东向南转向，NW 表示由北向西转向，SE 表示由南向东转向，WN 表示由西向北转向，EN 表示由东向北转向，SW 表示由南向西转向，具体如图2（a）所示，图2（b）表示非法转向。

图2 节点数据传输转向模型示意图

定义4：死锁。

在片上网络路由数据传输过程中出现的一种现象，即多个数据包在传输路径形成了无虚通道打结环路，这种现象称为死锁。死锁可以通过设计路由算法和数据流控制协议来避免，本文通过设计合理的路由算法避免死锁。

定义5：容错路由评价指标。

本文约定容错路由算法只对片上网络的时延进行评估，评价指标具体可分为静态仿真[14]指标均值μ和方差σ2，动态仿真指标饱和注入率η。具体说明如下：

均值是数据包在每个路由器上被途经的平均次数，均值越大则说明数据包传输距离越长，方差是每个路由器上被途经的次数的方差，方差反映了网络中的负载均衡情况，方差大则说明网络中某些区域负载过大，容易在该区域形成网络拥塞。均值和方差计算方法与文献[8]一致，具体公式如式（1）和式（2）所示。

式中，aij表示矩阵A中的一元素。具体计算方法如 下：把N×N的NoC中所有不重复的源-目的节点按照当前路由算法只发送一个数据包，然后在每个节点nij（1≤i≤N，1≤j≤N）处统计途经该节点的数据包个数aij，最终得到一个N×N矩阵A=（aij）。

注入率表示网络在单位时间内可处理的数据包个数，Ntotal_node表示网络中节点总数；Ttotal_cycle表示第一个头微片进入网络到最后一个微片尾离开网络的时间；LENi表示Ttotal_cycle时钟周期内成功到达目的节点的第i个数据包的长度，n表示所有到达目的节点的数据包个数，数据包长度单位为filts。

本文规定随着注入率的增大，当网络时延为零负载时延的两倍时所对应的注入率η记为饱和注入率。

3 实验动机和容错路由算法设计

3.1 实验动机

目前的故障节点绕行法，大多是先沿着正常路由传输，当检测到下一跳节点为故障节点时，才做出容错的策略，或者是将故障节点坐标存储在部分正常节点的故障存储器中，当数据包到达这些节点时，可以读取故障信息，从而作出容错策略。这样会使传输路径单一，部分数据包绕行距离过大等问题，本文提出一种单节点故障预测无虚通道路由算法，使数据包从第一跳就可以判断是否需要容错，以及采用何种容错策略，这样做可以提前容错，在尽可能追求传输路径最小的情况下，保证了传输路径多样性。使得负载平衡，降低网络时延。

3.2 容错路由算法设计

策略一：转向模型。本文是一种全局容错路由算法，就需要一种数据传输路径多样的转向模型，因此本文提出一种基于全局容错的无死锁转向模型（如图3 所示），对比RR 的转向模型和FTR 的转向模型，本文采用的转向模型禁止的转向少，使得数据传输路径更为多样。

图3 容错转向模型

策略二：X正方向绕行。当1≤Sx

（1）当Fx

（2）当Fx≤Dx≤N且Dy

（3）当Fx≤Dx≤N且Dy>Fy时，若Fx+ 2 =Dx沿YX路由传输到（Fx+ 1，Fy+ 1），此后沿YX路由传输，否则第一跳向北发送数据包，此后沿XY路由传输。

策略三：X负方向绕行。当Fx

（1）当1 ≤Dx＜Fx且Dy=Fy时，若Fx+ 1 =Sx，第一跳向南发送数据包此后沿XY路由传输，否则沿XY路由发送到（Fx+ 2，Fy+ 1），此后沿XY路由传输。

（2）当1 ≤Dx≤Fx且Dy

（3）当1 ≤Dx≤Fx且Dy>Fy时，若Fx+ 1 =Sx先以YX路由传输到（Fx- 1，Fy- 1），再向北传输到（Fx- 1，Fy+ 1），最后以XY算法传输，否则向西发送至（Fx+ 1，Fy）此后沿YX路由传输。

策略四：Y正方向绕行。当Fy

（1）当1 ≤Sy

（2）当1 ≤Sy

（3）当1 ≤SyFx+ 1 时，向西发送至Fx+ 1 列，再沿YX路由传输。

策略五：Y负方向绕行。当1 ≤Dy

（1）当Fy

（2）当Fy

（3）当FyFx时，先向西发送至Fx+ 1 行，再按YX路由传输。

策略六：避免死锁。若不满足策略二到策略五的条件，则按XY路由传输。然而这样会有以下两种情况，与图3 中禁止的转向相违背，会形成死锁：（1）当数据包满足在Fx+ 2 列由东向北转向；（2）当数据包满足在Fx+ 1 列且纵坐标小于Fy+ 2 处由东向南转向。对于第一种情况当数据包到达Fx+ 1 列时按YX算法路由；对于第二种情况直接按YX算法路由。

策略七：其他情况。对于策略六中的第二种情况，当1 ≤Sx≤Fx，Sy=Fy且Dx=Fx+ 1，Dy=Fy时，沿YX路由会遇到故障节点。此时可分为两种情况：

（1）Sx=Fx，先按XY算法传输到（Fx- 1，Fy-1），此后沿XY路由传输。

（2）Sx

由策略二到策略七设计实现了SFPVC 算法，算法流程图描述如图4 所示。

图4 SFPVC 流程图

4 实验比较及分析

4.1 SFPVC 与FTR 和RR 比 较

FTR 算法在（Fx+ 2，Fy- 1）处由东向北转弯时需要先到达（Fx+ 1，Fy+ 1）处再按XY算法路由，若数据包的目的节点为（Fx+ 1，Fy），则比最短路径多两跳。N×N规模的网络中，若1

如图5 所示，数据包源节点为S1，目的节点为D1，此后均表示为S1→D1，FTR 算法先沿XY算法路由在到达故障点左邻接点时开始绕行直到当前节点与目的节点的X坐标相等，而本文直接以YX算法路由，在故障节点处避免了绕行。如图5 中的S2→D2，FTR 算法由于要避免死锁禁止在（Fx+1，Fy- 1）处由东向北转向，因此数据包传输距离较长，而本文算法的传输路径较短。当时S3→D3时，FTR 允许了（Fx+ 2，Fy+ 1）处的由北向西的转弯，因此先把数据包传输到（Fx+2，Fy+ 1）再以XY路由传输；RR 算法由于没有提前预测，因此当数据包发送到（Fx，Fy- 1）时检测到北方向有故障节点，因此只能沿故障点周围绕行至（Fx，Fy+ 1）处再向北发送；而本文的转向模型路径更多，因此本文算法将数据包传输到Fx+ 2 列再以YX算法路由，比起FTR 传输固定的某一点，本文传输路径更为多样，相比于RR 算法，本文算法减少数据包传输距离，且减轻故障节点周围的负载。

图5 部分数据传输路径对比

4.2 静态仿真

为了比较三种算法的网络时延，首先要分析在路由算法层面影响网络时延的两大要素，分别为：数据包从源节点到目的节点的路由的平均长度和网络拥塞程度。为此引入均值μ和方差σ2，其计算如式（1）和式（2）所示。本小节在网络规模为6×6 和8×8 网络中随机选择4 个故障节点进行实验，共有不重复的源-目的节点对1 225、3 969 对（除去包含故障节点的源-目的节点对），统计每个路由器节点被经过的次数，得到6×6 和8×8 的矩阵，代入式（1）和式（2），算出μ和σ2，如表1 和表2 所示。在网络规模为6×6 时对比FTR 和RR，μ平均减少了0.13%和1.74%，σ2平均减少了8.83%和17.48%；在网络规模为8×8时对比FTR 和RR，μ平均减少了0.03%和1.21%，σ2平均减少了8.71%和15.06%。

表1 6×6均值方差对比

表2 8×8 均值方差对比

为了更直观地看出三种算法的负载均衡情况，将上文中的矩阵以图的形式展现，得到三种算法的流量分布图，如图6 所示，这里以8×8 故障节点为（5，5）举例。图6（c）所示相比于图6（a）和图6（b），本文算法改善了在故障节点的周围形成拥塞情况，因而表现为方差σ2的减少。

图6 流量分布图

4.3 动态仿真

为了进一步地评估三种算法的性能，采用一种精确周期的NoC 模拟器Booksim 2.0[15]，仿真分别在6×6 和8×8 网络中进行，故障点的选取与上一节保持一致，每条链路的缓存大小为8 flits，数据包长度为2 flits，采用uniform 流量模型，模拟器预热了1 000 个周期，在另外3 000 个周期中测量其性能。本小节以饱和注入率η作为评价指标，随着注入率的增大，网络进入饱和的越晚则η越大，说明其网络性能越好。图7 和图8 给出了三种算法在不同网络规模、不同故障点的网络时延和注入率的关系曲线。得益于上文中均值和方差的优化，使得本文算法比RR 和FTR更晚进入网络饱和状态，随着网络规模的增大，本文数据传输路径多样的特点将愈发明显，为了更精确说明，表3 和表4 给出了三种算法的饱和注入率η，在网络规模为6×6 时对比FTR 和RR 平均提高了12.02%和28.81%，在8×8 时对比FTR 和RR 平均提高了18.92%和39.42%。

图8 8×8 网络算法网络时延对比

表3 6×6饱和注入率对比η

表4 8×8饱和注入率对比η

5 结论

本文通过对故障位置预测使得数据包尽可能在不使用虚通道的情况下以最小路径传输，并且减少在故障节点周围绕行降低故障节点周围的负载，针对RR 算法绕行路径单一的问题做出了改进，采用多种容错策略，使得网络负载更加均衡，针对FTR 算法在为了避免死锁增加了绕行距离的问题上做出了优化，减少了部分数据包的传输距离。