Overview of routing algorithms for network on chip

This paper examines routing algorithms for networks on a chip (NoC). An analysis of existing routing algorithms is provided; their limitations and areas of application are highlighted. The algorithms were evaluated taking into account the requirements of specific applications and architecture features. The results of comparing the performance of the considered algorithms are presented. Analysis and comparison of various routing algorithms for NoC are carried out taking into account critical characteristics. The main attention is paid to such routing algorithms as the deterministic XY algorithm, the model rotation algorithm, congestion-aware routing, fault-tolerant routing, Quality of Service routing, and the ant colony algorithm. It is shown that the choice of routing algorithm should be based on the specific requirements and conditions of use of the network. The importance of adapting to a variety of conditions and tasks that NoC users and developers may encounter is shown. Based on data from existing studies, an analysis of algorithms was carried out based on several key indicators: latency, throughput, adaptability, fault tolerance and implementation complexity. The strengths and weaknesses of each algorithm are identified in various use scenarios and under different network loads. It is shown that the choice of a routing algorithm should be based on the specific requirements and conditions of use of the network, as well as on the balance between performance, adaptability, fault tolerance and implementation complexity. The study contributes to the understanding of the effectiveness of various routing algorithms in NoC, providing recommendations for their selection depending on the specific application requirements and system architecture. The study contributes to a better understanding of the impact of routing algorithms on the overall performance of NoC, suggesting directions for further improvements in this area. The results of the work can be applied in the design and development of highperformance multiprocessor systems on a chip where efficient data routing between various systems components is a key factor in ensuring high performance. The importance of developing fault-tolerant routing algorithms that can ensure the continuity of system operation in the event of failures of individual components or units is emphasized. This is especially important for mission-critical applications where service continuity and reducing the risk of data loss are top priorities.

1. Benini L., De Micheli G. Networks on chip: a new paradigm for systems on chip design. Proc. of the Design, Automation and Test in Europe Conference and Exhibition, 2002, pp. 418–419. https://doi.org/10.1109/DATE.2002.998307

2. Bjerregaard T., Mahadevan S. A survey of research and practices of Network-on-chip. ACM Computing Surveys, 2006, vol. 38, no. 1, pp. 1. https://doi.org/10.1145/1132952.1132953

3. Dielissen J., Goossens K., Rijpkema E. Concepts and Implementation of the Philips Network-on-Chip, 2003. Available at: https://www.es.ele.tue.nl/~kgoossens/2003-ipsoc.pdf (accessed: 20.02.2024).

4. Bertozzi D., Benini L., De Micheli G. Energy-efficient network-onchip design. Ultra Low-Power Electronics and Design, 2004, pp. 214–232. https://doi.org/10.1007/1-4020-8076-X_12

5. Mazumdar S., Scionti A., Portero A., Martinovič J., Terzo O. A scalable and low-power FPGA-aware network-on-chip architecture. Advances in Intelligent Systems and Computing, 2018, vol. 611, pp. 407–420. https://doi.org/10.1007/978-3-319-61566-0_3

6. Palesi M., Daneshtalab M. Routing Algorithms in Networks-on-Chip. Springer, 2014, 410 p. https://doi.org/10.1007/978-1-4614-8274-1

7. Khan K., Pasricha S. A reinforcement learning framework with region-awareness and shared path experience for efficient routing in networks-on-chip. IEEE Design & Test, 2023, vol. 40, no. 6, pp. 76–85. https://doi.org/10.1109/MDAT.2023.3306719

8. Dally W.J., Towles B. Route packets, not wires: On-chip interconnection networks. Proc. of the 38th Design Automation Conference, 2001, pp. 684–689. https://doi.org/10.1109/dac.2001.935594

9. Murali S., De Micheli G. Bandwidth-constrained mapping of cores onto NoC architectures. Proceedings Design, Automation and Test in Europe Conference and Exhibition. V. 2, 2004, pp. 896–901. https://doi.org/10.1109/DATE.2004.1269002

10. Ma S., Wang Z., Enright Jerger N., Shen L., Xiao N. Novel flow control for fully adaptive routing in cache-coherent NoCs. IEEE Transactions on Parallel and Distributed Systems, 2014, vol. 25, no. 9, pp. 2397–2407. https://doi.org/10.1109/TPDS.2013.166

11. Nicopoulos C.A., Park D., Kim J., Vijaykrishnan N., Yousif M.S., Das C.R. ViChaR: A dynamic virtual channel regulator for networkon-chip routers. Proc. of the 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO’06), 2006, pp. 333–346. https://doi.org/10.1109/MICRO.2006.50

12. Owens J.D., Dally W.J., Ho R., Jayasimha D.N., Keckler S.W., Peh L.-S. Research challenges for on-chip interconnection networks. IEEE Micro, 2007, vol. 27, no. 5, pp. 96–108. https://doi.org/10.1109/MM.2007.4378787

13. Mak T., Cheung P.Y.K., Lam K.-P., Luk W. Adaptive routing in network-on-chips using a dynamic-programming network. IEEE Transactions on Industrial Electronics, 2011, vol. 58, no. 8, pp. 3701–3716. https://doi.org/10.1109/TIE.2010.2081953

14. Paliwal K.K., Gaur M.S., Laxmi V., Janyani V. Performance analysis of guaranteed throughput and best effort traffic in network-on-chip under different traffic scenario. Proc. of the International Conference on Future Networks, 2009, pp. 74–78. https://doi.org/10.1109/ICFN.2009.45

15. Tedesco L., Mello A., Garibotti D., Calazans N., Moraes F. Traffic generation and performance evaluation for mesh-based NoCs. Proc. of the 18th Symposium on Integrated Circuits and Systems Design, 2005, pp. 184–189. https://doi.org/10.1109/SBCCI.2005.4286854

16. Soteriou V., Wang H., Peh L. A statistical traffic model for on-chip interconnection networks. Proc. of the 14th IEEE International Symposium on Modeling, Analysis, and Simulation, 2006, pp. 104–116. https://doi.org/10.1109/MASCOTS.2006.9

17. Velayudham S., Rajagopal S., Kathirvel S., Alhadidi B. An overview of multicast routing algorithms in network on chip. Learning and Analytics in Intelligent Systems, 2021, vol. 21, pp. 163–178. https://doi.org/10.1007/978-3-030-65407-8_14

18. Xiang D., Yu Z., Wu J. Deadlock-free fully adaptive routing in irregular networks without virtual channels. Proc. of the 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, 2013, pp. 983–990. https://doi.org/10.1109/TrustCom.2013.120

19. Palesi M., Holsmark R., Kumar S., Catania V. A methodology for design of application specific deadlock-free routing algorithms for NoC systems. Proc. of the 4th International Conference on Hardware/ Software Codesign and System Synthesis, 2006, pp. 142–147. https://doi.org/10.1145/1176254.1176289

20. Taheri E., Pasricha S., Nikdast M. DeFT: A Deadlock-free and faulttolerant routing algorithm for 2.5D chiplet networks. Proc. of the Design, Automation & Test in Europe Conference & Exhibition (DATE), 2022, pp. 1047–1052. https://doi.org/10.23919/DATE54114.2022.9774617

21. Valinataj M., Mohammadi S., Plosila J., Liljeberg P. A fault-tolerant and congestion-aware routing algorithm for Networks-on-Chip. Proc. of the 13th IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems, 2010, pp. 139–144. https://doi.org/10.1109/DDECS.2010.5491798

22. Patooghy A., Tabkhi H., Miremadi S.G. An efficient method to reliable data transmission in Network-on-Chips. Proc. of the 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools, 2010, pp. 467–474. https://doi.org/10.1109/DSD.2010.23

23. Lysne O., Montanana J.M., Flich J., Duato J., Pinkston T.M., Skei T. An efficient and deadlock-free network reconfiguration protocol. IEEE Transactions on Computers, 2008, vol. 57, no. 6, pp. 762–779. https://doi.org/10.1109/TC.2008.31

24. Adamu G., Chejara P., Garko A. Review of deterministic routing algorithm for Network-on-Chip. International Journal of Advance Research in Science and Engineering, 2015, vol. 4, spec. issue 1, pp. 123–128.

25. Mahendra C., Gaikwad M., Patrikar R. Review of XY routing algorithm for network-on-chip architecture. International Journal of Computer and Communication Technology, 2016, vol. 43, pp. 20–23. https://doi.org/10.47893/IJCCT.2016.1384

26. Kumar M., Laxmi V., Gaur M.S., Daneshtalab M., Zwolinski M. A novel non-minimal turn model for highly adaptive routing in 2D NoCs. Proc. of the 22nd International Conference on Very Large Scale Integration (VLSI-SoC), 2014, pp. 1–6. https://doi.org/10.1109/VLSISoC.2014.7004192

27. Brown J.W. Adaptive Network on Chip Routing using the Turn Model: Master’s Theses and Capstones. 2013. Available at: https://scholars.unh.edu/thesis/779 (accessed: 20.02.2024)

28. Ahmad K., Sethi M.A.J., Ullah R., Ahmed I., Ullah A., Jan N., Karami G.M. Congestion-aware routing algorithm for NoC using data packets. Wireless Communications and Mobile Computing, 2021, vol. 2921. https://doi.org/10.1155/2021/8588646

29. Ponnan S., Kumar T.A., Hemakumar V.S., Natarajan S., Shah M.A. Congestion aware low power on chip protocols with network on chip with cloud security. Journal of Cloud Computing, 2022, vol. 11, no. 1, pp 41. https://doi.org/10.1186/s13677-022-00307-4

30. Akbar R., Etedalpour A.A., Safaei F. An efficient fault-tolerant routing algorithm in NoCs to tolerate permanent faults. The Journal of Supercomputing, 2016, vol. 72, no. 12, pp. 4629–4650. https://doi.org/10.1007/s11227-016-1749-0

31. Zhang Z., Serwe W., Wu J., Yoneda T., Zheng H., Myers C. Formal analysis of a fault-tolerant routing algorithm for a Network-on-Chip. Lecture Notes in Computer Science, 2014, vol. 8718, pp. 48–62. https://doi.org/10.1007/978-3-319-10702-8_4

32. Carara E., Calazans N., Moraes F. Managing QoS flows at task level in NoC-based MPSoCs. Proc. of the 17th IFIP International Conference on Very Large Scale Integration. (VLSI-SoC), 2009, pp. 133–138. https://doi.org/10.1109/VLSISOC.2009.6041343

33. Xie P., Gu H. Intelligent bees for QoS routing in Networks-on-Chip. Proc. of the Second Pacific-Asia Conference on Circuits, Communications and System, 2010, pp. 311–314. https://doi.org/10.1109/PACCS.2010.5626974

34. Nedjah N., de Macedo Mourelle L. Routing in Network-on-Chips using ant colony optimization. Studies in Computational Intelligence, 2014, vol. 529, pp. 173–198. https://doi.org/10.1007/978-3-319-03110-1_11

35. Nedjah N., Silva Junior L., De Macedo Mourelle L. Congestion-aware an colony based routing algorithms for efficient application execution on Network-on-Chip platform. Expert Systems with Applications, 2013, vol. 40, no. 16, pp. 6661–6673. https://doi.org/10.1016/j.eswa.2013.06.005

36. Ahmad K., Sethi M.A.J. Review of Network on Chip routing algorithms. EAI Endorsed Transactions on Context-aware Systems and Applications, 2020, vol. 7, no. 2, pp. e5. https://doi.org/10.4108/eai.23-12-2020.167793

37. Xu Y., Zhou J., Liu S. Research and analysis of routing algorithms for NoC. Proc. of the 3rd International Conference on Computer Research and Development, 2011, pp. 98–102. https://doi.org/10.1109/ICCRD.2011.5764092

38. Uma R., Sarojadevi H., Sanju V. Network-On-Chip (NoC) - routing techniques: a study and analysis. Proc. of the Global Conference for Advancement in Technology (GCAT), 2019, pp. 1–6. https://doi.org/10.1109/GCAT47503.2019.8978403

39. Sharifi Z., Mohammadi S., Sirjani M. Comparison of NoC Routing Algorithms Using Formal Methods. 2013. Available at: https://rebecalang.org/assets/papers/2013/NoC-Routing-Algorithms-Comparison.pdf (accessed: 20.02.2024).

40. Saliu M., Momoh M., Chinedu P., Nwankwo W., Daniel A. Comparative performance analysis of selected routing algorithms by load variation of 2-dimensional mesh topology based Network-On-Chip. ELEKTRIKA-Journal of Electrical Engineering, 2021, vol. 20, no. 3, pp. 1–6. https://doi.org/10.11113/elektrika.v20n3.249

41. Kaleem M., Isnin I.F.B. A survey on network on chip routing algorithms criteria. Advances in Intelligent Systems and Computing, 2021, vol. 1188, pp. 455–466. https://doi.org/10.1007/978-981-15-6048-4_40

42. Singh J.K., Swain A.K., Kamal Reddy T.N., Mahapatra K.K. Performance evalulation of different routing algorithms in Network on Chip. Proc. of the IEEE Asia Pacific Conference on Postgraduate Research in Microelectronics and Electronics (PrimeAsia), 2013, pp. 180–185. https://doi.org/10.1109/PrimeAsia.2013.6731201

43. Soni N., Deshmukh K. Comparison between three different types of routing algorithms of Network on Chip. Springer Proceedings in Physics, 2015, vol. 166, pp. 447–459. https://doi.org/10.1007/978-81-322-2367-2_56

44. Palesi M., Holsmark R., Kumar S., Catania V. Application-specific routing algorithms for low power network on chip design. Low Power Networks-on-Chip. Springer, 2011, pp. 113–150. https://doi.org/10.1007/978-1-4419-6911-8_5

45. Zulkefli F.W., Ehkan P., Warip M.N.M., Phing N.Y., Zakaria F.F. A comparative review of adaptive routing approach for Network-on-Chip router architecture. Lecture Notes on Data Engineering and Communications Technologies, 2018, vol. 5, pp. 247–254. https://doi.org/10.1007/978-3-319-59427-9_27

46. Hesham S., Rettkowski J., Göhringer D., Abd El Ghany M.A. Survey on real-time network-on-chip architectures. Lecture Notes in Computer Science, 2015, vol. 9040, pp. 191–202. https://doi.org/10.1007/978-3-319-16214-0_16

47. Venkataraman N.L., Kumar R. Design and analysis of application specific network on chip for reliable custom topology. Computer Networks, 2019, vol. 158, pp. 69–76. https://doi.org/10.1016/j.comnet.2019.03.014

48. Madalozzo G., Indrusiak L.S., Moraes F.G. Mapping of real-time applications on a packet switching NoC-based MPSoC. Proc. of the IEEE International Conference on Electronics, Circuits and Systems (ICECS), 2016, pp. 640–643. https://doi.org/10.1109/ICECS.2016.7841283