Modeling and Improving Locality for Irregular Problems: Sparse Matrix-Vector product on Cache Memories as a Case Study

摘要

In this paper we introduce a model for representing and improving the locality of sparse matrices for irregular problems. We focus out attention on thebehavior of iterative methods for hte solution of sparse linear systems with irregular patterns. In particular the prouct of a sparse matrix by a nese vector is closely examined, as this is oe of the basic kernels in such codes. As a representative level of the memory hierarchy, we ocnsider the cache memory. In our model, locality is measured taking into account pairs of rows or columns of sparse matrices. In order to evaluate this locality four functins based on two parameters called entry matches and cache line matches are introduced. Using an analogy of this problem ot the traveling salesman problem we have applied tw algorithms in order to solve it; one based on the construction of minimum spanning trees and the other on the nearest-neighbor heuvristic. These techniques were tested over a set of sparse matrices. The results wre assesed through the measurement of cache misses on a standard cache memory.