一种低延迟的无虚通道NoC容错路由算法

doi:10.12066/j.issn.1007-2861.1918

Journal of Shanghai University（Natural Science Edition） ›› 2019, Vol. 25 ›› Issue (2): 189-197.doi: 10.12066/j.issn.1007-2861.1918

• Research Articles • Previous Articles Next Articles

A low-latency fault-tolerant routing algorithm for NoC without

virtual channelsLI Jiao^1,², XU Haipeng¹, CHONG Yunfeng¹, LIU Peng¹, RAN Feng^1,²()

^1. Microelectronic Research and Development Center,Shanghai University,Shanghai 200444, China
^2. Key Laboratory of Advanced Display and System Application,Shanghai University,Shanghai 200444, China

Received:2017-04-24 Online:2019-04-30 Published:2019-05-05
Contact: Feng RAN E-mail:ranfeng@shu.edu.cn

Abstract

Abstract:

As the characteristic size becomes smaller, network on chip (NoC) is prone to faults. To improve fault-tolerant ability of NoC and reduce network latency, a low-latency fault-tolerant routing algorithm without using virtual channels is presented. Based on a turn model,the algorithm uses a bypass structure to keep a fixed direction connection of fault nodes. This way can reduce packet latency and deal with arbitrary amount and arbitrary distribution of fault nodes. Simulation results in an 8$\times $8 2D-Mesh NoC show that,compared with two reference algorithms, the proposed algorithm can reduce average latency by 4.35% and 20.20% with a single fault node and a communication load of 30%. It can also effectively deal with multiple faults.

Key words: network on chip (NoC), fault-tolerant, low-latency, routing algorithm, bypass structure

CLC Number:

TP393

virtual channelsLI Jiao, XU Haipeng, CHONG Yunfeng, LIU Peng, RAN Feng. A low-latency fault-tolerant routing algorithm for NoC without[J]. Journal of Shanghai University（Natural Science Edition）, 2019, 25(2): 189-197.

Figures/Tables 11

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Table 1

Fig. 9

Fig. 10

References 10

[1]	Silva D R G, Oliveira B S, Moraes F G . Effects of the NoC architecture in the performance of NoC-based MPSoCs [C]// IEEE International Conference on Electronics, Circuits and Systems. 2014: 431-434.
[2]	Mahdoum A . An efficient network on chip design flow [C]// IEEE International Conference on Communication Technology. 2015: 1-8.
[3]	Radetzki M, Feng C C, Zhao X Q , et al. Methods for fault tolerance in networks-on-chip[J]. Acm Computing Surveys, 2013,46(1):28-36.
[4]	Zhang Z, Greiner A, Taktak S . A reconfigurable routing algorithm for a fault-tolerant 2DMesh network on chip [C]// 45th ZCM/IEEE Design Automation Conference. 2008: 441-446.
[5]	姚磊, 蔡觉平, 李赞 , 等. 基于内建自测技术的Mesh 结构NoC 无虚通道容错路由算法[J]. 电子学报, 2012,40(5):983-989. doi: 10.3969/j.issn.0372-2112.2012.05.019
[6]	Ebrahimi M, Daneshtalab M, Plosila J, et al. Minimal-path fault-tolerant approach using connection-retaining structure in Networks-on-Chip [C]// 17th IEEE/ACM International Symposium on Networks-on-Chip. 2013: 1-8.
[7]	Kumar M, Kumar K, Gupta S K, et al. FPGA based design of area efficient router architecture for network on chip [C]// IEEE International Conference on Computing Communication and Automation. 2016: 1600-1605.
[8]	Glass C J, Ni L M . The turn model for adaptive routing[J]. Journal of Association for Computering Machinery, 1994,41(5):874-902.
[9]	Dally W J, Seitz C L . Deadlock-free message routing in multiprocessor interconnection networks[J]. IEEE Transactions on Computers, 1987,36(5):547-553.
[10]	Nirgam. A . simulator for NoC interconnect routing andapplication modeling [EB/OL].( 2016- 05- 08)[2017-01-15]. .

A low-latency fault-tolerant routing algorithm for NoC without

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 10

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	LI Ming-song;SHAN Er-fang;GAO Ming-jing. Bounds of Fault-Tolerant Locating-Dominating Sets [J]. Journal of Shanghai University（Natural Science Edition）, 2008, 14(6): 611-616 .
[2]	ZHU Yong-hua;YAO Hong;XU Wei-ming. Message Passing Mechanism and Routing Algorithm in Message [J]. Journal of Shanghai University（Natural Science Edition）, 2007, 13(5): 611-616 .
[3]	ZHANG Jie;WANG Han xing;LU Gui lin . QoS Routing Algorithm for Ad Hoc Network Based on Multimedia Service [J]. Journal of Shanghai University（Natural Science Edition）, 2007, 13(1): 18-21 .