@Article{vitter:parmem1,
  author = {Jeffrey Scott Vitter and Elizabeth A. M. Shriver},
  title = {Algorithms for Parallel Memory {I}: Two-level Memories},
  journal = {Algorithmica},
  year = {1994},
  month = {August and September},
  volume = {12},
  number = {2/3},
  pages = {110--147},
  earlier = {vitter:parmem1-tr},
  keywords = {parallel I/O algorithms, parallel memory, pario-bib},
  abstract = {We provide the first optimal algorithms in terms of the number of
  input/outputs (I/Os) required between internal memory and multiple secondary
  storage devices for the problems of sorting, FFT, matrix transposition,
  standard matrix multiplication, and related problems. Our two-level memory
  model is new and gives a realistic treatment of {\em parallel block
  transfer}, in which during a single~I/O each of the $P$ secondary storage
  devices can simultaneously transfer a contiguous block of $B$ records. The
  model pertains to a large-scale uniprocessor system or parallel
  multiprocessor system with $P$ disks. In addition, the sorting, FFT,
  permutation network, and standard matrix multiplication algorithms are
  typically optimal in terms of the amount of internal processing time. The
  difficulty in developing optimal algorithms is to cope with the partitioning
  of memory into $P$~separate physical devices. Our algorithms' performance can
  be significantly better than those obtained by the well-known but nonoptimal
  technique of disk striping. Our optimal sorting algorithm is randomized, but
  practical; the probability of using more than $\ell$ times the optimal number
  of I/Os is exponentially small in $\ell (\log \ell) \log (M/B)$, where $M$ is
  the internal memory size.},
  comment = {See shorter version vitter:optimal. See TR version
  vitter:parmem1-tr. See also vitter:parmem2.}
}