ENG
РУС
Поиск
Меню
О журнале
Политика открытого доступа
Редакционная коллегия
Редакционная политика
Редакционная этика
Правила рецензирования статей
Требования к оформлению статей
Формы представляемых документов
Рекомендации по оформлению ссылок на наш журнал
Редакция
Информация для подписчиков
Аннотации номера
Список авторов
Выпуски
Лицензионное соглашение
Порядок работы с персональными данными
Публикации
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры













































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

УДК 004.3

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

Бондаренко М.И., Платунов А.Е.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования:
Бондаренко М.И., Платунов А.Е. Обзор алгоритмов маршрутизации для сетей на кристалле // Научно-технический вестник информационных технологий, механики и оптики. 2024. Т. 24, № 5. С. 687–698. doi: 10.17586/2226-1494-2024-24-5-687-698


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

Ключевые слова: интегральные схемы, многоядерные системы, сети на кристалле, шаблоны трафика, взаимоблокировка, ресурсное голодание, алгоритмы маршрутизации, детерминированные алгоритмы маршрутизации, отказоустойчивая маршрутизация, маршрутизация с учетом перегрузок, эффективность сети

Список литературы
  1. Benini L., De Micheli G. Networks on chip: a new paradigm for systems on chip design // Proc. of theDesign, 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-on-chip 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 network-on-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 fault-tolerant 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


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2024 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

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