Cache performance prediction typically works empirically: run the code, count the misses, build scaling rules. The rules are specific to the hardware configuration and input size tested. Change either and you need to re-measure.
Bao et al. derive the cache behavior symbolically. For affine loop nests — the regular nested loops that dominate scientific computing — they produce polynomial expressions where cache miss counts are explicit functions of input size and cache parameters. Once derived (about 41 seconds per kernel), evaluating the polynomial for any configuration takes under a millisecond. The prediction accuracy across 41 scientific kernels reaches 99.6% against simulated L1 behavior.
The key concept is imaginary reuse. Real cache reuse occurs when a memory access finds its data already in cache from a previous access. Imaginary reuse occurs when a memory location is accessed but not yet cached — a potential reuse that the cache geometry prevents. By tracking both real and imaginary reuse symbolically, the compiler constructs exact polynomials for the data movement volume without ever running the program.
The through-claim is about the relationship between execution and analysis. Empirical cache measurement conflates the program's data access pattern with the hardware's caching policy. Symbolic analysis separates them: the polynomial captures the program's locality structure as a mathematical object independent of hardware. The same polynomial predicts behavior across all cache sizes and associativities. The program's relationship to memory is a function, not a measurement — and functions generalize where measurements don't.