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

doi:10.12068/j.issn.1005-3026.2021.01.001

Abstract

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

CLC Number:

TP393.0

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.

References

[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.