EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Falcon: A Scalable Analytical Cache Model

Arjun Pitchanathan, Kunwar Grover, Tobias Grosser

Proceedings of the ACM on Programming Languages · 20.06.2024 · 8 (PLDI) · 1854-1878

DOI: 10.1145/3656452 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 20.06.2024. Verfasst von Arjun Pitchanathan und 2 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 42 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: HORIZON EUROPE Digital, Industry and Space.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 off the 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% of the networks, and this limit was never reached by our tool. Our model exploits parallelism effectively: running it on sixteen cores is 8.2x faster than running it single-threaded. While the state-of-the-art model takes over four hours to analyze a majority of the benchmark programs, Falcon produces results in at most 3 minutes and 3 seconds; moreover, after a local modification to the program being analyzed, our model efficiently updates the predictions in 513 ms on average (geomean). Thus, we provide the first scalable analytical cache model. CCS Concepts: • Software and its engineering → Compilers .

Förderung

  • HORIZON EUROPE Digital, Industry and Space

Zitieren

APA

Pitchanathan, A., Grover, K., & Grosser, T. (2024). Falcon: A Scalable Analytical Cache Model. Proceedings of the ACM on Programming Languages, 8(PLDI), 1854-1878. https://doi.org/10.1145/3656452

Vancouver

Pitchanathan A, Grover K, Grosser T. Falcon: A Scalable Analytical Cache Model. Proceedings of the ACM on Programming Languages. 2024;8(PLDI):1854-1878. doi:10.1145/3656452

BibTeX
@article{Pitchanathan2024,
  author = {Pitchanathan, Arjun and Grover, Kunwar and Grosser, Tobias},
  title = {Falcon: A Scalable Analytical Cache Model},
  journal = {Proceedings of the ACM on Programming Languages},
  year = {2024},
  volume = {8},
  number = {PLDI},
  pages = {1854--1878},
  doi = {10.1145/3656452}
}
Kostenlos starten →