Exact analysis of the cache behavior of nested loops

Conference Paper

We develop from first principles an exact model of the behavior of loop nests executing in a memory hierarchy, by using a nontraditional classification of misses that has the key property of composability. We use Presburger formulas to express various kinds of misses as well as the state of the cache at the end of the loop nest. We use existing tools to simplify these formulas and to count cache misses. The model is powerful enough to handle imperfect loop nests and various flavors of non-linear array layouts based on bit interleaving of array indices. We also indicate how to handle modest levels of associativity, and how to perform limited symbolic analysis of cache behavior. The complexity of the formulas relates to the static structure of the loop nest rather than to its dynamic trip count, allowing our model to gain efficiency in counting cache misses by exploiting repetitive patterns of cache behavior. Validation against cache simulation confirms the exactness of our formulation. Our method can serve as the basis for a static performance predictor to guide program and data transformations to improve performance. © 2001 ACM.

Full Text

Duke Authors

Cited Authors

  • Chatterjee, S; Parker, E; Hanlon, PJ; Lebeck, AR

Published Date

  • January 1, 2001

Published In

Volume / Issue

  • 36 / 5

Start / End Page

  • 286 - 297

International Standard Serial Number (ISSN)

  • 0362-1340

Digital Object Identifier (DOI)

  • 10.1145/381694.378859

Citation Source

  • Scopus