Sparse Matrix-Vector Multiplication

Sparse Matrix-Vector Multiplication (SPMV) is one of the most important computational kernels, lying at the heart of very effective and popular iterative solution methods like Conjugate Gradient (CG) and Generalized Minimal Residual (GMRES). Sparse matrices are generally stored in special formats (e.g. the Compressed Storage Row format) in order to save memory space and computations. SPMV is a challenging kernel posing various problems to the underlying architecture that need to be well understood in order consolidate an effective optimization process. Our work "Understanding the Performance of Sparse Matrix-Vector Multiplication" (pdf) published in Euromicro/PDP 2008 performs an extensive experimental evaluation of SPMV that leads to a number of optimization guidelines. The major problem that needs to be addressed is the memory bottleneck caused by the data intensity of the algorithm, which is further aggravated by the extra indexing information kept by the sparse matrix storage format. One approach to deal with this problem is to sacrifice CPU cycles in order to compress the data involved in the kernel and consequently alleviate the memory bus from excessive data transfers. A method to compress the indexing information of the matrix structure and the numerical values of the matrix is presented in CF'08 (pdf)

Publications


This topic: CSLab > ActivitiesProjects > SPMV
Topic revision: r9 - 2008-03-11 - NikosAnastopoulos
 
This site is powered by the TWiki collaboration platform Powered by Perl

No permission to view TWiki.WebBottomBar