ICS Theory Group

ICS 269, Fall 1996: Theory Seminar

1 Nov 1996:
Near-Optimal Parallel Prefetching and Caching
Dan Halem, ICS, UC Irvine

Recently there has been a great deal of interest in the operating systems research community in prefetching and caching data from parallel disks, as a technique for enabling serial appliications to improve I/O performance. We consider algorithms for integrated prefetching and caching in a model with a fixed-size cache and any number of backing storage devices(which we will call disks). The integration of caching and prefetching with a single disk was previously considered by Cao et al. We show that the natural extension of their aggressive algorithm to the parallel disk case is suboptimal by a factor of (nearly) the number of disks in the worst case. Our main result is a new algorithm, reverse agressive, with near optimal performance for integrated prefetching and caching in the presence of multiple disks.

(From a FOCS '96 paper by Tracy Kimbrel and Anna R. Karlin)