Static Probabilistic Timing Analysis of Random Replacement Caches using Lossy Compression
David Griffin, Benjamin Lesage, Alan Burns, Robert Ian Davis · 2014
The analysis of random replacement caches is an area that has recently attracted considerable attention in the field of probabilistic real-time systems. A major problem with performing static analysis on such a cache is that the relatively large number of successor states on a cache miss (equal to the cache associativity) renders approaches such as Collecting Semantics intractable. Other approaches must contend with non-trivial behaviours, such as the non-independence of accesses to the cache, which tends to lead to overly pessimistic or computationally expensive analyses.