Conference proceeding
Scaling and Selecting GPU Methods for All Pairs Shortest Paths (APSP) Computations
2022 IEEE 36TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2022), pp.190-200
International Parallel and Distributed Processing Symposium IPDPS
01/01/2022
DOI: 10.1109/IPDPS53621.2022.00027
Abstract
All Pairs Shortest Path (APSP) is one of the graph problems where the output size is significantly larger than the input size. This paper examines the issues in scaling GPU implementations for this problem beyond the memory limits. Because the existing (in-core) methods offer a complex trade-off between the overall computation complexity and the available parallelism, choosing the best out-of-core version for a given matrix is challenging. We develop three efficient out-of-core implementations, which are based on the blocked Floyd-Warshall algorithm, Johnson's algorithm, and the boundary algorithm, respectively. Next, we develop a methodology to select the best implementation for a given graph. Experimental results show that compared with an efficient multi-core APSP implementation, the out-of-core version achieves speedups of 8.22 to 12.40 for graphs with a small separator, and speedups of 2.23 to 2.79 for other sparse graphs, and our models can select the best implementation in most cases.
Details
- Title: Subtitle
- Scaling and Selecting GPU Methods for All Pairs Shortest Paths (APSP) Computations
- Creators
- Yang Xia - The Ohio State UniversityPeng Jiang - University of IowaGagan Agrawal - Augusta UniversityRajiv Ramnath - The Ohio State University
- Resource Type
- Conference proceeding
- Publication Details
- 2022 IEEE 36TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2022), pp.190-200
- Publisher
- IEEE
- Series
- International Parallel and Distributed Processing Symposium IPDPS
- DOI
- 10.1109/IPDPS53621.2022.00027
- ISSN
- 1530-2075
- eISSN
- 1530-2075
- Number of pages
- 11
- Grant note
- 2131509; 2034850; 2007793 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2022
- Academic Unit
- Computer Science
- Record Identifier
- 9984411064502771
Metrics
4 Record Views