收稿日期:20141223;修回日期:20150518 基金项目:国家自然科学基金资助项目(61401095/F0103)
作者简介:龚健虎(1967),男,广西桂林人,讲师,博士,主要研究方向为无线传感网、片上网络(18673113650@qq.com);王闻今(1979),男,
副教授,博士,主要研究方向为无线传感网、移动计算.
片上网络中面向链路故障的容错路由方法研究
龚健虎
1
,王闻今
2
(1.广东培正学院 计算机科学与工程系,广州 510800;2.东南大学 信息科学与工程学院,南京 210018)
摘 要:针对片上网络中传统的容错路由算法的高报文延时和故障区域拥塞等不足,利用两个虚拟信道提出一
种新的容错路由方法。该方法通过确定每个虚拟信道哪些转向被允许和禁止,使得一个虚拟信道中被禁止的转
向在另一信道被允许。当发生链路故障时,该方法基于一种新的故障信息传播机制使报文在最短路径上传输;
通过充分利用网络中的所有被允许转向对该方法进行扩展,以支持多链路故障。最后的仿真实验也验证了该方
法的有效性。
关键词:片上网络;链路故障;容错路由;最短路径;被允许转向
中图分类号:TN91502 文献标志码:A 文章编号:10013695(2016)05141504
doi:10.3969/j.issn.10013695.2016.05.031
Researchonfaulttolerantroutingmethodforfaultylinksinnetworksonchip
GongJianhu
1
,WangWenjin
2
(1.Dept.ofComputerScience& Engineering,GuangdongPeizhengCollege,Guangzhou510800,China;2.SchoolofInformationScience&
Engineering,SoutheastUniversity,Nanjing210018,China)
Abstract:Inordertosolvetheproblemofhighpacketdelayandcongestionaroundthefaultyregionofthetraditionalfault
tolerantroutingalgorithmsinnetworksonchip,thispaperpresentedafaulttolerantroutingmethodusingtwovirtualchannels.
Themethoddeterminedtheprohibitedandpermittedturnsoneachvirtualchannelinsuchawaythatprohibitedturnsinone
virtualchannelwerepermittedintheotherone.Whenalinkfailureoccured,theproposedmethodbasedonanewfaultinfor
mationdisseminationmechanismmadethepackettransmissionontheshortestpath.Inaddition,themethodwasextendedto
supportmultiplefaultylinksbyfullyutilizingallallowableturnsinthenetwork.Finally,thesimulationalsoverifiestheeffec
tivelyoftheproposedmethod.
Keywords:networksonchip(NoC);faultylinks;faulttolerantrouting;shortestpaths;allowableturns
片上网络(networksonchip,NoC)
[1]
具有可重用性和伸缩
性,已经成为多核片上系统潜在的片上互连解决方案。如果利
用深度亚微米半导体技术进行部署并运行于 GHz时钟频率
上,则片上互连容易发生故障
[2]
。路由技术可使 NoC提供一
定的容错性。路由算法主要分为确定性算法和自适应性算
法
[3~5]
。确定性路由算法为每对节点使用固定路径,导致报文
延时较高,当网络拥塞时更是如此。在自适应算法中,当从源
节点向目的节点传输时报文不是局限于一条路径上,自适应路
由算法采用了替代路径,因此容错性能更高。然而计算合适的
路径会导致硬件开销,当网络拥塞度不高时,自适应路由的延
时较大;同时,动态路由在设计时需要保证避免死锁。
NoC领域传统的容错方法主要是使报文绕过或凸或凹的
故障区域,此时选择的路由路径未必是最短路径。然而迂回策
略的代价较高,会显著增加报文延时及路由器的复杂性。这些
方法之所以效率不高,主要是因为故障组件的信息掌握不够,
或者是这些信息的利用率不高。为此,本文将对可容忍链路故
障的容错路由方法进行研究,以提高片上网络数据传输的可
靠性。
1 相关工作
目前已经有众多学者对片上网络的容错路由问题进行了
研究。文献[
6]提出片上网络监控器的概念,用于获取全局网
络实时状态信息及执行路径分配算法,基于此提出一种动态路
由机制 DyRSNM。该机制能检测和定位 NoC中的拥塞和故障
链路,并能区分瞬时和永久性链路故障,采用重传方式避免瞬
时故障,通过重新路由计算绕开拥塞和永久性故障。相比静态
XY路由和容错动态路由 FADR,DyRSNM机制在可接受的开
销代价下获得了更优的性能。文献[7]提出一种低成本的可
重构路由算法。该算法基于无共享边界的矩形故障模型,按照
故障区与网络边界的相对位置对故障区进行分类,针对不同类
型的故障区定义了具体的路由器状态更新策略。该算法不需
要增加虚拟通道来保证网络的无死锁特性,因此具有低成本、
高可靠的特性。文献[
8]提出一种面向片上网络缓冲资源争
用的路由器设计方案。在该路由器中,当某个输入端繁忙,发
生资源争用情况时,将阻塞数据包分配到其他拥有空闲缓存资
源的输入端口,解决缓冲资源的争用问题,从而提高网络整体
性能。
文献[9]提出迂回策略,该算法可容忍 NoC中的所有单故
障路由器,既无须使用虚拟信道又无须关闭正常节点。为了支
持更多故障路由器,迂回不得重叠,因此故障路由器间的位置
应该较大。当故障数量较少时,该策略效率较高;当故障组件
第 33卷第 5期
2016年 5月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol33No5
May2016