Breadth-First Search using Dynamic Parallelism on the GPU

Dominik Todling
Institute of Computer Graphics and Vision, Graz University of Technology, Austria
Central European Seminar on Computer Graphics, 2019


   title={Breadth-First Search using Dynamic Parallelism on the GPU},

   author={T{"o}dling, Dominik},



Download Download (PDF)   View View   Source Source   Source codes Source codes




Breadth-First Search is an important basis for many different graph-based algorithms with applications ranging from peer-to-peer networking to garbage collection. However, the performance of different approaches depends strongly on the type of graph. In this paper, three algorithms of varying complexity are implemented using the CUDA Programming Model for the GPU and are compared to one another on a variety of different, sparse graphs. As part of this, we look into utilizing dynamic parallelism in order to both reduce overhead from latency between the CPU and GPU, as well as speed up the algorithm itself. Lastly, the same three algorithms are then integrated with the faimGraph framework for dynamic graphs and the relative performance to a Compressed-Sparse-Row data structure is examined. We show that our algorithm can be well adapted to the dynamic setting and outperforms another competing dynamic graph framework on our test set.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: