The output of a cache under the independent reference model - Where did the locality of reference go?

Abstract

We consider a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). We characterize the popularity pmf of the stream of misses from the cache, the so-called output of the cache, for a large class of cache replacement policies, including standard on-demand replacement algorithms such as the policy A_0 and the random policy, as well as the LRU and CLIMB policies. We measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution. Using the notion of majorization to capture the degree of skewness, we show that for the policy A_0 and the random policy, the output always has less locality of reference than the input. However, we show by counterexamples that this is not always the case under the LRU and CLIMB policies when the input is selected according to a Zipf-like pmf. In that case, conjectures are offered (and supported by simulations) as to when LRU or CLIMB caching indeed reduces locality of reference. <p>