Pareto optimization for cache and memory management

Thesis (Ph.D.)--University of Rochester. Department of Computer Science, 2018.Advancements in computing have necessitated commensurate advancements in locality theory and replacement policies. Specifically, there is a need for replacement policies and shared cache management which facilitate minimum performance guarantees for each user, and policies that account for multiple costs associated with the presence or absence of data in a cache. Existing locality theory provides the framework to create such replacement policies with predictable behavior. This dissertation addresses the growing use of shared CPU caches, code-caching of justin-time (JIT) compiled code on burgeoning mobile devices, and the budding use of multiple main-memory technologies in a single system (heterogeneous memory). The thesis of this dissertation is that the increasing complexity and diversity of cache and memory management problems can be effectively addressed by extending locality theory to enable Pareto optimization. Pareto optimality indicates that in the presence of multiple objectives (e.g., space and time), no one objective can be improved without degrading another. When the only objective is time (with misses as a proxy), the optimal solution is also Pareto optimal. When both time and space are objectives, each Pareto optimal solution minimizes space, among all possible solutions, at each time point; and it minimizes time at each space point. The dissertation extends locality theory, and formulates Pareto optimal solutions for shared last-level caches, heterogeneous memories, and caching for JIT compilation, as well as practicable analogs that can be implemented without the need for oracular knowledge. In shared last-level caches, it presents new theory for predicting shared cache demand, a technique for minimizing group misses, and for balancing that objective with individual performance constraints. For mobile JIT compilation, it presents an optimal and a practicable compilation policy to maximize memory efficiency. Finally, in heterogeneous memories, it proposes adaptations of the optimal VMIN replacement policy and its practicable analog, the Working Set replacement policy (called H-VMIN and H-WS, respectively)