A trace-driven comparison of algorithms for parallel prefetching and caching

Tracy Kimbrel, Andrew Tomkins, R. Hugo Patterson, Brian Bershad, Pei Cao, Edward W. Feiten, Garth A. Gibson, Anna R. Karlin, Kai Li

Research output: Contribution to conferencePaperpeer-review

76 Scopus citations


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.

Original languageEnglish (US)
StatePublished - 1996
Externally publishedYes
Event2nd USENIX Symposium on Operating Systems Design and Implementation, OSDI 1996 - Seattle, United States
Duration: Oct 28 1996Oct 31 1996


Conference2nd USENIX Symposium on Operating Systems Design and Implementation, OSDI 1996
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Information Systems
  • Computer Networks and Communications

Cite this