Dynamic parallelism for simple and efficient GPU graph algorithms
Authors:
Open Access
- 15 November 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-4
Abstract
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.Keywords
Funding Information
- U.S. Department of War (FA8721-05-C-0003)
- National Science Foundation (1111888)
This publication has 8 references indexed in Scilit:
- Dynamic thread block launch2015
- Characterization and analysis of dynamic parallelism in unstructured GPU applications2014
- Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths2014
- Parallel distributed breadth first search on GPU2013
- Highly scalable graph search for the Graph500 benchmark2012
- Scalable GPU graph traversal2012
- Accelerating CUDA graph algorithms at maximum warp2011
- Accelerating Large Graph Algorithms on the GPU Using CUDA2008