Fully Symbolic Analysis of Loop Locality: Using Imaginary Reuse to Infer Real Performance
This provides a precise and efficient method for compiler optimization in high-performance computing, though it is incremental as it builds on existing affine loop analysis.
The paper tackles the problem of predicting cache performance for affine loop nests by developing a fully symbolic theory of locality that derives locality as polynomials, achieving 99.6% accuracy in data movement prediction compared to simulated cache across 41 scientific kernels and tensor operations.
This paper presents a new theory of locality and its compiler support. The theory is fully symbolic and derives locality as polynomials, and the compiler analysis supports affine loop nests. They derive cache-performance scaling in quadratic and reciprocal expressions and are more general and precise than empirical scaling rules. Evaluated on a benchmark suite of 41 scientific kernels and tensor operations, the compiler requires an average of 41 seconds to derive the locality polynomials. After derivation, predicting the cache miss count for any given input size and cache configuration takes less than a millisecond. Across all tests--with and without loop fusion--the accuracy in the data movement prediction is 99.6\%, compared to simulated set-associative L1 data cache.