Marginal Cost-Benefit Analysis for Predictive File Prefetching

Authors:Highley, Timothy, Department of Computer ScienceUniversity of Virginia Reynolds, Paul, Department of Computer ScienceUniversity of Virginia

File prefetching can reduce file access latencies and improve overall performance. Prefetching can be especially important in on-line software on demand, where network latencies create unacceptable delays. Prefetching involves predicting future accesses and establishing when/whether to prefetch, based on future access predictions. Cost-benefit analysis (CBA) addresses when/whether to prefetch and it addresses the interaction between prefetching and caching. CBA weighs the expected benefits of file prefetching and the cost of expected buffer usage. We describe 1-Marginal CBA, an approach that employs probabilistic predictions, as opposed to deterministic hints. We present a probabilistically optimal, though intractable, algorithm, Opt, for a representative prediction model, and demonstrate that any other optimal algorithm under that model will also be intractable. We argue that in many circumstances 1-Marginal and Opt will make the same decisions. Finally, we present simulation results in which 1-Marginal reduced I/O time by an average of 19% and a maximum of 49% over other prefetching schemes in the literature, even when using the same predictor. Since the cost of 1-Marginal is comparable to that of other published algorithms the improvement is real.

All rights reserved (no additional license for public reuse)
Source Citation:

Highley, Timothy, and Paul Reynolds. "Marginal Cost-Benefit Analysis for Predictive File Prefetching." University of Virginia Dept. of Computer Science Tech Report (2003).

University of Virginia, Department of Computer Science
Published Date: