On the complexity of cache analysis for different replacement policies

DOI10.1145/3366018MaRDI QIDQ5215470zbMATH OpenOpenAlexWikidataFDO

Authors David Monniaux, Valentin Touzeau

Publication date 11 February 2020

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.01740

zbMATH Keywords

complexityNP-completenessPSPACE-completenessstatic analysiscachescache analysis

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Abstract: Modern processors use cache memory: a memory access that "hits" the cache returns early, while a "miss" takes more time. Given a memory access in a program, cache analysis consists in deciding whether this access is always a hit, always a miss, or is a hit or a miss depending on execution. Such an analysis is of high importance for bounding the worst-case execution time of safety-critical real-time programs.There exist multiple possible policies for evicting old data from the cache when new data are brought in, and different policies, though apparently similar in goals and performance, may be very different from the analysis point of view. In this paper, we explore these differences from a complexity-theoretical point of view. Specifically, we show that, among the common replacement policies, LRU (Least Recently Used) is the only one whose analysis is NP-complete, whereas the analysis problems for the other policies are PSPACE-complete.

Recommendations

• The complexity gap in the static analysis of cache accesses grows if procedure calls are added
• Timing predictability of cache replacement policies
• Optimal Worst Case Formulas Comparing Cache Memory Associativity
• The hardness of cache conscious data placement
• Abstract Interpretation of FIFO Replacement

Cited in

(11)

• Data cache organization for accurate timing analysis
• A short proof of optimality for the MIN cache replacement algorithm
• Another short proof of optimality for the MIN cache replacement algorithm
• H-NMRU: An efficient cache replacement policy with low area
• On the analysis of random replacement caches using static probabilistic timing methods for multi-path programs
• Security Analysis of Cache Replacement Policies
• Timing predictability of cache replacement policies
• scientific article; zbMATH DE number 1760016 (Why is no real title available?)
• Abstract Interpretation of FIFO Replacement
• The complexity gap in the static analysis of cache accesses grows if procedure calls are added
• Optimal Worst Case Formulas Comparing Cache Memory Associativity

This page was built for publication: On the complexity of cache analysis for different replacement policies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215470)