Adaptive insertion policies for high performance caching

TLDR

LRU replacement causes thrashing and inefficient cache use for memory‑intensive workloads whose working set exceeds cache size. The study aims to improve cache performance for such workloads by retaining a fraction of the working set through modified insertion policies. The authors introduce three insertion policies—LRU Insertion Policy, Bimodal Insertion Policy, and Dynamic Insertion Policy—that place new lines at the LRU position, adaptively switch between BIP and LRU, and require no cache‑structure changes, using less than two bytes of storage. LIP effectively prevents thrashing and yields near‑optimal hit rates for cyclic workloads, while DIP cuts average MPKI by 21%, closing two‑thirds of the gap between LRU and optimal replacement.

Abstract

The commonly used LRU replacement policy is susceptible to thrashing for memory-intensive workloads that have a working set greater than the available cache size. For such applications, the majority of lines traverse from the MRU position to the LRU position without receiving any cache hits, resulting in inefficient use of cache space. Cache performance can be improved if some fraction of the working set is retained in the cache so that at least that fraction of the working set can contribute to cache hits.We show that simple changes to the insertion policy can significantly reduce cache misses for memory-intensive workloads. We propose the LRU Insertion Policy (LIP) which places the incoming line in the LRU position instead of the MRU position. LIP protects the cache from thrashing and results in close to optimal hitrate for applications that have a cyclic reference pattern. We also propose the Bimodal Insertion Policy (BIP) as an enhancement of LIP that adapts to changes in the working set while maintaining the thrashing protection of LIP. We finally propose a Dynamic Insertion Policy (DIP) to choose between BIP and the traditional LRU policy depending on which policy incurs fewer misses. The proposed insertion policies do not require any change to the existing cache structure, are trivial to implement, and have a storage requirement of less than two bytes. We show that DIP reduces the average MPKI of the baseline 1MB 16-way L2 cache by 21%, bridging two-thirds of the gap between LRU and OPT.