The Library
Developing the parallelization methods for finding the all-pairs shortest paths in distributed memory architecture
Tools
Tools
Tools
Alghamdi, Mohammed, He, Ligang, Zhou, Yujue and Li, Junyu (2020) Developing the parallelization methods for finding the all-pairs shortest paths in distributed memory architecture. In: 38th IEEE International Performance Computing and Communications Conference (IPCCC), London, UK, 29-31 Oct 2019 ISBN 9781728110257. doi:10.1109/IPCCC47392.2019.8958713 ISSN 2374-9628.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1109/IPCCC47392.2019.8958713
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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Publisher: | IEEE | ||||||
| ISBN: | 9781728110257 | ||||||
| ISSN: | 2374-9628 | ||||||
| Official Date: | 2020 | ||||||
| Dates: |
|
||||||
| DOI: | 10.1109/IPCCC47392.2019.8958713 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 38th IEEE International Performance Computing and Communications Conference (IPCCC) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | London, UK | ||||||
| Date(s) of Event: | 29-31 Oct 2019 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
