Prefetching Without Hints: A Cost-Benefit Analysis for Predicted Accesses

Prefetching disk blocks to main memory will become increasingly important to overcome the widening gap between disk access times and processor speeds. We present a prefetching scheme that chooses which blocks to prefetch based on their probability of access and decides whether to prefetch a particular block at a given time using a cost-benefit analysis. To calculate the probability of access of prefetch candidates, we construct a prefetch tree that records past access patterns. For the cost-benefit analysis, we derive equations for the benefit of prefetching an additional block and the cost of allocating a buffer to the prefetch. We use a trace-driven simulator to evaluate the performance of our prefetching scheme. For an efficient implementation of the prediction algorithm, we limit the size of the prefetch tree. We show that our prefetching scheme lowers overall cache miss rates by up to 32% compared to a system that performs no prefetching. Coupled with the one block lookahead prefetching, this scheme improves overall cache miss rates by up to 52% over a scheme that performs no prefetching and by up to 27% over an aggressive one block lookahead prefetching scheme for small cache sizes. However, the frequency and effectiveness of prefetching decrease as cache size grows