基于FPGA的2D-Torus片上网络无死锁路由算法

doi:10.12068/j.issn.1005-3026.2021.01.001

东北大学学报（自然科学版） ›› 2021, Vol. 42 ›› Issue (1): 1-6.DOI: 10.12068/j.issn.1005-3026.2021.01.001

• 信息与控制 • 下一篇

基于FPGA的2D-Torus片上网络无死锁路由算法

李贞妮，李晶皎，王骄，杨丹

(东北大学信息科学与工程学院，辽宁沈阳110819)

出版日期:2021-01-15 发布日期:2021-01-13
通讯作者: 李贞妮
作者简介:李贞妮(1982-)，女，辽宁沈阳人，东北大学讲师，博士; 李晶皎(1964-)，女，辽宁沈阳人，东北大学教授，博士生导师; 王骄(1978-)，男，辽宁沈阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(61836011); 中央高校基本科研业务费专项资金资助项目(2020GFYD011，2020GFZD008).

Deadlock-Free Routing Algorithm of 2D-Torus Network-on-Chip Based on FPGA

LI Zhen-ni， LI Jing-jiao， WANG Jiao， YANG Dan

School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.

Online:2021-01-15 Published:2021-01-13
Contact: LI Jing-jiao
About author:-
Supported by:
-

摘要/Abstract

摘要： 片上网络的拓扑结构和路由算法直接影响片上网络的传输延迟和传输效率.基于2D-Torus拓扑结构，提出了一种新的片上网络无死锁路由算法.通过改变数据包在片上网络路由过程中受限制转弯的位置，保证片上网络的自适应路由条件，从而有效降低片上网络的延迟.在FPGA硬件平台上，设计并实现了基于该路由算法的2D-Torus片上网络，并对其进行测试.实验结果表明，基于该路由算法的片上网络，可以满足片上网络多方向数据通信及多路数据并行通信等性能要求.

关键词: 2D-Torus, 片上网络, 无死锁, 路由算法, FPGA

Abstract: The topology and routing algorithm of network on chip (NoC) directly influence the transmission delay and the transmission efficiency of the network-on-chip. A new deadlock-free routing algorithm for NoC was proposed based on 2D-Torus topology. By changing the position of packets that are restricted to turn during NoC routing， the adaptive routing condition of network-on-chip was guaranteed， and the delay of network-on-chip was reduced. The 2D-Torus NoC based on this routing algorithm was designed and implemented on FPGA hardware platform， and then was tested. The experimental results indicated that the NoC based on this routing algorithm can meet the performance requirements of network-on-chip data communication for multi-direction and multi-channel.

Key words: 2D-Torus, NoC(network-on-chip), deadlock-free, routing algorithm, FPGA

中图分类号:

TP393.0

李贞妮, 李晶皎, 王骄, 杨丹. 基于FPGA的2D-Torus片上网络无死锁路由算法[J]. 东北大学学报（自然科学版）, 2021, 42(1): 1-6.

LI Zhen-ni, LI Jing-jiao, WANG Jiao, YANG Dan. Deadlock-Free Routing Algorithm of 2D-Torus Network-on-Chip Based on FPGA[J]. Journal of Northeastern University(Natural Science), 2021, 42(1): 1-6.

参考文献

[1]李贞妮，李晶皎，方志强，等.异步2D-Torus片上网络自适应路由算法［J］.东北大学学报(自然科学版)，2015，36(9):1217-1221.(Li Zhen-ni，Li Jing-jiao，Fang Zhi-qiang，et al.Adaptive routing algorithm of asynchronous 2D-Torus network-on-chip［J］.Journal of Northeastern University(Natural Science)，2015，36(9):1217-1221.)
[2]Wang L，Ma S，Li C，et al.A high performance reliable NoC router［J］.Integration，2017，58:583-592.
[3]Daneshtalab M，Palesi M，Mak T.Introduction to the special issue on NoC-based many-core architectures［J］.Computers & Electrical Engineering，2015，45(1):359-361.
[4]Hoefflinger B.The International technology roadmap for semiconductors［EB/OL］.(2013-06-26)［2018-04-01］.http://www.itrs.net/Links/2010ITRS/Home2010.htm.
[5]蔡源，罗伟，向东.基于列分转弯模型的片上网络路由算法［J］.清华大学学报(自然科学版)，2018，58(12):1051-1058.(Cai Yuan，Luo Wei，Xiang Dong.Routing algorithm based on a column-partition turn model for a network-on-chip［J］.Journal of Tsinghua University(Natural Science)，2018，58(12):1051-1058.)
[6]He A P，Feng G B，Zhang J L，et al.An asynchronous mesh NoC based booth multiplication［J］.IET Circuits，Devices & Systems，2019，13(1):73-78.
[7]Wang L，Wang X H，Leung H F，et al.A non-minimal routing algorithm for aging mitigation in 2D-Mesh NoCs［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits & Systems，2019，38(7):1373-1377.
[8]Feero B，Pande P.Performance evaluation for three-dimensional networks-on-chip［C］//IEEE Computer Society Annual Symposium on VLSI.Porto Alegre，2007:305-310.
[9]Chiu G M.The odd-even turn model for adaptive routing［J］.IEEE Transactions on Parallel and Distributed Systems，2000，11(7):729-738.
[10]Khawaja S G，Mushtaq M H，Khan S A，et al.Designing area optimized application-specific network-on-chip architectures while providing hard QoS guarantees［J］.PLoS One，2015，10(4):1-17.
[11]Dally W J，Seitz G L.Deadlock-free message routing in multiprocessor interconnection networks［J］.IEEE Transactions on Computers，1987，36(5):547-553.
[12]Rahmati D，Sarbazi-Azad H，Hessabi S，et al.Power-efficient deterministic and adaptive routing in Torus networks-on-chip［J］.Microprocessors and Microsystems，2012，36(7):571-585.
[13]Touzene A，Day K.All-to-all broadcasting in Torus network on chip［J］.The Journal of Supercomputing，2015，71(7):2585-2596.
[14]Ezz-Eldin R，El-Moursy M A，Hamed H F A，et al.Process variation delay and congestion aware routing algorithm for asynchronous NoC design［J］.IEEE Transactions on Very Large Scale Integration Systems，2016，24(3):909-919.
[15]周磊，吴宁，李云.一种基于2D-Mesh的片上网络无死锁容错路由算法［J］.上海交通大学学报，2013，47(1):18-22.(Zhou Lei，Wu Ning，Li Yun.A fault-tolerant and deadlock-free routing algorithm in 2D-Mesh for network on chip［J］.Journal of Shanghai Jiaotong University，2013，47(1):18-22.)
[16]Ren P J，Kinsy M A，Zheng N N.Fault-aware load-balancing routing for 2D-Mesh and Torus on-chip network topologies［J］.IEEE Transactions on Computers，2016，65(3):873-887.
[17]Dally W J.Virtual-channel flow control［J］.IEEE Transactions on Parallel and Distributed Systems，1992，3(2):194-205.
[18]Duato J，Yalamanchili S.Interconnection networks:an engineering approach［M］.San Francisco:Morgan Kaufmann，2002.

基于FPGA的2D-Torus片上网络无死锁路由算法

Deadlock-Free Routing Algorithm of 2D-Torus Network-on-Chip Based on FPGA

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

本文评价

[1]	李贞妮，王骄，李晶皎，王泽坤. 一种新的基于FPGA的立体图像差异性算法[J]. 东北大学学报:自然科学版, 2020, 41(6): 778-783.
[2]	李贞妮，李晶皎，王爱侠，张壬申. 一种新型片上网络拓扑结构及其自适应路由算法[J]. 东北大学学报:自然科学版, 2017, 38(9): 1217-1221.
[3]	李贞妮，李晶皎，方志强，王骄. 异步2D-Torus片上网络自适应路由算法[J]. 东北大学学报:自然科学版, 2015, 36(9): 1217-1221.
[4]	李晶皎，陈勇，许哲万，陆振林. 入侵检测中字符匹配系统的FPGA实现[J]. 东北大学学报(自然科学版), 2013, 34(3): 339-343.
[5]	马毅，陈东明，常桂然，谭振华. 基于多环结构的P2P覆盖网络路由算法[J]. 东北大学学报:自然科学版, 2013, 34(1): 44-47.
[6]	李晶皎;许哲万;王爱侠;陈勇;. 高速包分类平台的FPGA设计[J]. 东北大学学报(自然科学版), 2012, 33(8): 1115-1119.
[7]	李晶皎;陆振林;王爱侠;王骄;. 基于FPGA面向多媒体处理的MPSoC[J]. 东北大学学报(自然科学版), 2012, 33(4): 486-490.
[8]	王兴伟;王军伟;黄敏;. 基于狩猎搜索的可信QoS路由算法[J]. 东北大学学报(自然科学版), 2012, 33(10): 1385-1389.
[9]	谭振华;程维;常桂然;高晓兴;. 一种新的结构化P2P覆盖网络路由算法[J]. 东北大学学报(自然科学版), 2009, 30(2): 195-199.
[10]	乔百友;王国仁;邢云龙;王彩荣;. 一种基于语义的super-peer网络构建方法[J]. 东北大学学报(自然科学版), 2008, 29(1): 61-64.
[11]	尹震宇;赵海;张文波;王小英;. 一种嵌入式硬件多线程处理器的研究[J]. 东北大学学报(自然科学版), 2006, 27(9): 968-971.