Static probabilistic timing analysis of random replacement caches using Lossy Compression

TY - GEN

T1 - Static probabilistic timing analysis of random replacement caches using Lossy Compression

AU - Griffin, David

AU - Lesage, Benjamin

AU - Burns, Alan

AU - Davis, Robert I.

N1 - Publisher Copyright: Copyright © 2014 ACM.

PY - 2014/10/8

Y1 - 2014/10/8

N2 - 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. Utilising techniques from the field of Lossy Compression, where compactly representing large volumes of data without losing valuable data is the norm, this paper outlines a technique for applying compression to the Collecting Semantics of a Random Replacement Cache. This yields a Must and May analysis. Experimental evaluation shows that, with appropriate parameters, this technique is more accurate and significantly faster than current state-of-the-art techniques.

AB - 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. Utilising techniques from the field of Lossy Compression, where compactly representing large volumes of data without losing valuable data is the norm, this paper outlines a technique for applying compression to the Collecting Semantics of a Random Replacement Cache. This yields a Must and May analysis. Experimental evaluation shows that, with appropriate parameters, this technique is more accurate and significantly faster than current state-of-the-art techniques.

UR - http://www.scopus.com/inward/record.url?scp=84985914379&partnerID=8YFLogxK

U2 - 10.1145/2659787.2659809

DO - 10.1145/2659787.2659809

M3 - Conference contribution

AN - SCOPUS:84985914379

T3 - ACM International Conference Proceeding Series

SP - 289

EP - 298

BT - Proceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014

PB - Association for Computing Machinery, Inc

T2 - 22nd International Conference on Real-Time Networks and Systems, RTNS 2014

Y2 - 8 October 2014 through 10 October 2014

ER -