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

A computation of the shortest paths in optimal two-dimensional circulant networks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/7

For a family of optimal two-dimensional circulant networks with an analytical description, two new improved versions of the shortest paths search algorithm with a constant complexity estimate are obtained. A simple, based on the geometric model of circulant graphs, proof of the formulas used for the shortest path search algorithm is given. Algorithms of pair exchanges are presented and their estimates are given for networks on a chip with a topology in the form of the considered graphs. New versions of the algorithm also improve the previously proposed shortest path search algorithm for optimal generalized Petersen graphs with an analytical description.
Download file
Counter downloads: 116
  • Title A computation of the shortest paths in optimal two-dimensional circulant networks
  • Headline A computation of the shortest paths in optimal two-dimensional circulant networks
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 47
  • Date:
  • DOI 10.17223/20710410/47/7
Keywords
двумерные циркулянтные графы, диаметр, кратчайшие пути, оптимальные обобщённые графы Петерсена, сети на кристалле, two-dimensional circulant networks, diameter, shortest paths, optimal generalized Petersen graphs, networks-on-chip
Authors
References
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. № 3. С. 92-115
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
Perez-Roses H. Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey // Electr. J. Graph Theory Appl. 2014. No. 2(2). P. 166-190
Romanov A., Amerikanov A., and Lezhnev E. Analysis of approaches for synthesis of networks-on-chip by using circulant topologies // J. Physics: Conf. Ser. 2018. V. 1050. P. 1-12
Romanov A. Yu. Development of routing algorithms in networks-on-chip based on ring circulant topologies // Heliyon. 2019. V. 5. Iss. 4. https://www.sciencedirect.com/ science/article/pii/S2405844018355208
Щеголева М. А., Романов А. Ю. Разработка алгоритма маршрутизации в сетях на кристалле с топологией мультипликативный циркулянт // МЭС-2018. Россия, Москва, октябрь 2018. С. 119-124
Монахова Э. А. Об аналитическом описании оптимальных двумерных диофантовых структур однородных вычислительных систем // Вычислительные системы. 1981. №90. С. 81-91
Beivide R., Herrada E., Balcazar J. L., and Arruabarrena A. Optimal distance networks of low degree for parallel computers // IEEE Trans. Computers. 1991. V. 40. No. 10. P. 1109-1124
Liestman A. L., Opatrny J., and Zaragoza M. Network properties of double and triple fixed-step graphs // Int. J. Found. Comp. Sci. 1998. V. 9. P. 57-76
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. P. 58-67
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. P. 44-53
Yang Y., Funashashi A., Jouraku A., et al. Recursive diagonal torus: An interconnection network for massively parallel computers // IEEE Trans. Parallel and Distributed Systems. 2001. V. 12. No. 7. P. 701-715
Мартинес К., Стаффорд Э., Байвиде Р., Габидулин Э. М. Представление гексагональных созвездий с помощью графов Эйзенштейна - Якоби // Проблемы передачи информации. 2008. Т. 44. № 1. С. 3-13
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
Beivide R., Martinez C., Izu C., et al. Chordal topologies for interconnection networks // LNCS. 2003. V. 2858. P. 385-392
Cai J.-Y. et al. On routing in circulant graphs // LNCS. 1999. V. 1627. P. 360-369
Монахова Э. А. Алгоритмы межмашинных взаимодействий и реконфигурации графов связей в вычислительных системах с программируемой структурой // Вычислительные системы. 1982. № 94. C. 81-102
Robic B. Optimal routing in 2-jump circulant networks. Technical Report 397, University of Cambridge, U.K., Computer Laboratory, 1996
Gomez D., Gutierrez J., Ibeas A., and Beivide R. Optimal routing in double loop networks // Theor. Computer Sci. 2007. V. 381. Iss. 1-3. P. 68-85
Chen B.-X., Meng J.-X., and Xiao W.-J. A constant time optimal routing algorithm for undirected double-loop networks // Proc. MSN 2005, Wuhan, China, December 2005. P. 309-316
Монахова Э. А. Оптимальные обобщенные графы Петерсена // Дискретный анализ и исследование операций. 2009. Т. 16. № 4. C. 47-60
A computation of the shortest paths in optimal two-dimensional circulant networks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/7
A computation of the shortest paths in optimal two-dimensional circulant networks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/7
Download full-text version
Counter downloads: 315