Routing algorithm based on a column-partition turn model for a network-on-chip

doi:10.16511/j.cnki.qhdxxb.2018.22.043

Download: PDF(3044 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract Existing methods cannot easily determine whether a routing algorithm for a network-on-chip contains a deadlock and the traditional turn model has serious limitations. This paper presents a simple, intuitive algorithm to determine whether the routing algorithm is deadlock-free. This paper gives a proof of the algorithm's correctness. Then, a column-partition turn model is given to implement deadlock-free minimal partially adaptive routing for a virtual cut-through (VCT)-switched 2-D mesh without extra virtual channels. This algorithm avoids deadlocks by restricting the locations for certain turns, which is similar to the odd-even turn method. Simulations show that this routing algorithm reduces the average latency and increases the saturation points compared to routing algorithms based on the odd-even turn model for various traffic patterns. Therefore, this column-partition turn model improves the performance of the whole network.

Keywords turn model virtual cut-through switching 2-D mesh deadlock-free partially adaptive routing

Issue Date: 13 December 2018

	Service

	E-mail this article
	E-mail Alert
	RSS
	Articles by authors

	CAI Yuan
	LUO Wei
	XIANG Dong

Cite this article:

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(Science and Technology), 2018, 58(12): 1051-1058.

URL:

http://jst.tsinghuajournals.com/EN/10.16511/j.cnki.qhdxxb.2018.22.043 OR http://jst.tsinghuajournals.com/EN/Y2018/V58/I12/1051

[1] XU Y, DU Y, ZHAO B, et al. A low-radix and low-diameter 3D interconnection network design[C]//Proceedings of the 15th International Symposium on High Performance Computer Architecture. Raleigh, USA, 2009:30-42.
[2] 李晨, 马胜, 王璐, 等. 三维片上网络体系结构研究综述[J]. 计算机学报, 2016, 39(9):1812-1828. LI C, MA S, WANG L, et al. A survey on architecture for three-dimensional networks-on-chip[J]. Chinese Journal of Computers, 2016, 39(9):1812-1828. (in Chinese)
[3] XIANG D. Deadlock-free adaptive routing in meshes with fault-tolerance ability based on channel overlapping[J]. IEEE Transactions on Dependable and Secure Computing, 2011, 8(1):74-88.
[4] KHAN H U R, SHI F, JI W X, et al. Computationally efficient locality-aware interconnection topology for multi-processor system-on-chip (MP-SoC)[J]. Chinese Science Bulletin, 2010, 55(29):3363-3371.
[5] XIANG D, ZHANG Y L, PAN Y, et al. Deadlock-free adaptive routing in meshes based on cost-effective deadlock avoidance schemes[C]//Proceedings of International Conference on Parallel Processing. Xi'an, China, 2007:41-48.
[6] ALLEN F, ALMASI G, ANDREONI G, et al. Blue gene:A vision for protein science using a petaflop supercomputer[J]. IBM Systems Journal, 2011, 40(2):310-327.
[7] MUKHERJEE S S, BANNON R, LANG S, et al. The Alpha 21364 network architecture[J]. IEEE Micro, 2002, 22(1):26-35.
[8] DALLY W, TOWLES B. Principles and practices of interconnection networks[M]. San Francisco, USA:Morgan Kaufmann, 2003.
[9] DUATO J, YALAMANCHILI S, NI L. Interconnection networks:An engineering approach[M]. San Francisco, USA:Morgan Kaufmann, 2002.
[10] VERBEEK F, SCHMALTZ J. A decision procedure for deadlock-free routing in wormhole networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(8):1935-1944.
[11] GLASS C J, NI L M. The turn model for adaptive routing[J]. Journal of the ACM, 1994, 41(5):874-902.
[12] CHIU G M. The odd-even turn model for adaptive routing[J]. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(7):729-738.
[13] DUATO J. A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(8):841-854.