Prescriptive Software Caching Using Leases

The cost and performance of a modern system depend on its memory hierarchy. Manual management of the memory hierarchy is complex and not portable. Automatic management is sub-optimal — it reacts to program behavior but does not directly utilize program knowledge. This research seeks a middle ground with a new type of cache called Lease Cache. It enables prescriptive caching by utilizing proogram knowledge, variable cache sizes, and multi-policy caching.

Prescriptive caching takes a principled approach building on theory and optimization. It connects programming and caching directly with programming abstractions and program analysis. The research solves four problems. (1) Lease cache theory, ensuring performance no worse than LRU cache when there is no program knowledge and optimal when there is program knowledge. (2) Lease cache optimization, incuding statistical caching as well as optimization for multi-policy and multi-granularity caching. (3) Locality analysis, combining static analysis and run-time sampling to analyze program locality. (4) Lease cache system, with efficient lease management including the use of approximation to reduce the overhead.