负载均衡的2D Mesh单节点故障容错路由算法.pdf
《负载均衡的2D Mesh单节点故障容错路由算法.pdf》由会员分享,可在线阅读,更多相关《负载均衡的2D Mesh单节点故障容错路由算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、长春理工大学学报(自然科学版)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
2、,李抗1(1.安徽工程大学计算机与信息学院,芜湖241000;2.安徽工程大学电气工程学院,芜湖241000)摘要:单故障节点 2D Mesh 环路故障绕行常常会导致数据传输负载和网络时延增大,针对这一问题,提出一种单节点故障预测无虚通道容错路由算法。该算法首先基于内建自测试机制获取故障节点的坐标信息;然后根据源节点、目标节点和故障节点的相对位置分别采用不同的路由策略进行数据传输,并且数据传输具有无死锁的特性。基于88 的 2D Mesh 网络,实验结果表明,相比较可重构路由算法,新算法的饱和注入率提高了 39.42%;相比较容错路由算法,新算法的饱和注入率提高了 18.92%。在网络负载均衡
3、、减少端到端传输距离和网络时延方面,单节点故障预测无虚通道算法具有可行性。关键词:负载均衡;单节点故障;容错路由;无虚通道;饱和注入率中图分类号: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
4、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 t
5、ransmission 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 tra
6、nsmission,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 satu
7、ration 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随着可重构多核处理器的进一步发展,其编译映射工具片上数据传
8、输的容错显得越来越重要1,片上网络数据传输拥塞或路由器故障导致可重构多核系统之间的数据传输时延显著增加,韩承浩,等:负载均衡的2D Mesh单节点故障容错路由算法目前针对片上网络(network-on-chip,NoC)节点故障国内外学者大多采用路由容错等解决方法。一般而言,片上网络数据传输的容错机制大多从网络传输层找到可以替代的传输路径来避开故障节点位置,因为要改变 NoC 原有的数据传输路径,所以需要解决网络死锁的问题,根据不同的 解 决 网 络 死 锁 的 方 法,被 分 为 有 虚 通 道 路由2-3和无虚通道路由。有虚通道路由将物理信道分为几个逻辑信道,通过切换不同的逻辑信道,来避免
9、信道之间的相互依赖,从而解决死锁问题,然而这样就使得路由节点的逻辑门个数增大,功耗增大。无虚通道路由算法大多采用转向模型来避免死锁,通过禁止一定数量的转向,避免信道之间形成环形依赖4。由于有虚通道路由需要消耗额外的硬件达到容错的目的,而无虚通道路由主要依赖在故障节点周围的链路绕行来避开故障节点以达到容错的目的。1 相关工作关于故障预测的 2D Mesh 单故障节点的无虚通道容错路由相关工作阐述可分为故障位置的检测和无虚通道容错路由算法。1.1故障位置的检测对于故障位置的检测主要依赖于内建自测技术(Built-in Self Test,BIST),将外部检测的工具集成到电路内部,实现对故障类型、
10、故障位置的诊断。Biswajit 等人5提出了一种面向在线分布式内建自测试的测试机制,该机制专门检测通信链路上的开放故障,并从 NoC 中识别故障链路。随后,提出一种合适的容错策略。内建自测试是实现高可靠性的主要测试方案之一。该方案可对 NoC 的基本组件进行故障测试和恢复。Bhowmik 等人6提出了一种检测通信介质中短路故障的内建自测试方法,提高了 NoC 的产量和性能。1.2无虚通道容错路由算法Zhang 等人7提出 RR 算法在无故障时采用XY 路由算法,当有故障节点在网络非边界区域时将故障节点相邻的四个节点,以及间接的四个 顶 点 组 成 绕 行 环 路,在 绕 行 环 路 的 东
11、北 角(SW,ES)禁止转向,来避免死锁,因此当故障节点出现在网络中心区域时由于需要考虑避免死锁,导致了某些数据包的长距离绕行,绕行环路负载不均衡等问题。针对此问题,姚磊等人8提出了 FTR 算法对 RR 算法进行了改进,对 RR 算法中在绕行环路的东北角无法转向的数据包,在东北角节点的右邻接节点定义为辅助拐点允许数据包由北向西转向。Xie 等人9提出了一种具 有 一 定 容 错 能 力 的 转 向 模 型(Fault-TolerantOdd-Even,FTOE),使得数据包有更多的路径进行传输,从而避开故障节点,可以被用于单故障节点容错,有较好的效果。Bahrebar 等人10利用算珠转向模
12、型提出一种可重构无死锁路由方法,通过对算珠的动态调整,赋予数据包高度的适应性。谢瑞莲等人11提出一种低开销的无虚通道隔离路由算法,根据凸故障模型的思想划分不规则区域,利用不规则区域的边界传输数据包,来达到容错的目的。Rahaman 等人12提出无 死 锁 的 自 适 应 容 错 NoC 路 由(F-Route-NoC-Mesh,FRNM),该 方 法 将 NoC 中 的 多 个 故 障 节点,构造成一个正交凸形故障区域,通过自适应路由算法来绕过这个区域,实现容错。路由算法通过当前数据包的位置和目的节点的位置来作出不同的路由策略。通过转向模型来避免死锁,没有使用虚通道。通过虚拟故障块边界路由数据
13、包来平衡流量,减小故障区域负载,通过实验表明网络平均时延、平均吞吐量和功耗均有改善。Sayed 等人13提出一种拥塞感知、容错和过程变化感知的自适应路由算法(CFPA),在每个路由器上都有一个路由表,以跟踪所有路由器的排队延迟。在路由决策中考虑到排队延迟,使路由器有能力通过非拥挤路径向目的地转发数据信息。CFPA 通过对数据包路由进行优先排序来避免死锁。因此,长路径的数据包比短路径的数据包有更高的优先权。CFPA 将 NoC韩承浩,等:负载均衡的2D Mesh单节点故障容错路由算法第2期129长春理工大学学报(自然科学版)2023年的吞吐量提高 60%,使用 CFPA,故障对 NoC 吞吐量的
14、影响减轻了 48%,减少了网络时延。通过对上述文献的研究发现,相关路由算法存在数据包传输距离长、网络负载不均衡等问题。本文对此展开深入研究,其研究方案列举如下:(1)设计一种基于全局容错的转向模型,提出 一 种 单 节 点 故 障 预 测 无 虚 通 道(Single-nodeFault Prediction without Virtual Channels,SFPVC)路由算法。(2)利用内建自测机制在X方向和Y方向作出预测,避免数据包垂直或水平方向进入绕行环路,减轻故障节点周围负载,减少数据包传输距离。2问题定义定义 1:节点坐标。方向约定X+方向为东,X-方向为西,Y+方向为北,Y-方向
15、为南;节点类型符号可表示为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 表示由
16、东向北转向,SW 表示由南向西转向,具体如图 2(a)所示,图 2(b)表示非法转向。(a)合法转向(b)非法转向图 2节点数据传输转向模型示意图定义 4:死锁。在片上网络路由数据传输过程中出现的一种现象,即多个数据包在传输路径形成了无虚通道打结环路,这种现象称为死锁。死锁可以通过设计路由算法和数据流控制协议来避免,本文通过设计合理的路由算法避免死锁。定义 5:容错路由评价指标。本文约定容错路由算法只对片上网络的时延进行评估,评价指标具体可分为静态仿真14指标均值和方差2,动态仿真指标饱和注入率。具体说明如下:均值是数据包在每个路由器上被途经的平均次数,均值越大则说明数据包传输距离越长,方差是
17、每个路由器上被途经的次数的方差,方差反映了网络中的负载均衡情况,方差大则说明网络中某些区域负载过大,容易在该区域形成网络拥塞。均值和方差计算方法与文献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_cy
18、cle表示第一个头微片进入网络到最后一个微片尾离开网络的时间;LENi表示Ttotal_cycle时钟周期内成功到达目的节点的第i个数据包的长度,n表示所有到达目的节点的数据包个数,数据包长度单位为 filts。=i=1nLENiNtotal_node Ttotal_cycle(3)本文规定随着注入率的增大,当网络时延为零负载时延的两倍时所对应的注入率记为饱和注入率。3实验动机和容错路由算法设计3.1实验动机目前的故障节点绕行法,大多是先沿着正常路由传输,当检测到下一跳节点为故障节点时,才做出容错的策略,或者是将故障节点坐标存储在部分正常节点的故障存储器中,当数据包到达这些节点时,可以读取故障
19、信息,从而作出容错策略。这样会使传输路径单一,部分数据包绕行距离过大等问题,本文提出一种单节点故障预测无虚通道路由算法,使数据包从第一跳就可以判断是否需要容错,以及采用何种容错策略,这样做可以提前容错,在尽可能追求传输路径最小的情况下,保证了传输路径多样性。使得负载平衡,降低网络时延。3.2容错路由算法设计策略一:转向模型。本文是一种全局容错路由算法,就需要一种数据传输路径多样的转向模型,因此本文提出一种基于全局容错的无死锁转向模型(如图 3 所示),对比 RR 的转向模型和 FTR 的转向模型,本文采用的转向模型禁止的转向少,使得数据传输路径更为多样。策 略 二:X正 方 向 绕 行。当 1
20、SxFx且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 F
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 负载均衡的2D Mesh单节点故障容错路由算法 负载 均衡 Mesh 节点 故障 容错 路由 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。