A deeper dent can be made in I/O latency by speculatively prefetching or prestaging pages even before they are requested [9].
To prefetch, a prediction of likely future data accesses based on past accesses is needed. The accuracy of prediction plays an important role in reducing cache pollution and in increasing the utility of prefetching. The accuracy is generally dependent upon the amount of history that can be maintained and mined on-line, and on the stationarity of the access patterns.
A number of papers have focused on predictive approaches to prefetching, for example, [10] used relationship graph models, [11] used a prediction scheme based on classical information-theoretic Lempel-Ziv algorithm, [12] used a scheme based on associative memory, and [13] used a scheme based on partitioned context modeling. Commercial systems have rarely used very sophisticated prediction schemes. There are several reasons for this gap between research and practice. To be effective, sophisticated prediction schemes need extensive history of page accesses which is cumbersome and expensive to maintain for real-life systems. For example, a high-end storage controller may serve many tens of thousands of I/Os per second. Recording and mining such data online and in real-time is a non-trivial challenge. Furthermore, to be effective a prefetch must complete before the predicted request. This requires sufficient prior notice. However, long-term predictive accuracy is generally very low to begin with and becomes worse with interleaving of a large number of different workloads. A further degradation in predictive accuracy happens if the workloads do not exhibit stationarity which is the founding axiom behind many predictive approaches. Finally, for a disk subsystem operating near its peak capacity, average response time increases drastically with the increasing number of disk fetches. Thus, low accuracy predictive prefetching, which results in an increased number of disk fetches, can in fact worsen the performance.
In a well-known paper, [14] proposed an approach to significantly increase the predictive accuracy of prefetching by letting applications disclose their knowledge of future accesses to enable informed caching and prefetching. Building on [14], [15] utilized idle processor cycles while an application is stalled on I/O to speculatively pre-execute application's code to garner information about its future read accesses.