电子学报 ›› 2016, Vol. 44 ›› Issue (4): 920-925.DOI: 10.3969/j.issn.0372-2112.2016.04.024

• 学术论文 • 上一篇    下一篇

针对路径故障与局部拥塞的NoC容错路由算法

欧阳一鸣1, 何鑫城1, 梁华国2, 易茂祥2, 杜高明2, 安鑫1   

  1. 1. 合肥工业大学计算机与信息学院, 安徽合肥 230009;
    2. 合肥工业大学电子科学与应用物理学院, 安徽合肥 230009
  • 收稿日期:2014-11-15 修回日期:2015-11-23 出版日期:2016-04-25 发布日期:2016-04-25
  • 作者简介:欧阳一鸣 男,1963年生,博士,教授,中国计算机学会高级会员,研究方向:片上网络(NoC)与片上系统(SoC)、嵌入式系统的综合与测试、数字系统设计自动化. E-mail:oyymbox@163.com;何鑫城 女,1990年生,硕士研究生,研究方向:片上系统以及片上网络容错方法. E-mail:372521359@qq.com
  • 基金资助:

    国家自然科学基金(No.61474036,No.61274036,No.61371025);安徽省自然科学基金(No.1508085MF117)

A Fault-Tolerant Routing Algorithm Aiming at a Path Fault and Local Congestion in NoC

OUYANG Yi-ming1, HE Xin-cheng1, LIANG Hua-guo2, YI Mao-xiang2, DU Gao-ming2, AN Xin1   

  1. 1. School of Computer and Information, Hefei University of Technology, Hefei, Anhui 230009, China;
    2. School of Electronic Science & Applied Physics, Hefei University of Technology, Hefei, Anhui 230009, China
  • Received:2014-11-15 Revised:2015-11-23 Online:2016-04-25 Published:2016-04-25

摘要:

片上网络作为一种新型片上互连架构,克服了片上系统在发展中遭遇的瓶颈问题.然而,片上网络中的路由器故障以及路由器之间的链路故障都会造成网络性能损失.对此,文章提出一种针对路径故障与局部拥塞的NoC容错路由算法.首先,设计了一种相隔节点间路径故障模型,该模型下的路由器以较小的开销为代价,动态感知两跳以内的路径故障状态.其次,提出了一种新颖的更能准确反映局部网络拥塞状态的拥塞模型来均衡网络流量.最后,当网络无故障时,算法保证走最优路径;有故障时,算法不仅可以实现容错还能保证网络具有良好的性能.实验表明,在无故障的情况下,本文方案相较于对比对象延迟降低了10%~20%,吞吐率提高了25%左右.在有故障的情况下,本文方案较对比对象的优势更加明显.

关键词: 片上网络, 故障模型, 拥塞模型, 容错路由算法

Abstract:

As a new type of on-chip interconnection architecture,network-on-chip overcomes the bottleneck problem of the system-on-chip during the development.However,a failure arising in a router or a link between routers in network-on-chip will cause the reduction of network performance.To avoid this phenomenon,this paper puts forward a fault-tolerant routing algorithm aiming at a path fault and local congestion in network-on-chip.Firstly,the algorithm designs a fault model that reflects the fault status of the path within two hops.As a result,this novel fault model makes the router achieve a dynamic perception of path state within two hops with less cost.Secondly,a novel congestion model has been proposed for reflecting the state of the local network more accurately,contributing to balance network traffic.Finally,when a fault occurs,the algorithm not only is fault-tolerant but also makes sure the network has a good performance.What's more,the algorithm chooses the optimal path under the condition of fault-free.Experimental results show that the proposed algorithm has 10%~20% lower latency in average and 25% higher throughput rate than the contrast case when the network is fault-free.In the case of defective in the network,the advantage of the present scheme has a bigger superiority.

Key words: network-on-chip, fault model, congestion model, fault-tolerant routing algorithm

中图分类号: