Масштабируемый подход к кодизайну топологий и алгоритмов маршрутизации

Масштабируемый подход к кодизайну топологий и алгоритмов маршрутизации для семейств оптимальных циркулянтных сетей степени четыре

Монахов О. Г., Монахова Э. А.
Дискретный анализ и исследование операций, 32, 2, 88-106 (2025)
Скачать статью

УДК 519.176+519.8+519.7 
DOI: 10.33048/daio.2025.32.808

Аннотация:

В настоящей работе представлен новый подход к совместному конструированию топологий оптимальных по диаметру циркулянтных сетей $C(N; 1, s_{2})$ и реализуемых для них оптимальных алгоритмов маршрутизации сложности $O$(1). Новые алгоритмы маршрутизации основаны на использовании масштабируемых параметров $L$-образных шаблонов в плотной укладке графов на плоскости для семейств оптимальных сетей. Доказана масштабируемость параметров $L$-образных шаблонов для множества семейств оптимальных сетей $C(N; 1, s_{2})$. Получены аналитические формулы зависимости этих параметров от диаметра графов, сокращающие время настройки алгоритма маршрутизации на предварительном этапе с $O$(log $N$) до $O$(1). Сравнение нового алгоритма маршрутизации с известным в литературе оптимальным алгоритмом маршрутизации показывает его большую эффективность в среднем более чем на 10% по затратам времени на маршрутизацию в семействах оптимальных графов. Благодаря хорошей масштабируемости и простоте маршрутизации оптимальные циркулянтные сети степени четыре представляют интерес как эффективные и надёжные сети связи для сетей на кристалле, многопроцессорных суперкомпьютерных систем, телекоммуникационных сетевых структур и нейронных сетей связи. 

Табл. 1, ил. 6, библиогр. 20.

Литература:
  1. Hwang F. K. A survey on multi-loop networks // Theor. Comput. Sci. 2003. V. 299, No. 1–3. P. 107–121.
     
  2. Monakhova E. A. A survey on undirected circulant graphs // Discrete Math. Algorithms Appl. 2012. V. 4, No. 1. Article ID 1250002. 30 p.
     
  3. Huang X., Ramos A. F., Deng Y. Optimal circulant graphs as low-latency network topologies // J. Supercomput. 2022. V. 78, No. 11. P. 13491–13510.
     
  4. Monakhova E. A., Romanov A. Yu., Lezhnev E. V. Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for networks-on-chip // IEEE Access. 2020. V. 8. P. 215010–215019.
     
  5. Liu H., Li X., Wang S. Construction of dual optimal bidirectional doubleloop networks for optimal routing // Mathematics. 2022. V. 10. Article ID 4016. 17 p.
     
  6. Hoffmann R., Deserable D., Seredynski F. Cellular automata rules solving the wireless sensor network coverage problem // Natural Comput. 2022. V. 21. P. 417–447.
     
  7. Erickson A., Stewart I. A., Navaridas J., Kiasari A. E. The stellar transformation: From interconnection networks to data-center networks // Comput. Networks. 2017. V. 113. P. 29–45.
     
  8. Fei J., Lu C. Adaptive sliding mode control of dynamic systems using double loop recurrent neural network structure // IEEE Trans. Neural Netw. Learn. Syst. 2018. V. 29. P. 1275–1286.
     
  9. Monakhova E. A., Monakhov O. G., Romanov A. Yu. Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for networks-on-chip // IEEE Trans. Netw. Sci. Eng. 2023. V. 10, No. 1. P. 413–425.
     
  10. Deng Y., Guo M., Ramos A. F., Huang X., Xu Z., Liu W. Optimal lowlatency network topologies for cluster performance enhancement // J. Supercomput. 2020. V. 76, No. 12. P. 9558–9584.
     
  11. Monakhova E. A., Monakhov O. G. Optimal double loop networks or optimal circulant graphs ($N; 1, s$). Dataset. 2024. URL: github.com/mila0411/Double-loop-networks/tree/main/Dataset (accessed 23.07.2025).
     
  12. Beivide R., Herrada E., Balcazar J. L., Arruabarrena A. Optimal distance networks of low degree for parallel computers // IEEE Trans. Comput. 1991. V. 40, No. 10. P. 1109–1124.
     
  13. Jha P. K. Dimension-order routing algorithms for a family of minimaldiameter circulants // J. Interconnect. Netw. 2013. V. 14, No. 1. Article ID 1350002. 24 p.
     
  14. Chen B.-X., Meng J.-X., Xiao W.-J. A constant time optimal routing algorithm for undirected double-loop networks // Mobile ad-hoc and sensor networks. Proc. 1st Int. Conf. (Wuhan, China, Dec. 13–15, 2005). Heidelberg: Springer, 2005. P. 308–316. (Lect. Notes Comput. Sci.; V. 3794).
     
  15. Camarero C., Martinez C., Beivide R. $L$-networks: A topological model for regular two-dimensional interconnection networks // IEEE Trans. Comput. 2013. V. 62, No. 7. P. 1362–1375.
     
  16. Hwang F. K. A complementary survey on double-loop networks // Theor. Comput. Sci. 2001. V. 263, No. 1–2. P. 211–229.
     
  17. Fiol M. A., Yebra J. L. A., Alegre I., Valero M. A discrete optimization problem in local networks and data alignment // IEEE Trans. Comput. 1987. V. 36, No. 6. P. 702–713.
     
  18. Wong C. K., Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. Assoc. Comput. Mach. 1974. V. 21, No. 3. P. 392–402.
     
  19. Монахова Э. А., Монахов О. Г. Генерация и анализ датасета оптимальных двухконтурных циркулянтных сетей // Программная инженерия. 2024. Т. 15, № 8. С. 402–410.
     
  20. Монахова Э. А., Монахов О. Г. Анализ базы данных оптимальных двухконтурных кольцевых сетей // Прикл. дискрет. математика. 2024. № 64. С. 56–71.

Исследование выполнено за счёт бюджетного проекта Института вычислительной математики и математической геофизики (проект № FWNM–2022– 0005). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Монахов Олег Геннадьевич
  1. Институт вычислительной математики и математической геофизики, 
    пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия

E-mail: monakhov@rav.sscc.ru

Монахова Эмилия Анатольевна
  1. Институт вычислительной математики и математической геофизики, 
    пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия

E-mail: emilia@rav.sscc.ru

Статья поступила 19 июля 2024 г.
После доработки — 11 августа 2024 г.
Принята к публикации 22 сентября 2024 г.

Abstract:

This paper presents a new approach to the joint construction of topologies for diameter-optimal circulant networks $C(N; 1, s_{2})$ and optimal routing algorithms of complexity $O$(1) implemented for them. New routing algorithms are based on the use of scalable parameters of $L$-shaped patterns in a dense packing of graphs on the plane for families of optimal networks. The scalability of the parameters of $L$-shaped patterns for a set of families of optimal networks $C(N; 1, s_{2})$ is shown. We obtain analytical formulas for the dependence of these parameters on the graph diameter, reducing the time for setting up the routing algorithm at the preliminary stage from $O$(log $N$) to $O$(1). A comparison of the new routing algorithm with the optimal one known in the literature demonstrates its greater efficiency, on average, by more than 10% in terms of routing time in families of optimal graphs. Due to their good scalability and ease of routing, optimal degree-four circulant networks are of interest as efficient and reliable communication networks for networks-on-chip, multiprocessor supercomputer systems, telecommunications network structures, and neural communication networks. 

Tab. 1, illustr. 6, bibliogr. 20.

References:
  1. F. K. Hwang, A survey on multi-loop networks, Theor. Comput. Sci. 299 (1–3), 107–121 (2003).
     
  2. E. A. Monakhova, A survey on undirected circulant graphs, Discrete Math. Algorithms Appl. 4 (1), ID 1250002 (2012).
     
  3. X. Huang, A. F. Ramos, and Y. Deng, Optimal circulant graphs as lowlatency network topologies, J. Supercomput. 78 (11), 13491–13510 (2022).
     
  4. E. A. Monakhova, A. Yu. Romanov, and E. V. Lezhnev, Shortest path search algorithm in optimal two-dimensional circulant networks: Implementation for networks-on-chip, IEEE Access 8, 215010–215019 (2020). 
     
  5. H. Liu, X. Li, and S. Wang, Construction of dual optimal bidirectional double-loop networks for optimal routing, Mathematics 10, ID 4016 (2022).
     
  6. R. Hoffmann, D. Deserable, and F. Seredynski, Cellular automata rules solving the wireless sensor network coverage problem, Natural Comput. 21, 417–447 (2022).
     
  7. A. Erickson, I. A. Stewart, J. Navaridas, and A. E. Kiasari, The stellar transformation: From interconnection networks to data-center networks, Comput. Netw. 113, 29–45 (2017).
     
  8. J. Fei and C. Lu, Adaptive sliding mode control of dynamic systems using double loop recurrent neural network structure, IEEE Trans. Neural Netw. Learn. Syst. 29, 1275–1286 (2018).
     
  9. E. A. Monakhova, O. G. Monakhov, and A. Yu. Romanov, Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for networks-on-chip, IEEE Trans. Netw. Sci. Eng. 10 (1), 413–425 (2023).
     
  10. Y. Deng, M. Guo, A. F. Ramos, X. Huang, Z. Xu, and W. Liu, Optimal low-latency network topologies for cluster performance enhancement, J. Supercomput. 76 (12), 9558–9584 (2020).
     
  11. E. A. Monakhova and O. G. Monakhov, Optimal double loop networks or optimal circulant graphs ($N; 1, s$). Dataset (2024), URL: github.com/mila0411/Double-loop-networks/tree/main/Dataset (accessed 23.07.2025). 
     
  12. R. Beivide, E. Herrada, J. L. Balcazar, and A. Arruabarrena, Optimal distance networks of low degree for parallel computers, IEEE Trans. Comput. 40 (10), 1109–1124 (1991).
     
  13. P. K. Jha, Dimension-order routing algorithms for a family of minimaldiameter circulants, J. Interconnect. Netw. 14 (1), ID 1350002 (2013).
     
  14. B.-X. Chen, J.-X. Meng, and W.-J. Xiao, A constant time optimal routing algorithm for undirected double-loop networks, in Mobile Ad-Hoc and Sensor Networks (Proc. 1st Int. Conf., Wuhan, China, Dec. 13–15, 2005) (Springer, Heidelberg, 2005), pp. 308–316 (Lect. Notes Comput. Sci., Vol. 3794).
     
  15. C. Camarero, C. Martinez, and R. Beivide, $L$-networks: A topological model for regular two-dimensional interconnection networks, IEEE Trans. Comput. 62 (7), 1362–1375 (2013).
     
  16. F. K. Hwang, A complementary survey on double-loop networks, Theor. Comput. Sci. 263 (1–2), 211–229 (2001).
     
  17. M. A. Fiol, J. L. A. Yebra, I. Alegre, and M. Valero, A discrete optimization problem in local networks and data alignment, IEEE Trans. Comput. 36 (6), 702–713 (1987).
     
  18. C. K. Wong and D. Coppersmith, A combinatorial problem related to multimodule memory organizations, J. Assoc. Comput. Mach. 21 (3), 392–402 (1974).
     
  19. E. A. Monakhova and O. G. Monakhov, Generation and analysis of a dataset of optimal double-loop circulant networks, Program. Inzh. 15 (8), 402–410 (2024) [Russian].
     
  20. E. A. Monakhova and O. G. Monakhov, Database analysis of optimal double-loop networks, Prikl. Diskretn. Mat., No. 64, 56–71 (2024) [Russian].