Cache Behavior Modelling for Codes Involving Banded Matrices
Diego Andrade, Basilio B. Fraguela and Ramón Doallo
The 19th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2006)
New Orleans, Louisiana, November 2-4, 2006
Abstract
Understanding and improving the memory hierarchy behavior is one of the most important challenges in current architectures. Analytical models are a good approach for this, but they have been traditionally limited by either their restricted scope of application or their lack of accuracy. Most models can only predict the cache behavior of codes that generate regular access patterns. The Probabilistic Miss Equation(PME) model is able nevertheless to model accurately the cache behavior for codes with irregular access patterns due to data-dependent conditionals or indirections. Its main limitation is that it only considers irregular access patterns that exhibit an uniform distribution of the accesses. In this work, we extend the PME model to enable to analyze more realistic and complex irregular accesses. Namely, we consider indirections due to the compressed storage of most real banded matrices, which appear very often in scientific and engineering codes.