On the Complexity of Cache Analysis for Different Replacement Policies

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

Valentin Touzeau, David Monniaux

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

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 (6)

• A short proof of optimality for the MIN cache replacement algorithm
• Another short proof of optimality for the MIN cache replacement algorithm
• On the analysis of random replacement caches using static probabilistic timing methods for multi-path programs
• Title not available (Why is that?)
• 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)