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

doi:10.12066/j.issn.1007-2861.1918

上海大学学报(自然科学版) ›› 2019, Vol. 25 ›› Issue (2): 189-197.doi: 10.12066/j.issn.1007-2861.1918

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

李娇^1,², 徐海鹏¹, 崇云锋¹, 刘鹏¹, 冉峰^1,²()

^1. 上海大学微电子研究与开发中心, 上海200444
^2. 上海大学新型显示技术及应用集成教育部重点实验室, 上海200444

收稿日期:2017-04-24 出版日期:2019-04-30 发布日期:2019-05-05
通讯作者: 冉峰 E-mail:ranfeng@shu.edu.cn
基金资助:
国家自然科学基金资助项目(61674100)

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

摘要：

随着特征尺寸的减小, 片上网络发生故障的概率显著增加.为了提高片上网络的容错能力, 降低网络延迟,提出一种低延迟的无虚通道容错路由算法. 该算法在转向模型的基础上,采用旁路结构, 保持故障节点在固定方向上的连接, 能够有效降低数据包延迟同时应对故障节点任意数量、任意分布的情况. 8$\times$8的2DMeshNoC的仿真结果表明, 相比于参考的两种算法,本算法在单故障且通信负载为30%时,平均延迟分别降低4.35%和20.20%,且在多故障情况下同样具有较好的性能.

关键词: 片上网络, 容错, 低延迟, 路由算法, 旁路结构

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

中图分类号:

TP393

李娇, 徐海鹏, 崇云锋, 刘鹏, 冉峰. 一种低延迟的无虚通道NoC容错路由算法[J]. 上海大学学报(自然科学版), 2019, 25(2): 189-197.

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.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

图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]. .

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

相关文章 5

编辑推荐

Metrics

本文评价

[1]	李娇, 郭润龙, 蔡升, 崇云锋, 徐海鹏, 冉峰. 一种转向均衡的3D NoC感知容错路由算法[J]. 上海大学学报(自然科学版), 2020, 26(5): 726-734.
[2]	陈健杨兴随. 基于WLAN信标的连续时钟同步算法[J]. 上海大学学报(自然科学版), 2009, 15(4): 331-335.
[3]	李明松;单而芳;高明晶. 容错定位控制集的界[J]. 上海大学学报(自然科学版), 2008, 14(6): 611-616 .
[4]	朱永华;姚洪;徐炜民. 消息传递网络中的消息传递机制和路由算法[J]. 上海大学学报(自然科学版), 2007, 13(5): 611-616 .
[5]	张杰;王汉兴;卢桂林. 基于多媒体业务的Ad Hoc网络QoS路由算法[J]. 上海大学学报(自然科学版), 2007, 13(1): 18-21 .