Globally homogeneous, locally adaptive sparse matrix-vector multiplication on the GPU
Authors:
Open Access
- 14 June 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-11
Abstract
The rising popularity of the graphics processing unit (GPU) across various numerical computing applications triggered a breakneck race to optimize key numerical kernels and in particular, the sparse matrix-vector product (SpMV). Despite great strides, most existing GPU-SpMV approaches trade off one aspect of performance against another. They either require preprocessing, exhibit inconsistent behavior, lead to execution divergence, suffer load imbalance or induce detrimental memory access patterns. In this paper, we present an uncompromising approach for SpMV on the GPU. Our approach requires no separate preprocessing or knowledge of the matrix structure and works directly on the standard compressed sparse rows (CSR) data format. From a global perspective, it exhibits a homogeneous behavior reflected in efficient memory access patterns and steady per-thread workload. From a local perspective, it avoids heterogeneous execution paths by adapting its behavior to the work load at hand, it uses an efficient encoding to keep temporary data requirements for on-chip memory low, and leads to divergence-free execution. We evaluate our approach on more than 2500 matrices comparing to vendor provided, and state-of-the-art SpMV implementations. Our approach not only significantly outperforms approaches directly operating on the CSR format ( 20% average performance increase), but also outperforms approaches that preprocess the matrix even when preprocessing time is discarded. Additionally, the same strategies lead to significant performance increase when adapted for transpose SpMV.Keywords
This publication has 23 references indexed in Scilit:
- CSR52015
- A decomposition for in-place matrix transpositionACM SIGPLAN Notices, 2014
- A Unified Sparse Matrix Data Format for Efficient General Sparse Matrix-Vector Multiplication on Modern Processors with Wide SIMD UnitsSIAM Journal on Scientific Computing, 2014
- clSpMV2012
- Optimization of sparse matrix–vector multiplication using reordering techniques on GPUsMicroprocessors and Microsystems, 2012
- A new approach for sparse matrix vector product on NVIDIA GPUsConcurrency and Computation: Practice and Experience, 2010
- Model-driven autotuning of sparse matrix-vector multiply on GPUsACM SIGPLAN Notices, 2010
- Automatically Tuning Sparse Matrix-Vector Multiplication for GPU Architectures2010
- Implementing sparse matrix-vector multiplication on throughput-oriented processors2009
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009