High-Performance and Scalable GPU Graph Traversal
| Autor: | Michael Garland, Andrew S. Grimshaw, Duane Merrill |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Power graph analysis
SPQR tree Dense graph Computer science Breadth-first search Parallel algorithm Graph theory Parallel computing Graph Computer Science Applications Tree traversal Graph bandwidth Computational Theory and Mathematics Hardware and Architecture Modeling and Simulation Graph traversal Prefix sum Software Implicit graph MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | ACM Transactions on Parallel Computing. 1:1-30 |
| ISSN: | 2329-4957 2329-4949 |
| Popis: | 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 nontrivial diameter. We present a BFS parallelization focused on fine-grained task management constructed from efficient prefix sum computations that achieves an asymptotically optimal O(|V| + |E|) gd 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 on both CPU and GPU platforms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|