High Performance Parallelism Pearls edition:1st pages:1-20
Sparse computations are ubiquitous in computational codes, with the sparse matrix-vector (SpMV) multiplication as an important computational kernel in software for simulation (e.g., computational fluid dynamics, structural analysis), optimization (e.g., economics, transport scheduling), data analysis (e.g., drug testing, social networks), and so on.
A sparse matrix is characterized by having most of its elements equal to zero. To take advantage of the sparsity, such matrices are stored in specifically designed data structures so that meaningless multiplications with zeroes can be avoided.
Current hardware trends lead to an increasing width of vector units as well as to decreasing effective bandwidth-per-core. For sparse computations, these two trends conflict. In this chapter, we consider sparse matrix computations on multicore architectures with vector processing capabilities, and design a usable and efficient data structure for vectorized sparse computations.