Tech Report CS-90-22

Algorithms for Parallel Memory II: Hierarchical Multilevel Memories

Jeffrey Scott Vitter and Elizabeth A. M. Shriver

September 1990


In this paper we introduce parallel versions of 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 a 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$.

Order hardcopy report from