2D Mesh片上网络分区容错路由算法

doi:10.11772/j.issn.1001-9081.2016.05.1201

计算机应用 ›› 2016, Vol. 36 ›› Issue (5): 1201-1205.DOI: 10.11772/j.issn.1001-9081.2016.05.1201

2D Mesh片上网络分区容错路由算法

胡哲琨¹, 杨升春¹, 陈杰²

1. 武汉数字工程研究所研发部, 武汉 430205;
2. 中国科学院微电子研究所通信与多媒体技术研究室, 北京 100029

收稿日期:2015-09-17 修回日期:2015-12-20 出版日期:2016-05-10 发布日期:2016-05-09
通讯作者: 胡哲琨
作者简介:胡哲琨(1986-),男,湖南常德人,工程师,博士,主要研究方向:片上网络结构、多核并行计算;杨升春(1971-),男,湖南常德人,高级工程师,硕士,主要研究方向:网络通信协议;陈杰(1963-),男,湖北孝感人,研究员,博士,主要研究方向:多核计算机体系结构。

Region-based fault tolerant routing algorithm for 2D mesh network on chip

HU Zhekun¹, YANG Shengchun¹, CHEN Jie²

1. Department of Research and Development, Wuhan Digital Engineering Institute, Wuhan Hubei 430205, China;
2. Laboratory of Communication and Multimedia Technology, Institute of Microelectronics of Chinese Academy of Sciences, Beijing 100029, China

Received:2015-09-17 Revised:2015-12-20 Online:2016-05-10 Published:2016-05-09

摘要/Abstract

摘要： 为了减小路由表的规模且避免使用较多虚通道(VC),从而降低硬件资源用量,针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由(RFTR)算法。该算法根据故障节点和链路的位置将2D Mesh网络划分为若干个相连的矩形区域,数据包在矩形区域内可使用确定性或自适应路由算法进行路由,而在区域间则按照up^*/down^*算法确定路由路径。此外,利用通道依赖图(CDG)模型,证明了该算法仅需两个虚通道就能避免死锁。在6×6 Mesh网络中,RFTR算法能减少25%的路由表资源用量。仿真结果表明,在队列缓存资源相同的情况下,RFTR算法能实现与up^*/down^*算法和segment算法相当甚至更优的性能。

关键词: 片上网络, 容错路由, 死锁避免, 路由表, 通道依赖图

Abstract: In order to reduce the entries of routing tables and avoid using large numbers of Virtual Channels (VC), a Region-based Fault Tolerant Routing (RFTR) algorithm was proposed for wormhole switching 2D Mesh Network on Chip (NoC) to reduce the amount of hardware resources. According to the positions of faulty nodes and links, the 2D Mesh network was divided into several rectangular regions. Within each region the packet could be routed by deterministic or adaptive routing algorithms, while among these regions the routing path was determined by up^*/down^* routing algorithm. Besides, with the Channel Dependency Graph (CDG) model, the proposed algorithm was proved to be deadlock-free using only two VCs. In a 6×6 Mesh network, the RFTR algorithm can reduce the amount of routing table resources by 25%. Simulation results show that, with the same amount of buffer resources, the RFTR algorithm can achieve an equivalent or even higher performance compared to up^*/down^* and segment-based routing algorithms.

Key words: Network on Chip (NoC), fault tolerant routing, deadlock avoidance, routing table, Channel Dependency Graph (CDG)

中图分类号:

TP302

胡哲琨, 杨升春, 陈杰. 2D Mesh片上网络分区容错路由算法[J]. 计算机应用, 2016, 36(5): 1201-1205.

HU Zhekun, YANG Shengchun, CHEN Jie. Region-based fault tolerant routing algorithm for 2D mesh network on chip[J]. Journal of Computer Applications, 2016, 36(5): 1201-1205.

参考文献

[1] CHEN C L, CHIU G M. A fault-tolerant routing scheme for meshes with nonconvex faults[J]. IEEE Transactions on Parallel and Distributed Systems, 2001, 12(5):467-475.
[2] ZHOU J P, LAU F C M. Multi-phase minimal fault-tolerant wormhole routing in meshes[J]. Parallel Computing, 2004, 30(3):423-442.
[3] FLICH J, SKEIE T, MEJIA A, et al. A survey and evaluation of topology-agnostic deterministic routing algorithms[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(3):405-423.
[4] DUATO J, YALAMANCHILI S, NI L. Interconnection Networks:An Engineering Approach[M]. San Francisco:Morgan Kaufmann Publishers, 2003:190-194.
[5] SANCHO J, ROBLES A, DUATO J. An effective methodology to improve the performance of the up^*/down^* routing algorithm[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(8):740-753.
[6] MEJIA A, FLICH J, DUATO J, et al. Segment-based routing:an efficient fault-tolerant routing algorithm for meshes and tori[C]//Proceedings of the 20th International Parallel and Distributed Processing Symposium. Washington, DC:IEEE Computer Society, 2006:10-19.
[7] FLICH J, RODRIGO S, DUATO J. An efficient implementation of distributed routing algorithms for NoCs[C]//Proceedings of the 2nd ACM/IEEE International Symposium on Networks-on-Chip. Washington, DC:IEEE Computer Society, 2008:87-96.
[8] 姚磊, 蔡觉平, 李赞, 等. 2D-Mesh结构片上网络无虚通道容错路由算法[J]. 西安电子科技大学学报(自然科学版), 2012, 39(6):26-33. (YAO L, CAI J P, LI Z, el al. Fault-tolerant routing algorithm for the 2D-Mesh network-on-chip without using virtual channels[J]. Journal of Xidian University(Natural Science), 2012, 39(6):26-33.)
[9] 周磊, 吴宁, 李云. 一种基于2D-mesh的片上网络无死锁容错路由算法[J]. 上海交通大学学报, 2013, 47(1):18-22. (ZHOU L, WU N, LI Y. A fault-tolerant and deadlock-free routing algorithm in 2D-mesh for network on chip[J]. Journal of Shanghai Jiaotong University, 2013, 47(1):18-22.)
[10] HOLSMARK R, KUMAR S, PALESI M, et al. HiRA:a methodology for deadlock free routing in hierarchical networks on chip[C]//Proceedings of the 3rd ACM/IEEE International Symposium on Networks-on-Chip. Washington, DC:IEEE Computer Society, 2009:2-11.
[11] DUBOIS F, SHEIBANYRAD A, PETROT F, et al. Elevator-first:a deadlock-free distributed routing algorithm for vertically partially connected 3D-NoCs[J]. IEEE Transactions on Computers, 2013, 62(3):609-615.
[12] DALLY W J, SEITZ C L. Deadlock-free message routing in multiprocessor interconnection networks[J]. IEEE Transactions on Computers, 1987, 36(5):547-553. BackgroundHU Zhekun, born in 1986, Ph. D., engineer. His research interests include network on-chip, multicore parallel computing.YANG Shengchun, born in 1971, M. S., senior engineer. His research interests include network communication protocol.CHEN Jie, born in 1963, Ph. D., professor. His research interest include multicore computer architecture.

[1]	孙美东, 刘勤让, 刘冬培, 燕昺昊. 面向非全互连3D NoC的自适应单播路由算法[J]. 计算机应用, 2018, 38(5): 1470-1475.
[2]	杭彦希, 徐金甫, 南龙梅, 郭朋飞. 端口故障粒度划分的虚通道动态分配式容错路由器设计[J]. 计算机应用, 2017, 37(6): 1560-1568.
[3]	宋国治, 王铖, 涂遥, 张大坤. 基于Prim初始种群选取优化遗传算法的三维片上网络低功耗映射[J]. 计算机应用, 2017, 37(1): 90-96.
[4]	周玉瀚, 韩国栋, 沈剑良, 姜奎. 基于Rent规则的片上网络局部化特性流量生成算法[J]. 计算机应用, 2016, 36(5): 1206-1211.
[5]	周端彭景张剑贤张晗. 低功耗片上网络路由器设计[J]. 计算机应用, 2011, 31(10): 2621-2624.
[6]	袁景凌刘华谢威蒋幸. 基于拥塞控制的片上网络多播路由算法[J]. 计算机应用, 2011, 31(10): 2630-2633.
[7]	王坚李玉柏彭启琮. 片上网络路由节点优化设计[J]. 计算机应用, 2011, 31(03): 617-620.
[8]	林红君王长山. 面向应用的NoC带宽感知路由技术[J]. 计算机应用, 2010, 30(12): 3176-3179.
[9]	张立鹏顾华玺王长山. 一个新颖的模块化NoC路由器设计[J]. 计算机应用, 2009, 29(2): 511-513.
[10]	安世全高涛丁进标. 非结构对等网络中一种有效的资源搜索策略[J]. 计算机应用, 2009, 29(11): 2881-2883.
[11]	欧阳一鸣冯伟梁华国. 功耗限制下的NoC测试端口的优化选择方法[J]. 计算机应用, 2008, 28(4): 1026-1028.
[12]	田丰仇庆丰孙小平高骞边婷婷. 一种基于路由表的无线传感器网络路由协议[J]. 计算机应用, 2008, 28(10): 2584-2586.
[13]	常政威谢晓娜熊光泽. 片上网络拓扑结构[J]. 计算机应用, 2007, 27(11): 2847-2850.
[14]	张林行林君陈祖斌 . 基于嵌入式以太网的分布式地震数据采集系统[J]. 计算机应用, 2006, 26(9): 2258-2260.
[15]	高集荣苏振林 . Chord改进算法在文件共享系统的实现[J]. 计算机应用, 2006, 26(12): 2803-2805.

2D Mesh片上网络分区容错路由算法

Region-based fault tolerant routing algorithm for 2D mesh network on chip

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics