PLDIFalcon: A Scalable Analytical Cache Model
Compilers often use performance models to decide how to optimize code. This is often preferred over using hardware performance measurements, since hardware measurements can be expensive, limited by hardware availability, and makes the output of compilation non-deterministic. Analytical models, on the other hand, serve as efficient and noise-free performance indicators. Since many optimizations focus on improving memory performance, memory cache miss rate estimations can serve as an effective and noise-free performance indicator for superoptimizers, worst-case execution time analyses, manual program optimization, and many other performance-focused use cases. Existing methods to model the cache behavior of affine programs work on small programs such as those in the Polybench benchmark but do not scale to the larger programs we would like to optimize in production, which can be orders of magnitude bigger by lines of code. These analytical approaches hand of fthe whole program to a Presburger solver and perform expensive mathematical operations on the huge resulting formulas. We develop a scalable cache model for affine programs that splits the computation into smaller pieces that do not trigger the worst-case asymptotic behavior of these solvers. We evaluate our approach on 46 TorchVision neural networks, finding that our model has a geomean runtime of 44.9 seconds compared to over 32 minutes for the state-of-the-art prior cache model, and the latter is actually smaller than the true value because the prior model reached our four-hour time limit on 54
Cite
@article{pitchanathan2024falcon,
author = {Pitchanathan, Arjun and Grover, Kunwar and Grosser, Tobias},
title = {Falcon: A Scalable Analytical Cache Model},
journal = {Proceedings of the ACM on Programming Languages},
series = {PLDI},
volume = {8},
number = {PLDI},
pages = {1854--1878},
year = {2024},
publisher = {ACM},
doi = {10.1145/3656452},
url = {https://doi.org/10.1145/3656452}
}