A Study of Non-datapath Cache Replacement Algorithms

Conventionally, caching algorithms have been designed for the datapath — the levels of memory that must contain the data before it gets made available to the CPU. Attaching a fast device (such as an SSD) as a cache to a host that runs the application workload are recent developments. These host-side caches open up possibilities for what are referred to as non-datapath caches to exist. Non-Datapath caches are referred to as such because the caches do not exist on the traditional datapath, instead being optional memory locations for data. As these caches are optional, a new capability is available to caching algorithms that manage these caches: not caching at all and instead bypassing the cache entirely for an access. With this option, items may not get inserted into the cache, which is an outcome that is beneficial to the lifetime of cache devices that can only sustain a limited number of writes before they degrade and become unusable. We propose several non- datapath caching algorithms that are optimized to make these choices and achieve high hit-rates while reducing writes: mARC, FOMO, and ANX. We also propose a polynomial time optimal solution to non-datapath caches: mOPT. mOPT provides an optimal solution for non-datapath caches that can maximize hits while minimizing writes. This provides further insight into how appropriate non-datapath caches are for specific workloads, if at all.