Dynamic Parallelism for Simple and Efficient GPU Graph Algorithms
December 2015 • Conference Paper
Peter Zhang (Indiana University), Eric Holk (Indiana University), John Matty, Samantha Misurda, Marcin Zalewski (Indiana University), Jonathan Chu, Scott McMillan, Andrew Lumsdaine (Indiana University)
Presented at the 2015 Supercomputing Conference, this paper shows that dynamic parallelism enables relatively high-performance graph algorithms for GPUs.
Dynamic parallelism allows GPU kernels to launch additional kernels at runtime directly from the GPU. In this paper we show that dynamic parallelism enables relatively simple high-performance graph algorithms for GPUs. We present breadth-first search (BFS) and single-source shortest paths (SSSP) algorithms that use dynamic parallelism to adapt to the irregular and data-driven nature of these problems. Our approach results in simple code that closely follows the high-level description of the algorithms but yields performance competitive with the current state of the art.