Sparsity and Performance

This dissertation is by Sardar Ansul Haque, University of Lethbridge, Alberta, Canada. 

I'll be doing this review in stages as I go through the dissertation in parts during the next few days. The review will contain content from the dissertation as well as some of my own input.

The SpMV problem is solving Ax=y; where A is a matrix that is mostly zeros and x is a dense vector. This kernel displays irregular vector writes but regular matrix reads and regular vector (y) writes. The problem is natural memory bound and providing intuition into data reuse is hard particularly when the sparsity is unknown prior to run time. This irregular access leads to a large number of cache misses. This is intensified when the matrix and vector do not fit inside of cache. Several machine learning algorithms, PDEs, mesh calculations, and several computational problems utilize sparse structures where sparsity structure is not really known until during runtime. (Hint hint: we need better Top500 benchmarks ;) )

Most data structures for storing sparse matrices use array-based data structures to introduce some sort of regularity into the data access patterns. Most commonly, column indices and row indices of every non zero element are stored into arrays leading to a form of compressed storage. Compressed Row Storage and Compressed Column Storage are some of the popular storage formats. The whole point of these different storages is to regularize data access and ensure either Spatial or Temporal Locality. Spatial locality of A is reordering A such that the nonzeros in each row are consecutive. This improves the regularity of accessing A. Temporal locality says that the data (parts of the vector) recently used will be used again by A.