MUSTACHE: Multi-Step-Ahead Predictions for Cache Eviction
This work addresses cache management inefficiencies for systems handling memory access, offering a novel learned approach with measurable performance gains.
The paper tackles the problem of page cache replacement by proposing MUSTACHE, a learned algorithm that predicts future memory accesses to improve eviction decisions, resulting in a 1.9% increase in cache hit ratio and reductions of 18.4% and 10.3% in reads and writes for cache misses.
In this work, we propose MUSTACHE, a new page cache replacement algorithm whose logic is learned from observed memory access requests rather than fixed like existing policies. We formulate the page request prediction problem as a categorical time series forecasting task. Then, our method queries the learned page request forecaster to obtain the next $k$ predicted page memory references to better approximate the optimal Bélády's replacement algorithm. We implement several forecasting techniques using advanced deep learning architectures and integrate the best-performing one into an existing open-source cache simulator. Experiments run on benchmark datasets show that MUSTACHE outperforms the best page replacement heuristic (i.e., exact LRU), improving the cache hit ratio by 1.9% and reducing the number of reads/writes required to handle cache misses by 18.4% and 10.3%.