Practical Massively Parallel Sorting
Open Access
- 13 June 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 13-23
Abstract
Previous parallel sorting algorithms do not scale to the largest available machines, since they either have prohibitive communication volume or prohibitive critical path length. We describe algorithms that are a viable compromise and overcome this gap both in theory and practice. The algorithms are multi-level generalizations of the known algorithms sample sort and multiway mergesort. In particular, our sample sort variant turns out to be very scalable both in theory and practice where it scales up to 215 MPI processes with outstanding performance in particular for medium sized inputs. Some tools we develop may be of independent interest -- a simple, practical, and flexible sorting algorithm for very small inputs, a near linear time ptimal algorithm for solving a constrained bin packing problem, and an algorithm for data delivery, that guarantees a small number of message startups on each processor.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Two-tree algorithms for full bandwidth broadcast, reduction and scanParallel Computing, 2009
- Fast priority queues for cached memoryACM Journal of Experimental Algorithmics, 2000
- Communication-Efficient Parallel SortingSIAM Journal on Computing, 1999
- CCL: a portable and tunable collective communication library for scalable parallel computersIEEE Transactions on Parallel and Distributed Systems, 1995
- Direct Bulk-Synchronous Parallel AlgorithmsJournal of Parallel and Distributed Computing, 1994
- Merging multiple lists on hierarchical-memory multiprocessorsJournal of Parallel and Distributed Computing, 1991
- A bridging model for parallel computationCommunications of the ACM, 1990
- Optimal merging and sorting on the EREW PRAMInformation Processing Letters, 1989
- Parallel Merge SortSIAM Journal on Computing, 1988
- Algorithm 64: QuicksortCommunications of the ACM, 1961