Name
Abstract | ||
|---|---|---|
It is universally accepted that the performance of graph algorithms is heavily dependent on the algorithm, the execution platform, and the structure of the input graph. This variability remains difficult to predict and hinders the choice of the right algorithm for a given problem. In this work, we focus on a case study: breadth-first search (BFS), a level-based graph traversal algorithm, running on GPUs. We first demonstrate the severity of this variability by presenting 32 variations of 5 implementation strategies for GPU-enabled BFS, and showing how selecting one single algorithm for the entire traversal can significantly limit performance. To alleviate these performance losses, we propose to mix-and-match, at runtime, different algorithms to compose the best performing BFS traversal. Our approach is based on two novel elements: a predictive model, based on a decision tree, which is able to dynamically select the best performing algorithm for each BFS level, and a quick context switch between algorithms, which limits the overhead of the combined BFS. We demonstrate empirically that our dynamic switching BFS achieves better performance, outperforming our non-switching implementations by 2x and existing state-of-the-art GPU BFS implementations by 3x. We conclude that mix-and-match BFS is a competitive approach for doing fast graph traversal, while being easily extended to include more BFS implementations and easily adaptable to other types of processors or specific types of graphs. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/IA3.2018.00014 | 2018 IEEE/ACM 8th Workshop on Irregular Applications: Architectures and Algorithms (IA3) |
Keywords | Field | DocType |
Prediction algorithms,Instruction sets,Predictive models,Runtime,Decision trees,Programming,Computational modeling | Decision tree,Tree traversal,Graph traversal,Instruction set,CUDA,Computer science,Breadth-first search,Parallel computing,Implementation,Context switch | Conference |
ISBN | Citations | PageRank |
978-1-7281-0186-6 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Merijn Verstraaten | 1 | 56 | 4.96 |
| Ana Lucia Varbanescu | 2 | 520 | 44.83 |
| Cees Laat | 3 | 21 | 5.57 |