A Classification of Prefetching Algorithms

Sequential prefetching is the most promising and widely deployed prefetching technique for data servers. It has a high predictive accuracy and is extremely simple to implement. Simple methods are used to isolate the sequential components of workloads [17], upon which prefetching is applied. We can classify the known sequential prefetching techniques as follows:

• Fixed Synchronous (FS) prefetching: The simplest form of sequential prefetching is where we prefetch the next page on a miss (OBL [18]). Another variant is where a fixed number of pages ($p$) are prefetched on every miss.

• Adaptive Synchronous (AS) prefetching: This is a popular form of sequential prefetching where the number of pages prefetched on every miss ($p$) is gradually increased as the length of the sequence referenced becomes longer. The degree of prefetch, $p$ starts with $1$ and is either linearly incremented on every miss [20] (Linear-AS) or exponentially incremented (Exp-AS). Usually, there is a predefined upper limit for incrementing $p$. Although Exp-AS adapts faster than the Linear-AS method, it is prone to more wastage in workloads with many short sequences or when cache space is limited.

• Fixed Asynchronous (FA) prefetching: In this class, a hit on a trigger page causes a prefetch. Tagged prefetching [18], a variant of OBL, is the earliest example of asynchronous prefetching where the degree of prefetch was $1$ and the trigger distance was 0. Subsequently, the idea has been extended to any pair of fixed values of $p$ and $g$ [17]. Unlike synchronous prefetching methods, this class of algorithms can achieve zero misses for a workload when the chosen values of $p$ and $g$ are adequate. However, since the algorithm is hand-tuned and not adaptive, it does not work well for all workloads.

• Adaptive Asynchronous (AA) prefetching: To the best of our knowledge, there is no published work that dynamically adapts both the degree of prefetch ($p$) and the trigger distance ($g$). This is the most promising class of prefetching algorithms. The only algorithm that comes close is the one proposed by Dalhgren [19] where the degree of prefetch is the same for all streams and every page is a trigger page. It is not truly applicable in the context of data servers because it is wasteful. As each page is a trigger page it inefficiently prefetches one page at a time for sequential streams. It also requires some amount of prefetch wastage to adapt $p$ which is blindly applied for all sequential streams.