Large-Scale Sorting in Uniform Memory Hierarchies
View/ Open
Issue Date
1993Author
Vitter, Jeffrey Scott
Nodine, Mark H.
Publisher
Elsevier
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Metadata
Show full item recordAbstract
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.
Collections
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
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.