Markov Prediction for Adaptive Network Memory Prefetching

Modern operating systems use main memory as a cache over disk-based storage. The time spent waiting for data transfers from disk to memory can dominate the running time of data intensive applications. Prefetching hides this latency by initiating fetches early, before the data is needed. Before prefetching can occur, however, the system must be able to predict future requests accurately and efficiently. Because incorrect predictions cause longer delays than no predictions at all, a general theory for when and how to predict and prefetch is needed. Prediction by partial matching, or PPM, is a method of determining the next element in a sequence based on some number of previous elements. A PPM algorithm of order n uses the previous n \Gamma 1 elements to describe the current state of the sequence and evaluate the most likely next element. We use a Markov-based implementation of PPM to learn and predict the access patterns of real applications. The predictor quickly learns and adapts to ch..