负载均衡的2D Mesh单节点故障容错路由算法.pdf

长春理工大学学报（自然科学版）Journal of Changchun University of Science and Technology（Natural Science Edition）Vol.46No.2Apr.2023第46卷第2期2023年4月收稿日期：2022-08-23基金项目：国家自然科学基金重点项目（61432017）；安徽省自然科学基金面上项目（1808085MF203）作者简介：韩承浩（1998-），男，硕士研究生，E-mail：通讯作者：陈乃金（1972-），男，博士，教授，E-mail：负载均衡的 2D Mesh 单节点故障容错路由算法韩承浩1，陈乃金1，胡宇杨2，李抗1（1.安徽工程大学计算机与信息学院，芜湖241000；2.安徽工程大学电气工程学院，芜湖241000）摘要：单故障节点 2D Mesh 环路故障绕行常常会导致数据传输负载和网络时延增大，针对这一问题，提出一种单节点故障预测无虚通道容错路由算法。该算法首先基于内建自测试机制获取故障节点的坐标信息；然后根据源节点、目标节点和故障节点的相对位置分别采用不同的路由策略进行数据传输，并且数据传输具有无死锁的特性。基于88 的 2D Mesh 网络，实验结果表明，相比较可重构路由算法，新算法的饱和注入率提高了 39.42%；相比较容错路由算法，新算法的饱和注入率提高了 18.92%。在网络负载均衡、减少端到端传输距离和网络时延方面，单节点故障预测无虚通道算法具有可行性。关键词：负载均衡；单节点故障；容错路由；无虚通道；饱和注入率中图分类号：TP302文献标志码：A文章编号：1672-9870（2023）02-0128-08Fault Tolerant Routing Algorithm for2D Mesh Single Node Failure with Load BalancingHAN Chenghao1，CHEN Naijin1，HU Yuyang2，LI Kang1（1.School of Computer and Information，Anhui Polytechnic University，Wuhu 241000；2.School of Electrical Engineering，Anhui Polytechnic University，Wuhu 241000）Abstract：A single-node fault prediction without virtual channels（SFPVC）fault-tolerant routing algorithm is presented tosolve the problem that 2D Mesh loop fault bypass often results in increased data transmission load and network latency.Firstly，SFPVC gets the coordinate information of the fault node based on the built-in self-test（BIST）mechanism.Then，according to the relative positions of the source node，the destination node and the fault node，different routing strategies areadopted for data transmission，and the data transmission has the characteristics of no deadlock.In view of the 88 2D Meshnetwork，compared with the reconfigurable routing（RR），the experimental results show that the saturation injection rate ofSFPVC increased by 39.42%.Compared with the fault-tolerant routing（FTR），the saturation injection rate of SFPVCincreased by 18.92%.Thus，the SFPVC is feasible in load balancing，the distance of point-to-point transmission and networklatency.Key words：load balance；single-node fault；fault-tolerant routing；without virtual channel；saturation injection rate随着可重构多核处理器的进一步发展，其编译映射工具片上数据传输的容错显得越来越重要1，片上网络数据传输拥塞或路由器故障导致可重构多核系统之间的数据传输时延显著增加，韩承浩，等：负载均衡的2D Mesh单节点故障容错路由算法目前针对片上网络（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-TolerantOdd-Even，FTOE），使得数据包有更多的路径进行传输，从而避开故障节点，可以被用于单故障节点容错，有较好的效果。Bahrebar 等人10利用算珠转向模型提出一种可重构无死锁路由方法，通过对算珠的动态调整，赋予数据包高度的适应性。谢瑞莲等人11提出一种低开销的无虚通道隔离路由算法，根据凸故障模型的思想划分不规则区域，利用不规则区域的边界传输数据包，来达到容错的目的。Rahaman 等人12提出无 死 锁 的 自 适 应 容 错 NoC 路 由（F-Route-NoC-Mesh，FRNM），该 方 法 将 NoC 中 的 多 个 故 障 节点，构造成一个正交凸形故障区域，通过自适应路由算法来绕过这个区域，实现容错。路由算法通过当前数据包的位置和目的节点的位置来作出不同的路由策略。通过转向模型来避免死锁，没有使用虚通道。通过虚拟故障块边界路由数据包来平衡流量，减小故障区域负载，通过实验表明网络平均时延、平均吞吐量和功耗均有改善。Sayed 等人13提出一种拥塞感知、容错和过程变化感知的自适应路由算法（CFPA），在每个路由器上都有一个路由表，以跟踪所有路由器的排队延迟。在路由决策中考虑到排队延迟，使路由器有能力通过非拥挤路径向目的地转发数据信息。CFPA 通过对数据包路由进行优先排序来避免死锁。因此，长路径的数据包比短路径的数据包有更高的优先权。CFPA 将 NoC韩承浩，等：负载均衡的2D Mesh单节点故障容错路由算法第2期129长春理工大学学报（自然科学版）2023年的吞吐量提高 60%，使用 CFPA，故障对 NoC 吞吐量的影响减轻了 48%，减少了网络时延。通过对上述文献的研究发现，相关路由算法存在数据包传输距离长、网络负载不均衡等问题。本文对此展开深入研究，其研究方案列举如下：（1）设计一种基于全局容错的转向模型，提出 一 种 单 节 点 故 障 预 测 无 虚 通 道（Single-nodeFault 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）表示非法转向。（a）合法转向（b）非法转向图 2节点数据传输转向模型示意图定义 4：死锁。在片上网络路由数据传输过程中出现的一种现象，即多个数据包在传输路径形成了无虚通道打结环路，这种现象称为死锁。死锁可以通过设计路由算法和数据流控制协议来避免，本文通过设计合理的路由算法避免死锁。定义 5：容错路由评价指标。本文约定容错路由算法只对片上网络的时延进行评估，评价指标具体可分为静态仿真14指标均值和方差2，动态仿真指标饱和注入率。具体说明如下：均值是数据包在每个路由器上被途经的平均次数，均值越大则说明数据包传输距离越长，方差是每个路由器上被途经的次数的方差，方差反映了网络中的负载均衡情况，方差大则说明网络中某些区域负载过大，容易在该区域形成网络拥塞。均值和方差计算方法与文献8一致，具体公式如式（1）和式（2）所示。=E aij（1）2=E i,j(aij-)2（2）式中，aij表示矩阵A中的一元素。具体计算方法如下：把N N的 NoC 中所有不重复的源-目的节点按照当前路由算法只发送一个数据包，然后在每个节点nij（1iN，1jN）处统计途经该节点的数据包个数aij，最终得到一个N N矩阵130A=（aij）。注入率表示网络在单位时间内可处理的数据包个数，Ntotal_node表示网络中节点总数；Ttotal_cycle表示第一个头微片进入网络到最后一个微片尾离开网络的时间；LENi表示Ttotal_cycle时钟周期内成功到达目的节点的第i个数据包的长度，n表示所有到达目的节点的数据包个数，数据包长度单位为 filts。=i=1nLENiNtotal_node Ttotal_cycle（3）本文规定随着注入率的增大，当网络时延为零负载时延的两倍时所对应的注入率记为饱和注入率。3实验动机和容错路由算法设计3.1实验动机目前的故障节点绕行法，大多是先沿着正常路由传输，当检测到下一跳节点为故障节点时，才做出容错的策略，或者是将故障节点坐标存储在部分正常节点的故障存储器中，当数据包到达这些节点时，可以读取故障信息，从而作出容错策略。这样会使传输路径单一，部分数据包绕行距离过大等问题，本文提出一种单节点故障预测无虚通道路由算法，使数据包从第一跳就可以判断是否需要容错，以及采用何种容错策略，这样做可以提前容错，在尽可能追求传输路径最小的情况下，保证了传输路径多样性。使得负载平衡，降低网络时延。3.2容错路由算法设计策略一：转向模型。本文是一种全局容错路由算法，就需要一种数据传输路径多样的转向模型，因此本文提出一种基于全局容错的无死锁转向模型（如图 3 所示），对比 RR 的转向模型和 FTR 的转向模型，本文采用的转向模型禁止的转向少，使得数据传输路径更为多样。策 略 二：X正 方 向 绕 行。当 1SxFx且Sy=Fy时，此时分为三种情况：（1）当Fx Dx N且Dy=Fy时，若Fx+2=Dx，第一跳向北发送数据包，否则向南，此后沿XY路由传输。（2）当Fx Dx N且Dy Fy时，若Fx+2=Dx沿YX路由传输到（Fx+1，Fy+1），此后沿YX路由传输，否则第一跳向北发送数据包，此后沿XY路由传输。图 3容错转向模型策 略 三：X负 方 向 绕 行。当Fx Sx N且Sy=Fy，此时分为三种情况：（1）当1 DxFx且Dy=Fy时，若Fx+1=Sx，第一跳向南发送数据包此后沿XY路由传输，否则沿XY路由发送到（Fx+2，Fy+1），此后沿XY路由传输。（2）当1 Dx Fx且Dy Fy时，若Fx+1=Sx先以YX路由传输到（Fx-1，Fy-1），再向北传输到（Fx-1，Fy+1），最后以XY算法传输，否则向西发送至（Fx+1，Fy）此后沿YX路由传输。策 略 四：Y正 方 向 绕 行。当Fy Dy N且Dx=Fx，此时分为三种情况：（1）当1 Sy Fy且Sx Fx时，向北发送至Fy+1行，再沿XY路由传输。（2）当1 Sy Fy且Fx-1 Sx Fx+2时，先向西发送至Fx-1列，再向北发送至Fy+1行，韩承浩，等：负载均衡的2D Mesh单节点故障容错路由算法第2期131长春理工大学学报（自然科学版）2023年最后沿XY路由传输。（3）当1 Sy Fx+1时，向西发送至Fx+1列，再沿YX路由传输。策 略 五：Y负 方 向 绕 行。当1 Dy Fy且Dx=Fx时，此时分为三种情况：（1）当Fy Sy N且Sx Fx时，按YX路由传输。（2）当Fy Sy N且Sx=Fx时，第一跳向西发送数据包，再按YX路由传输。（3）当Fy Fx时，先向西发送至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 Fx，向南发送至Fx-1再按XY路由传输。由策略二到策略七设计实现了 SFPVC 算法，算法流程图描述如图 4 所示。4实验比较及分析4.1SFPVC 与 FTR 和 RR 比较FTR 算法在（Fx+2，Fy-1）处由东向北转弯时需要先到达（Fx+1，Fy+1）处再按XY算法路由，若数据包的目的节点为（Fx+1，Fy），则比最短路径多两跳。N N规模的网络中，若 1 FxN-1，并且存在m个数据包的源节点满足Dx=Fx+1，Dy=Fx，则本文的均值相比于 FTR 会减少 2m/N2。由于 FTR 算法和 RR 算法在数据包到达故障节点周围的环路开始做出容错，本文在数据包第一跳之前做出容错，因此在数据包传输路径上本文算法更为多样。图 4SFPVC 流程图图 5部分数据传输路径对比如图 5 所示，数据包源节点为S1，目的节点为D1，此后均表示为S1D1，FTR 算法先沿XY算法路由在到达故障点左邻接点时开始绕行直到当前节点与目的节点的X坐标相等，而本文直接以YX算法路由，在故障节点处避免了绕行。如图 5 中的S2D2，FTR 算法由于要避免死锁禁止在（Fx+1，Fy-1）处由东向北转向，因此数据包传输距离较长，而本文算法的传输路径较短。当时S3D3时，FTR 允许了（Fx+2，Fy+1）处的由北向西的转弯，因此先把数据包传输到（Fx+2，Fy+1）再以XY路由传输；RR 算法由于没有提132前预测，因此当数据包发送到（Fx，Fy-1）时检测到北方向有故障节点，因此只能沿故障点周围绕行至（Fx，Fy+1）处再向北发送；而本文的转向模型路径更多，因此本文算法将数据包传输到Fx+2列再以YX算法路由，比起 FTR 传输固定的某一点，本文传输路径更为多样，相比于RR 算法，本文算法减少数据包传输距离，且减轻故障节点周围的负载。4.2静态仿真为了比较三种算法的网络时延，首先要分析在路由算法层面影响网络时延的两大要素，分别为：数据包从源节点到目的节点的路由的平均长度和网络拥塞程度。为此引入均值和方差2，其计算如式（1）和式（2）所示。本小节在网络规模为 66 和 88 网络中随机选择 4 个故障节点进行实验，共有不重复的源-目的节点对1 225、3 969 对（除去包含故障节点的源-目的节点对），统计每个路由器节点被经过的次数，得到 66 和 88 的矩阵，代入式（1）和式（2），算出和2，如表 1 和表 2 所示。在网络规模为 66 时对比 FTR 和 RR，平均减少了 0.13%和 1.74%，2平均减少了 8.83%和 17.48%；在网络规模为 88时对比 FTR 和 RR，平均减少了 0.03%和 1.21%，2平均减少了 8.71%和 15.06%。为了更直观地看出三种算法的负载均衡情况，将上文中的矩阵以图的形式展现，得到三种算法的流量分布图，如图 6 所示，这里以 88 故障节点为（5，5）举例。图 6（c）所示相比于图 6（a）和图 6（b），本文算法改善了在故障节点的周围形成拥塞情况，因而表现为方差2的减少。表166均值方差对比66网络故障节点坐标66故障点（3，4）66故障点（2，4）66故障点（3，3）66故障点（4，3）平均SFPVC171.50170.44171.67171.89171.38FTR171.72170.61171.89172.17171.60RR174.33173.50175.11174.67174.40/%-0.13-0.10-0.13-0.16-0.13-1.62-1.76-1.96-1.59-1.742SFPVC3 182.972 927.803 216.503 575.773 225.76FTR3 572.533 109.853 680.323 802.083 541.20RR4 237.943 208.314 023.994 267.563 934.45/%-10.90-5.85-12.60-5.90-8.83-24.89-8.74-20.07-16.21-17.48表 288 均值方差对比88网络故障节点坐标88故障点（5，5）88故障点（3，5）88故障点（4，4）88故障点（7，5）平均SFPVC393.75392.86393.75392.13393.12FTR393.94393.00393.91392.13393.25RR398.50398.19399.47395.56397.93/%-0.05-0.04-0.040.00-0.03-1.19-1.34-1.43-0.87-1.212SFPVC16 568.6915 301.3016 031.6016 418.2016 079.95FTR17 858.7016 738.0018 030.1017 834.6017 615.35RR20 658.5017 845.9019 624.7017 819.8018 987.23/%-7.22-8.58-11.08-7.94-8.71-19.80-14.26-18.31-7.87-15.06（a）RR（b）FTR（c）SFPVC图 6流量分布图韩承浩，等：负载均衡的2D Mesh单节点故障容错路由算法第2期133长春理工大学学报（自然科学版）2023年4.3动态仿真为了进一步地评估三种算法的性能，采用一种精确周期的 NoC 模拟器 Booksim 2.015，仿真分别在 66 和 88 网络中进行，故障点的选取与上一节保持一致，每条链路的缓存大小为 8 flits，数据包长度为 2 flits，采用 uniform 流量模型，模拟器预热了 1 000 个周期，在另外 3 000 个周期中测量其性能。本小节以饱和注入率作为评价指标，随着注入率的增大，网络进入饱和的越晚则越大，说明其网络性能越好。图 7 和图 8 给出了三种算法在不同网络规模、不同故障点的网络时延和注入率的关系曲线。得益于上文中均值和方差的优化，使得本文算法比 RR 和 FTR更晚进入网络饱和状态，随着网络规模的增大，本文数据传输路径多样的特点将愈发明显，为了更精确说明，表 3 和表 4 给出了三种算法的饱和注入率，在网络规模为 66 时对比 FTR 和 RR 平均提高了 12.02%和 28.81%，在 88 时对比 FTR 和RR平均提高了18.92%和39.42%。（a）故障点（2，4）和（4，3）（b）故障点（3，3）和（3，4）图 766 网络算法网络时延对比（a）故障点（3，5）和（4，4）（b）故障点（5，5）和（7，5）图 888 网络算法网络时延对比表366饱和注入率对比66网络故障节点坐标66故障点（3，4）66故障点（2，4）66故障点（3，3）66故障点（4，3）平均SFPVC0.058 80.061 50.055 30.055 00.058 0FTR0.049 80.054 70.051 40.050 00.051 0RR0.044 80.049 90.042 20.042 40.045 0/%18.0712.437.5910.0012.0231.2523.2531.0429.7228.81表488饱和注入率对比88网络故障节点坐标88故障点（5，5）88故障点（3，5）88故障点（4，4）88故障点（7，5）平均SFPVC0.044 00.046 30.043 40.052 30.047 0FTR0.038 00.039 30.039 00.040 00.039 0RR0.031 50.034 00.030 50.037 50.033 0/%15.7917.8111.3330.7518.9239.6836.1842.3639.4739.425结论本文通过对故障位置预测使得数据包尽可能在不使用虚通道的情况下以最小路径传输，并且减少在故障节点周围绕行降低故障节点周围的负载，针对 RR 算法绕行路径单一的问题做134出了改进，采用多种容错策略，使得网络负载更加均衡，针对 FTR 算法在为了避免死锁增加了绕行距离的问题上做出了优化，减少了部分数据包的传输距离。参考文献1CHEN N J，WANG Z，HE R X，et al.Efficient scheduling mapping algorithm for row parallel coarse-grainedreconfigurable architectureJ.Tsinghua Science andTechnology，2021，26（5）：724-735.2CHARIF A，COELHO A，ZERGAINOH N，et al.a dynamic sufficient condition of deadlock freedom for high-performance fault-tolerant routing in networks-on-chipsJ.IEEE Transactions on Emerging Topics in Computing，2020，8（3）：642-654.3 IPEK A，TOSUN S，OZDEMIR S.HAFT a：highly adaptive fault-tolerant routing algorithm for two-dimensionalnetwork-on-chips J .Concurrency Computation-PracticeExperience，2021，33（21）：e6378-1-9.4GLASS C J，NI L M.The turn model for adaptive routing J.Journal of the Acm，1992（5）：278-287.5BISWAJIT B.Maximal connectivity test with channel-open faults in on-chip communication networksJ.Journal of Electronic Testing.Theory and Applications，2020，36（3）：385-408.6BHOWMIK B，DEKA J K，BISWAS S.Selective fault-masking for improving yield and performance of on-chip networksC.Australia：2021 IEEE InternationalConference on Systems，Man and Cybernetics（SMC），2021.7ZHANG Z，GREINER A，TAKTAK S.A reconfigurableroutingalgorithmforafault-tolerant2D-MeshNetwork-on-ChipC.Anaheim：2008 45th ACM/IEEEDesign Automation Conference，2008.8姚磊，蔡觉平，李赞，等.2D-Mesh 结构片上网络无虚通道容错路由算法J.西安电子科技大学学报，2012，39（6）：26-33.9 XIE R L，CAI J P，XIN X，et al.LBFT：a fault-tolerantrouting algorithm for load-balancing network-on-chipbased on odd-even turn modelJ.Journal of Supercomputing，2018，74（8）：37263747.10 BAHREBAR P，STROOBANDT D.Abacus turn model-based NoC routing for interconnects with switch or linkfailures J.Microprocessors&Microsystems，2018，59（6）：69-91.11 谢瑞莲，焦继业，刘有耀.片上网络无虚通道隔离路由算法J.计算机辅助设计与图形学学报，2021，33（5）：806-814.12RAHAMAN M M，GHOSAL P，DAS T S.Latency，throughput and power aware adaptive NoC routing onorthogonal convex faulty region J.Journal of Circuits，Systems，and Computers，2019，28（4）：1-21.13SAYED T M，MOHAMED S，ALI A E，et al.CFPA：Congestion aware，fault tolerant and process variationawareadaptiveroutingalgorithmforasynchronousNetworks-on-Chip J.Journal of Parallel and Distributed Computing，2019，128（2019）：151-166.14LIN S Y，HUANG C，CHAO C，et al.Traffic-balanced routing algorithm for irregular mesh-basedon-chip networksJ.IEEE Trans on Computers，2008，57（9）：1156-1168.15NAN J，BECKER D U，MICHELOGIANNAKIS G，etal.A detailed and flexible cycle-accurate Network-on-Chip simulatorC.Austin：IEEE International Symposium on Performance Analysis of Systems and Software（ISPASS 2013），2013.韩承浩，等：负载均衡的2D Mesh单节点故障容错路由算法第2期135