The complexity gap in the static analysis of cache accesses grows if procedure calls are added

  • Monniaux, David
ORKG logo Add to ORKG
Publication date
May 2022
Publisher
Springer Science and Business Media LLC

Abstract

International audienceThe static analysis of cache accesses consists in correctly predicting which accesses are hits or misses.While there exist good exact and approximate analyses for caches implementing the least recently used (LRU) replacement policy, such analyses were harder to find for other replacement policies.A theoretical explanation was found: for an appropriate setting of analysis over control-flow graphs, cache analysis is PSPACE-complete for all common replacement policies (FIFO, PLRU, NMRU) except for LRU, for which it is only NP-complete.In this paper, we show that if procedure calls are added to the control flow, then the gap widens: analysis remains NP-complete for LRU, but becomes EXPTIME-complete for the three other poli...

Extracted data

Related items

The complexity gap in the static analysis of cache accesses grows if procedure calls are added
  • Monniaux, David
May 2022

International audienceThe static analysis of cache accesses consists in correctly predicting which a...

On the complexity of cache analysis for different replacement policies
  • Monniaux, David
  • Touzeau, Valentin
January 2019

International audienceModern processors use cache memory: a memory access that “hits” the cache retu...

Fast and exact analysis for LRU caches
  • Maïza, Claire
  • Touzeau, Valentin
  • Monniaux, David
  • Reineke, Jan
January 2019

International audienceFor applications in worst-case execution time analysis and in security, it is ...

We use cookies to provide a better user experience.