Cache Miss Equations: Precise Miss Analysis for Program Transformations in Caches with Arbitrary Associativity

Margaret Martonosi
Princeton University

The peak performance of current microprocessors is improving at dramatic rates, but unfortunately memory performance has not kept pace. While caches are often effective at masking this performance gap, program transformations are often needed to allow programs to use cache most effectively.

In this talk, I discuss compile-time mechanisms for improving memory system behavior using "Cache Miss Equations" (CMEs). CMEs are a mathematical framework we have developed that allows the compiler to analyze potential cache miss points in scientific code by expressing cache conflicts in terms of a system of linear Diophantine equations. I describe and give performance results for precise loop transformation algorithms we have developed. These algorithms improve cache performance by analyzing the number of CME solution points given a particular memory hierarchy. Thus, they can specialize array positions and loop constructs to the given hardware structure. In particular, I present a tiling algorithm that uses CME analysis to eliminate self-interference misses in blocked linear algebra codes.

Further info and related paper(s):

• send mail to Margaret