Comparing Locality of Reference - Some Folk Theorems for the Miss Rates and the Output of Caches
Abstract
The performance of demand-driven caching is known to depend on the locality of reference exhibited by the stream of requests made to the cache. In spite of numerous efforts, no consensus has been reached on how to formalize this notion, let alone on how to compare streams of requests on the basis of their locality of reference. The authors take on this issue with an eye towards validating operational expectations associated with the notion of locality of reference. They focus on two "folk theorems," namely (1) the stronger locality of reference, the smaller the miss rate of the cache; and (2) good caching is expected to produce an output stream of requests exhibiting less locality of reference than the input stream of requests. The authors discuss these two folk theorems in the context of a cache operating under a demand-driven replacement policy when document requests are modeled according to the Independent Reference Model (IRM). As they propose to measure strength of locality of reference in a stream of requests through the skewness of its popularity distribution, they introduce the notion of majorization as a means for capturing this degree of skewness. They show that these folk theorems hold for caches operating under a large class of cache replacement policies, including the optimal policy and the random policy, but may fail under the Least Recently Used (LRU) policy.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2004
- Accession Number
- ADA444359
Entities
People
- Armand M. Makowski
- Sarut Vanichpun
Organizations
- University of Maryland