CNS Core:Small: Prescriptive Software Caching Using Leases

University Of Rochester, Rochester NY

Investigators

Abstract

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 program 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 Least Recently Used (LRU) cache when there is no program knowledge and optimal when there is program knowledge. (2) Lease cache optimization, including 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. Caching techniques are widely used in today's computing infrastructure from virtual memory management to server cache and memory cache. Lease cache is a new paradigm where an application can directly control cache management. Under this paradigm, future efforts by the research community and industry may substantially improve the utilization of computer memory for practically all applications and systems. Beyond its technical content, the project will develop material to teach locality theory and optimization and strive to increase the diversity and participation in computing research and development. The project will produce software and data from experiments for research papers. Source code, experimental data and metadata will be maintained in version-controlled repositories using open-source software (git and/or Mercurial). Source code will be made available through the Internet on the University website and on publicly-accessible source code repositories such as Github and/or Bitbucket. The repositories will be maintained as long as the research is on-going and remains relevant and at least for three years after the end of the project in 2022. The project page is https://roclocality.org/2019/04/12/nsf1909099/. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.