A Row Decomposition-based Approach for Sparse Matrix Multiplication on GPUs
Open Access
- 20 February 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 377-389
Abstract
Sparse-Matrix Dense-Matrix Multiplication (SpMM) and Sampled Dense Dense Matrix Multiplication (SDDMM) are important sparse kernels in various computation domains. The uneven distribution of nonzeros in the sparse matrix and the tight data dependence between sparse and dense matrices make it a challenge to run sparse matrix multiplication efficiently on GPUs. By analyzing the aforementioned problems, we propose a row decomposition (RoDe)-based approach to optimize the two kernels on GPUs, using the standard Compressed Sparse Row (CSR) format. Specifically, RoDe divides the sparse matrix rows into regular parts and residual parts, to fully optimize their computations separately. We also devise the corresponding load balancing and finegrained pipelining technologies. Profiling results show that RoDe can achieve more efficient memory access and reduce warp stall cycles significantly. Compared to the state-of-the-art (SOTA) alternatives, RoDe achieves a speedup of up to 7.86× with a geometric mean of 1.45× for SpMM, and a speedup of up to 8.99× with a geometric mean of 1.49× for SDDMM; the dataset is SuiteSparse. RoDe also outperforms its counterpart in the deep learning dataset. Furthermore, its preprocessing overhead is significantly smaller, averaging only 16% of the SOTA.Keywords
This publication has 16 references indexed in Scilit:
- Efficient sparse-matrix multi-vector product on GPUs2018
- The tensor algebra compilerProceedings of the ACM on Programming Languages, 2017
- Globally homogeneous, locally adaptive sparse matrix-vector multiplication on the GPU2017
- Optimizing Sparse Matrix-Multiple Vectors Multiplication for Nuclear Configuration Interaction Calculations2014
- Big data analytics with small footprint2013
- FastSpMM: An Efficient Library for Sparse Matrix Matrix Product on GPUsThe Computer Journal, 2013
- The university of Florida sparse matrix collectionACM Transactions on Mathematical Software, 2011
- Matrix Factorization Techniques for Recommender SystemsComputer, 2009
- Optimization of sparse matrix-vector multiplication on emerging multicore platforms2007
- OSKI: A library of automatically tuned sparse matrix kernelsJournal of Physics: Conference Series, 2005