Tech Report CS-92-05

Algorithms for Parallel Memory II: Hierarchical Multilevel Memories

Jeffrey Scott Vitter and Elizabeth A.M. Shriver

August 1992


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 l times the optimal running time is exponentially small in $l$ $(\log l) \log P$.

(complete text in pdf or gzipped postscript)