Parallel patterns: sparse matrix computation: An introduction to data compression and regularization

This chapter introduces the parallel sparse matrix-vector computation pattern. It starts with the basic concepts of sparse matrices as a data compaction technique. It then introduces a kernel based on Compressed Sparse Row (CSR) data storage for sparse matrices. The ELL format with data padding is then introduced as a regularization technique for reduced control divergence and improved memory coalescing. The COO format is further introduced, a complementary regularization technique to reduce padding overhead. Finally, the Jagged Diagonal Storage (JDS) format based on sorting is introduced to smooth out variation from one row to the next row, allowing one to further reduce padding overhead in the regularization process. The chapter shows that the same sparse matrix kernel code can exhibit very different performance behaviors on different data sets.