An efficient SIMD compression format for sparse matrix-vectormultiplication

摘要

Sparse matrix-vectormultiplication (SpMV) is an essential kernel in sparse linear algebra and hasbeen studied extensively on all modern processor and accelerator architectures. CompressedSparse Row (CSR) is a frequently used format for sparse matrices storage. However, CSR-basedSpMV has poor performance on processors with vector units. In order to take full advantageof SIMD acceleration technology in SpMV, we proposed a new matrix storage format calledCSR-SIMD. The newstorage format compresses the non-zero elements intomany variable-lengthdata fragments with consecutive memory access addresses. Thus, the data locality of sparsematrix A and dense vector x expands and the floating-point operations for each fragment canbe completely calculated by vectorized implementation on wide SIMD units. Our experimentalresults indicate that CSR-SIMD has better storage efficiency and low-overhead for format conversion.Besides, the newformat achieves high scalability on wide SIMD units. In comparison withtheCSR-based andBCSR-basedSpMV,CSR-SIMD obtains better performance on FT1500A, IntelXeon, and Intel Xeon Phi.