@Article{vitter:parmem2,
  author = {Jeffrey Scott Vitter and Elizabeth A. M. Shriver},
  title = {Algorithms for Parallel Memory {II}: Hierarchical Multilevel
  Memories},
  journal = {Algorithmica},
  year = {1994},
  month = {August and September},
  volume = {12},
  number = {2/3},
  pages = {148--169},
  earlier = {vitter:parmem2-tr},
  keywords = {parallel I/O algorithms, parallel memory, pario-bib},
  abstract = {In this paper we introduce parallel versions of two hierarchical
  memory models and give optimal algorithms in these models for sorting, FFT,
  and matrix multiplication. In our parallel models, there are $P$ memory
  hierarchies operating simultaneously; communication among the hierarchies
  takes place at a base memory level. Our optimal sorting algorithm is
  randomized and is based upon the probabilistic partitioning technique
  developed in the companion paper for optimal disk sorting in a two-level
  memory with parallel block transfer. The probability of using $\ell$ times
  the optimal running time is exponentially small in~$\ell (\log \ell) \log
  P$.},
  comment = {Summarized in vitter:optimal.}
}