Show simple item record

dc.contributor.authorKrishnan, P.
dc.contributor.authorVitter, Jeffrey Scott
dc.identifier.citationKrishnan, P., and Jeffrey Scott Vitter. "Optimal Prediction for Prefetching in the Worst Case." SIAM J. Comput. SIAM Journal on Computing 27.6 (1998): 1617-636. DOI:10.1137/S0097539794261817en_US
dc.descriptionThis is the published version. Copyright © 1998 Society for Industrial and Applied Mathematicsen_US
dc.description.abstractResponse 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 efficient way. Unlike other online problems, prefetching cannot admit a competitive analysis, since the optimal offline prefetcher incurs no cost when it knows the future page requests. Previous analytical work on prefetching [. Vitter Krishnan 1991.] [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 finite 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 finite state prefetcher for the sequence. This analysis model can 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 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 Matias, Vitter, and Ni [Proc. 4th Annual SIAM/ACM Symposium on Discrete Algorithms, Austin, TX, January 1993].
dc.publisherSociety for Industrial and Applied Mathematicsen_US
dc.subjectMachine learningen_US
dc.subjectCompetitive analysisen_US
dc.subjectFinite state prefetchersen_US
dc.subjectResponse timeen_US
dc.subjectFault rateen_US
dc.subjectOperating systemsen_US
dc.titleOptimal Prediction for Prefetching in the Worst Caseen_US
kusw.kuauthorVitter, Jeffrey Scott
kusw.kudepartmentElectrical Engr & Comp Scienceen_US
kusw.oaversionScholarly/refereed, publisher version
kusw.oapolicyThis item does not meet KU Open Access policy criteria.

Files in this item


This item appears in the following Collection(s)

Show simple item record