Paper
Fully Symbolic Analysis of Loop Locality: Using Imaginary Reuse to Infer Real Performance
Authors
Yifan Zhu, Yekai Pan, Chen Ding, Yanghui Wu
Abstract
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.
Metadata
Related papers
Cosmic Shear in Effective Field Theory at Two-Loop Order: Revisiting $S_8$ in Dark Energy Survey Data
Shi-Fan Chen, Joseph DeRose, Mikhail M. Ivanov, Oliver H. E. Philcox • 2026-03-30
Stop Probing, Start Coding: Why Linear Probes and Sparse Autoencoders Fail at Compositional Generalisation
Vitória Barin Pacela, Shruti Joshi, Isabela Camacho, Simon Lacoste-Julien, Da... • 2026-03-30
SNID-SAGE: A Modern Framework for Interactive Supernova Classification and Spectral Analysis
Fiorenzo Stoppa, Stephen J. Smartt • 2026-03-30
Acoustic-to-articulatory Inversion of the Complete Vocal Tract from RT-MRI with Various Audio Embeddings and Dataset Sizes
Sofiane Azzouz, Pierre-André Vuissoz, Yves Laprie • 2026-03-30
Rotating black hole shadows in metric-affine bumblebee gravity
Jose R. Nascimento, Ana R. M. Oliveira, Albert Yu. Petrov, Paulo J. Porfírio,... • 2026-03-30
Raw Data (Debug)
{
"raw_xml": "<entry>\n <id>http://arxiv.org/abs/2603.10196v1</id>\n <title>Fully Symbolic Analysis of Loop Locality: Using Imaginary Reuse to Infer Real Performance</title>\n <updated>2026-03-10T19:51:31Z</updated>\n <link href='https://arxiv.org/abs/2603.10196v1' rel='alternate' type='text/html'/>\n <link href='https://arxiv.org/pdf/2603.10196v1' rel='related' title='pdf' type='application/pdf'/>\n <summary>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.\n 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.</summary>\n <category scheme='http://arxiv.org/schemas/atom' term='cs.PL'/>\n <published>2026-03-10T19:51:31Z</published>\n <arxiv:primary_category term='cs.PL'/>\n <author>\n <name>Yifan Zhu</name>\n </author>\n <author>\n <name>Yekai Pan</name>\n </author>\n <author>\n <name>Chen Ding</name>\n </author>\n <author>\n <name>Yanghui Wu</name>\n </author>\n </entry>"
}