@Article{kallahalla:pc-opt,
  author = {M. Kallahalla and P.~J. Varman},
  title = {{PC-OPT}: Optimal Offline Prefetching and Caching for Parallel {I/O}
  Systems},
  journal = {IEEE Transactions on Computers},
  year = {2002},
  month = {November},
  volume = {51},
  number = {11},
  pages = {1333--1344},
  publisher = {IEEE Computer Society Press},
  URL = {http://www.computer.org/tc/tc2002/tytoc.htm},
  keywords = {parallel I/O, file prefetching, pario-bib},
  abstract = {We address the problem of prefetching and caching in a parallel
  I/O system and present a new algorithm for parallel disk scheduling.
  Traditional buffer management algorithms that minimize the number of block
  misses are substantially suboptimal in a parallel I/O system where multiple
  I/Os can proceed simultaneously. We show that in the offline case, where a
  priori knowledge of all the requests is available, PC-OPT 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
  parallel disk model. In the online case, we study 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
  PC-OPT, with global L-block lookahead, is \Theta (M - L + D), when L < M, and
  \Theta (M D / L), when L > M, where the number of disks is D and buffer size
  is M.}
}