OPTIMAL PREDICTION FOR PREFETCHING IN THE WORST-CASE

Response time delays caused by I/O are a major problem in many systems and database applications. Prefetching and cache replacement methods are attracting renewed attention because of their success in avoiding costly I/Os. Prefetching can be looked upon as a type of online sequen tial prediction, where the predictions must be accurate as well as mad e in a computationally efficient way. Unlike other online problems, pr efetching cannot admit a competitive analysis, since the optimal offli ne prefetcher incurs no cost when it knows the future page requests. P revious analytical work on prefetching [J. Assoc. Comput. Mach., 143 ( 1996), pp. 771-793] consisted of modeling the user as a probabilistic Markov source. In this paper, we look at the much stronger form of wor st-case analysis and derive a randomized algorithm for pure prefetchin g. We compare our algorithm for every page request sequence with the i mportant class of finite state prefetchers, making no assumptions as t o how the sequence of page requests is generated. We prove analyticall y that the fault rate of our online prefetching algorithm converges al most surely for every page request sequence to the fault rate of the o ptimal finite state prefetcher for the sequence. This analysis model c an be looked upon as a generalization of the competitive framework, in that it compares an online algorithm in a worst-case manner over all sequences with a powerful yet nonclairvoyant opponent. We simultaneous ly achieve the computational goal of implementing our prefetcher in op timal constant expected time per prefetched page using the optimal dyn amic discrete random variate generator of Matias, Vitter, and Ni [Proc . 4th Annual SIAM/ACM Symposium on Discrete Algorithms, Austin, TX, Ja nuary 1993].