上海交通大学学报

上海交通大学学报（自然版） ›› 2013, Vol. 47 ›› Issue (01): 18-22.

• 无线电电子学、电信技术 • 上一篇    下一篇

一种基于2D-mesh的片上网络无死锁容错路由算法

周磊1,2，吴宁1，李云2   

  1.  （1.南京航空航天大学 电子信息工程学院， 南京 210016；2.扬州大学 信息工程学院， 江苏 扬州 225009）
  • 收稿日期:2012-07-12 出版日期:2013-01-30 发布日期:2013-01-30
  • 基金资助:

    国家自然科学基金项目(61076019),江苏省科技支撑计划项目(BE2010003)资助

A Fault-Tolerant and Deadlock-Free Routing Algorithm in2D-Mesh for Network on Chip

 ZHOU  Lei-1, 2 , WU  Ning-1, LI  Yun-2   

  1. (1. College of Electronic and Information Technology, Nanjing University of Aeronautics and Astronautic, Nanjing 210016, China; 2. College of Information Engineering, Yangzhou University, Yangzhou 225009, Jiangsu, China)
  • Received:2012-07-12 Online:2013-01-30 Published:2013-01-30

摘要： 为解决片上网络中的永久性故障问题，提出一种基于2D-mesh拓扑结构的无死锁容错路由算法.定义了新的故障块生成规则，减小了故障节点的区域和受影响的健康节点数目，设计了一种故障节点探测和绕道路径生成算法，通过递归式消息传递实现了故障块区域的建立和绕道路径列表的生成.在绕道容错路由算法中，采用部分路由表与路由规则相结合的方法，通过在报头中加入绕道路径列表的方式引导报文绕过故障区域.结果表明，与现有算法相比，所提出的容错路由算法在随机均衡负载和热点负载2种情况下的延时都有所降低.    

关键词: 片上网络, 路由算法, 容错, 死锁避免

Abstract: A fault-tolerant and deadlock-free routing algorithm applied in 2D-mesh was proposed to solve the problem of the permanent and unpredictable failure occurrence in network on chip. Firstly a new definition of fault block is proposed to reduce the region of fault and the affected healthy node, and then a detour-path construction algorithm is designed to implement the construction of fault block and the generation of detour-path list by recursive of message deliver. The detour-path routing algorithm combines the detour-path list and routing rules, makes a detour to avoid the fault block by adding detour-path list into the header flit. The experimental results show that the proposed algorithm achieves a reduction of average delay under uniform random distribution and hotspot distribution.  

Key words: network on chip (NoC), routing algorithm, faulttolerant, deadlock avoidance

中图分类号: