Modeling Set Associative Caches Behavior for Irregular Computations

While much work has been devoted to the study of cache behavior during the execution of codes with regular access patterns, little attention has been paid to irregular codes. An important portion of these codes are scientific applications that handle compressed sparse matrices. In this work a probabilistic model for the prediction of the number of misses on a K-way associative cache memory considering sparse matrices with a uniform or banded distribution is presented. Two different irregular kernels are considered: the sparse matrix-vector product and the transposition of a sparse matrix. The model was validated with simulations on synthetic uniform matrices and banded matrices from the Harwell-Boeing collection. Keywords: Sparse matrix, irregular computation, cache performance, probabilistic model. 1 Introduction Sparse matrices are in the kernel of many numerical applications. Their compressed storage [2], which permits both operations and memory savings, generates irregular access ..