Для семейства оптимальных двумерных циркулянтных сетей с аналитическим описанием получены две новые улучшенные версии алгоритма поиска кратчайших путей с константной оценкой сложности. Дано простое, основанное на геометрической модели циркулянтных графов, доказательство формул, используемых для алгоритма поиска кратчайших путей. Представлены алгоритмы парных обменов и даны их оценки для сетей на кристалле с топологией в виде рассмотренных графов. Новые версии алгоритма улучшают также предложенный ранее автором алгоритм поиска кратчайших путей для оптимальных обобщённых графов Петерсена с аналитическим описанием.
Скачать электронную версию публикации
Загружен, раз: 114
- Title Поиск кратчайших путей в оптимальных двумерных циркулянтах
- Headline Поиск кратчайших путей в оптимальных двумерных циркулянтах
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 47
- Date:
- DOI 10.17223/20710410/47/7
Ключевые слова
двумерные циркулянтные графы, диаметр, кратчайшие пути, оптимальные обобщённые графы Петерсена, сети на кристалле, two-dimensional circulant networks, diameter, shortest paths, optimal generalized Petersen graphs, networks-on-chipАвторы
Ссылки
Монахова Э. А. Структурные и коммуникативные свойства циркулянтных сетей // Прикладная дискретная математика. 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
Поиск кратчайших путей в оптимальных двумерных циркулянтах | Прикладная дискретная математика. 2020. № 47. DOI: 10.17223/20710410/47/7
Скачать полнотекстовую версию
Загружен, раз: 313