Маршрутизация в циркулянтных графах на основе виртуальной координатной системы
https://doi.org/10.26907/2541-7746.2023.3.282-293
Аннотация
Рассмотрены методы маршрутизации в двумерных циркулянтных графах (каждая вершина соединена с четырьмя соседними). Уникальная группа симметрий циркулянта позволяет использовать его в качестве топологии для вычислительных устройств большой мощности, в том числе сетей на кристалле и суперкомпьютеров кластерного типа. Показано, что в качестве координат вершин можно использовать минимальное число переходов по образующим от начальной вершины. Разработаны два метода маршрутизации на основе координат. Первый предполагает восстановление номеров вершин и нахождение разности между ними, координаты соответствующей вершины задают маршрут. Второй метод состоит в нахождении разности координат конечной и начальной вершин и минимизации маршрута на основе предложенного алгоритма.
Ключевые слова
циркулянтный граф,
сеть на кристалле,
суперкомпьютерный кластер,
маршрутизация на основе виртуальной координатной системы
При поддержке: Исследование выполнено за счет средств гранта РНФ (проект № 22-29-00979).
Об авторах
А. М. Сухов
Севастопольский государственный университет
Россия
Россия
Сухов Андрей Михайлович, д. т. н., к. ф.-м. н., ведущий научный сотрудник Научно-исследовательской лаборатории прикладной математики и суперкомпьютерных вычислений
ул. Университетская, д. 33, г. Севастополь, 299053
А. Ю. Романов
Национальный исследовательский университет "Высшая школа экономики"
Россия
Россия
Романов Александр Юрьевич, к. т. н., доцент, ведущий научный сотрудник Департамента компьютерной инженерии
ул. Мясницкая, д. 20, г. Москва, 101000
Е. В. Глушак
Поволжский государственный университет телекоммуникаций и информатики
Россия
Россия
Глушак Елена Владимировна, к. т. н., доцент кафедры сетей и систем связи
ул. Льва Толстого, д. 23, г. Самара, 443010
Список литературы
1. Kahle J.A., Moreno J., Dreps D. 2.1 Summit and Sierra: Designing AI/HPC supercomputers // 2019 IEEE Int. Solid-State Circuits Conf. – (ISSCC). IEEE. 2019. P. 42–43. https://doi.org/10.1109/ISSCC.2019.8662426.
2. Jain A., Dwivedi R.K., Alshazly H., Kumar A., Bourouis S., Kaur M. Design and simulation of ring network-on-chip for different configured nodes // Comput., Mater. Continua. 2022. V. 71, No 2. P. 4085–4100. https://doi.org/10.32604/cmc.2022.023017.
3. Bjerregaard T., Mahadevan S. A survey of research and practices of network-on-chip // ACM Comput. Surv. 2006. V. 38, No 1. P. 1–51. https://doi.org/10.1145/1132952.1132953.
4. Deng Y., Guo M., Ramos A.F., Huang X., Xu Z., Liu W. Optimal low-latency network topologies for cluster performance enhancement // J. Supercomput. 2020. V. 76, No 12. P. 9558–9584. https://doi.org/10.1007/s11227-020-03216-y.
5. Huang X., F. Ramos A., Deng Y. Optimal circulant graphs as low-latency network topologies // J. Supercomput. 2022. V. 78, No 11. P. 13491–13510. https://doi.org/10.1007/s11227-022-04396-5.
6. Belov A.V., Los A.B., Rozhkov M.I. Some classes of the MDS matrices over a finite field // Lobachevskii J. Math. 2017. V. 38, No 5. P. 880–883. https://doi.org/10.1134/S1995080217050067.
7. Monakhova E.A. A survey on undirected circulant graphs // Discrete Math., Algorithms Appl. 2012. V. 4, No 1. Art. 1250002. https://doi.org/10.1142/S1793830912500024.
8. Абросимов М.Б., Лось И.В., Костин С.В. Примитивные однородные графы с экспонентом 2 и числом вершин до 16 // Изв. Сарат. ун-та. Нов. сер. Сер. Матем. Механ. Информатика. 2021. Т. 21, № 2. С. 238–245.
9. El-Mesady A., Hamed Y.S., Shabana H. On the decomposition of circulant graphs using algorithmic approaches // Alexandria Eng. J. 2022. V. 61, No 10. P. 8263–8275. https://doi.org/10.1016/j.aej.2022.01.049.
10. Romanov A., Myachin N., Sukhov A. Fault-tolerant routing in networks-on-chip using self-organizing routing algorithms // IECON 2021 – 47th Annu. Conf. of the IEEE Industrial Electronics Society. IEEE. 2021. P. 1–6. https://doi.org/10.1109/IECON48115.2021.9589829.
11. Monakhova E.A., Monakhov O.G., Romanov A.Y. Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for networks-on-chip // IEEE Trans. Network Sci. Eng. 2022. V. 10, No 1. P. 413–425. https://doi.org/10.1109/TNSE.2022.3211985.
12. Sukhov A.M., Romanov A.Y. Serendipity: When research in one area leads to a positive result in another: [Электронный ресурс]. Режим доступа: https://cacm.acm.org/blogs/blog-cacm/270457-serendipity-when-research-in-one-area-leads-to-a-positive-result-in-another/fulltext, свободный. Проверено 17.10.2023.
13. Das S., Karfa C., Biswas S. Formal modeling of network-on-chip using CFSM and its application in detecting deadlock // IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 2020. V. 28, No 4. P. 1016–1029. https://doi.org/10.1109/TVLSI.2019.2959618.
14. Montanana J.M., de Andres D., Tirado F. Fault tolerance on NoCs // 2013 27th Int. Conf. on Advanced Information Networking and Applications Workshops. IEEE. 2013. P. 138–143. https://doi.org/10.1109/WAINA.2013.221.
15. Gabis A.B., Koudil M. NoC routing protocols – objective-based classification // J. Syst. Archit. 2016. V. 66–67. P. 14–32. https://doi.org/10.1016/j.sysarc.2016.04.011.
16. Radetzki M., Feng Ch., Zhao X., Jantsch A. Methods for fault tolerance in networks-on-chip // ACM Comput. Surv. 2013. V. 46, No 1. P. 1–38. https://doi.org/10.1145/2522968.2522976.
17. Nadeem M.F., Imran M., Afzal Siddiqui H.M., Azeem M. Fault tolerance designs of interconnection networks // Peer-to-Peer Networking Appl. 2023. V. 16, No 2. P. 1125–1134. https://doi.org/10.1007/s12083-023-01462-4.
18. Demin A., Shakhov O., Sukhov A. Coaxing performance from the complexity of HPC: [Электронный ресурс]. Режим доступа: https://cacm.acm.org/blogs/blog-cacm/275134-coaxing-performance-from-the-complexity-of-hpc/fulltext, свободный. – Проверено 17.10.2023.
19. Jerger N.D.E., Krishna T., Peh L.-S. On-Chip Networks. Ser.: Synthesis Lectures on Computer Architecture / Ed. by M. Martonosi. Morgan & Claypool, 2017. 190 p. https://doi.org/10.2200/S00772ED1V01Y201704CAC040.
20. Dai Y., Zhang Y. Adaptive digital twin for vehicular edge computing and networks // J. Commun. Inf. Networks. 2022. V. 7, No 1. P. 48–59. https://doi.org/10.23919/JCIN.2022.9745481.
Рецензия
Для цитирования:
Сухов А.М., Романов А.Ю., Глушак Е.В. Маршрутизация в циркулянтных графах на основе виртуальной координатной системы. Ученые записки Казанского университета. Серия Физико-математические науки. 2023;165(3):282-293. https://doi.org/10.26907/2541-7746.2023.3.282-293
For citation:
Sukhov A.M., Romanov A.Y., Glushak E.V. Routing in circulant graphs based on a virtual coordinate system. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2023;165(3):282-293. (In Russ.) https://doi.org/10.26907/2541-7746.2023.3.282-293
Просмотров:
1173
Послать статью по эл. почте 