Algorithms for Parallel Memory II: Hierarchical Multilevel Memories

J. S. Vitter and E. A. M. Shriver. ``Algorithms for Parallel Memory II: Hierarchical Multilevel Memories,'' double special issue on Large-Scale Memories in Algorithmica, 12(2-3), 1994, 148-169. A shortened version appears in ``Optimal Disk I/O with Parallel Block Transfer,'' Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC '90), Baltimore, MD, May 1990, 159-169.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

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$.