Performance Optimization for Sparse AtAx in Parallel on Multicore CPU

Yuan TAO  Yangdong DENG  Shuai MU  Zhenzhong ZHANG  Mingfa ZHU  Limin XIAO  Li RUAN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.2   pp.315-318
Publication Date: 2014/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E97.D.315
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
Keyword: 
sparse AtAx,  compressed sparse block,  compressed sparse rows,  multicore platform,  

Full Text: PDF(633.7KB)>>
Buy this Article




Summary: 
The sparse matrix operation, yy+AtAx, 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 Atx. We develop a multithreaded implementation for the CSB format and apply it to solve yy+AtAx. 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.