@InProceedings{nodine:loadbalance,
  author = {Mark H. Nodine and Jeffrey Vitter},
  title = {Load Balancing Paradigms for Optimal Use of Parallel Disks and
  Parallel Memory Hierarchies},
  booktitle = {Proceedings of the 1993 DAGS/PC Symposium},
  year = {1993},
  month = {June},
  pages = {26--39},
  organization = {Dartmouth Institute for Advanced Graduate Studies},
  address = {Hanover, NH},
  keywords = {parallel I/O algorithm, memory hierarchy, load balance, sorting,
  pario-bib},
  abstract = {We present several load balancing paradigms pertinent to
  optimizing I/O performance with disk and processor parallelism. We use
  sorting as our canonical application to illustrate the paradigms, and we
  survey a wide variety of applications in computational geometry. The use of
  parallel disks can help overcome the I/O bottleneck in sorting if the records
  in each read or write are evenly balanced among the disks. There are three
  known load balancing paradigms that lead to optimal I/O algorithms: using
  randomness to assign blocks to disks, using the disks predominantly
  independently, and deterministically balancing the blocks by matching. In
  this report, we describe all of these techniques in detail and compare their
  relative advantages. We show how randomized and deterministic balancing can
  be extended to provide sorting algorithms that are optimal both in terms of
  the number of I/Os and the internal processing time for parallel-processing
  machines with scalable I/O subsystems and with parallel memory hierarchies.
  We also survey results achieving optimal performance in the these models for
  a large range of online and batch problems in computational geometry.},
  comment = {Invited speaker: Jeffrey Vitter.}
}