Modeling data locality for the sparse matrix--vector product using distance measures

摘要

In this work, we model the data locality in the execution of codes with irregular accesses. We focus on the product of a sparse matrix by a dense vector (SPM x V). In the model, locality is established taking into account pairs of rows or columns of sparse matrices. In order to evaluate this locality three functions are introduced based on two parameters: number of entry matches and number of block matches. The model is generalized considering windows of lo- cality (groups of consecutive rows/columns of the matrix). We show results for a broad set of matrices measuring the goodness of our predictions of locality.