A computation of the shortest paths in optimal two-dimensional circulant networks

E. A. Monakhova

Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 87-100.

Résumé

A family of tight optimal two-dimensional circulant networks designed by analytical formulas has a description of the form $C(N;d,d+1)$, where $N$ is the order of a graph and the generator $d$ is the nearest integer to $(\sqrt {2N-1}-1)/2$. For this family, two new improved versions of a shortest-path routing algorithm with a complexity $O(1)$ are presented. Simple proofs for formulas used for routing algorithms based on the plane tessellation are received. In the routing algorithm, for a graph $C(N;d,d+1)$ the following formulas for the computing shortest routing vector $(x,y)$ from 0 to a node $k\le \lfloor N/2 \rfloor$ are used: if $k\bmod(d+1)=0$ or $\lfloor k/(d+1)\rfloor$, then $x=-k\bmod(d+1)$, $y=\lfloor k/(d+1)\rfloor -x$, else $x=-k\bmod(d+1)+d+1$, $y= =\lfloor k/(d+1)\rfloor-x+1$. The routing algorithms and their estimates are considered for using in topologies of networks-on-chip. For implementation in networks-on-chip the proposed routing algorithm requires $ \lceil \log_{2}N \rceil+ \lceil \log_{2}\lceil \sqrt{N/2} \rceil \rceil$ bits. New versions of the routing algorithm improve also the routing algorithm proposed early by the author for optimal generalized Petersen graphs with an analytical description of the form $P(N,a,a+1)$, where $2N$ is the order of a graph and $a = \lceil \sqrt{(N-1)/2} \rceil-1$.

Détail

Keywords: two-dimensional circulant networks, diameter, shortest paths, optimal generalized Petersen graphs, networks-on-chip.

Bibliographie

[1] Monakhova E. A., “Structural and communicative properties of circulant networks”, Prikladnaya Diskretnaya Matematika, 2011, no. 3, 92–115 (in Russian)

[2] Monakhova E. A., “A survey on undirected circulant graphs”, Discrete Math., Algorithms Appl., 2012, no. 4 https://www.researchgate.net/publication/267143246_A_survey_on_undirected_circulant_graphs | MR | Zbl

[3] Perez-Roses H., “Algebraic and computer-based methods in the undirected degree/diameter problem — A brief survey”, Electr. J. Graph Theory Appl., 2:2 (2014), 166–190 | DOI | MR | Zbl

[4] Romanov A., Amerikanov A., Lezhnev E., “Analysis of approaches for synthesis of networks-on-chip by using circulant topologies”, J. Physics: Conf. Ser., 1050 (2018), 1–12 | DOI

[5] Romanov A. Yu., “Development of routing algorithms in networks-on-chip based on ring circulant topologies”, Heliyon, 5:4 (2019) | DOI | Zbl

[6] Shchegoleva M. A., Romanov A. Yu., “Development of routing algorithm in networks-on-chip with a multiplicative circulant topology”, Proc. MES-2018 (Russia, Moscow, October 2018), 119–124 (in Russian)

[7] Monakhova E. A., “On analytical representation of optimal two-dimensional Diophantine structures of homogeneous computer systems”, Vychislitel'nye Sistemy, 1981, no. 90, 81–91 (in Russian) | MR | Zbl

[8] Beivide R., Herrada E., Balcazar J. L., Arruabarrena A., “Optimal distance networks of low degree for parallel computers”, IEEE Trans. Computers, 40:10 (1991), 1109–1124 | DOI | MR | Zbl

[9] Liestman A. L., Opatrny J., Zaragoza M., “Network properties of double and triple fixed-step graphs”, Int. J. Found. Comp. Sci., 9 (1998), 57–76 | DOI | Zbl

[10] Puente V., Gregorio J.-A., Prellezo J. M., et al., “Adaptive bubble router: a design to balance latency and throughput in networks for parallel computers”, Proc. ICCP'99 (Toulouse, France, August/September 1999), 58–67

[11] Puente V., Izu C., Gregorio J.-A., et al., “Improving parallel system performance by changing the arrangement of the network links”, Proc. ISC'00 (Santa Fe, New Mexico, USA, May 8–11, 2000), 44–53

[12] Yang Y., Funashashi A., Jouraku A., et al., “Recursive diagonal torus: An interconnection network for massively parallel computers”, IEEE Trans. Parallel and Distributed Systems, 12:7 (2001), 701–715 | DOI

[13] Martines K., Stafford E., Bayvide R., Gabidulin E. M., “Modeling hexagonal constellations with Eisenstein–Jacobi graphs”, Problemy Peredachi Informatsii, 44:1 (2008), 3–13 (in Russian) | MR

[14] Martinez C., Beivide R., Stafford E., et al., “Modeling toroidal networks with the Gaussian integers”, IEEE Trans. Comput., 57:8 (2008), 1046–1056 | DOI | MR | Zbl

[15] Beivide R., Martinez C., Izu C., et al., “Chordal topologies for interconnection networks”, LNCS, 2858, 2003, 385–392

[16] Cai J.-Y. et al., “On routing in circulant graphs”, LNCS, 1627, 1999, 360–369 | MR

[17] Monakhova E. A., “Algorithms of interprocessor exchanges and reconfiguration of interconnection networks in computer systems with programmable structure”, Vychislitel'nye Sistemy, 1982, no. 94, 81–102 (in Russian) | MR | Zbl

[18] Robic̆ B., Optimal routing in 2-jump circulant networks, Technical Report 397, University of Cambridge, U.K., Computer Laboratory, 1996

[19] Gomez D., Gutierrez J., Ibeas A., Beivide R., “Optimal routing in double loop networks”, Theor. Computer Sci., 381:1–3 (2007), 68–85 | DOI | MR | Zbl

[20] Chen B.-X., Meng J.-X., Xiao W.-J., “A constant time optimal routing algorithm for undirected double-loop networks”, Proc. MSN 2005 (Wuhan, China, December 2005), 309–316 | MR

[21] Monakhova E. A., “Optimal generalized Petersen graphs”, Diskretnyy Analiz i Issledovanie Operatsiy, 16:4 (2009), 47–60 (in Russian) | MR | Zbl