Поиск и исследование идеальных двумерных циркулянтных сетей на основе графовых баз данных

Поиск и исследование идеальных двумерных циркулянтных сетей на основе графовых баз данных

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

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

Аннотация:

На основе анализа больших массивов экспериментальных данных исследуется проблема поиска идеальных двумерных кольцевых циркулянтных сетей, оптимальных по двум параметрам — диаметру и среднему расстоянию. Ранее авторами был получен большой датасет (база данных) оптимальных по диаметру двумерных кольцевых циркулянтных сетей. В настоящей работе получен новый датасет рассматриваемых сетей, оптимальных по среднему расстоянию. Исследование графов указанных датасетов позволило вывести новые свойства соотношений диаметра и среднего расстояния в оптимальных циркулянтах и получить семейства наилучших по двум параметрам оптимальных циркулянтных сетей, для которых применим настраиваемый по числу узлов эффективный алгоритм маршрутизации константной сложности. Идеальные двумерные кольцевые циркулянты представляют интерес как эффективные и надёжные топологии для межузловых связей в сетях на кристалле и информационно-коммуникационных системах. 

Ил. 6, библиогр. 27.

Литература:
  1. Huang X., Ramos A. F., Deng Y. Optimal circulant graphs as low-latency network topologies // J. Supercomputing. 2022. V. 78, No. 11. P. 13491–13510. DOI: 10.1007/s11227-022-04396-5.
     
  2. 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. DOI: 10.3390/math10214016.
     
  3. Hoffmann R., Deserable D., Seredynski F. Cellular automata rules solving the wireless sensor network coverage problem // Nat. Comput. 2022. V. 21. P. 417–447.
     
  4. 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.
     
  5. Ledziński D., Bujnowski S., Marciniak T., Pedersen J. M., Gutierrez Lopez J. M. Networks structures constructed on basis of chordal rings 4th degree // Image processing and communications challenges 5. Proc. 5th Int. Conf. (Bydgoszcz, Poland, Sept. 11–13, 2013). Cham: Springer, 2014. P. 281–299. (Adv. Intell. Syst. Comput.; V. 233). DOI: 10.1007/978-3-319-01622-1_33.
     
  6. Martínez C., Vallejo E., Beivide R., Izu C., Moretó M. Dense Gaussian networks: Suitable topologies for on-chip multiprocessors // Int. J. Parallel Program. 2006. V. 34, No. 3. P. 193–211. DOI: 10.1007/s10766-006-0014-1.
     
  7. Bermond J.-C., Comellas F., Hsu D. F. Distributed loop computer networks: A survey // J. Parallel Distrib. Comput. 1995. V. 24, No. 1. P. 2–10. DOI: 10.1006/jpdc.1995.1002.
     
  8. Hwang F. K. A survey on multi-loop networks // Theor. Comput. Sci. 2003. V. 299, No. 1–3. P. 107–121.
     
  9. Monakhova E. A. A survey on undirected circulant graphs // Discrete Math. Algorithms Appl. 2012. V. 4, No. 1. Article ID 1250002. 30 p.
     
  10. Deng Y., Guo M., Ramos A. F., Huang X., Xu Z., Liu W. Optimal lowlatency network topologies for cluster performance enhancement // J. Supercomputing. 2020. V. 76, No. 12. P. 9558–9584.
     
  11. Monakhova E. A., Monakhov O. G. Double-loop-networks. Datasets of optimal double loop networks or optimal circulant graphs (N; 1, s). 2024. github.com/mila0411/Double-loop-networks (accessed: 29.08.2025). 
     
  12. Монахова Э. А., Монахов О. Г. Анализ базы данных оптимальных двухконтурных кольцевых сетей // Прикл. дискрет. математика. 2024. № 64. С. 56–71.
     
  13. Tzvieli D. Minimal diameter double-loop networks. I. Large infinite optimal families // Networks. 1991. V. 21, No. 4. P. 387–415.
     
  14. Bermond J.-C., Illiades G., Peyrat C. An optimization problem in distributed loop computer networks // Ann. New York Acad. Sci. 1989. V. 555, No. 1. P. 45–55.
     
  15. Browne R. F., Hodgson R. M. Symmetric degree-four chordal ring networks // IEE Proc. Ser. E. 1990. V. 137, No. 4. P. 310–318.
     
  16. Bian Q.-F., Hang T., Liu H., Fang M. Research on the diameter and average diameter of undirected double-loop networks // Proc. 9th Int. Conf. Grid and Cloud Computing (Nanjing, China, Nov. 1–5, 2010). Los Alamitos: IEEE Comput. Soc., 2010. P. 461–466.
     
  17. Корнеев В. В. О макроструктуре однородных вычислительных систем // Вычислительные системы. Вып. 60. Вопросы теории и построения вычислительных систем. Новосибирск: ИМ СО АН СССР, 1974. С. 17–34.
     
  18. Wong C. K., Coppersmith D. A combinatorial problem related to multimodule memory organizations // J. ACM. 1974. V. 21, No. 3. P. 392–402.
     
  19. Lewis R. R. Distance partitions of extremal and largest known circulant graphs of degree 2 to 9. Ithaca, NY, 2014. 22 p. (e-Print Archive / Cornell Univ.; arXiv:1408.0988).
     
  20. Boesch F., Wang J.-F. Reliable circulant networks with minimum transmission delay // IEEE Trans. Circuits Syst. 1985. V. 32, No. 12. P. 1286–1291.
     
  21. Romanov A. Yu. The dataset for optimal circulant topologies // Big Data Cogn. Comput. 2023. V. 7, No. 2. Article ID 80. 14 p.
     
  22. Монахов О. Г., Монахова Э. А. Масштабируемый подход к кодизайну топологий и алгоритмов маршрутизации для семейств оптимальных циркулянтных сетей степени четыре // Дискрет. анализ и исслед. операций. 2025. Т. 32, № 2. С. 88–106.
     
  23. Fiol M. À., Yebra J. L. A., Alegre I., Valero M. A discrete optimization problem in local networks and data alignment // IEEE Trans. Comput. 1987. V. C-36, No. 6. P. 702–713.
     
  24. Hwang F. K. A complementary survey on double-loop networks // Theor. Comput. Sci. 2001. V. 263, No. 1–2. P. 211–229.
     
  25. 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.
     
  26. 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.
     
  27. 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).

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

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

E-mail: emilia@rav.sscc.ru 

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

E-mail: monakhov@rav.sscc.ru 

Статья поступила 29 ноября 2024 г.
После доработки — 21 декабря 2024 г.
Принята к публикации 22 марта 2025 г.

Abstract:

Based on analysis of large arrays of experimental data, the problem of finding ideal two-dimensional ring circulant networks optimal with respect to two parameters, diameter and average distance, is investigated. Previously, the authors obtained a large dataset (database) of two-dimensional ring circulant networks that are optimal with respect to diameter. In this paper, a new dataset of the considered networks that are optimal with respect to average distance is obtained. The study of the graphs of these datasets allowed us to derive new properties of the ratios of diameter and average distance in optimal circulants and to obtain families of the best optimal circulant networks with respect to two parameters, for which an efficient routing algorithm of constant complexity, adjustable by the number of nodes, is applicable. Ideal two-dimensional ring circulants are of interest as efficient and reliable topologies for inter-node connections in networks on a chip and information and communication systems. 

Illustr. 6, bibliogr. 27.

References:
  1. X. Huang, A. F. Ramos, and Y. Deng, Optimal circulant graphs as lowlatency network topologies, J. Supercomputing 78 (11), 13491–13510 (2022), DOI: 10.1007/s11227-022-04396-5.
     
  2. H. Liu, X. Li, and S. Wang, Construction of dual optimal bidirectional double-loop networks for optimal routing, Mathematics 10, ID 4016 (2022), DOI: 10.3390/math10214016.
     
  3. R. Hoffmann, D. Deserable, and F. Seredynski, Cellular automata rules solving the wireless sensor network coverage problem, Nat. Comput. 21, 417–447 (2022).
     
  4. 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).
     
  5. D. Ledziński, S. Bujnowski, T. Marciniak, J. M. Pedersen, and J. M. Gutierrez Lopez, Networks structures constructed on basis of chordal rings 4th degree, in Image Processing and Communications Challenges 5, Proc. 5th Int. Conf. (Bydgoszcz, Poland, Sept. 11–13, 2013) (Springer, Cham, 2014), pp. 281–299 (Adv. Intell. Syst. Comput., Vol. 233), DOI: 10.1007/ 978-3-319-01622-1_33.
     
  6. C. Martínez, E. Vallejo, R. Beivide, C. Izu, and M. Moretó, Dense Gaussian networks: Suitable topologies for on-chip multiprocessors, Int. J. Parallel Program. 34 (3), 193–211 (2006), DOI: 10.1007/s10766-006-0014-1.
     
  7. J.-C. Bermond, F. Comellas, and D. F. Hsu, Distributed loop computer networks: A survey, J. Parallel Distrib. Comput. 24 (1), 2–10 (1995), DOI: 10.1006/jpdc.1995.1002.
     
  8. F. K. Hwang, A survey on multi-loop networks, Theor. Comput. Sci. 299 (1–3), 107–121 (2003).
     
  9. E. A. Monakhova, A survey on undirected circulant graphs, Discrete Math. Algorithms Appl. 4 (1), ID 1250002 (2012).
     
  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. Supercomputing 76 (12), 9558–9584 (2020).
     
  11. E. A. Monakhova and O. G. Monakhov, Double-loop-networks. Datasets of optimal double loop networks or optimal circulant graphs (N; 1, s) (2024), github.com/mila0411/Double-loop-networks (accessed: 29.08.2025). 
     
  12. E. A. Monakhova and O. G. Monakhov, Database analysis of optimal double-loop networks, Prikl. Diskretn. Mat., No. 64, 56–71 (2024) [Russian].
     
  13. D. Tzvieli, Minimal diameter double-loop networks. I. Large infinite optimal families, Networks 21 (4), 387–415 (1991).
     
  14. J.-C. Bermond, G. Illiades, and C. Peyrat, An optimization problem in distributed loop computer networks, Ann. New York Acad. Sci. 555 (1), 45–55 (1989).
     
  15. R. F. Browne and R. M. Hodgson, Symmetric degree-four chordal ring networks, IEE Proc, Ser. E, 137 (4), 310–318 (1990).
     
  16. Q.-F. Bian, T. Hang, H. Liu, and M. Fang, Research on the diameter and average diameter of undirected double-loop networks, in Proc. 9th Int. Conf. Grid and Cloud Computing (Nanjing, China, Nov. 1–5, 2010) (IEEE Comput. Soc., Los Alamitos, 2010), pp. 461–466.
     
  17. V. V. Korneev, On macrostructure of homogeneous computing systems, in Computing Systems, Vol. 60. Problems of Theory and Construction of Computing Systems (IM SO AN SSSR, Novosibirsk, 1974) [Russian], pp. 17–34.
     
  18. C. K. Wong and D. Coppersmith, A combinatorial problem related to multimodule memory organizations, J. ACM 21 (3), 392–402 (1974).
     
  19. R. R. Lewis, Distance partitions of extremal and largest known circulant graphs of degree 2 to 9 (Ithaca, NY, 2014) (e-Print Archive / Cornell Univ., arXiv:1408.0988).
     
  20. F. Boesch and J.-F. Wang, Reliable circulant networks with minimum transmission delay, IEEE Trans. Circuits Syst. 32 (12), 1286–1291 (1985).
     
  21. A. Yu. Romanov, The dataset for optimal circulant topologies, Big Data Cogn. Comput. 7 (2), ID 80 (2023).
     
  22. O. G. Monakhov and E. A. Monakhova, A scalable approach to co-design of topologies and routing algorithms for families of optimal degree-four circulant networks, Diskretn. Anal. Issled. Oper. 32 (2), 88–106 (2025) [Russian] [J. Appl. Ind. Math. 19 (2) (2025)].
     
  23. M. À. Fiol, J. L. A. Yebra, I. Alegre, and M. Valero, A discrete optimization problem in local networks and data alignment, IEEE Trans. Comput. C-36 (6), 702–713 (1987).
     
  24. F. K. Hwang, A complementary survey on double-loop networks, Theor. Comput. Sci. 263 (1–2), 211–229 (2001).
     
  25. P. K. Jha, Dimension-order routing algorithms for a family of minimaldiameter circulants, J. Interconnect. Netw. 14 (1), ID 1350002 (2013).
     
  26. 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).
     
  27. 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).