Processor speeds are improving at a much faster rate than the speeds
of accessing main memory.As a result, data access time dominates the
execution times of many programs. Understanding the behavior of
programs executing in a memory hierarchy is therefore an important
part of improving program performance. This work describes
an analytical framework for understanding the behavior of loop-oriented
programs executing in a memory hierarchy. The framework has three
components: 1) an alternative classification of cache misses that makes
it possible to obtain the exact cache behavior of a sequence of
program fragments by combining the cache behavior of the individual
fragments; 2) the use of Presburger arithmetic to model data access
patterns and describe events such as cache misses; and 3) algorithms
exploiting the connection among Presburger arithmetic, automata theory,
and graph theory to allow an exact model of cache behavior.

The analytical framework presented goes beyond existing analytical
frameworks for modeling cache behavior: it handles set-associative
caches, data cache and translation lookaside buffer (TLB) misses,
imperfect loop nests, and nonlinear array layouts in an exact
manner. Experiments show both the framework's value in the exploration
of new memory system designs and its usefulness in guiding code and
data transformations for improved program performance.