Modeling and improving locality for the sparse-matrixvector product on cache memories
A model for representing and improving the locality exhibited by the execution of sparse irregular problems is developed in this work. We focus on the product of a sparse matrix by a dense vector (SpMV). We consider the cache memory as a representative level of the memory hierarchy. Locality is evaluated through four functions based on two parameters called entry matches and line matches. In order to increase the locality, two algorithms are applied: one based on the construction of minimum spanning trees and the other on the nearest-neighbor heuristic. These techniques were tested and compared with some standard ordering algorithms.
locality cache memory sparse matrix memory hierarchy ordering algorithms