Parallel Sorting With Limited Bandwidth
Title | Parallel Sorting With Limited Bandwidth |
Publication Type | Technical Report |
Year of Publication | 1995 |
Authors | Adler, M., Byers J. W., & Karp R. M. |
Other Numbers | 971 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-031.pdf |
Bibliographic Notes | ICSI Technical Report TR-95-031 |
Abbreviated Authors | M. Adler, J. W. Byers, and R. M. Karp |
ICSI Publication Type | Technical Report |