一种转向均衡的3D NoC感知容错路由算法

doi:10.12066/j.issn.1007-2861.2081

上海大学学报(自然科学版) ›› 2020, Vol. 26 ›› Issue (5): 726-734.doi: 10.12066/j.issn.1007-2861.2081

一种转向均衡的3D NoC感知容错路由算法

李娇¹^,², 郭润龙¹, 蔡升¹, 崇云锋¹, 徐海鹏¹, 冉峰¹^,²()

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

收稿日期:2018-08-30 出版日期:2020-10-30 发布日期:2020-01-09
通讯作者: 冉峰 E-mail:ranfeng@shu.edu.cn
基金资助:
国家自然科学基金资助项目(61774101);国家自然科学基金资助项目(61674100)

A conscious fault-tolerant routing algorithm with turn balanced in 3D NoC

LI Jiao¹^,², GUO Runlong¹, CAI Sheng¹, CHONG Yunfeng¹, XU Haipeng¹, RAN Feng¹^,²()

1. Microelectronics R&D Center, Shanghai University, Shanghai 200444, China
2. Key Laboratory of Advanced Display and System Application, Ministry of Education, Shanghai University, Shanghai 200444, China

Received:2018-08-30 Online:2020-10-30 Published:2020-01-09
Contact: RAN Feng E-mail:ranfeng@shu.edu.cn

摘要/Abstract

摘要：

针对复杂三维片上网络中自适应路由策略存在性能较差与容错机制不完善的问题, 提出一种转向均衡的感知容错路由算法. 首先将XY, XZ和YZ分为奇偶平面, 并在行与列上制定6种不同的禁止转向, 以得到更均衡的转向模型; 然后以奇偶行列对水平和垂直方向上边界及内部链路故障分类设计故障模型, 并进行容错绕行; 最后将提出的转向及故障模型应用到结合“全平面一跳预先感知”策略的路由算法中, 以提高网络的性能与容错能力. 实验结果表明, 所提出算法在无链路故障时较对比算法吞吐量提升16.2%, 传输延时降低3.6%, 在较低链路故障率时传输延时降低11.8%, 随着链路故障率的增加, 算法仍具有优势.

关键词: 三维片上网络, 转向均衡, 高性能, 感知容错

Abstract:

Aiming at the poor performance of adaptive routing strategy and the imperfect fault tolerant mechanism in 3D NoC, the study proposes a perceptually fault-tolerant routing algorithm with turn balanced. Firstly, the XY, XZ and YZ are divided into the odd and even planes and six different forbidden turn directions are established on the row and column to get a more balanced turn model. Then, the horizontal and vertical boundary and internal link fault classification design fault model and fault-tolerant bypass. Finally, the proposed turn and fault model is applied to the routing algorithm combined with the strategy of “full plane 1 hop look-ahead” to improve network performance and fault tolerance. The experimental results show that the proposed algorithm improves throughput by 16.2% and transmission delay by 3.6% when no link failure occurs, and decreases transmission delay by 11.8% at lower link failure rate. With the link failure rate increased, this algorithm still has advantages.

Key words: 3D network on chip (3D NoC), turn balance, high performance, fault-tolerance

中图分类号:

TP393

李娇, 郭润龙, 蔡升, 崇云锋, 徐海鹏, 冉峰. 一种转向均衡的3D NoC感知容错路由算法[J]. 上海大学学报(自然科学版), 2020, 26(5): 726-734.

LI Jiao, GUO Runlong, CAI Sheng, CHONG Yunfeng, XU Haipeng, RAN Feng. A conscious fault-tolerant routing algorithm with turn balanced in 3D NoC[J]. Journal of Shanghai University（Natural Science Edition）, 2020, 26(5): 726-734.

图/表 8

图1

图2

图3

图4

图5

表1

图6

图7

参考文献 10

[1]	Kim B, Cho S B. Recent advances in TSV inductors for 3D IC technology[C]// SoC Design Conference (ISOCC). 2016: 29-30.
[2]	Radfar F, Zabihi M, Sarvari R. Comparison between optimal interconnection network in different 2D and 3D NoC structures[C]// System-on-Chip Conference (SOCC). 2014: 171-176.
[3]	Charif A, Coelho A, Zergainoh N E, et al. A dynamic sufficient condition of deadlock-freedom for high-performance fault-tolerant routing in networks-on-chips[J]. IEEE Transactions on Emerging Topics in Computing, 2020,8(3):642-654.
[4]	Ahmed A B, Abdallah A B. Adaptive fault-tolerant architecture and routing algorithm for reliable many-core 3D-NoC systems[J]. Journal of Parallel and Distributed Computing, 2016,93:30-43.
[5]	Dahir N, Mak T, Yakovlev A. Highly adaptive and deadlock-free routing for three-dimensional networks-on-chip[J]. IET Computers and Digital Techniques, 2013,7(6):255-263.
[6]	Chiu G M. The odd-even turn model for adaptive routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2000,11(7):729-738.
[7]	Zhou J, Li H, Wang T, et al. LOFT: a low-overhead fault-tolerant routing scheme for 3D NoCs[J]. Integration, 2016,52:41-50.
[8]	Zhou J, Li H, Wang T, et al. TURO: a lightweight turn-guided routing scheme for 3D NoCs[C]// 2015 IEEE Symposium in Low-Power and High-Speed Chips. 2015: 1-3.
[9]	Lei X, Jiang X, Zeng L, et al. Vertical-mesh-conscious-dynamic routing algorithm for 3D NoCs[C]// IEEE TENCON 2015. 2015:1-6.
[10]	Su J, Chai C, Lei X, et al. Vertical-mesh-conscious-dynamic routing algorithm for fault tolerant 3D NoC[C]// IEEE International Conference on Computer and Communications (ICCC). 2016: 2004-2008.

一种转向均衡的3D NoC感知容错路由算法

A conscious fault-tolerant routing algorithm with turn balanced in 3D NoC

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 10

相关文章 2

编辑推荐

Metrics

本文评价

[1]	宋文祥, 姜书豪, 阮智勇, 杨影, 阮毅. 基于定子磁链轨迹跟踪的优化PWM高性能闭环控制[J]. 上海大学学报(自然科学版), 2015, 21(1): 128-140.
[2]	石海田莉. 3Tnet视频点播的动态协作合并流调度[J]. 上海大学学报(自然科学版), 2009, 15(2): 116-120.