Loading...
Large-Scale Sorting in Uniform Memory Hierarchies
Vitter, Jeffrey Scott Nodine, Mark H.
Vitter, Jeffrey Scott
Nodine, Mark H.
Citations
Altmetric:
Abstract
We present several e cient algorithms for sorting on the uniform
memory hierarchy (UMH), introduced by Alpern, Carter, and Feig, and its paral-
lelization P-UMH.We give optimal and nearly-optimal algorithms for a wide range of
bandwidth degradations, including a parsimonious algorithm for constant bandwidth.
We also develop optimal sorting algorithms for all bandwidths for other versions of
UMH and P-UMH, including natural restrictions we introduce called RUMH and
P-RUMH, which more closely correspond to current programming languages.
Description
Date
1993
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Files
Loading...
ViN93.hierarchies.pdf
Adobe PDF, 180.39 KB
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
J. S. Vitter and M. H. Nodine. “Large-Scale Sorting in Uniform Memory Hierarchies,” special issue on parallel I/O systems in Journal of Parallel and Distributed Computing, 17, January 1993, 107–114. An extended abstract appears in “Large-Scale Sorting in Parallel Memories,” Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’91), Hilton Head, SC, July 1991, 29–39. http://dx.doi.org/10.1006/jpdc.1993.1008