MIT Department of Electrical Engineering & Computer Science

E E C S

On the Integration of Prefetching and Caching

Anna R. Karlin
University of Washington

Thursday, February 29, 1996
4:00 PM (3:45 refreshments)
Room NE43-518
EECS Special Seminar

Abstract

Prefetching and caching are effective techniques for improving the performance of I/O systems, but they have not been studied in an integrated fashion. The main complication is that prefetching blocks into a cache can be harmful even if the blocks will be accessed in the near future. This is because prefetching requires performing a replacement earlier than it would have been performed otherwise, which can ultimately result in extraneous fetches.

We describe properties that optimal integrated prefetching and caching strategies must satisfy and present a simple prefetching algorithm that is provably close to optimal. We have evaluated our approach via trace-driven simulation on a collection of file system traces. Our results show that the integrated strategy achieves performance that is indeed close to optimal and that it can reduce the running times of applications by up to 50%.

We will also discuss the parallel version of this problem, where the data being accessed resides on multiple disks. Here the interaction between caching and prefetching is further complicated by the fact that replacement choices affect the load imbalance between the disks. We describe an algorithm with near-optimal performance for this problem and the results of a simulation study of its performance under a variety of data placement alternatives.

This is joint work with Tracy Kimbrel, Pei Cao, Ed Felten and Kai Li.

HOST: Prof. Barbara Liskov

URL of this page: http://www-eecs.mit.edu/AY95-96/events/21.html
Created: Feb 23, 1996 | Modified: Jun 25, 1997
This announcement is from the MIT EECS 1995-96 archive. | Current events
To MIT EECS home page | Your comments and inquiries are welcome.