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

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

References

[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

[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

[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

[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

[7] Bjerregaard T, Mahadevan S. A survey of research and practices of network-on-chip. ACM Computing Surveys, 2006, 38(1): 1–51

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[21] Glass C, Ni L. The turn model for adaptive routing. In: Proceedings of the International Symposium on Computer Architecture. 1992, 278–287

[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

[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

[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

[25] Chiu G M. The odd-even turn model for adaptive routing. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(7): 729–738

[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

[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

[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

[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

[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

[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

[34] Henning J L. SPEC CPU2000: measuring CPU performance in the new millennium. Computer, 2000, 33(7): 28–35

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg