Reuse-based Analytical Models for Caches

File(s):

Author(s): Wood, David A.; Sen, Rathijit
Citation: TR1706
Date: Nov 18, 2011
Subject(s): RANDOM; PLRU; LRU; repalcement policies; reuse distance; stack distance; cache
Abstract: 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.
Permanent link: http://digital.library.wisc.edu/1793/60995
Export: Export to RefWorks