Dominik Tödling
Supervisor(s): Martin Winter
TU Graz
Abstract: 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.
Keywords: Graphics Hardware
Full text: Year: 2019
