Доктор технических наук, профессор кафедры «Программное обеспечение информационных систем и технологий» Минск
Doctor of Science, full professor at Computer and system software department Minsk
Кандидат технических наук, ведущий инженер Минск
PhD in Technical Science, is a Technology Lead
В статье рассматриваются два семейства конкурирующих алгоритмов поиска кратчайших путей между всеми парами вершин (APSP) в ориентированных взвешенных больших графах с различной плотностью ребер: Дейкстры и Флойда-Уоршелла. Для сравнения мы взяли алгоритм Дейкстры с динамически изменяемой двоичной кучей, который решает задачу APSP чисто параллельно путем многократного выполнения на всех вершинах графа, рассматриваемых в качестве исходных, и взяли блочный алгоритм Флойда-Уоршелла, который также является хорошо распараллеливаемым. Известно, что с точки зрения вычислительной сложности первый алгоритм предпочтительнее на разреженных графах, а второй – на плотных. В то же время неясно, каковы диапазоны плотностей графов, при которых первый алгоритм будет потреблять процессорное время, меньшее, чем второй алгоритм. В статье описаны реализации многопоточных параллельных алгоритмов на многоядерных процессорах, которые по-разному используют такие примитивы синхронизации, как мьютекс, условная переменная, блокировка и атомарная операция. Проведя вычислительные эксперименты на 8-ядерном процессоре Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz, мы обнаружили, что каждый алгоритм имеет предпочтительную плотность графов. В случае многопоточной параллельной реализации блочный алгоритм Флойда-Уоршелла имеет меньшее время работы, чем алгоритм Дейкстры, если плотность графа больше 0,5. В противном случае алгоритм Дейкстры работает быстрее. В случае однопоточной реализации точка разделения – 0,43.
In this paper we consider two families of competing algorithms for finding the shortest paths between all pairs of vertices (APSP) in directed weighted large graphs with different edge densities: Dijkstra and Floyd-Warshall. For comparison, we have taken Dijkstra's algorithm with dynamically varying binary heap, which solves the APSP problem purely in parallel by repeatedly executing on all vertices of the graph considered as source vertices, and we have taken blocked Floyd-Warshall algorithm, which is also well-parallelizable. It is known that in terms of computational complexity, the first algorithm is preferable on sparse graphs and the second algorithm is preferable on dense graphs. At the same time, it is not clear what are the ranges of graph densities at which the first algorithm will consume less CPU time than the second algorithm. This paper describes multithreaded implementations of parallel algorithms on multicore processors that make different usage of synchronization primitives such as mutex, conditional variable, locking, and atomic operation. By conducting computational experiments on an 8-core Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz, we found that each algorithm has a preferred graph density. In the case of multithreaded parallel implementation, the blocked Floyd-Warshall algorithm has lower running time than Dijkstra's algorithm if the graph density is greater than 0.5. Otherwise, Dijkstra's algorithm runs faster. In the case of single-threaded implementation, the split point is 0.43.
The authors declare that there are no conflicts of interest present.