Loading...
Optimal Prediction for Prefetching in the Worst Case
Krishnan, P. Vitter, Jeffrey Scott
Krishnan, P.
Vitter, Jeffrey Scott
An error occurred retrieving the object's statistics
Citations
Altmetric:
Abstract
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 sequential prediction, where the predictions must be accurate as well as made in a computationally
e cient way. Unlike other online problems, prefetching cannot admit a competitive analysis, since the
optimal o ine prefetcher incurs no cost when it knows the future page requests. Previous 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 worst-case analysis and derive a randomized
algorithm for pure prefetching. We compare our algorithm for every page request sequence with the
important class of nite state prefetchers, making no assumptions as to how the sequence of page
requests is generated. We prove analytically that the fault rate of our online prefetching algorithm
converges almost surely for every page request sequence to the fault rate of the optimal nite state
prefetcher for the sequence. This analysis model can be looked upon as a generalization of the com-
petitive framework, in that it compares an online algorithm in a worst-case manner over all sequences
with a powerful yet nonclairvoyant opponent. We simultaneously achieve the computational goal of
implementing our prefetcher in optimal constant expected time per prefetched page using the optimal
dynamic discrete random variate generator of Matias, Vitter, and Ni [Proc. 4th Annual SIAM/ACM
Symposium on Discrete Algorithms, Austin, TX, January 1993].
Description
AMS subject classi cations. 68Q25, 68T05, 68P20, 68N25, 60J20
PII. S0097539794261817
Date
1998-12
Journal Title
Journal ISSN
Volume Title
Publisher
Society for Industrial and Applied Mathematics
Collections
Research Projects
Organizational Units
Journal Issue
Keywords
Caching, Prefetching, Competitive analysis, Nite state prefetchers, Response time, Fault rate, Hypertext, Operating systems, Databases, Prediction, Machine learning
Citation
P. Krishnan and J. S. Vitter. “Optimal Prediction for Prefetching in theWorst Case,” SIAM Journal on Computing, 27(6), December 1998, 1617–1636. An extended abstract appears in Proceedings of the 5th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA ’94), Alexandria, VA, January 1994, 392–401. http://dx.doi.org/10.1137/S0097539794261817