|
|
A survey of routing algorithm for mesh Network-on-Chip |
Yue WU1,2,Chao LU2,3,Yunji CHEN1,*( ) |
1. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China 2. School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 101408, China 3. Loongson Technology Corporation Limited, Beijing 100095, China |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|