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 poses 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" 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 and 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 Computing Frontiers 2008.

- G. Goumas, K. Kourtis, N. Anastopoulos, V. Karakasis and N. Koziris, "Understanding the Performance of Sparse Matrix-Vector Multiplication," Proceedings of the 16th Euromicro International Conference on Parallel, Distributed and network-based Processing (PDP2008), Toulouse, France, 13-15 February, 2008
- K. Kourtis, G. Goumas, and N. Koziris, "Optimizing Sparse Matrix-Vector Multiplication Using Index and Value Compression," Proceedings of the ACM International Conference on Computing Frontiers, Ischia, Italy, 4-6 May, 2008

-- GeorgiosGoumas - 06 Mar 2008

This topic: CSLab > WebHome > Arch > SPMV

Topic revision: r2 - 2008-03-06 - GeorgiosGoumas