ГлавнаяАрхивЭффективный алгоритм поиска кратчайших путей в плотных Гауссианских сетях

Эффективный алгоритм поиска кратчайших путей в плотных Гауссианских сетях | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/9

Для семейства плотных Гауссианских сетей вида C(D2 + (D + 1)2; D, D + 1) как перспективной топологии сетей на кристалле предложен алгоритм поиска кратчайших путей между вершинами графа, использующий относительную адресацию вершин и позволяющий в отличие от ряда известных алгоритмов рассчитать кратчайшие пути без использования координат соседних нулей решетки в плотной укладке графов на плоскости ℤ2. Это сокращает затраты памяти и времени выполнения по сравнению с другими алгоритмами при реализации данного алгоритма в сетях на кристалле с топологией плотной Гауссианской сети.
  • Title Эффективный алгоритм поиска кратчайших путей в плотных Гауссианских сетях
  • Headline Эффективный алгоритм поиска кратчайших путей в плотных Гауссианских сетях
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 58
  • Date:
  • DOI 10.17223/20710410/58/9
Ключевые слова
плотные Гауссианские сети, циркулянтные графы, кратчайшие пути, сети на кристалле
Авторы
Ссылки
Martinez C., Vallejo E., Beivide R., et al. Dense Gaussian networks: Suitable topologies for on-chip multiprocessors // Intern. J. Parallel Programming. 2006. V. 34. P. 193-211.
Martinez C., Vallejo E., Moreto M., et al. Hierarchical topologies for large-scale two-level networks // XVI Jornadas de Paralelismo, Granada, Spain, September 2005. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.7372.
Martinez C., Beivide R., Stafford E., et al. Modeling toroidal networks with the Gaussian integers // IEEE Trans.Computers. 2008. V. 57. No. 8. P. 1046-1056.
Flahive M. and Bose B. The topology of Gaussian and Eisenstein - Jacobi interconnection networks // IEEE Trans. Parall. Distrib. Syst. 2010. V. 21. No. 8. P.1132-1142.
Pay K.-J., Yang J.-S., Chen G.-Y., and Chang J.-M. Configuring protection routing via completely independent spanning trees in Dense Gaussian On-Chip Networks // IEEE Trans.Netw. Sci. Eng. 2022. V. 9. No. 2. P. 932-946.
Touzene A. On all-to-all broadcast in dense Gaussian network on-chip // IEEE Trans. Parall. Distrib. Syst. 2015. V.26. No.4. P.1085-1095.
Alsaleh O., Bose B., and Hamdaoui B. On-to-many node-disjoint paths routing in dense Gaussian networks // Computer J. 2015. V. 58. No. 2. P. 173-187.
Bermond J.-C., Comellas F., and Hsu D. F. Distributed loop computer networks: a survey //j. Parallel Distrib.Comput. 1995. No. 24 (1). P.2-10.
Hwang F.K. A survey on multi-loop networks // Theor.Comput. Sci. 2003. V. 299. P.107-121.
Монахова Э.А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 2011. №3(13). С. 92-115.
Monakhova E.A., Romanov A.Y., and 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.
Zerovnik J. and Pisanski T.Computing the diameter in multiple-loop networks //j. Algorithms. 1993. V. 14. P. 226-243.
Gomez D., Gutierrez J., Ibeas A., et al. On finding a shortest path in circulant graphs with two jumps // LNCS. 2005. V. 3595. P.777-786.
Cai J.Y., Havas G., Mans B., et al. On routing in circulant graphs // LNCS. 1999. V. 1627. P. 360-369.
Monakhova E.A., Monakhov O.G., and Romanov A.Yu. Routing algorithms in optimal degree four circulant networks based on relative addressing: Comparative analysis for Эффективный алгоритм поиска кратчайших путей в плотных Гауссианских сетях 103 Networks-on-Chip // IEEE Trans.Network Science and Engineering. 2022. https://ieeexplore.ieee.org/document/9910381.
Monakhova E. and Monakhov O. A generalized routing algorithm for a family of optimal 2D circulant networks based on relative addressing // Proc. 17th Inter. Asian School-Seminar (OPCS-21), Novosibirsk, Russia. 2021. P. 55-59.
Jha P.K. Dimension-order routing algorithms for a family of minimal-diameter circulants //j.Inter.Networks. 2013. V. 14. No. 1. P. 1350002 (24 pages).
Монахова Э.А. Поиск кратчайших путей в оптимальных двумерных циркулянтах // Прикладная дискретная математика. 2020. №47. С. 87-100.
Romanov A.Y. Development of routing algorithms in networks-on-chip based on ring circulant topologies // Heliyon. 2019. V. 5. Iss.4. Article e01516.
Romanov A.Y., Lezhnev E.V., Glukhikh A.Y., and Amerikanov A.A. Development of routing algorithms in networks-on-chip based on two-dimensional optimal circulant topologies // Heliyon. Jan. 2020. V. 6. No. 1. Art. No.e03183.
Camarero C., Martinez C., and Beivide R. L-networks: A topological model for regular two-dimensional interconnection networks // IEEE Trans.Computers. 2013. V. 62. No. 7. P. 1362-1375.
Dijkstra E.W. A note on two problems in connexion with graphs // Numer. Math. 1959. V. 1. No. 1. P.269-271.
Эффективный алгоритм поиска кратчайших путей в плотных Гауссианских сетях | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/9
Эффективный алгоритм поиска кратчайших путей в плотных Гауссианских сетях | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/9