Performance Optimization for Sparse A(t)Ax in Parallel on Multicore CPU

摘要

The sparse matrix operation, y - y+A(t)Ax, where A is a sparse matrix and x and y are dense vectors, is a widely used computing pattern in High Performance Computing (HPC) applications. The pattern poses challenge to efficient solutions because both a matrix and its transposed version are involved. An efficient sparse matrix format, Compressed Sparse Blocks (CSB), has been proposed to provide nearly the same performance for both Ax and A(t)x. We develop a multithreaded implementation for the CSB format and apply it to solve y - y+A(t)Ax. Experiments show that our technique outperforms the Compressed Sparse Row (CSR) based solution in POSKI by up to 2.5 fold on over 70 of benchmarking matrices.