|
Дискретная математика и Математическая кибернетика
Обобщенный блочный алгоритм Флойда – Уоршелла
Н. А. Лиходед, Д. С. Сипейко Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь
Аннотация:
Одним из наиболее используемых на практике алгоритмов для поиска кратчайших путей между всеми парами вершин во взвешенных графах является алгоритм Флойда – Уоршелла. Блочная версия алгоритма служит основой для получения эффективных параллельных алгоритмов при реализации на многоядерных центральных процессорах, компьютерах с распределенной памятью, графических процессорах. Увеличение зернистости вычислений в блочных версиях алгоритмов приводит к более эффективному использованию кешей и более эффективной организации параллельных вычислений. В этой работе предложено обобщение блочного алгоритма Флойда – Уоршелла. Порядок выполнения блоков вычислений реорганизован таким образом, чтобы элементы массива, участвующие в коммуникационных операциях как чтения, так и записи, реже вытеснялись из памяти с быстрым доступом. Тогда при реализации алгоритма на графическом процессоре реже, по сравнению с исходным блочным алгоритмом, используется медленная глобальная память.
Ключевые слова:
параллельные алгоритмы; поиск кратчайших путей; графы; алгоритм Флойда – Уоршелла; блочный алгоритм; графический процессор; GPU.
Поступила в редакцию: 22.09.2019
Образец цитирования:
Н. А. Лиходед, Д. С. Сипейко, “Обобщенный блочный алгоритм Флойда – Уоршелла”, Журн. Белорус. гос. ун-та. Матем. Инф., 3 (2019), 84–92
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/bgumi106 https://www.mathnet.ru/rus/bgumi/v3/p84
|
Статистика просмотров: |
Страница аннотации: | 117 | PDF полного текста: | 106 | Список литературы: | 21 |
|