BelRed: Constructing GPGPU graph applications with software building blocks
Shuai Che, Bradford M. Beckmann, Steven K. Reinhardt · IEEE High Performance Extreme Computing Conference · 2014
Graph applications are common in scientific and enterprise computing. Recent research studies used graphics processing units (GPUs) to accelerate graph workloads. These applications tend to present characteristics that are challenging for single instruction multiple data (SIMD) computation. To achieve high performance, prior work studied individual graph problems, and designed device-specific algorithms and optimizations to achieve high performance. However, programmers have to expend significant manual effort, packing data and computation to make such solutions GPU-friendly. Usually, they are too complex for regular programmers, and the resultant implementations may not be portable nor perform well across platforms. To address these concerns, we present a library of software building blocks, BelRed1 which allows programmers to build GPGPU graph applications with ease. BelRed is based on the prior research of graph algorithms in linear algebra, and is implemented and optimized for the GPU platform. BelRed currently is built on top of the OpenCL framework. It consists of fundamental building blocks necessary for graph processing. This paper introduces the library and presents several case studies on how to leverage it for a variety of representative graph problems. We evaluate application performance on an AMD GPU and investigate optimization approaches to improve performance.
Cited by 12 works. doi:10.1109/hpec.2014.7040961
Authors
References
- Pregel
- Rodinia: A benchmark suite for heterogeneous computing
- Accelerating Large Graph Algorithms on the GPU Using CUDA
- Ecient Sparse Matrix-Vector Multiplication on CUDA
- The Scalable Heterogeneous Computing (SHOC) benchmark suite
- GraphChi: Large-Scale Graph Computation on Just a PC
- Scalable GPU graph traversal
- The Combinatorial BLAS: design, implementation, and applications
- Graph Algorithms in the Language of Linear Algebra
- A quantitative study of irregular programs on GPUs