VNEC: A Vectorized Non-Empty Column Format for SpMV on CPUs
Authors:
- 27 May 2024
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 14-25
Abstract
Sparse matrix-vector multiplication (SpMV) is a widely used computational kernel for many applications. The performance of existing vectorization-oriented and locality-optimized SpMV works is limited by increasing additional memory accesses to the output vector or using expensive gather operations. To address these issues, we present the Vectorized Non-Empty Column (VNEC), a novel SpMV storage format aiming to optimize locality and vectorization while alleviating the existing limitations. The VNEC chunks the sparse matrix by rows and removes the empty columns from each row block to improve input vector locality and reduce extra output vector memory access. It can also relieve the cost of expensive gather operations by padding zeros and employing less costly vector load instruction. Specifically, we design two variants of VNEC for different non-zero distributions and propose an effective heuristic selection model by introducing the Intra-Row Density (IRD) to evaluate which variant is suitable for optimizing a given matrix. Experimental results show that in a multicore environment, VNEC achieves up to 6.94× speedup (2.10× on average) against the standard MKL SpMV routine on the x86 CPU and up to 5.92× speedup (1.73× on average) over ArmPL on the ARM CPU. We emphasize that the VNEC format is practical for real-world iterative applications because of its low preprocessing overhead for format conversion.Keywords
Funding Information
- National Natural Science Foundation of China
This publication has 38 references indexed in Scilit:
- SpV8: Pursuing Optimal Vectorization and Regular Computation Pattern in SpMV2021
- Performance analysis and optimization for SpMV based on aligned storage formats on an ARM processorJournal of Parallel and Distributed Computing, 2021
- Variable-Sized Blocks for Locality-Aware SpMV2021
- CSR2: A New Format for SIMD-accelerated SpMV2020
- A sparse matrix‐vector multiplication method with low preprocessing costConcurrency and Computation: Practice and Experience, 2018
- Structural Agnostic SpMV: Adapting CSR-Adaptive for Irregular Matrices2015
- LightSpMV: Faster CSR-based sparse matrix-vector multiplication on CUDA-enabled GPUs2015
- Regularizing graph centrality computationsJournal of Parallel and Distributed Computing, 2015
- Optimizing and auto-tuning scale-free sparse matrix-vector multiplication on Intel Xeon Phi2015
- Intel Math Kernel Library2014