BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation - Laboratoire d'Informatique de Paris 6 Accéder directement au contenu
Article Dans Une Revue ACM Transactions on Architecture and Code Optimization Année : 2023

BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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 Consultations
18 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More