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

• Original Articles • Previous Articles Next Articles

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
Contact: YAO Lei E-mail:leiyao@mail.xidian.edu.cn

Abstract

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

CLC Number:

TP302

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.

References

［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]	GONG Yanchao;WAN Shuai;YANG Kaifang;CHEN Hao;LI Bo. Real-time 3D bare-hand gesture recognition using binocular vision videos [J]. J4, 2014, 41(4): 130-136.
[2]	ZHANG Ximin;WEI Ting. Research on the test and verification system of the ARINC 659 fault-tolerant backplane data bus [J]. J4, 2011, 38(6): 140-145.
[3]	FAN Kang-qi;JIA Jian-yuan;WANG Wei-dong. Elastic nanocontact model of micro-mechanical systems [J]. J4, 2007, 34(1): 96-100.

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

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 3

Metrics

Comments

Recommended 0