Chapter 10

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 ...

Get Programming Massively Parallel Processors, 3rd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.