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)|
|Number of pages||11|
|Journal||Parallel processing letters|
|State||Published - Jan 1 1999|
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Hardware and Architecture