Dynamical adjustment of block replacement algorithms

Abstract

Block replacement algorithms are an important component of any cache controller, specially for disk caches. In recent years, complex and sophisticated algorithms have been developed, that reduce the miss-rate of disk caches. All of these algorithms require some sort of tuning in order to achieve their full performance. Up until now, the “optimal” parameters have been determined by running simulations with access traces. Parameters found have then been implemented in the hope that the actual access patterns would not deviate too much from the ones used in the simulations. When they did, miss-rates would increase, often exceeding miss-rates of more conventional replacement strategies like the least recently used block replacement algorithm (LRU). In this paper, we present a method of adjusting an algorithm's tuning parameter at run-time, by constantly monitoring its performance. We will show that dynamic tuning is able to approach the results of an optimal value that was determined by using simulations. Additionally, we will demonstrate the ability of this new technique to adapt to completely different workloads.