Locality-Aware Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication on Many-Core Processors

摘要

Sparse matrix-vector and matrix-transpose-vector multiplication () repeatedly performed as and (or ) for the same sparse matrix is a kernel operation widely used in various iterative solvers. One important optimization for serial is reusing -matrix nonzeros, which halves the memory bandwidth requirement. However, thread-level parallelization of that reuses -matrix nonzeros necessitates concurrent writes to the same output-vector entries. These concurrent writes can be handled in two ways: via atomic updates or thread-local temporary output vectors that will undergo a reduction operation, both of which are not efficient or scalable on processors with many cores and complicated cache-coherency protocols. In this work, we identify five quality criteria for efficient and scalable thread-level parallelization of that utilizes one-dimensional (1D) matrix partitioning. We also propose two locality-aware 1D partitioning methods, which achieve reusing -matrix nonzeros and intermediate -vector entries; exploiting locality in accessing -, -, and -vector entries; and reducing the number of concurrent writes to the same output-vector entries. These two methods utilize rowwise and columnwise singly bordered block-diagonal (SB) forms of