Построение серий семейств циркулянтных сетей степени шесть

Построение серий семейств циркулянтных сетей степени шесть

Монахова Э. А., Монахов О. Г.
Дискретный анализ и исследование операций, 29, 4, 59-76 (2022)
Скачать статью

УДК 519.176 
DOI: 10.33048/daio.2022.29.743

Аннотация:

Рассматривается решение проблемы построения серий семейств циркулянтных сетей степени шесть, задаваемых аналитически с помощью двух параметров, один из которых является диаметром сети. На основе анализа и обобщения свойств нового описания экстремального семейства циркулянтов построена общего вида серия семейств циркулянтных графов степени шесть произвольных диаметров, которая включает экстремальные циркулянтные графы степени шесть и новые бесконечные семейства циркулянтов с чётным числом вершин. В найденной серии семейств аналитически определены описания серии циркулянтных графов любого заданного диаметра. Алгоритмически выделены диапазоны оптимальности графов серии, где под оптимальным понимается циркулянтный граф степени шесть с минимально возможным диаметром для заданного числа вершин. Полученная серия семейств циркулянтных сетей перспективна как масштабируемая модель топологий для сетей на кристалле. 
Табл. 3, ил. 3, библиогр. 21.

Литература:
  1. Monakhova E. A. Series of families of degree six circulant graphs // Прикл. дискрет. математика. 2021. № 54. C. 109–124.
     
  2. Romanov A. Yu., Amerikanov A. A., Lezhnev E. V. Analysis of approaches for synthesis of networks-on-chip by using circulant topologies // J. Phys.: Conf. Ser. 2018. V. 1050, ID 012071. 12 p. 
     
  3. 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. 
     
  4. Monakhova E. A., Monakhov O. G., Romanov A. Yu., Lezhnev E. V. Analytical routing algorithm for networks-on-chip with the three-dimensional circulant topology // Proc. Moscow Workshop Electron. Netw. Technol. (Moscow, Russia, March 11–13, 2020). Moscow: Higher School of Economics, 2020. 6 p. 
     
  5. Hwang F. K. A survey on multi-loop networks // Theor. Comput. Sci. 2003. V. 299. P. 107–121. 
     
  6. Monakhova E. A. A survey on undirected circulant graphs // Discrete Math. Algorithms Appl. 2012. V. 4, No. 1, ID 1250002. 30 p. 
     
  7. Pérez-Rosés H., Bras-Amorós M., Serradilla-Merinero J. M. Greedy routing in circulant networks // Graphs Comb. 2022. V. 38, ID 86. 16 p. 
     
  8. 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. P. 193–211. 
     
  9. Martínez C., Vallejo E., Moretó M., Beivide R., Valero M. Hierarchical topologies for large-scale two-level networks // Actas XVI Jornadas Paralelismo (Granada, Spain, Sept. 13–16, 2005). Madrid: Paraninfo, 2005. P. 133–140.
     
  10. Monakhova E. Optimal triple loop networks with given transmission delay: Topological design and routing // Proc. Int. Network Optimization Conf. (Évry/Paris, France, Oct. 27–29, 2003). Évry: Inst. Natl. Télécommun., 2003. P. 410–415. 
     
  11. Dougherty R., Faber V. The degree-diameter problem for several varieties of Cayley graphs I: The abelian case // SIAM J. Discrete Math. 2004. V. 17, No. 3. P. 478–519. 
     
  12. Huang X., Ramos A. F., Deng Y. Optimal circulant graphs as low-latency network topologies // J. Supercomput. 2022. V. 78. P. 13491–13510.
     
  13. Lewis R. R. Analysis and construction of extremal circulant and other abelian Cayley graphs: PhD thes. London, 2021. 390 p. 
     
  14. Research problems // J. Comb. Theory. 1967. V. 2, No. 3. P. 393. 
     
  15. Göbel F., Neutel E. A. Cyclic graphs // Discrete Appl. Math. 2000. V. 99. P. 3–12. 
     
  16. Du D.-Z., Hsu D. F., Li Q., Xu J. A combinatorial problem related to distributed loop networks // Networks. 1990. V. 20, No. 2. P. 173–180. 
     
  17. Chen B.-X., Meng J.-X., 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–312. 
     
  18. Tzvieli D. Minimal diameter double-loop networks. I. Large infinite optimal families // Networks. 1991. V. 21, No. 4. P. 387–415. 
     
  19. Lewis R. R. The degree-diameter problem for circulant graphs of degree 8 and 9 // Electron. J. Comb. 2014. V. 21, No. 4, ID P4.50. P. 1–19. 
     
  20. Lewis R. R. The degree-diameter problem for circulant graphs of degrees 10 and 11 // Discrete Math. 2018. V. 341, No. 9. P. 2553–2566. 
     
  21. Dalfó C., Fiol M. A., Lopéz N., Ryan J. An improved Moore bound and some new optimal families of mixed abelian Cayley graphs // Discrete Math. 2020. V. 343, No. 10, ID 112034. 10 p.

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

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

E-mail: emilia@rav.sscc.ru

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

E-mail: monakhov@rav.sscc.ru

Статья поступила 1 июня 2022 г. 
После доработки — 19 июля 2022 г. 
Принята к публикации 26 июля 2022 г.

Abstract:

We consider a solution to the problem of constructing a series of families of circulant networks of degree six, specified analytically with the help of two parameters, one of which is the diameter of the network. Based on the analysis and generalization of the properties of a new description of an extremal family of circulants, a general series of families of circulant graphs of degree six of arbitrary diameters is constructed, which includes extremal circulant graphs of degree six and new infinite families of circulants with an even number of vertices. In the found series of families, descriptions of a series of circulant graphs of any given diameter are analytically defined. Optimality ranges of series graphs are algorithmically identified, where optimal is understood as a circulant graph of degree six with the minimum possible diameter for a given number of vertices. The resulting series of families of circulant networks is promising as a scalable topology model for networks on a chip. 
Tab. 3, illustr. 3, bibliogr. 21.

References:
  1. E. A. Monakhova, Series of families of degree six circulant graphs, Prikl. Diskretn. Mat., No. 54, 109–124 (2021).
     
  2. A. Yu. Romanov, A. A. Amerikanov, and E. V. Lezhnev, Analysis of approaches for synthesis of networks-on-chip by using circulant topologies, J. Phys.: Conf. Ser. 1050, ID 012071, 12 p. (2018).
     
  3. 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).
     
  4. E. A. Monakhova, O. G. Monakhov, A. Yu. Romanov, and E. V. Lezhnev, Analytical routing algorithm for networks-on-chip with the three-dimensional circulant topology, in Proc. Moscow Workshop Electron. Netw. Technol., Moscow, Russia, March 11–13, 2020 (Higher School of Economics, Moscow, 2020).
     
  5. F. K. Hwang, A survey on multi-loop networks, Theor. Comput. Sci. 299, 107–121 (2003).
     
  6. E. A. Monakhova, A survey on undirected circulant graphs, Discrete Math. Algorithms Appl. 4 (1), ID 1250002, 30 p. (2012).
     
  7. H. Pérez-Rosés, M. Bras-Amorós, and J. M. Serradilla-Merinero, Greedy routing in circulant networks, Graphs Comb. 38, ID 86, 16 p. (2022).
     
  8. 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, 193–211 (2006).
     
  9. C. Martínez, E. Vallejo, M. Moretó, R. Beivide, and M. Valero, Hierarchical topologies for large-scale two-level networks, in Actas XVI Jornadas Paralelismo, Granada, Spain, Sept. 13–16, 2005 (Paraninfo, Madrid, 2005), pp. 133–140.
     
  10. E. Monakhova, Optimal triple loop networks with given transmission delay: Topological design and routing, in Proc. Int. Network Optimization Conf., Évry/Paris, France, Oct. 27–29, 2003 (Inst. Natl. Télécommun., Évry, 2003), pp. 410–415.
     
  11. R. Dougherty and V. Faber, The degree-diameter problem for several varieties of Cayley graphs I: The abelian case, SIAM J. Discrete Math. 17 (3), 478–519 (2004).
     
  12. X. Huang, A. F. Ramos, and Y. Deng, Optimal circulant graphs as lowlatency network topologies, J. Supercomput. 78, 13491–13510 (2022).
     
  13. R. R. Lewis, Analysis and construction of extremal circulant and other abelian Cayley graphs, PhD thes. (London, 2021).
     
  14. Research problems, J. Comb. Theory. 2 (3), 393 (1967).
     
  15. F. Göbel and E. A. Neutel, Cyclic graphs, Discrete Appl. Math. 99, 3–12 (2000).
     
  16. D.-Z. Du, D. F. Hsu, Q. Li, and J. Xu, A combinatorial problem related to distributed loop networks, Networks 20 (2), 173–180 (1990).
     
  17. B.-X. Chen, J.-X. Meng, andW.-J. Xiao, Some new optimal and suboptimal infinite families of undirected double-loop networks, Discrete Math. Theor. Comput. Sci. 8, 299–312 (2006).
     
  18. D. Tzvieli, Minimal diameter double-loop networks. I. Large infinite optimal families, Networks 21 (4), 387–415 (1991).
     
  19. R. R. Lewis, The degree-diameter problem for circulant graphs of degree 8 and 9, Electron. J. Comb. 21 (4), ID P4.50, 1–19 (2014).
     
  20. R. R. Lewis, The degree-diameter problem for circulant graphs of degrees 10 and 11, Discrete Math. 341 (9), 2553–2566 (2018).
     
  21. C. Dalfó, M. A. Fiol, N. Lopéz, and J. Ryan, An improved Moore bound and some new optimal families of mixed abelian Cayley graphs, Discrete Math. 343 (10), ID 112034, 10 p. (2020).