Scalable GPU graph traversal

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

587 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/3c84f22df1948dfa8b1b14bbd4c850baf9c5b632

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Hardware and Architecture

Citations in the corpus

A quantitative study of irregular programs on GPUs (2012, methodology): “• Breadth-First Search (BFS): This is a classic graphtraversal algorithm [34].”
Ligra: a lightweight graph processing framework for shared memory (2013, background): “Recently, GPU systems have been explored for implementing graph traversal problems [20, 35].”
Gunrock: a high-performance graph processing library on the GPU (2015, methodology): “All three GPU BFS-based high-level-programming-model efforts (Medusa, Map-Graph, and Gunrock) adopt load-balancing strategies from Merrill et al.’s BFS [21].”
Cache-Conscious Wavefront Scheduling (2012, background): “Figure 15 show the effect of increasing the size of the BFS input graph from the baseline 500k edges to 20M edges.”
The GAP Benchmark Suite (2015, background): “eachability since it allows for verifying the traversal, but BFS implementations that track depth can perform optimizations not possible in the more challenging applications of BFS that track parents [23]. • Single-SourceShortestPaths(SSSP)computes the distances of the shortest paths from a given so”
Direction-optimizing Breadth-First Search (2012, methodology): “Our hybrid implementation also provides typical speedups of 2 or greater over prior state-of-the-arts for multicore [1, 10, 15] and GPUs [20] when utilizing the same graphs and the same or similar hardware.”
A scalable processing-in-memory accelerator for parallel graph processing (2015, methodology): “Although the use of multiple GPGPUs alleviates this problem to some extent, relatively low bandwidth and high latency of PCIe-based interconnect may not be sufficient for fast graph processing, which generates a massive amount of random memory accesses across the entire graph [40].”