Том 29, номер 4, 2022 г., Стр. 59-76

УДК 519.176
Монахова Э. А., Монахов О. Г.
Построение серий семейств циркулянтных сетей степени шесть

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

Ключевые слова: семейство циркулянтных сетей степени шесть, диаметр, экстремальный циркулянтный граф степени шесть, сеть на кристалле.

DOI: 10.33048/daio.2022.29.743

Монахова Эмилия Анатольевна ¹
Монахов Олег Геннадьевич ¹
1. Институт вычислительной математики и математической геофизики СО РАН,
пр. Акад. Лаврентьева, 6, 630090 Новосибирск, Россия
е-mail: emilia@rav.sscc.ru, monakhov@rav.sscc.ru

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

Литература

[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.