Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths
Authors:
- Andrew DavidsonADAndrew Davidson
- Sean BaxterSBSean Baxter
- Michael GarlandMGMichael Garland
- John D. OwensJOJohn D. Owens
- 1 May 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 349-359
Abstract
Finding the shortest paths from a single source to all other vertices is a fundamental method used in a variety of higher-level graph algorithms. We present three parallel friendly and work-efficient methods to solve this Single-Source Shortest Paths (SSSP) problem: Work front Sweep, Near-Far and Bucketing. These methods choose different approaches to balance the trade off between saving work and organizational overhead. In practice, all of these methods do much less work than traditional Bellman-Ford methods, while adding only a modest amount of extra work over serial methods. These methods are designed to have a sufficient parallel workload to fill modern massively-parallel machines, and select reorganizational schemes that map well to these architectures. We show that in general our Near-Far method has the highest performance on modern GPUs, outperforming other parallel methods. We also explore a variety of parallel load-balanced graph traversal strategies and apply them towards our SSSP solver. Our work-saving methods always outperform a traditional GPU Bellman-Ford implementation, achieving rates up to 14x higher on low-degree graphs and 340x higher on scale free graphs. We also see significant speedups (20-60x) when compared against a serial implementation on graphs with adequately high degree.Keywords
This publication has 14 references indexed in Scilit:
- A lightweight infrastructure for graph analytics2013
- Ligra2013
- Scalable GPU graph traversal2012
- The university of Florida sparse matrix collectionACM Transactions on Mathematical Software, 2011
- Memory-Scalable GPU Spatial Hierarchy ConstructionIEEE Transactions on Visualization and Computer Graphics, 2010
- Implementing sparse matrix-vector multiplication on throughput-oriented processors2009
- Lonestar: A suite of parallel irregular programs2009
- Reach for A*: Efficient Point-to-Point Shortest Path Algorithms2006
- Δ-stepping: a parallelizable shortest path algorithmJournal of Algorithms, 2003
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987