Communication-Efficient Parallel Sorting
Author:
- Michael T. GoodrichMGMichael T. Goodrich
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 29 (2) , 416-432
Abstract
We study the problem of sorting n numbers on a p-processor bulk-synchronous parallel (BSP) computer, which is a parallel multicomputer that allows for general processor-to-processor communication rounds provided each processor sends and receives at most h items in any round. We provide parallel sorting methods that use internal computation time that is $O({n\log n \over p})$ and a number of communication rounds that is $O({\log n \over \log (h+1)})$ for $h=\Theta(n/p)$. The internal computation bound is optimal for any comparison-based sorting algorithm. Moreover, the number of communication rounds is bounded by a constant for the (practical) situations when $p\le n^{1-{1/c}}$ for a constant $c\ge 1$. In fact, we show that our bound on the number of communication rounds is asymptotically optimal for the full range of values for p, for we show that just computing the "or"of n bits distributed evenly to the first O(n/h) of an arbitrary number of processors in a BSP computer requires $\Omega(\log n/\log (h+1))$ communication rounds.
Keywords
This publication has 21 references indexed in Scilit:
- Direct Bulk-Synchronous Parallel AlgorithmsJournal of Parallel and Distributed Computing, 1994
- Cubesort: A parallel algorithm for sorting N data items with S-sortersJournal of Algorithms, 1992
- A parallel partition for enhanced parallel QuickSortParallel Computing, 1992
- Communication complexity of PRAMsTheoretical Computer Science, 1990
- Parallel Merge SortSIAM Journal on Computing, 1988
- Fractional cascading: I. A data structuring techniqueAlgorithmica, 1986
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous WritesSIAM Journal on Computing, 1986
- A taxonomy of parallel sortingACM Computing Surveys, 1984
- Sorting inc logn parallel stepsCombinatorica, 1983
- Samplesort: A Sampling Approach to Minimal Storage Tree SortingJournal of the ACM, 1970