6875

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

@article{merrill2011high,

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

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

   year={2011}

}

Download Download (PDF)   View View   Source Source   

647

views

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-2017 hgpu.org

All rights belong to the respective authors

Contact us: