@InProceedings{kallahalla:prefetch,
  author = {Mahesh Kallahalla and Peter J. Varman},
  title = {Optimal Prefetching and Caching for Parallel {I/O} Systems},
  booktitle = {Proceedings of the Thirteenth Symposium on Parallel Algorithms
  and Architectures},
  year = {2001},
  month = {July},
  pages = {219--228},
  publisher = {ACM Press},
  note = {To appear},
  URL = {http://www.ece.rice.edu/~pjv/spaa.ps},
  keywords = {parallel I/O, prefetch, disk cache, pario-bib},
  abstract = {We address the problem of prefetching and caching in a parallel
  I/O system and present a new algorithm for optimal parallel-disk scheduling.
  Traditional buffer management algorithms that minimize the number of I/O disk
  accesses, are substantially suboptimal in a parallel I/O system where
  multiple I/Os can proceed simultaneously. \par We present a new algorithm
  Super for parallel-disk I/O scheduling. We show that in the off-line case,
  where a priori knowledge of all the requests is available, Super performs the
  minimum number of I/Os to service the given I/O requests. This is the first
  parallel I/O scheduling algorithm that is provably offline optimal. In the
  on-line case, we study Super in the context of global L-block lookahead,
  which gives the buffer management algorithm a lookahead consisting of L
  distinct requests. We show that the competitive ratio of Super, with global
  L-block lookahead, is Theta(M-L+D), when L < M, and Theta(MD/L), when L >= M,
  where the number of disks is D and buffer size is M.}
}