High Performance and Scalable GPU Graph Traversal

Duane Merrill, Michael Garland, Andrew Grimshaw
Department of Computer Science, University of Virginia
Department of Computer Science, University of Virginia, Technical Report CS-2011-05, 2011


   title={High Performance and Scalable GPU Graph Traversal},

   author={Merrill, D. and Garland, M. and Grimshaw, A.},



Download Download (PDF)   View View   Source Source   



Breadth-first search (BFS) is a core primitive for graph traversal and a basis for many higher-level graph analysis algorithms. It is also representative of a class of parallel computations whose memory accesses and work distribution are both irregular and data-dependent. Recent work has demonstrated the plausibility of GPU sparse graph traversal, but has tended to focus on asymptotically inefficient algorithms that perform poorly on graphs with non-trivial diameter. We present a BFS parallelization focused on fine-grained task management that achieves an asymptotically optimal O(|V|+|E|) work complexity. Our implementation delivers excellent performance on diverse graphs, achieving traversal rates in excess of 3.3 billion and 8.3 billion traversed edges per second using single and quad-GPU configurations, respectively. This level of performance is several times faster than state-of-the-art implementations both CPU and GPU platforms.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: