Parallel Sorting With Limited Bandwidth

TitleParallel Sorting With Limited Bandwidth
Publication TypeTechnical Report
Year of Publication1995
AuthorsAdler, M., Byers J. W., & Karp R. M.
Other Numbers971

We study the problem of sorting on a parallel computer with limited communication bandwidth. By using the recently proposed PRAM(m) model, where p processors communicate through a small, globally shared memory consisting of m bits, we focus on the trade-off between the amount of local computation and the amount of inter-processor communication required for parallel sorting algorithms. We prove a lower bound of ?({n log m}/{m}) on the time to sort n numbers in an exclusive-read variant of the PRAM(m) model. We show that Leighton's Columnsort can be used to give an asymptotically matching upper bound in the case where m grows as a fractional power of n. The bounds are of a surprising form, in that they have little dependence on the parameter p. This implies that attempting to distribute the workload across more processors while holding the problem size and the size of the shared memory fixed will not improve the optimal running time of sorting in this model. We also show that both the upper and the lower bound can be adapted to bridging models that address the issue of limited communication bandwidth: the LogP model and the BSP model. The lower bounds provide convincing evidence that efficient parallel algorithms for sorting rely strongly on high communication bandwidth.

Bibliographic Notes

ICSI Technical Report TR-95-031

Abbreviated Authors

M. Adler, J. W. Byers, and R. M. Karp

ICSI Publication Type

Technical Report