ENG
РУС
Search
Menu
About the Edition
Open Access Statement
Editorial Board
Editorial Policy
Editorial Ethics
Rules for peer-review
Rules for presentation of papers
Forms of Submitted Documents
Recommendations for the Design of References to Our Journal
Editorial Staff
Information for Subscribers
Summaries of the Issue
List of Authors
Issues
Publishers license agreement
Procedure of work with personal data
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.
Partners













































doi: 10.17586/2226-1494-2024-24-5-687-698

Overview of routing algorithms for network on chip

M. I. Bondarenko, A. E. Platunov


Read the full article  ';
Article in Russian

For citation:
Bondarenko M.I., Platunov A.E. Overview of routing algorithms for network on chip. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2024, vol. 24, no. 5, pp. 687–698 (in Russian). doi: 10.17586/2226-1494-2024-24-5-687-698


Abstract
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.

Keywords: integrated circuits, multicore systems, network on a chip, traffic patterns, deadlock, resource starvation, routing algorithms, deterministic routing algorithms, fault-tolerant routing, congestion-aware routing, network efficiency

References
  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-on-chip 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_37
  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 network-on-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 fault-tolerant 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., Skeie 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/VLSI-SoC.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://rebeca-lang.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


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2024 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.

Яндекс.Метрика