Absolute Cost-Benefit Analysis for Predictive File Prefetching

Report
Authors:Highley, Timothy, Department of Computer ScienceUniversity of Virginia Reynolds, Paul, Department of Computer ScienceUniversity of Virginia Vellanki, Vivekanand, Department of Computer ScienceUniversity of Virginia
Abstract:

Cost-benefit analysis attempts to balance the benefits of file prefetching against the costs of giving up a buffer from the cache. This is a comprehensive approach to prefetching. It simultaneously answers the questions of what and when/whether to prefetch, and also addresses the interaction between prefetching and caching. Original research on cost-benefit analysis relied on hints about prefetching that were supplied by the program, though other research has considered the more general case of programs without hints. In this paper, we revisit previous research on cost-benefit analysis without hints, present new estimators for the costs and benefits of prefetching under a system model without hints, and generalize the system model to consider probability trees that may have the same block lie along multiple paths of the tree. We present a distinction between absolute and marginal cost-benefit analysis, two different approaches to file prefetching that previous researchers have used. The difference between the two is a subtlety that has not been previously noted or investigated. Our new estimators are based on absolute cost-benefit analysis, with modifications to address observed weaknesses in the absolute approach.

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

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

Publisher:
University of Virginia, Department of Computer Science
Published Date:
2002