The Study of Impact of Matrix-Processor Mapping on the Parallel Sparse Matrix-Vector Multiplication

Sparse matrix-vector multiplication (shortly spM × V) is one of the most common subroutines in the numerical linear algebra. The parallelization of this task looks easy and straightforward, but it is not optimal in general case. This paper discuss some matrix-processor mappings and their impact on parallel spM × V execution on massively parallel systems. We try to balance the performance and the overhead of the required transformation. We also present algorithms for redistribution. We propose four quality measures and derive lower and upper bound for different mappings. Our spM × V algorithms are scalable for almost all matrices arising from various technical areas.