Performance Analysis of the Parallel Shared-Memory Sparse Matrix-Vector Multiplication on Unstructured Matrices

This paper investigates sparse matrix-vector (SpMV) multiplication algorithm performance for unstructured sparse matrices. The development of an SpMV multiplication algorithm for this type of data is hard due to two factors. First, parallel load balancing issues arise because of the unpredictable nonzero structure. Second, SpMV multiplication algorithms are inevitably memory-bound because the sparsity causes a low arithmetic intensity. Three state-of-the-art algorithms for parallel SpMV multiplication on shared-memory systems are discussed. Three new hybrid algorithms are developed which combine optimization techniques of the current algorithms. A modern and high-performance implementation of all discussed algorithms is provided as open-source software. Using this implementation the algorithms are compared to Intel’s oneMKL library. Furthermore, SpMV multiplication algorithms require the matrix to be stored in a specific storage format. Therefore, the conversion time between these storage formats is also analyzed. Both tests are performed for multiple unstructured sparse matrices on different machines: two multi-CPU and two single-CPU architectures. We show that one of the newly developed algorithms outperforms oneMKL by 40% on one of the multi-CPU architectures.