ГлавнаяАрхивАнализ базы данных оптимальных двухконтурных кольцевых сетей

Анализ базы данных оптимальных двухконтурных кольцевых сетей | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/5

Оптимальные циркулянтные сети вызывают практический интерес как модели надёжных с низкой задержкой сетей связи мультипроцессорных кластерных систем и сетей на кристалле. Авторами впервые построена большая база данных (дата-сет) оптимальных по диаметру двухконтурных кольцевых циркулянтных сетей до 50 тысяч узлов, содержащая полный набор образующих оптимальных графов. Проведён анализ датасета с целью исследования проблемы поиска аналитически задаваемых семейств оптимальных графов. Разработаны два новых алгоритма автоматизированного поиска аналитических, описываемых полиномами от диаметра, описаний семейств оптимальных графов. С помощью реализованных алгоритмов найдено большое количество новых аналитически описываемых семейств оптимальных сетей, проверенное с помощью валидации на всём диапазоне изменения диаметров графов датасета. Найденные семейства оптимальных сетей могут быть использованы при масштабировании алгоритмов передачи информации в двухконтурных кольцевых циркулянтных структурах.
  • Title Анализ базы данных оптимальных двухконтурных кольцевых сетей
  • Headline Анализ базы данных оптимальных двухконтурных кольцевых сетей
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 64
  • Date:
  • DOI 10.17223/20710410/64/5
Ключевые слова
дата сет оптимальных сетей, неориентированные двухконтурные кольцевые сети, циркулянтные сети, минимальный диаметр
Авторы
Ссылки
Bermond J.-C., Cornelias F., and Hsu D. F. Distributed loop computer networks: a survey //j. Parallel Distrib.Comput. 1995. No. 24(1). P. 2-10.
Hwang F.K. A survey on multi-loop networks // Theoret.Comput. Sci. 2003. V. 299. P.107-121.
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. УЗ. С.92-115.
Huang X., Ramos A. F., and Deng Y. Optimal circulant graphs as low-latency network topologies //j. Supercomput. 2022. V. 78. P. 13491-13510.
Chen B.-X., Meng J.-X., and Xiao W.-J. Some new optimal and suboptimal infinite families of undirected double-loop networks // Discrete Math. Theor.Comput. Sci. 2006. V. 8. P.299-311.
Romanov A. Y. Development of routing algorithms in networks-on-chip based on ring circulant topologies // Helivon. 2019. V. 5. Iss.4. Article e01516.
Chen B.-X., Xiao W.-J., and Parhami B. Diameter formulas for a class of undirected doubleloop networks // Networks. 2005. V. 6(1). P. 1-15.
Jha К. P. Tight-optimal circulants vis-a-vis twisted tori // Discrete Appl. Math. 2014. V. 175. P. 24-34.
Huanping L. and Yixian Y.-J. On the fault-tolerant routing in distributed loop networks //j. Electronics. 2000. V. 17. P. 84-89.
Bian Q.-F., Hang T., Liu H., and Fang M. Research on the diameter and average diameter of undirected double-loop networks // Int. Conf. Grid Cloud Computing. Naniang, Jiangsu China, 2010. P.461-466.
Martinez C., Beivide R., Stafford E., et al. Modeling toroidal networks with the Gaussian integers // IEEE Trans.Comput. 2008. V.57. No. 8. P.1046-1056.
Monakhova E. A., Monakhov O. G., and 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.
Perez-Roses Н., Bras-Amoros М., and Seradilla-Merinero J. М. Greedy routing in circulant networks // Graphs Combinatorics. 2022. V. 38. Article 86.
Lewis R. R. Analysis and Construction of Extremal Circulant and Other Abelian Cayley Graphs. Ph.D. Thesis. The Open University, London, UK, 2022.
Pai K.-J., Yang J.-S., Chen G.-Y., and Chang J.-M. Configuring protection routing via completely independent spanning trees in dense Gaussian on-chip networks // IEEE Trans.Netw. ScL Eng. 2022. V.9. No. 2. P.932-946.
Monakhov O. G., Monakhova E. A., Romanov A. Y., et al. Adaptive dynamic shortest path search algorithm in networks-on-chip based on circulant topologies // IEEE Access. 2021. V. 9. P. 160836-160846.
Мопахова Э.А. Об аналитическом описании оптимальных двумерных диофантовых структур однородных вычислительных систем // Вычислительные системы. 1981. №90. С.81-91.
Boesch F. and Wang J.-F. Reliable circulant networks with minimum transmission delay // IEEE Trans. Circuits Svst. 1985. V. 32. No. 12. P. 1286-1291.
Tzvieli D. Minimal diameter double-loop networks. 1. Large infinite optimal families // Networks. 1991. V.21. P.387-415.
Liu H., Li X., and Wang S. Construction of dual optimal bidirectional double-loop networks for optimal routing // Mathematics. 2022. V. 10. Article 4016.
Monakhova E. A., Romanov A. Y., and 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.
Монахова Э. А. Синтез оптимальных диофантовых структур // Вычислительные системы. 1979. №80. С. 18-35.
Du D.-Z., Hsu D. F., Li Q., and Xu J. A combinatorial problem related to distributed loop networks // Networks. 1990. V.20. P.173-180.
Li Y., Chen Y., Tai W., and Wang R. The minimum distance diagram and diameter of undirected double-loop networks // Proc. ICMEMTC. Taiyuan, China, 2016. P.1682-1687.
Loudiki L., Kchikech M., and Essaky E. H. A New Approach for Computing the Distance and the Diameter in Circulant Graphs, https://arxiv.org/abs/2210.11116. 2022.
Jha P. K. Dense bipartite circulants and their routing via rectangular twisted torus // Discrete Appl. Math. 2014. V. 166. P. 141-158.
Jha P. K. and Smith J. D. H. Cycle Kronecker products that are representable as optimal circulants // Discrete Appl. Math. 2015. V. 181. P. 130-138.
Liu H., Yang Y., and Hu M. Tight optimal infinite families of undirected double-loop networks // Systems Eng. Theory Practice. 2002. V. 1. P. 75-79.
Jha P. K. Dimension-order routing algorithms for a family of minimal-diameter circulants //j.Interconn.Networks. 2013. V. 14. No. 1. Article 1350002. 24p.
Bermond J.-C. and Tzvieli D. Minimal diameter double-loop networks: Dense optimal families // Networks. 1991. V.21. P. 1-9.
Chen B.-X., Meng J.-X., and Xiao W.-J. A constant time optimal routing algorithm for undirected double-loop networks // LNCS. 2005. V.3794. P.308-316.
Monakhova E. A. Optimal circulant computer networks // Proc. PaCT'91. Novosibirsk, USSR, 1991. P.450-458.
Монахова Э. А., Монахов О. Г. Эволюционный синтез семейств оптимальных двумерных циркулянтных сетей j j Вестник СибГУТII. 2014. №2. С. 72-81.
Zerovnik J. and Pisanski T.Computing the diameter in multiple-loop networks //j. Algorithms. 1993. V. 14. P.226-243.
Romanov A. The dataset for optimal circulant topologies // Big Data Cogn.Comput. 2023. V. 7. P. 80.
Monakhova E. A. and Monakhov O. G. Generation and analysis of optimal double-loop circulant networks dataset // Proc. CEUR Workshop SibDATA. 2023. (to be published).
Storn R. and Price K. Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces //j. Global Optimization. 1997. V. 11. P.341-359.
Zaheer H., Pant M., Monakhov O., and Monakhova E. Simple and efficient co-operative approach for solving multi modal problems // Proc. ICEEOT. Chennai, Tamilnadu, India, 2016. P.731-737.
Анализ базы данных оптимальных двухконтурных кольцевых сетей | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/5
Анализ базы данных оптимальных двухконтурных кольцевых сетей | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/5