Tech Report CS-92-05

Algorithms for Parallel Memory II: Hierarchical Multilevel Memories

Jeffrey Scott Vitter and Elizabeth A.M. Shriver

August 1992

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

(complete text in pdf or gzipped postscript)