SpV8: Pursuing Optimal Vectorization and Regular Computation Pattern in SpMV
Authors:
- 5 December 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 661-666
Abstract
Sparse Matrix-Vector Multiplication (SpMV) plays an important role in many scientific and industry applications, and remains a well-known challenge due to the high sparsity and irregularity. Most existing researches on SpMV try to pursue high vectorization efficiency. However, such approaches may suffer from non-negligible speculation penalty due to their irregular computation patterns. In this paper, we propose SpV8, a novel approach that optimizes both speculation and vectorization in SpMV. Specifically, SpV8 analyzes data distribution in different matrices and row panels, and accordingly applies optimization method that achieves the maximal vectorization with regular computation patterns. We evaluate SpV8 on Intel Xeon CPU and compare with multiple state-of-art SpMV algorithms using 71 sparse matrices. The results show that SpV8 achieves up to 10× speedup (average 2.8×) against the standard MKL SpMV routine, and up to 2.4× speedup (average 1.4×) against the best existing approach. Moreover, SpMV features very low preprocessing overhead in all compared approaches, which indicates SpV8 is highly-applicable in real-world applications.Keywords
Funding Information
- Research and Development
- National Natural Science Foundation of China
This publication has 7 references indexed in Scilit:
- Adaptive sparse tiling for sparse matrix multiplication2019
- CVR: efficient vectorization of SpMV on x86 processors2018
- CSR52015
- Regularizing graph centrality computationsJournal of Parallel and Distributed Computing, 2015
- Optimizing and auto-tuning scale-free sparse matrix-vector multiplication on Intel Xeon Phi2015
- Efficient sparse matrix-vector multiplication on x86-based many-core processors2013
- The university of Florida sparse matrix collectionACM Transactions on Mathematical Software, 2011