Efficient SpMV for Graph Matrices Through Vectoring and Caching

Sparse Matrix-Vector Multiplication (SpMV) plays a pivotal role in a wide range of scientific computations. However, SpMV operations on graph matrices often encounter challenges such as inefficient cache utilization and imbalanced workloads. This paper presents a novel solution, named VeCa, to accelerating SpMV for sparse graph matrices by integrating selective vectorization with hierarchical blocking. Firstly, the matrix is divided into small blocks fitting in the cache, where multi-level partitioning occurs according to the estimated workloads per blocks. Then, the rows within each block is selectively vectorized with distinct instruction sets. Experimental results show that VeCa considerably outperforms state-of-the-art SpMV methods and graph processing systems, achieving a speedup of 1.29 \(\times \) compared to the second fastest approach. Moreover, a comprehensive evaluation is conducted, analyzing performance factors, branch prediction, cache efficiency, and parameter tuning, to promote a thorough understanding of VeCa’s efficacy.