Cache management is important in exploiting locality and reducing data movement. Ideal cache management requires replacement of the cache block which will be used furthest in the future at every cache miss. In this work, we explore a new cache design called a lease cache. In a lease cache, every block is assigned a positive integer lease representing its maximum lifetime in cache if it is not reused. Instead of making eviction decisions at the time of a cache miss, a lease cache makes decisions when data is placed in cache. In this way, a lease can be thought of as an allocation of cache resources. Lease caching requires two problems to be solved: how to gather information required to assign leases, and how to use this information to assign the leases which best make use of cache resources. For information gathering, memory accesses with a high hit probability and low expected time in cache are valuable. These accesses should be prioritized by the lease assignment algorithm. In this work, we present existing solutions to the problem of optimal lease assignment in variable-sized cache, as well as optimizations for balanced cache allocation in fixed-sized cache. Furthermore, we propose the independent tenancy model for understanding dynamic variation in lease cache allocation, which can help to close the gap between optimal variable-size performance and fixed-size performance. We propose new contexts for lease cache implementation and examine the challenges that arise from these design shifts. We discuss possible solutions to the information-gathering problem, through compiler tools that use static sampling techniques to extract RI distributions for compile-time enumerable programs, and through dynamic statistical measurements for programs that are not amenable to static analysis.

Advisor: Prof. Chen Ding (Computer Science) 

Committee: Prof. Kaave Hosseini (Computer Science), Prof. Michael Scott (Computer Science), Prof. Dorin Patru (Rochester Institute of Technology)