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 areP 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/times the optimal running time is exponentially small in ι(log ι) logP.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Aggarwal, B. Alpern, A. K. Chandra, and M. Snir, A Model for Hierarchical Memory,Proceedings of the 19th Annual ACM Symposium on Theory of Computing, May 1987, pp. 305–314.
A. Aggarwal, A. Chandra, and M. Snir, Hierarchical Memory with Block Transfer,Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, October 1987, pp. 204–216.
A. Aggarwal and J. S. Vitter, The Input/Output Complexity of Sorting and Related Problems,Communications of the ACM 31(9) (September 1988), 1116–1127.
B. Alpem, L. Carter, E. Feig, and T. Selker, The Uniform Memory Hierarchy Model of Computation,Algorithmica, this issue, pp. 72–109.
F. Luccio and L. Pagli, A Model of Sequential Computation Based on a Pipelined Access to Memory,Proceedings of the 27th Annual Allerton Conference on Communication, Control, and Computing, September 1989.
M. H. Nodine and J. S. Vitter, Large-Scale Sorting in Parallel Memories,Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1991, pp. 29–39.
M. H. Nodine and J. S. Vitter, Large-Scale Sorting in Uniform Memory Hierarchies,Journal of Parallel and Distributed Computing (January 1993), special issue.
M. H. Nodine and J. S. Vitter, Deterministic Distribution Sort in Shared and Distributed Memory Multiprocessors,Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, July 1993, pp. 120–129.
J. H. Reif and L. G. Valiant, A Logarithmic Time Sort on Linear Size Networks,Journal of the ACM 34 (January 1987), 60–76.
J. Savage and J. S. Vitter, Parallelism in Space-Time Tradeoffs, inAdvances in Computing Research, Vol. 4, F. P. Preparata, ed., JAI Press, Greenwich, CT 1987, pp. 117–146.
J. S. Vitter and E. A. M. Shriver, Algorithms for Parallel Memory, I: Two-Level Memories,Algorithmica, this issue, pp. 110–147.
Author information
Authors and Affiliations
Additional information
Communicated by C. K. Wong.
Rights and permissions
About this article
Cite this article
Vitter, J.S., Shriver, E.A.M. Algorithms for parallel memory, II: Hierarchical multilevel memories. Algorithmica 12, 148–169 (1994). https://doi.org/10.1007/BF01185208
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01185208