Uniform lease vs. LRU cache: analysis and evaluation
- 22 June 2021
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
Lease caching is a new technique that provides greater control of the cache than what is allowed in conventional caches. The simplest control is uniform lease (UL), which means that all leases are identical in length. The UL cache is prescriptive and based on allocation. In comparison, a conventional cache is reactive and based on replacement. They represent two fundamentally different approaches to cache management. This paper shows two results. First, it proves that a previous model of the LRU cache called Higher-Order Theory of Locality (HOTL) computes the miss ratio of the UL cache. Second, it shows how UL and LRU behave the same and differently through contrived examples and in the 30 benchmarks of PolyBench.Keywords
Funding Information
- National Science Foundation (CNS-1909099, CCF-1717877)
This publication has 8 references indexed in Scilit:
- A Relational Theory of LocalityACM Transactions on Architecture and Code Optimization, 2019
- Beating OPT with Statistical Clairvoyance and Variable Size CachingPublished by Association for Computing Machinery (ACM) ,2019
- Back to the Future: Leveraging Belady's Algorithm for Improved Cache ReplacementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2016
- Improving Cache Management Policies Using Dynamic Reuse DistancesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Program locality analysis using reuse distanceACM Transactions on Programming Languages and Systems, 2009
- Improving the ratio of memory operations to floating-point operations in loopsACM Transactions on Programming Languages and Systems, 1994
- Evaluation techniques for storage hierarchiesIBM Systems Journal, 1970
- The working set model for program behaviorCommunications of the ACM, 1968