OVERT: Orchestrating Vector-Scalar Execution for Efficient SpMV on Modern CPUs

Sparse Matrix-Vector Multiplication (SpMV) is a key operation in many applications, and optimizing its performance is crucial for achieving high computational efficiency. Existing efforts have optimized SpMV performance on CPUs with corresponding sparse matrix formats adopted. However, the performance of existing SpMV implementations primarily focuses on maximizing hardware's vector unit usage, neglecting the potential for exploiting idle scalar units simultaneously. To address such limitation, we propose OVERT, a new storage format of sparse matrix designed to exploit both vector and scalar execution units on modern CPUs for accelerating SpMV performance. OVERT, containing two format variants (OVERT-S and OVERT-E), outperforms existing formats by partitioning the matrix into multiple data panels, which can efficiently utilize vector and scalar units. Moreover, we propose an effective format selection model that dynamically chooses the optimal format variant from OVERT according to the characteristics of the input matrix. Experimental results on SuiteSparse show that OVERT achieves an average speedup of 3.91 × against Intel MKL on X86 CPU and an average speedup of 1.24 × against ArmPL on ARM CPU.