|
USENIX 2001 Abstract
Design and Implementation of a Predictive File Prefetching Algorithm
Thomas M. Kroeger, Nokia Cluster IP Solutions, and Darrell E. Long, University of California, Santa Cruz
Abstract
We have previously shown that the patterns in which files are
accessed offer information that can accurately predict upcoming file
accesses. Most modern caches ignore these patterns, thereby failing
to use information that enables significant reductions in I/O latency.
While prefetching heuristics that expect sequential accesses are often
effective methods to reduce I/O latency, they cannot be applied across
files, because the abstraction of a file has no intrinsic concept of a
successor. This limits the ability of modern file systems to
prefetch. Here we presents our implementation of a predictive
prefetching system, that makes use of file access patterns to reduce
I/O latency.
Previously we developed a technique called Partitioned Context
Modeling (PCM) that efficiently models file accesses to
reliably predict upcoming requests. We present our experiences in
implementing predictive prefetching based on file access patterns.
From the lessons learned we developed of a new technique Extended
Partitioned Context Modeling (EPCM), which has even better
performance.
We have modified the Linux kernel to prefetch file data based on Partitioned Context Modeling and Extended Partitioned Context
Modeling. With this implementation we examine how a prefetching
policy, that uses such models to predict upcoming accesses, can result
in large reductions in I/O latencies. We tested our implementation
with four different application-based benchmarks and saw I/O latency
reduced by 31% to 90% and elapsed time reduced by 11% to 16%.
- View the full text of this paper in
HTML,
PDF, and
PostScript.
The Proceedings are published as a collective work, © 2001 by the USENIX Association. All Rights Reserved. Rights
to individual papers remain with the author or the author's employer.
Permission is granted for the noncommercial reproduction of the complete
work for educational or research purposes. USENIX acknowledges all
trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
- To become a USENIX Member, please see our Membership Information.
|
Need help? Use our Contacts page.
