Loading...
Please wait, while we are loading the content...
Similar Documents
Parallel Sorting with Limited Bandwidth (1999)
| Content Provider | CiteSeerX |
|---|---|
| Author | Adler, Micah Byers, John W. Karp, Richard M. |
| Description | in Proc. 7th ACM Symp. on Parallel Algorithms and Architectures We study the problem of sorting on a parallel computer with limited communication bandwidth. By using the PRAM(m) model, where p processors communicate through a globally shared memory which can service m requests per unit time, we focus on the trade-off between the amount of local computation and the amount of inter-processor communication required for parallel sorting algorithms. Our main result is a lower bound of Ω((n log m)/(m log n)) on the time required to sort n numbers on the exclusive-read and queued-read variants of the PRAM(m). We also 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 t... |
| File Format | |
| Language | English |
| Publisher Date | 1999-01-01 |
| Access Restriction | Open |
| Subject Keyword | Little Dependence Problem Size Surprising Form Unit Time Local Computation Matching Upper Bound Parallel Computer Limited Bandwidth Main Result Fractional Power Queued-read Variant Optimal Running Shared Memory Limited Communication Bandwidth Inter-processor Communication |
| Content Type | Text |
| Resource Type | Article |
