Geodesic
Routing in circulant graphs based on a virtual coordinate system
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 165 (2023) no. 3, pp. 282-293
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

This article explores routing methods in two-dimensional circulant graphs where each vertex is linked to four neighboring ones. The unique symmetries of the circulant graph make it a viable topology for high-performance computing devices, such as networks-on-chip and cluster supercomputers. It was shown that the coordinates of the vertices can be determined as the minimum number of transitions along the generators from the initial vertex. Two virtual coordinate-based routing methods were developed. The first method entails restoring the vertex numbers and finding the difference between them, with the coordinates of the corresponding vertex setting the route. The second method involves calculating the difference between the final and initial vertex coordinates, while minimizing the route based on the proposed algorithm.
Mots-clés : сirculant graph
Keywords: network-on-chip, supercomputer cluster, virtual coordinate-based routing. 
@article{UZKU_2023_165_3_a7,
     author = {A. M. Sukhov and A. Y. Romanov and E. V. Glushak},
     title = {Routing in circulant graphs based on a virtual coordinate system},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {282--293},
     year = {2023},
     volume = {165},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2023_165_3_a7/}
}
TY  - JOUR
AU  - A. M. Sukhov
AU  - A. Y. Romanov
AU  - E. V. Glushak
TI  - Routing in circulant graphs based on a virtual coordinate system
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2023
SP  - 282
EP  - 293
VL  - 165
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2023_165_3_a7/
LA  - ru
ID  - UZKU_2023_165_3_a7
ER  - 
%0 Journal Article
%A A. M. Sukhov
%A A. Y. Romanov
%A E. V. Glushak
%T Routing in circulant graphs based on a virtual coordinate system
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2023
%P 282-293
%V 165
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2023_165_3_a7/
%G ru
%F UZKU_2023_165_3_a7
A. M. Sukhov; A. Y. Romanov; E. V. Glushak. Routing in circulant graphs based on a virtual coordinate system. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 165 (2023) no. 3, pp. 282-293. http://geodesic.mathdoc.fr/item/UZKU_2023_165_3_a7/

[1] J. A. Kahle, J. Moreno, D. Dreps, “2.1 Summit and Sierra: Designing AI/HPC supercomputers”, 2019 IEEE Int. Solid-State Circuits Conf. (ISSCC), IEEE, 2019, 42–43 | DOI

[2] A. Jain, R. K. Dwivedi, H. Alshazly, A. Kumar, S. Bourouis, M. Kaur, “Design and simulation of ring network-on-chip for different configured nodes”, Comput., Mater. Continua, 71:2 (2022), 4085–4100 | DOI

[3] T. Bjerregaard, S. Mahadevan, “A survey of research and practices of network-on-chip”, ACM Comput. Surv, 38:1 (2006), 1–51 | DOI

[4] Y. Deng, M. Guo, A. F. Ramos, X. Huang, Z. Xu, W. Liu, “Optimal low-latency network topologies for cluster performance enhancement”, J. Supercomput, 76:12 (2020), 9558–9584 | DOI

[5] X. Huang, F. Ramos A., Y. Deng, “Optimal circulant graphs as low-latency network topologies”, J. Supercomput, 78:11 (2022), 13491–13510 | DOI

[6] A. V. Belov, A. B. Los, M. I. Rozhkov, “Some classes of the MDS matrices over a finite field”, Lobachevskii J. Math, 38:5 (2017), 880–883 | DOI | MR | Zbl

[7] E. A. Monakhova, “A survey on undirected circulant graphs”, Discrete Math., Algorithms Appl., 4:1 (2012), 1250002 | DOI | MR | Zbl

[8] M. B. Abrosimov, I. V. Los, S. V. Kostin, “Primitivnye odnorodnye grafy s ekspo nentom 2 i chislom vershin do 16”, Izv. Sarat. un-ta. Nov. ser. Ser. Matem. Mekhan. Informatika, 21:2 (2021), 238–245 | MR | Zbl

[9] A. El-Mesady, Y. S. Hamed, H. Shabana, “On the decomposition of circulant graphs using algorithmic approaches”, Alexandria Eng. J., 61:10 (2022), 8263–8275 | DOI

[10] A. Romanov, N. Myachin, A. Sukhov, “Fault-tolerant routing in networks-on-chip using self organizing routing algorithms”, IECON 2021 47th Annu. Conf. of the IEEE Industrial Electronics Society, IEEE, 2021, 1–6 | DOI

[11] E. A. Monakhova, O. G. Monakhov, A. Y. Romanov, “Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for networks-on-chip”, IEEE Trans. Network Sci. Eng, 10:1 (2022), 413–425 | DOI | MR

[12] A. M. Sukhov, A. Y. Romanov, Serendipity: When research in one area leads to a positive result in another (svobodnyi. Provereno 17.10.2023) https://cacm.acm.org/blogs/blog-cacm/270457-serendipity-when-research-in-one-area-leads-to-a-positive-result-in-another/fulltext

[13] S. Das, C. Karfa, S. Biswas, “Formal modeling of network-on-chip using CFSM and its application in detecting deadlock”, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 28:4 (2020), 1016–1029 | DOI

[14] J. M. Montanana, D. de Andres, F. Tirado, “Fault tolerance on NoCs”, 2013 27th Int. Conf. on Advanced Information Networking and Applications Workshops, IEEE, 2013, 138–143 | DOI

[15] A. B. Gabis, M. Koudil, “NoC routing protocols objective-based classification”, J. Syst. Archit, 66-67 (2016), 14–32 | DOI

[16] M. Radetzki, Ch. Feng, X. Zhao, A. Jantsch, “Methods for fault tolerance in networks-on chip”, ACM Comput. Surv, 46:1 (2013), 1–38 | DOI

[17] M. F. Nadeem, M. Imran, H. M. Afzal Siddiqui, M. Azeem, “Fault tolerance designs of interconnection networks”, Peer-to-Peer Networking Appl, 16:2 (2023), 1125–1134 | DOI

[18] A. Demin, O. Shakhov, A. Sukhov, Coaxing performance from the complexity of HPC (svobodnyi. Provereno 17.10.2023) https://cacm.acm.org/blogs/blog-cacm/275134-coaxing-performance-from-the-complexity-of-hpc/fulltext

[19] N. D.E. Jerger, T. Krishna, L.-S. Peh, On-Chip Networks, Synthesis Lectures on Computer Architecture, ed. M. Martonosi, Morgan Claypool, 2017, 190 pp. | DOI

[20] Y. Dai, Y. Zhang, “Adaptive digital twin for vehicular edge computing and networks”, J. Commun. Inf. Networks, 7:1 (2022), 48–59 | DOI | MR