Characterizing the miss sequence of the LRU cache
- 31 August 2008
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 36 (2), 119-121
- https://doi.org/10.1145/1453175.1453203
Abstract
Renewed interest in caching systems stems from their wide-spread use for reducing the document download latency over the Internet. Since caches are usually organized in a hierarchical manner, it is important to study the performance properties of tandem caches. The first step in understanding this problem is to characterize the miss stream from one single cache since it represents the input to the next level cache. In this regard, we discover that the miss stream from one single cache is approximated well by the superposition of a number of asymptotically independent renewal processes. Interestingly, when this weakly correlated miss sequence is fed into another cache, this barely observable correlation can lead to measurably different caching performance when compared to the independent reference model. This result is likely to enable the development of a rigorous analysis of the tandem cache performance.Keywords
This publication has 7 references indexed in Scilit:
- The Cache Inference Problem and its Application to Content and Request RoutingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- The LCD interconnection of LRU caches and its analysisPerformance Evaluation, 2006
- Least-recently-used caching with dependent requestsTheoretical Computer Science, 2004
- The output of a cache under the independent reference modelPublished by Association for Computing Machinery (ACM) ,2004
- Analysis and design of hierarchical Web caching systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilitiesThe Annals of Applied Probability, 1999
- On the distribution of search cost for the move-to-front ruleRandom Structures & Algorithms, 1996