ПОСТРОЕНИЕ И ОПТИМИЗАЦИЯ ТОПОЛОГИЧЕСКИХ СТРУКТУР РЕГУЛЯРНЫХ СЕТЕЙ С ПАРАМЕТРИЧЕСКИМ ОПИСАНИЕМ

EDN: MNWAGY

Рассмотрены алгоритмы построения и оптимизации перспективных классов топологических структур — параметрически задаваемых регулярных графов (R графов). Предложена новая модель топологий сетей связи для многопроцессорных систем и сетей на кристалле — класс многоуровневых параметрически задаваемых регулярных MR сетей (MR графов). В данной работе в качестве элементов построения при генерации многоуровневых сетей рассмотрены параметрически задаваемые регулярные графы, имеющие компактное параметрическое описание с периодической симметрией, которые объединяются с помощью предложенной ранее авторами операции многоуровневой композиции графов. При синтезе многоуровневых сетей разработан и применен алгоритм дифференциальной эволюции для определения оптимальных параметров генерируемой топологии, минимизирующих среднее расстояние сети при заданных числе узлов, степени узлов, числе классов симметрии и числе уровней. Алгоритм синтеза оптимальных сетей разработан с помощью больших языковых моделей и реализован на процессоре Kunpeng 920. Показано, что построенные обычные и многоуровневые R сети имеют лучшие структурные характеристики, чем циркулянтные сети и многоуровневые циркулянтные сети при одинаковых затратах оборудования (количестве узлов и линий связи).

Работа выполнена при финансовой поддержке бюджетным проектом ИВМ и МГ СО РАН (код проекта FWNM-2025-0005).

Список литературы

1. Монахов О. Г. Параметрическое описание структур однородных вычислительных систем // В кн.: Вопросы теории и построения вычислительных систем. (Вычислительные системы, вып. 80). Новосибирск, 1979. С. 3–17.
2. Monakhov O., Monakhova E. A Class of Parametric Regular Networks for Multicomputer Architectures // Computaci´on y Sistemas. 2000. Vol. 4. P. 85–93.
3. Huang X., Ramos A. F., Deng Y. Optimal circulant graphs as low-latency network topologies // Journal of Supercomputing. 2022. Vol. 78. P. 13491–13510. DOI 10.1007/s11227-022-04396-5.
4. Deng Y., Guo M., Ramos A. F., Huang X., Xu Z., Liu W. Optimal low-latency network topologies for cluster performance enhancement // Journal of Supercomputing. 2020. Vol. 76, № 12. P. 9558–9584.
5. Monakhov O., Monakhova E. Construction of Multi-level Regular Networks Based on the Operation of Composition of Circulant Graphs // Mathematical Modeling and Supercomputer Technologies. MMST 2025. Communications in Computer and Information Science. Vol. 2815. Cham: Springer, 2026. DOI 10.1007/978-3-032-15761-4.
6. Монахов О. Г., Монахова Э. А. Генерация многоуровневых регулярных сетей на основе операции композиции модифицированных хордальных графов с использованием больших языковых моделей // Проблемы информатики. 2025. № 4. С. 38–51. DOI 10.24412/2073-0667-2025-438-51.
7. Kivela M., Arenas A., Barthelemy M., Gleeson J. P., Moreno Y., Porter M. Multilayer Networks // Journal of Complex Networks. 2014. Vol. 2, № 3. P. 203–271. DOI 10.1093/comnet/cnu016.
8. Кальней А. М. Модели многоуровневых сетей (краткий обзор) // Проблемы информатики. 2021. № 3. С. 5–20. DOI 10.24412/2073-0667-2021-3-5-20.
9. Кальней А. М., Родионов А. С. Анализ надежности многоуровневых сетей с ненадежными вершинами // Проблемы информатики. 2020. № 2. С. 5–15. DOI 10.24411/2073-0667-2020-10005.
10. Monakhova E. A Survey on Undirected Circulant Graphs // Discrete Mathematics, Algorithms and Applications. 2012. Vol. 4, № 1. Article 1250002.
11. Ledzinski D., Smigiel S., Zabludowski L. Analyzing methods of network topologies based on chordal rings // Turkish Journal of Electrical Engineering and Computer Sciences. 2018. Vol. 26, № 3. Article 25.
12. Krnc M., Wilson R. Recognizing generalized Petersen graphs in linear time // Discrete Applied Mathematics. 2020. Vol. 283. P. 756–761. DOI 10.1016/j.dam.2020.03.007.
13. Storn R., Price K. Differential Evolution — A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces // Journal of Global Optimization. 1997. Vol. 11, № 4. P. 341– 359.
14. Монахов О. Г., Монахова Э. А. База данных оптимальных циркулянтных сетей степени четыре с единичной образующей. [Электрон. Рес.]: https://github.com/mila0411/Double-loop- networks/tree/main/Dataset (дата обращения 29.04.2026).