BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation - Sorbonne Université Access content directly
Journal Articles ACM Transactions on Architecture and Code Optimization Year : 2023

BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation

Abstract

For Affine Control Programs or Static Control Programs (SCoP), symbolic counting of reuse distances could induce polynomials for each reuse pair. These polynomials along with cache capacity constraints lead to non-affine (semi-algebraic) sets; and counting these sets is considered to be a hard problem. The state-of-the-art methods use various exact enumeration techniques relying on existing cardinality algorithms that can efficiently count affine sets. We propose BullsEye , a novel, scalable, accurate, and problem-size independent approximation framework. It is an analytical cache model for fully associative caches with LRU replacement policy focusing on sampling and linearization of non-affine stack distance polynomials. First, we propose a simple domain sampling method that can improve the scalability of exact enumeration. Second, we propose linearization techniques relying on Handelman’s theorem and Bernstein’s representation . To improve the scalability of the Handelman’s theorem linearization technique, we propose template (Interval or Octagon) sub-polyhedral approximations. Our methods obtain significant compile-time improvements with high-accuracy when compared to HayStack on important polyhedral compilation kernels such as nussinov , cholesky , and adi from PolyBench , and harris , gaussianblur from LLVM -TestSuite. Overall, on PolyBench kernels, our methods show up to 3.31× (geomean) speedup with errors below ≈ 0.08% (geomean) for the octagon sub-polyhedral approximation.
Fichier principal
Vignette du fichier
BullsEye_arxiv_Jan_2023.pdf (1.54 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03918318 , version 1 (31-01-2023)

Identifiers

Cite

Nilesh Rajendra Shah, Ashitabh Misra, Antoine Miné, Rakesh Venkat, Ramakrishna Upadrasta. BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation. ACM Transactions on Architecture and Code Optimization, 2023, 20 (1), pp.1-28. ⟨10.1145/3558003⟩. ⟨hal-03918318⟩
25 View
19 Download

Altmetric

Share

Gmail Facebook X LinkedIn More