Communication-efficient parallel sorting (preliminary version)
Michael T. Goodrich · 1996
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(*) and a number of communication rounds that is 0( ~$$~1) ) for h = @(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 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 fl(log n/ log(h + 1)) communication rounds.