SPMV < CSLab

CSLab Web>ActivitiesProjects>SPMV (2011-02-10, KorniliosKourtis) (raw view)
For our more recent work on the Sparse Matrix-Vector Multiplication check: CSX.

---++ 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" ([[http://www.cslab.ece.ntua.gr/~goumas/Publications/downloads/euromicro2008.pdf][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 [[http://www.computingfrontiers.org/][CF'08]] ([[http://www.cslab.ece.ntua.gr/~kkourt/papers/cf08-spmv-kkourt.pdf][pdf]])

Another important optimization that has been widely applied to !SPMV is blocking. While such optimization was initially intended to increase register reuse and the locality of references to the input vector, the main advantage of blocking is that it can significantly reduce the working set of the algorithm, thus leading to less memory traffic, meaning better performance for the case of the memory-bound !SPMV. After attacking the memory intensiveness of the algorithm, the computational part of the kernel becomes more significant as a result. This allows for computation optimizations, such as vectorization, which can add a further performance boost to the blocked kernel. However, preliminary experiments have shown that the performance among different block shapes, which lead to the same working set, can have significantly varying performance, especially in the case of vectorization, due to a number of architectural issues raised from modern commodity microprocessors. Considering the multitude of blocked storage formats available for sparse matrices and the fact that block shapes can heavily affect the performance of !SPMV, a performance model that could accurately predict the performance of a blocked storage format and then guide through the proper selection of both the right method and the right block shape would be desirable. Towards this direction, we have developed a performance model that accounts for both the memory and computation times of the blocked kernels. Our model is capable to better approximate the real execution time and lead to a more fit selection of method and block shape than earlier models, which solely based their prediction to memory traffic.

---+++ Publications
   * V. Karakasis, G. Goumas, and N. Koziris, "[[http://www.cslab.ece.ntua.gr/~bkk/files/papers/icpp09.pdf][Performance models for blocked Sparse Matrix-Vector multiplication kernels]]," International Conference on Parallel Processing (ICPP), Vienna, Austria, September 22&ndash;25, 2009.
   * V. Karakasis, G. Goumas, and N. Koziris, "[[http://www.cslab.ece.ntua.gr/~bkk/files/papers/cse09.pdf][A comparative study of blocking storage methods for sparse matrices on multicore architectures]]," IEEE International Conference on Computational Science and Engineering (CSE), Vancouver, BC, Canada, August 29&ndash;31, 2009.
   * V. Karakasis, G. Goumas, and N. Koziris, "[[http://www.cslab.ece.ntua.gr/~bkk/files/papers/pdsec09.pdf][Exploring the effect of block shapes on the performance of sparse kernels]]," Proceedings of the 23rd International Parallel and Distributed Processing Symposium (IPDPS-PDSEC), Rome, Italy, May 25&ndash;29, 2009.
   * K. Kourtis, G. Goumas and N. Koziris, "[[http://www.cslab.ece.ntua.gr/~kkourt/papers/icpp08-spmv_mt-kkourt.pdf][Improving the Performance of Multithreaded Sparse Matrix-Vector Multiplication using Index and Value Compression  ]]", International Conference on Parallel Processing (ICPP), Portland, Oregon, USA, September 8&dash;12, 2008.
   * K. Kourtis, G. Goumas, and N. Koziris, "[[http://www.cslab.ece.ntua.gr/~kkourt/papers/cf08-spmv-kkourt.pdf][Optimizing Sparse Matrix-Vector Multiplication Using Index and Value Compression]]," Proceedings of the ACM International Conference on Computing Frontiers, Ischia, Italy, 4&ndash;6 May, 2008
   * G. Goumas, K. Kourtis, N. Anastopoulos, V. Karakasis and N. Koziris, "[[http://www.cslab.ece.ntua.gr/~goumas/Publications/downloads/euromicro2008.pdf][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&ndash;15 February, 2008

---+++ Diploma Thesis
   * Implementation of the Sparse Matrix-Vector Multiplication computational kernel on massively threaded graphics processors ([[http://www.cslab.ece.ntua.gr/diplom/files/diploma-gpus-spmv.pdf][pdf]]).
   * A comparative study of blocking storage methods for sparse matrices for the efficient implementation of the Sparse Matrix-Vector Multiplication kernel ([[http://www.cslab.ece.ntua.gr/diplom/files/diploma-spmv-blocking.pdf][pdf]]).
Topic revision: r17 - 2011-02-10 - KorniliosKourtis
CSLab
Research

Courses

CSLab

Home
People
No permission to view TWiki.WebLeftBarWebsList
No permission to view TWiki.WebTopBar
No permission to view TWiki.WebBottomBar