Special Joint Seminar with the Multicomputer Seminar
Date: February 23, 1996
Speaker: Anna R. Karlin, University of Washington
On the Integration of Prefetching and Caching
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.
SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/