Performance Modeling and Analysis of Cache Blocking in Sparse Matrix Vector Multiply
Rajesh Nishtala, Richard W. Vuduc, James Weldon Demmel, Katherine Yelick · 2004
SpMV), or y = y +A x, which is an important and ubiquitous computational kernel. Prior work indicates that cache blocking of SpMV is extremely important for some matrix and machine combinations, with speedups as high as 3x. In this paper we present a new, more compact data structure for cache blocking for SpMV and look at the general question of when and why performance improves. Cache blocking appears to be most e#ective when simultaneously 1) the vector x does not fit in cache 2) the vector y fits in cache 3) the non zeros are distributed throughout the matrix and 4) the non zero density is su#ciently high. In particular we find that cache blocking does not help with band matrices no matter how large x and y are since the matrix structure already lends itself to the optimal access pattern.