Accelerating Large Graph Algorithms on the GPU Using CUDA

By P. Harish, P J Narayanan. International Conference on High Performance Computing, 2007

838 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/dff4fc8957393d2ee8b839625166d63c359b61cf

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Hardware and Architecture

Citations in the corpus

A quantitative study of irregular programs on GPUs (2012, methodology): “Many irregular GPU implementations have been published, including single-source shortest paths (SSSP) and all-pairs shortest paths algorithms [20], breadth-first search (BFS) codes [14], [20], [34], algorithms for constructing kdtrees [48], Boruvka’s minimum spanning tree algorithm [45], the MPM alg”
MachSuite: Benchmarks for accelerator design and customized architectures (2014, methodology): “The BFS/BULK code uses a brute-force, data parallel method [26], [25] which is typically used on SIMD and vector architectures.”
CUDA cuts: Fast graph cuts on the GPU (2008, neutral): “These enable the acceleration of algorithms on irregular graphs [18] and other application involving graphs.”
Inter-block GPU communication via fast barrier synchronization (2010, background): “However, GPUs typically map well only to data or task parallel applications whose execution requires minimal or even no interblock communication [9, 24, 26, 30].”
Large Vocabulary Speech Recognition on Parallel Architectures (2013, methodology): “In this form, the computation of acoustic probabilities is perfectly suitable for SIMD parallel architectures such as SSE or GPUs, since each distribution can be independently computed, and the results rest upon basic dot product operations.”
Analyzing CUDA workloads using a detailed GPU simulator (2009, methodology): “Performance is reduced by over 40% when using FIFO for BFS, LIB, MUM, RAY, and WP.”
Efficient Parallel Graph Exploration on Multi-Core CPU and GPU (2011, methodology): “Second, we study the architectural effects on BFS performance of multiple kinds of GPUs and CPUs.”
Rodinia: A benchmark suite for heterogeneous computing (2009, methodology): “The CUDA version of BFS was contributed by IIIT [9].”