Paper Info
Title
Developing the Parallelization Methods for Finding the All-Pairs Shortest Paths in Distributed Memory Architecture
Abstract
The All-Pairs Shortest Paths (APSP) is a fundamental graph problem aiming to find the shortest path between any two nodes in a graph. In this paper, a new method is presented to solve the APSP problem for big graphs on distributed systems. In this method, a graph is partitioned judiciously and then processed in parallel. In particular, the graph is first pre-processed to prepare the partition in the computation stages. After the graph is partitioned into smaller sub-graphs, a traditional shortest path algorithm, such as the Floyd-Warshall algorithm or the Dijkstra's algorithm, can be used to find the APSP in each sub-graph. Finally, through the common nodes between the sub-graphs, the local results in each sub-graph are combined to establish the APSP for the entire graph. Our method is implemented with MPI. Two different communication patterns among partitions (and processes) are proposed to achieve the parallelization and the combination of the local results. We then conducted extensive experiments on a high performance cluster. The experimental results show that comparing with the existing solution, our method is able to accelerate the solving of the APSP problem significantly.
Year
DOI
Venue
2019
10.1109/IPCCC47392.2019.8958713
2019 IEEE 38th International Performance Computing and Communications Conference (IPCCC)
Keywords
Field
DocType
All-Pairs Shortest Path,Graph partition,parallel processing,distributed memory architecture
Graph,Shortest path problem,High performance cluster,Computer science,Parallel computing,Distributed memory architecture,Partition (number theory),Graph partition,Computation,Dijkstra's algorithm
Conference
ISSN
ISBN
Citations 
1097-2641
978-1-7281-1026-4
0
PageRank 
References 
Authors
0.34
4
4
Name
Order
Citations
PageRank
Mohammed Alghamdi100.34
Ligang He254256.73
Yujue Zhou300.34
Junyu Li400.34