Обзор алгоритмов маршрутизации для сетей на кристалле

Введение. В работе исследованы алгоритмы маршрутизации для сетей на кристалле (СенК). Приведен анализ существующих алгоритмов маршрутизации, выделены их ограничения и области применения. Оценка алгоритмов проведена с учетом требований конкретных приложений и особенностей архитектур. Представлены результаты сравнения производительности рассматриваемых алгоритмов.
Метод. Анализ и сравнение различных алгоритмов маршрутизации для СенК проведены с учетом критически важных характеристик. Основное внимание уделено таким алгоритмам маршрутизации, как детерминированный XY-алгоритм, алгоритм поворота модели, маршрутизация с учетом перегрузок, отказоустойчивая маршрутизация, маршрутизация с учетом «качества услуги», алгоритм муравьиной колонии. Показано, что выбор алгоритма маршрутизации должен основываться на специфических требованиях и условиях использования сети. Показана важность адаптации к разнообразным условиям и задачам, с которыми могут столкнуться пользователи и разработчики СенК.
Основные результаты. С использованием данных из существующих исследований проведен анализ алгоритмов на основе нескольких ключевых показателей: задержка, пропускная способность, адаптивность, отказоустойчивость и сложность реализации. Выявлены сильные и слабые стороны каждого алгоритма в различных сценариях использования и при разной нагрузке на сеть. Показано, что выбор алгоритма маршрутизации должен опираться на конкретные требования и условия использования сети, а также на баланс между производительностью, адаптивностью, отказоустойчивостью и сложностью реализации.
Обсуждение. Исследование вносит вклад в понимание эффективности различных алгоритмов маршрутизации в СенК. Предоставлены рекомендации для их выбора в зависимости от специфических требований приложения и архитектуры системы. Исследование способствует углублению понимания влияния алгоритмов маршрутизации на общую эффективность СенК. Предложены направления дальнейших усовершенствований в этой области. Результаты работы могут быть применены при проектировании и разработке высокопроизводительных многопроцессорных систем на кристалле, где эффективная маршрутизация данных между различными компонентами системы является ключевым фактором обеспечения высокой производительности. Подчеркнута значимость разработки отказоустойчивых алгоритмов маршрутизации, способных обеспечивать непрерывность работы системы в случае отказов отдельных компонентов или узлов. Это особенно важно для критических приложений, где непрерывность сервиса и снижение риска потери данных являются приоритетными задачами.

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. P. 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. V. 38. N 1. P. 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 [Электроный ресурс]. URL: https://www.es.ele.tue.nl/~kgoossens/2003-ipsoc.pdf (дата обращения: 20.02.2024).

4. Bertozzi D., Benini L., De Micheli G. Energy-efficient network-onchip design // Ultra Low-Power Electronics and Design, 2004. P. 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. V. 611. P. 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. V. 40. N 6. P. 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. P. 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. P. 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. V. 25. N 9. P. 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. P. 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. V. 27. N 5. P. 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. V. 58. N 8. P. 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. P. 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. P. 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. P. 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. V. 21. P. 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. P. 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. P. 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. P. 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. P. 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. P. 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. V. 57. N 6. P. 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. V. 4. Spec. Issue 1. P. 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. V. 43. P. 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. P. 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 [Электронный ресурс]. URL: https://scholars.unh.edu/thesis/779 (дата обращения: 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. V. 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. V. 11. N 1. P 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. V. 72. N 12. P. 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. V. 8718. P. 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. P. 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. P. 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. V. 529. P. 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. V. 40. N 16. P. 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. V. 7. N 2. P. 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. P. 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. P. 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 [Электронный ресурс]. URL: https://rebeca-lang.org/assets/papers/2013/NoC-Routing-Algorithms-Comparison.pdf (дата обращения: 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. V. 20. N 3. P. 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. V. 1188. P. 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. P. 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. V. 166. P. 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. P. 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. V. 5. P. 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. V. 9040. P. 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. V. 158. P. 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. P. 640–643. https://doi.org/10.1109/ICECS.2016.7841283