Characterizing the behavior of sparse algorithms on caches

A methodology is presented for modeling the irregular references of sparse codes using probabilistic methods. The behavior on cache of one of the most frequent primitives, SpMxV sparse matrix vector multiply, is analyzed. A model of its references is built, and performance bottlenecks of SpMxV are analyzed using the model and simulations. The main parameters are identified and their role is explained and quantified. This analysis is then used to discuss optimizations of SpMxV. A blocking technique which takes into account the specifics of sparse codes is proposed