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$.
Order hardcopy report from techreports@cs.brown.edu