Scalable GPU graph traversal

Duane Merrill, Michael Garland, Andrew S. Grimshaw · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · 2012

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.

Cited by 506 works. doi:10.1145/2145816.2145832

Authors

References