Aarhus University Seal

Efficient approximations for cache-conscious data placement

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


  • Ali Ahmadi, Sharif University of Technology
  • ,
  • Majid Daliri, University of Tehran
  • ,
  • Amir Kafshdar Goharshady, Hong Kong University of Science and Technology
  • ,
  • Andreas Pavlogiannis

There is a huge and growing gap between the speed of accesses to data stored in main memory vs cache. Thus, cache misses account for a significant portion of runtime overhead in virtually every program and minimizing them has been an active research topic for decades. The primary and most classical formal model for this problem is that of Cache-conscious Data Placement (CDP): given a commutative cache with constant capacity k and a sequence ς of accesses to data elements, the goal is to map each data element to a cache line such that the total number of cache misses over ς is minimized. Note that we are considering an offline single-threaded setting in which ς is known a priori. CDP has been widely studied since the 1990s. In POPL 2002, Petrank and Rawitz proved a notoriously strong hardness result: They showed that for every k ≥ 3, CDP is not only NP-hard but also hard-to-approximate within any non-trivial factor unless P=NP. As such, all subsequent works gave up on theoretical improvements and instead focused on heuristic algorithms with no theoretical guarantees. In this work, we present the first-ever positive theoretical result for CDP. The fundamental idea behind our approach is that real-world instances of the problem have specific structural properties that can be exploited to obtain efficient algorithms with strong approximation guarantees. Specifically, the access graphs corresponding to many real-world access sequences are sparse and tree-like. This was already well-known in the community but has only been used to design heuristics without guarantees. In contrast, we provide fixed-parameter tractable algorithms that provably approximate the optimal number of cache misses within any factor 1 + ", assuming that the access graph of a specific degree d "is sparse, i.e. sparser real-world instances lead to tighter approximations. Our theoretical results are accompanied by an experimental evaluation in which our approach outperforms past heuristics over small caches with a handful of lines. However, the approach cannot currently handle large real-world caches and making it scalable in practice is a direction for future work.

Original languageEnglish
Title of host publicationProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation
EditorsRanjit Jhala, Isil Dillig
Number of pages15
Place of publicationNew York
PublisherAssociation for Computing Machinery
Publication yearJun 2022
ISBN (Electronic)9781450392655
Publication statusPublished - Jun 2022
Event43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2022 - Virtual, Online, United States
Duration: 13 Jun 202217 Jun 2022


Conference43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2022
LandUnited States
ByVirtual, Online
SeriesProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Bibliographical note

Publisher Copyright:
© 2022 ACM.

    Research areas

  • approximation, cache management, cache misses, data placement, parameterization, treewidth

See relations at Aarhus University Citationformats

ID: 281261867