Abstract
We present a new algorithm for deterministic sorting on the Bulk-Synchronous Parallel (BSP) model of computation. We sort n keys using a partitioning scheme that achieves the requirements of efficiency (one-optimality) and insensitivity against initial key distribution. Although we employ sampling to realize efficiency, we give a precise worst-case estimation of the maximum imbalance which might occur. The algorithm is one-optimal for a wide range of the BSP parameters in the sense that its speedup on p processors is asymptotically (1 - o(1)) p.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 69-79 |
| Number of pages | 11 |
| Journal | Parallel processing letters |
| Volume | 9 |
| Issue number | 1 |
| State | Published - 1999 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Hardware and Architecture