A survey of routing algorithm for mesh Network-on-Chip

doi:10.1007/s11704-016-5431-8

Front. Comput. Sci.

2016, Vol. 10

Issue (4) : 591-601 https://doi.org/10.1007/s11704-016-5431-8

REVIEW ARTICLE

A survey of routing algorithm for mesh Network-on-Chip

Yue WU^1,²,Chao LU^2,³,Yunji CHEN^1,^*(

)

¹. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
². School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 101408, China
³. Loongson Technology Corporation Limited, Beijing 100095, China

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

Abstract

With the rapid development of semiconductor industry, the number of cores integrated on chip increases quickly, which brings tough challenges such as bandwidth, scalability and power into on-chip interconnection. Under such background, Network-on-Chip (NoC) is proposed and gradually replacing the traditional on-chip interconnections such as sharing bus and crossbar. For the convenience of physical layout, mesh is the most used topology in NoC design. Routing algorithm, which decides the paths of packets, has significant impact on the latency and throughput of network. Thus routing algorithm plays a vital role in a wellperformed network. This study mainly focuses on the routing algorithms of mesh NoC. By whether taking network information into consideration in routing decision, routing algorithms of NoC can be roughly classified into oblivious routing and adaptive routing. Oblivious routing costs less without adaptiveness while adaptive routing is on the contrary. To combine the advantages of oblivious and adaptive routing algorithm, half-adaptive algorithms were proposed. In this paper, the concepts, taxonomy and features of routing algorithms of NoC are introduced. Then the importance of routing algorithms in mesh NoC is highlighted, and representative routing algorithms with respective features are reviewed and summarized. Finally, we try to shed light upon the future work of NoC routing algorithms.

Keywords Network-on-Chip mesh topology routing algorithm adaptive routing oblivious routing

Corresponding Author(s): Yunji CHEN

Just Accepted Date: 16 March 2016 Online First Date: 19 April 2016 Issue Date: 06 July 2016

Cite this article:

Yue WU,Chao LU,Yunji CHEN. A survey of routing algorithm for mesh Network-on-Chip[J]. Front. Comput. Sci., 2016, 10(4): 591-601.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5431-8
https://academic.hep.com.cn/fcs/EN/Y2016/V10/I4/591

1	Dally W J. and Towles B. Route packets, not wires: on-chip inter connection networks. In: Proceedings of the 38th Design Automation Conference. 2001, 684–689
2	Gratz P, Kim C, McDonald R, Keckler S W, Burger D. Implementation and evaluation of on-chip network architectures. In: Proceedings of International Conference on Computer Design. 2006, 477–484 https://doi.org/10.1109/iccd.2006.4380859
3	Benini L, Micheli D G. Networks on chip: a new paradigm for systems on chip design. In: Proceedings of Design, Automation and Test in Europe Conference and Exhibition. 2002 https://doi.org/10.1109/date.2002.998307
4	Vangal S, Howard J, Ruhl G, Dighe S, Wilson H, Tschanz J, Finan D, Iyer P, Singh A, Jacob T, Jain S, Venkataraman S, Hoskote Y, Borkar N. An 80-tile 1.28 TFLOPS network-on-chip in 65nmCMOS. In: Proceedings of IEEE International Solid-State Circuits Conference. 2007
5	Sankaralingam K, Nagarajan R, Gratz P, Desikan R, Gulati D, Hanson H, Kim C, Liu H, Ranganathan N, Sethumadhavan S, Sharif S, Shivakumar P, Yoder W, McDonald R, Keckler S, Burger D. Distributed microarchitectural protocols in the TRIPS prototype processor. In: Proceedings of International Symposium on Microarchitecture. 2006, 480–491 https://doi.org/10.1109/micro.2006.19
6	Liang J, Swaminathan S, Tessier R. aSOC: a scalable, single-chip communication architectures. In: Proceedings of the 22nd International Conference on Parallel Architectures and Compilation Techniques. 2000, 37–46 https://doi.org/10.1109/pact.2000.888329
7	Bjerregaard T, Mahadevan S. A survey of research and practices of network-on-chip. ACM Computing Surveys, 2006, 38(1): 1–51 https://doi.org/10.1145/1132952.1132953
8	Intel Corporation. A Touchstone DELTA System Description. Technical Report.1991
9	BadrH G, Podar S. An optimal shortest-path routing policy for network computers with regular mesh-connected topologies. IEEE Transactions on Computers, 1989, 38(10): 1362–1371 https://doi.org/10.1109/12.35831
10	Nesson T, Johnsson S L. ROMM routing on mesh and torus networks. In: Proceedings of Annual ACM Symposium on Parallel Algorithms & Architectures. 1995, 275–287 https://doi.org/10.1145/215399.215455
11	Singh A, Dally W, Gupta A, Towles B. GOAL: a load-balanced adaptive routing algorithm for torus networks. In: Proceedings of the 30th Annual International Symposium on Computer Architectur. 2003, 194–205 https://doi.org/10.1145/859618.859641
12	Li M, Zeng Q A, Jone W B. DyXY—a proximity congestion-aware deadlock-free dynamic routing method for network on chip. In: Proceedings of the 43rd ACM/IEEE Design Automation Conference. 2006, 849–852
13	Gratz P, Grot B, Keckler S. Regional congestion awareness for load balance in networks-on-chip. In: Proceedings of the 14th IEEE International Symposium on High Performance Computer Architecture. 2008, 203–214 https://doi.org/10.1109/hpca.2008.4658640
14	Ma S, Jerger N, Wang Z Y. DBAR: an efficient routing algorithm to support multiple concurrent applications in networks on-chip. ACM SIGARCH Computer Architecture News, 2011, 39(3): 413–424 https://doi.org/10.1145/2024723.2000113
15	Kakoulli E, Soteriou V, Theocharides T. Intelligent hotspot prediction for network-on-chip-based multicore systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 31(3): 418–431 https://doi.org/10.1109/TCAD.2011.2170568
16	Dally M J, Towles B P. Principles and Practices of Interconnection Networks. San Francisco:Morgan Kaufmann Publishers Inc., 2003
17	Valiant L G. A scheme for fast parallel communication. SIAM Journal on Computing, 1982, 11(2): 350–361 https://doi.org/10.1137/0211027
18	Singh A, Dally W J, Towles B, Gupta A K. Locality preserving randomized routing on torus networks. In: Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures. 2002, 9–13 https://doi.org/10.1145/564870.564873
19	Ascia G, Catania V, Palesi M, Patti D. Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip. IEEE Transactions on Computers, 2008, 57(6): 809–820 https://doi.org/10.1109/TC.2008.38
20	Ramanujam R S, Lin B. Destination-based adaptive routing on 2D mesh networks. In: Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. 2010 https://doi.org/10.1145/1872007.1872030
21	Glass C, Ni L. The turn model for adaptive routing. In: Proceedings of the International Symposium on Computer Architecture. 1992, 278–287 https://doi.org/10.1109/isca.1992.753324
22	Duato J. A new theory of deadlock-free adaptive routing in wormhole networks. IEEE Transactions on Parallel and Distributed Systems, 1993, 4(12): 1320–1331 https://doi.org/10.1109/71.250114
23	Duato J. A necessary and sufficient condition for deadlock-free adaptive routing in wormhole networks. IEEE Transactions on Parallel and Distributed Systems, 1995, 6(10): 1055–1067 https://doi.org/10.1109/71.473515
24	Duato J. A necessary and sufficient condition for deadlock-free routing in cut-through and store-and-forward networks. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(8): 841–854 https://doi.org/10.1109/71.532115
25	Chiu G M. The odd-even turn model for adaptive routing. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(7): 729–738 https://doi.org/10.1109/71.877831
26	Fu B Z, Han Y H, Ma J, Li H W, Li X W. An Abacus turn model for time/space-efficient reconfigurable routing. In: Proceedings of the 38th annual international symposium on Computer architecture. 2011, 259–270 https://doi.org/10.1145/2000064.2000096
27	Hu J, Marculescu R. DyAD—smart routing for networks-on-chip. In: DAC 2004, 2004, 260–263
28	Marculescu R, Ogras U Y, Peh L S, Jerger N E, Hoskote Y. Outstanding research problems in NoC design: System, microarchitecture, and circuit perspectives. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2009, 28(1): 3–21 https://doi.org/10.1109/TCAD.2008.2010691
29	Ogras U Y, Marculescu R. Analysis and optimization of predictionbased flow control in networks-on-chip. ACM Transactions on Design Automation of Electronic Systems, 2008, 13(1): 105–133 https://doi.org/10.1145/1297666.1297677
30	Barrow-Williams N, Fensch C, Moore S. A communication characterization of splash-2 and Parsec. In: Proceedings of IEEE International Symposium on Workload Characterization. 2009, 86–97
31	Kakoulli E, Soteriou V, Theocharides T. Intelligent hotspot prediction for network-on-chip-based multicore systems. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, 31(3): 418–431 https://doi.org/10.1109/TCAD.2011.2170568
32	Singh A, Dally W J, Towles B, Gupta A K. Globally adaptive loadbalanced routing on tori. Computer Architecture Letters, 2004, 3(1): 6–9 https://doi.org/10.1109/L-CA.2004.8
33	Woo S C, Ohara M, Torrie E, Singh J P, Gupta A. The splash-2programs: Characterization and methodological considerations. ACM SIGARCH Computer Architecture News, 1995, 23(2): 24–36 https://doi.org/10.1145/225830.223990
34	Henning J L. SPEC CPU2000: measuring CPU performance in the new millennium. Computer, 2000, 33(7): 28–35 https://doi.org/10.1109/2.869367
35	Ramanujam R S, Lin B. Destination-based adaptive routing on 2Dmesh networks. In: Proceedings of the 6th ACM/IEEE Symposium on Architecture for Networking and Communications Systems. 2010 https://doi.org/10.1145/1872007.1872030
36	Sasakawa R, Kise K. LEF: long edge firstrouting for two-dimensional mesh network on chip. In: Proceedings of the 6th International Workshop on Network on Chip Architectures. 2013, 5–10 https://doi.org/10.1145/2536522.2536530
37	Baydal E, Lopez P, Duato J. A family of mechanisms for congestion control in wormhole networks. IEEE Transactions on Parallel & Distributed Systems, 2005, 16(9): 772–784 https://doi.org/10.1109/TPDS.2005.102
38	Dally W J, Aoki H. Deadlock-free adaptive routing in multicomputer networks using virtual channels. IEEE Transactions on Parallel & Distributed Systems, 1993, 4(4): 466–475 https://doi.org/10.1109/71.219761
39	Ebrahimi M, Daneshtalab M, Liljeberg P, Plosila J, Tenhunen H. CATRA-congestion aware trapezoid-based routing algorithm for onchip networks. In: Proceedings of Design, Automation & Test in Europe Conference & Exhibition. 2012, 320–325
40	Wang J H, Gu H X, Yang Y T, Wang K. An energy-and buffer-aware fully adaptive routing algorithm for network-on-chip. Microelectronics Journal, 2013, 44(2): 137–144 https://doi.org/10.1016/j.mejo.2012.12.008
41	Qian Z L, Bogdan P, Wei G P, Tsui C Y, Marculescu R. A trafficaware adaptive routing algorithm on a highly reconfigurable networkon- chip architecture. In: Proceedings of the 8th IEEE/ACM/IFIP International Conference on Hardware/software Codesign & System Synthesis. 2012, 161–170
42	Wang L, Song H, Jiang Y T, Zhang L H. A routing table-based adaptive and minimal routing scheme on network-on-chip architectures. Computers and Electrical Engineering, 2009, 35(6): 846–855 https://doi.org/10.1016/j.compeleceng.2008.11.019
43	Palesi M, Kumar S, Holsmark R. A method for router table compression for application specific routing in mesh topology NoC architectures. Lecture Notes in Computer Science, 2006, 4017: 373–384 https://doi.org/10.1007/11796435_38
44	Duato J, Johnson I, Flich J, Naven F, Garcia P, Nachiondo T. A new scalable and cost-effective congestion management strategy for lossless multistage interconnection networks. In: Proceedings of the 19th IEEE International Symposium on High Performance Computer Architecture. 2005, 108–119 https://doi.org/10.1109/hpca.2005.1
45	Mitchell T. Machine Learning. New York: McGraw-Hill Inc., 1997
46	Kumar M, Laxmi V, Gaur M S, Ko S B, Zwolinsk M. CARM: congestion adaptive routing method for on chip networks. In: Proceedings of International Conference on VLSI Design. 2014, 240–245 https://doi.org/10.1109/vlsid.2014.48
47	Kumar M, Laxmi V, Gaur M S, Daneshtage M, Zwolinsk M. A novel non-minimal turn model for highly adaptive routing in 2D NoCs. In: Proceedings of the 22nd International Conference on Very Large Scale Integration. 2014, 1–6 https://doi.org/10.1109/vlsi-soc.2014.7004192
48	Bolotin E, Morgenshtein A, Cidon I, Kolodny A. Automatic and hardware-efficient SoC integration by QoS network on chip. In: Proceedings of the 11th IEEE International Conference on Electronics, Circuits & Systems. 2005, 479–482

[1]

FCS-0591-15431-YJC_suppl_1

Download

[1]	Haizheng YU, Jianfeng MA, Hong BIAN. Reasonable routing in delay/disruption tolerant networks[J]. Front Comput Sci Chin, 2011, 5(3): 327-334.
[2]	Jian WANG, Yu-bai LI, Chang WU. An analytical model for Network-on-Chip with finite input buffer[J]. Front Comput Sci Chin, 2011, 5(1): 126-134.
[3]	Xin LI, Zhe LI, . A MANET accessing Internet routing algorithm based on dynamic gateway adaptive selection[J]. Front. Comput. Sci., 2010, 4(1): 143-150.

Viewed

Full text

Abstract

Cited

Shared

Discussed