Ведущий инженер иностранного производственного унитарногопредприятия «ИССОФТ СОЛЮШЕНЗ»
г. Минск
Karasik Oleg is a Technology Lead at ISsoft Solutions (part of Coherent Solutions) in Minsk, Belarus, and PhD in Technical Science
Minsk
Профессор кафедры «Программное обеспечение информационных систем и технологий», доктор технических наук
г. Минск
Anatoly Prihozhy is full professor at Computer and system software department, Doctor of Science
Minsk
Задача поиска кратчайших путей между всеми парами вершин в графе (APSP) имеет применяется в планировании, коммуникациях, экономике и многих других сферах. На сегодняшний день существует ряд алгоритмов решения APSP задач, начиная с алгоритма Флойда-Уоршелла (Floyd-Warshall) и заканчивая более продвинутыми и быстрыми блочными алгоритмами (например, неоднородным блочным алгоритмом поиска кратчайших путей Heterogeneous Blocked All-Pairs Shortest Paths), предназначенными для максимально эффективного использования вычислительных средств и зависимостей между данными, участвующими в вычислениях. В статье предлагается новый блочный алгоритм BSPCG поиска кратчайших путей в кластеризованных графах в однопоточном и многопоточном вариантах, который использует информацию о кластеризации для сокращения объема вычислений посредством поиска кратчайших путей, проходящих через граничные вершины кластеров. В статье проведена серия вычислительных экспериментов над стандартным блочным алгоритмом BFW и новым алгоритмом BSPCG с целью доказательства эффективности поиска кратчайших путей в случае использования граничных вершин кластеров. Эксперименты выполнялись с использованием графов размером 4800 и 9600 вершин с различными кластерными конфигурациями. Эксперименты проведены на компьютере с двумя процессорами Intel Xeon E5-2620v4 (каждый процессор включает 8 физических ядер и 16 аппаратных потоков, а также кэш L3 объемом 20 МБ). Во всех проведенных экспериментах новый алгоритм BSPCG превзошел стандартный алгоритм BFW в несколько раз. В однопоточных сценариях BSPCG продемонстрировал ускорение по сравнению с BFW до 4.6 раз на графах с 4800 вершинами и до 2.7 раз на графах с 9600 вершинами. В многопоточных сценариях BSPCG также продемонстрировал ускорение до 4 раз на графах с 4800 вершинами и до 2,7 раз на графах с 9600 вершинами. Предложенный в статье алгоритм может быть использован в сценариях, где информация о кластеризации остается неизменной или изменяется незначительно и может быть повторно использована для множественных нахождений всех кратчайших путей в графе.
The problem of finding all shortest paths between vertices in a graph (APSP) has real-life applications in planning, communication, economics and many other areas. APSP problem can be solved using various algorithms, starting from Floyd-Warshall’s algorithm and ending with advanced, much faster blocked algorithms like Heterogeneous Blocked All-Pairs Shortest Path Algorithm designed to fully utilize underlying hardware resources and utilize inter-data relationships. In the paper, we propose a novel Blocked all-pairs Shortest Paths algorithm for Clustered Graphs (BSPCG) (in sequential and parallel forms) which utilizes the graph clustering information to significantly reduce the number of calculations by performing shortest paths search only though bridge vertices between clusters. We performed a set of comparing experiments for BSPCG and standard Blocked All-Pairs Shortest Path (BFW) algorithm on four randomly generated graphs of 4800 and 9600 vertices with different cluster configurations to determine the efficiency of calculation of paths passing through bridge vertices. All experiments were executed on a computer with two Intel Xeon E5-2620v4 processors (8 cores, 16 hardware threads and shared 20 MB L3 cache). In all the experiments the novel BSPCG algorithm outperformed the standard BFW algorithm. In single-threaded scenarios, BSPCG outperformed BFW up to 4.6 times on graphs of 4800 vertices and up to 2.7 times on graphs of 9600 vertices. In the multi-threaded scenarios, BSPCG also outperformed BFW up to times on graphs of 4800 vertices and up to 2.7 times on graphs of 9600 vertices. The proposed algorithm can be used in scenarios where clustering information stays intact or slightly modified based on the changes in graph and can be reused for future calculation of all-pairs shortest paths in the graph.
The authors declare that there are no conflicts of interest present.