Modeling set associative caches behavior for irregular computations
- 1 June 1998
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 26 (1) , 192-201
- https://doi.org/10.1145/277858.277910
Abstract
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
This publication has 7 references indexed in Scilit:
- Trace-driven memory simulationACM Computing Surveys, 1997
- Cache miss equationsPublished by Association for Computing Machinery (ACM) ,1997
- Block algorithms for sparse matrix computations on high performance workstationsPublished by Association for Computing Machinery (ACM) ,1996
- Cache profiling and the SPEC benchmarks: a case studyComputer, 1994
- Cache interference phenomenaPublished by Association for Computing Machinery (ACM) ,1994
- Templates for the Solution of Linear Systems: Building Blocks for Iterative MethodsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1994
- Sparse Matrix AlgebraPublished by Elsevier ,1984