TileSpMV: A Tiled Algorithm for Sparse Matrix-Vector Multiplication on GPUs
Authors:
- 1 May 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 68-78
Abstract
With the extensive use of GPUs in modern supercomputers, accelerating sparse matrix-vector multiplication (SpMV) on GPUs received much attention in the last couple of decades. A number of techniques, such as increasing utilization of wide vector units, reducing load imbalance and selecting the best formats, have been developed. However, the 2D spatial sparsity structure has not been well exploited in the existing work for SpMV on GPUs. In this paper, we propose an efficient tiled algorithm called TileSpMV for optimizing SpMV on GPUs through exploiting 2D spatial structure of sparse matrices. We first implement seven warp-level SpMV methods for calculating sparse tiles stored in a variety of formats, and then design a selection method to find the best format and SpMV implementation for each tile. We also adaptively extract nonzeros in the very sparse tiles into a separate matrix to maximize the overall performance. The experimental results show that our method is faster than state-of-the-art SpMV methods such as Merge-SpMV, CSR5 and BSR in most matrices of the full SuiteSparse Matrix Collection and delivers up to 2.61x, 3.96x and 426.59x speedups, respectively.Keywords
Funding Information
- Science Challenge Project
- National Natural Science Foundation of China
This publication has 54 references indexed in Scilit:
- A Performance Modeling and Optimization Analysis Tool for Sparse Matrix-Vector Multiplication on GPUsIEEE Transactions on Parallel and Distributed Systems, 2013
- Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and ExperimentsSIAM Journal on Scientific Computing, 2012
- Two-dimensional cache-oblivious sparse matrix–vector multiplicationParallel Computing, 2011
- The Combinatorial BLAS: design, implementation, and applicationsThe International Journal of High Performance Computing Applications, 2011
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009
- Cache-Oblivious Sparse Matrix–Vector Multiplication by Using Sparse Matrix Partitioning MethodsSIAM Journal on Scientific Computing, 2009
- Performance evaluation of the sparse matrix-vector multiplication on modern architecturesThe Journal of Supercomputing, 2008
- Performance Optimization and Modeling of Blocked Sparse KernelsThe International Journal of High Performance Computing Applications, 2007
- OSKI: A library of automatically tuned sparse matrix kernelsJournal of Physics: Conference Series, 2005
- Sparsity: Optimization Framework for Sparse Matrix KernelsThe International Journal of High Performance Computing Applications, 2004