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)
| Page Owner: John Bazik | Last Modified: Fri Feb 9 17:44:33 2007 |