On the complexity of cache analysis for different replacement policies

DOI10.1145/3366018zbMATH Open1473.68097arXiv1811.01740OpenAlexW2985278829WikidataQ130952142 ScholiaQ130952142MaRDI QIDQ5215470FDOQ5215470

Authors: David Monniaux, Valentin Touzeau 

Publication date: 11 February 2020

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

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.

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

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

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)

Cited In (9)

• 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
• Timing predictability of cache replacement policies
• Title not available (Why is that?)
• 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)