Exact Analysis of the Cache Behavior of Nested Loops

We develop from first principles an exact model of the behavior of loop nests executing in a memory hierarchy, by using a nontra-ditional classification of misses that has the key property of com-posability. 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 in-terleaving of array indices. We also indicate how to handle modest levels of associativity, and how to perform limited symbolic analy-sis 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. 1