Обобщенный блочный алгоритм Флойда – Уоршелла

  • Николай Александрович Лиходед Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь https://orcid.org/0000-0002-0998-1349
DOI: https://doi.org/10.33581/2520-6508-2019-3-84-92

Аннотация

Одним из наиболее используемых на практике алгоритмов для поиска кратчайших путей между всеми парами вершин во взвешенных графах является алгоритм Флойда – Уоршелла. Блочная версия алгоритма служит основой для получения эффективных параллельных алгоритмов при реализации на многоядерных центральных процессорах, компьютерах с распределенной памятью, графических процессорах. Увеличение зернистости вычислений в блочных версиях алгоритмов приводит к более эффективному использованию кешей и более эффективной организации параллельных вычислений. В этой работе предложено обобщение блочного алгоритма Флойда – Уоршелла. Порядок выполнения блоков вычислений реорганизован таким образом, чтобы элементы массива, участвующие в коммуникационных операциях как чтения, так и записи, реже вытеснялись из памяти с быстрым доступом. Тогда при реализации алгоритма на графическом процессоре реже, по сравнению с исходным блочным алгоритмом, используется медленная глобальная память.

Биография автора

Николай Александрович Лиходед, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

доктор физико-математических наук, профессор; профессор кафедры вычислительной математики факультета прикладной математики и информатики

Литература

  1. Venkataraman G, Sahni S, Mukhopadhyaya S. A blocked all-pairs shortest-paths algorithm. Journal of Experimental Algorithmics. 2003;8:857– 874. DOI: 10.1145/996546.996553.
  2. Park J, Penner M, Prasanna VK. Optimizing graph algorithms for improved cache performance. IEEE Transactions on Parallel and Distributed Systems. 2004;15(9):769 –782. DOI: 10.1109/TPDS.2004.44.
  3. Srinivasan T, Balakrishnan R, Gangadharan SA, Hayawardh V. A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment. In: Proceedings of the 13th International Conference on Parallel and Distributed Systems; 2007 December 5–7; Hsinchu, Taiwan. Washington: IEEE Computer Society; 2007. p. 1– 8. DOI: 10.1109/ICPADS.2007.4447721.
  4. Lund BD, Smith JW. A multi-stage CUDA kernel for Floyd – Warshall. arXiv:1001.4108. 2010 [Preprint]. 2010 [cited 2019 June 3]. Available from: https://arxiv.org/abs/1001.4108.
  5. Mullapudi RT, Bondhugula U. Tiling for dynamic scheduling. In: IMPACT 2014. Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques; 2014 January 20 –22; Vienna, Austria. [S. l.]: [s. n.]; 2014.
  6. Prihozhy AA, Karasik ON. Heterogenious blocked all-pairs shortest paths algorithm. Sistemnyi analiz i prikladnaya informatika. 2017;3:68 –75. Russian. DOI: 10.21122/2309-4923-2017-3-68-75.
  7. Voevodin VlV, Voevodin VadV. [The fortunate locality of supercomputers]. Otkrytye sistemy. SUBD. 2013;9:12–15. Russian.
  8. Buluc A, Gilberta JR, Budak C. Solving path problems on the GPU. Parallel Computing. 2010;36(5– 6):241–253. DOI: 10.1016/j.parco.2009.12.002.
  9. Likhoded NA, Paliashchuk MA. Conditions for privatizing the elements of arrays by computing threads. Journal of the Belarusian State University. Mathematics and Informatics. 2018;3:59 – 67. Russian.
  10. Harish P, Narayanan P. Accelerating large graph algorithms on the GPU using CUDA. In: High Performance Computing – HiPC 2007. Proceedings of the 14th International Conference; 2007 December 18–21; Goa, India. Berlin: Springer-Verlag; 2007. p. 197–208. DOI: 10.1007/978-3-540-77220-0_21.
  11. Katz GJ, Kider JT. All-pairs shortest-paths for large graphs on the GPU. In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware; 2008 June 20 –21; Sarajevo, Bosnia and Herzegovina. Aire-la-Ville: Eurographics Association; 2008. p. 47–55.
Опубликован
2019-11-25
Ключевые слова: параллельные алгоритмы, поиск кратчайших путей, графы, алгоритм Флойда – Уоршелла, блочный алгоритм, графический процессор, GPU
Поддерживающие организации Работа выполнена в рамках государственной программы научных исследований Республики Беларусь «Конвергенция-2020» (подпрограмма «Методы математического моделирования сложных систем»).
Как цитировать
Лиходед, Н. А. (2019). Обобщенный блочный алгоритм Флойда – Уоршелла. Журнал Белорусского государственного университета. Математика. Информатика, 3, 84-92. https://doi.org/10.33581/2520-6508-2019-3-84-92
Выпуск
№ 3 (2019): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

Copyright (c) 2019 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).