Michael Garland

See Also

Scalable GPU Graph Traversal

Publication

D. Merrill, M. Garland, and A. Grimshaw. Scalable GPU Graph Traversal. Proc. PPoPP 2012, February 2012.

Abstract

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 constructed from efficient prefix sum 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.

Citation

@inproceedings{Merrill2012:bfs,
    author = {Duane Merrill and Michael Garland and Andrew Grimshaw},
    title = {Scalable {GPU} Graph Traversal},
    booktitle = {Proc. 17th ACM Symposium on Principles and Practice of
                 Parallel Programming},
    series = {PPoPP '12},
    month = feb,
    year = 2012,
}