Reuse-based Analytical Models for Caches

We develop a reuse distance/stack distance based analytical modeling framework for efficient, online prediction of cache performance for a range of cache configurations and replacement policies LRU, PLRU, RANDOM, NMRU. Such a predictive framework can be extremely useful in selecting the optimal parameters in a dynamic reconfiguration environment that performs power-shifting or resource reallocation through cache partitioning. Our framework unifies existing cache miss-rate prediction techniques such as Smith?s associativity model, Poisson variants, and hardware way-counter based schemes. We also show how to adapt way-counters to work when the number of sets in the cache changes. We propose a novel low-overhead hardware mechanism to estimate reuse distance/stack distance distributions using a combination of set-sampling and time-sampling. This can be used even in cases where using way-counters is not possible, e.g. RANDOM/NMRU replacement policies.