Breadth-First Search using Dynamic Parallelism on the GPU
Institute of Computer Graphics and Vision, Graz University of Technology, Austria
Central European Seminar on Computer Graphics, 2019
@article{todling2019breadth,
title={Breadth-First Search using Dynamic Parallelism on the GPU},
author={T{"o}dling, Dominik},
year={2019}
}
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.
May 30, 2019 by hgpu
