Tech Report CS-90-22

Algorithms for Parallel Memory II: Hierarchical Multilevel Memories

Jeffrey Scott Vitter and Elizabeth A. M. Shriver

September 1990

Abstract:

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