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
- Introduction to Algorithms
- Introduction to Algorithms
- Scans as primitive parallel operations
- Rodinia: A benchmark suite for heterogeneous computing
- Data parallel algorithms
- Implementing sparse matrix-vector multiplication on throughput-oriented processors
- Accelerating Large Graph Algorithms on the GPU Using CUDA
- Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2
- A Scalable Distributed Parallel Breadth-First Search Algorithm on BlueGene/L
- Accelerating CUDA graph algorithms at maximum warp