|
USENIX 2nd Symposium on
OS Design and Implementation (OSDI '96)
A Trace-Driven Comparison of Algorithms for Parallel Prefetching
and Caching
Tracy Kimbrel,
Andrew Tomkins,
R. Hugo Patterson,
Brian Bershad,
Pei Cao,
Edward Felten,
Garth Gibson,
Anna R. Karlin and
Kai Li
Abstract
High-performance I/O systems depend on prefetching and caching in
order to deliver good performance to applications. These two
techniques have generally been considered in isolation, even though
there are significant interactions between them; a block prefetched
too early reduces the effectiveness of the cache, while a block cached
too long reduces the effectiveness of prefetching. In this paper we
study the effects of several combined prefetching and caching
strategies for systems with multiple disks. Using disk-accurate
trace-driven simulation, we explore the performance characteristics of
each of the algorithms in cases in which applications provide full
advance knowledge of accesses using hints. Some of the strategies
have been published with theoretical performance bounds, and some are
components of systems that have been built. One is a new algorithm
that combines the desirable characteristics of the others. We find
that when performance is limited by I/O stalls, aggressive prefetching
helps to alleviate the problem; that more conservative prefetching is
appropriate when significant I/O stalls are not present; and that a
single, simple strategy is capable of doing both.
|
Need help? Use our Contacts page.
Conference Index