2D-Mesh结构片上网络无虚通道容错路由算法

doi:10.3969/j.issn.1001-2400.2012.06.005

J4 ›› 2012, Vol. 39 ›› Issue (6): 26-33.doi: 10.3969/j.issn.1001-2400.2012.06.005

2D-Mesh结构片上网络无虚通道容错路由算法

姚磊²;蔡觉平¹;李赞²;张海林²;王韶力²

(1. 西安电子科技大学宽带隙半导体国家重点实验室，陕西西安 710071；
2. 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071)

收稿日期:2012-04-06 出版日期:2012-12-20 发布日期:2013-01-17
作者简介:姚磊(1984-)，男，西安电子科技大学博士研究生，E-mail: leiyao@mail.xidian.edu.cn．
基金资助:
国家新一代宽带无线移动通信网科技重大专项资助项目(2010ZX03006-002-04); 高等学校学科创新引智计划资助项目(B08038);国家自然科学基金资助项目(61076031, 60832001,61072070)

Fault-tolerant routing algorithm for the 2D-mesh network-on-chip without using virtual channels

YAO Lei²;CAI Jueping¹;LI Zan²;ZHANG Hailin²;WANG Shaoli²

(1. State Key Lab. of Integrated Service Networks, Xidian Univ., Xi'an 710071， China;
2. State Key Lab. of Wide Bandgap Semiconductor Technology Disciplines, Xidian Univ., Xi'an 710071， China)

Received:2012-04-06 Online:2012-12-20 Published:2013-01-17

摘要/Abstract

摘要：

为了解决单故障节点情况下片上网络的无虚通道容错通信问题，提出一种新的片上网络容错路由算法．该算法在已有算法绕行思想的基础上，首先利用内建自测试机制获取故障节点的位置信息，再通过辅助节点来优化数据的绕行策略，达到了均衡故障节点周围链路负载并减少部分数据的绕行距离的目的．针对8×8 2D-Mesh网络的仿真结果表明，与Zhang's算法和Chen's算法相比，采用本文算法后网络的饱和注入率分别提高了3.13%和21.77%，在注入率为0.09时网络的通信功耗分别降低了3.40%和5.57%．

关键词: 容错, 无死锁, 片上网络, 虚通道

Abstract:

To solve one fault node tolerant problem in the Network on Chip (NoC) without using virtual channels, a novel fault-tolerant routing algorithm for the 2D-Mesh NoC is proposed based on Zhang's algorithm. This algorithm uses the Built-in Self Test (BIST) mechanism to get location information on the fault node first, and then sets auxiliary nodes to optimize the fault-tolerant strategy. By these two steps, the traffic loads on the fault ring can be balanced and the transmission distance of the packets routing around the fault node is shortened. Simulation results in the 8×8 2D-Mesh NoC show that, compared to Zhang's algorithm and Chen's algorithm, the network saturation injection rate of the proposed algorithm can be improved by 3.13% and 21.77%, respectively, and the communication power consuption of the proposed algorithm can be reduced by 3.40% and 5.57% respectively, when the injection rate is 0.09.

Key words: fault-tolerance, deadlock free, NoC, virtual channel

中图分类号:

TP302

姚磊;蔡觉平;李赞;张海林;王韶力. 2D-Mesh结构片上网络无虚通道容错路由算法[J]. J4, 2012, 39(6): 26-33.

YAO Lei;CAI Jueping;LI Zan;ZHANG Hailin;WANG Shaoli. Fault-tolerant routing algorithm for the 2D-mesh network-on-chip without using virtual channels[J]. J4, 2012, 39(6): 26-33.

参考文献

［1］ Rameshan N, Laxmi V, Gaur M S, et al. Minimal Path, Fault Tolerant, QoS Aware Routing with Node and Link Failure in 2-D Mesh NoC ［C］//Proc of the 2010 25th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems. Los Alamitos: IEEE Computer Society, 2010: 60-66.
［2］ Seyrafi M, Asad A, Zonouz A E, et al. A New Low Cost Fault Tolerant Solution for Mesh Based NoCs ［C］//2010 International Conference on Electronics and Information Engineering. Piscataway: IEEE, 2010: 207-213.
［3］ Duan Xinming, Sun Xuemei. Fault-tolerant Routing in A PRDT(2,1)-based NoC ［C］ //2010 2nd International Conference on Computer Engineering and Technology. Piscataway: IEEE, 2010: 506-510.
［4］ Chen K H, Chiu G M. Fault-tolerant Routing Algorithm for Meshes Without Using Virtual Channels ［J］. Journal of Information Science and Engineering, 1998, 14(4): 765-783.
［5］ Fukushima Y, Fukushi M. Fault-Tolerant Routing Algorithm for Network on Chip without Virtual Channels ［C］//2009 IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems. Piscataway: IEEE, 2009: 313-321
［6］ Zhang Z, Greiner A, Taktak S. A Reconfigurable Routing Algorithm for a Fault- Tolerant 2D-Mesh Network-on-chip ［C］ //45th ACM/IEEE Design Automation Conference. Piscataway: IEEE, 2008: 441-446.
［7］ Chien A A. A Cost and Speed Model for k-ary n-Cube Wormhole Routers ［J］. IEEE Trans on Parallel and Distributed Systems, 1998, 9(2): 150-162.
［8］ Duato J. A Theory of Fault-Tolerant Routing in Wormhole Networks ［J］. IEEE Trans on Parallel and Distributed Systems, 1997, 8(8): 790-802.
［9］ Cai Jueping, Huang Gang, Wang Shaoli, et al. OPNEC-Sim: an Efficient Simulation Tool for Network -on-Chip Communication and Energy Performance Analysis ［C］//International Conference on Solid-State and Integrated Circuit Technology 2010. Piscataway: IEEE, 2010: 1892-1894.
［10］ Lin Shuyen, Huang Chunhsiang, Chao Chihhao, et al. Traffic-Balanced Routing Algorithm for Irregular Mesh-Based On-Chip Networks ［J］. IEEE Trans on Computers, 2008, 57(9): 1156-1168.
［11］ Kiasari A E, Rahmati D. A Markovian Performance Model for Networks-on- Chip. Parallel［C］//Proc of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing. Piscataway: IEEE, 2008: 157-164.
［12］ Kahng A B, Li B, Peh L S, et al. Orion 2.0: a Fast and Accurate Noc Power and Area Model for Early-Stage Design Space Exploration［C］//2009 Design, Automation & Test in Europe Conference & Exhibition. Piscataway: IEEE, 2009: 423-428.
［13］ Merkel A, Bellosa F. Task Activity Vectors: a New Metric for Temperature-Aware Scheduling［C］//Proc of the EuroSys 2008 Conference. New York: ACM, 2008: 1-12.

[1]	支文韬, 赵辉, 孟繁鑫, 王静, 万波, 王泉. 面向WaaS平台的多工作流容错调度策略[J]. 西安电子科技大学学报, 2025, 52(1): 181-195.
[2]	胡东伟,尚德龙,张勇,王力男. 时钟及面积优化的可配置片上网络路由器[J]. 西安电子科技大学学报, 2022, 49(2): 125-134.
[3]	范亮;王晓梅;杨东煜. 一种利用最佳路径搜索的PDU容错定界算法[J]. 西安电子科技大学学报, 2016, 43(5): 160-166.
[4]	臧明相;王勐;周文宏;陈会仓. 改进混合蛙跳优化的片上网络低功耗映射算法[J]. J4, 2015, 42(1): 118-123.
[5]	臧明相;王婷;周文宏. 类电磁优化的片上网络低功耗映射算法[J]. J4, 2014, 41(4): 82-86+93.
[6]	李啸天;张润生;李艳斌. 归零Turbo码识别算法[J]. J4, 2013, 40(4): 161-166.
[7]	刘毅;陈博;杨银堂;刘刚. 一种高速低功耗的NoC时钟网络设计[J]. J4, 2013, 40(3): 115-120.
[8]	邓植;顾华玺;杨银堂;曾代兵. 基于人工蜂群算法的低能耗高性能NoC映射[J]. J4, 2012, 39(2): 114-119.
[9]	杨延飞;朱樟明;周端;杨银堂. 用于片上网络的延时无关异步动态优先级仲裁器[J]. J4, 2012, 39(1): 42-48+110.
[10]	张喜民;魏婷. ARINC 659容错数据总线测试验证系统研制[J]. J4, 2011, 38(6): 140-145.
[11]	张剑贤;周端;杨银堂;赖睿;高翔. 一种低能耗的片上网络映射算法[J]. J4, 2011, 38(4): 95-100.
[12]	管旭光；杨银堂；朱樟明. 用于片上网络的准延时不敏感全异步仲裁器[J]. J4, 2011, 38(3): 83-89.
[13]	刘毅;杨银堂;周东红. 一种面向片上网络的多时钟路由器设计[J]. J4, 2011, 38(2): 146-150.
[14]	刘有耀;韩俊刚. 一种星簇双环片上网络拓扑结构[J]. J4, 2009, 36(6): 1063-1069.
[15]	杜建超(1);吴成柯(1);杨亚东(1;2);肖嵩(1). 一种基于图像内容的数据分割方法[J]. J4, 2006, 33(2): 200-204.

2D-Mesh结构片上网络无虚通道容错路由算法

Fault-tolerant routing algorithm for the 2D-mesh network-on-chip without using virtual channels

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0