Optimal parallel sorting in multi-level storage
Alok Aggarwal, C. Greg Plaxton · 1994
We adapt the Sharesort algorithm of Cypher and Plaxton to run on various parallel models of multi-level storage, and analyze its resulting performance. Sharesort was originally defined in the context of sorting n records on an n-processor hypercubic network. In that context, it is not known whether Sharesort is asymptotically optimal. Nonetheless, we find that Sharesort achieves optimal time bounds for parallel sorting in multi-level storage, under a variety of models that have been defined in the literature.
Cited by 42 works. doi:10.5555/314464.314669
Authors
References
- Sorting networks and their applications
- The input/output complexity of sorting and related problems
- Tight Bounds on the Complexity of Parallel Sorting
- Permuting Information in Idealized Two-Level Storage
- Ultracomputers: a teraflop before its time
- Parallel permutation and sorting algorithms and a new generalized connection network
- A Self-Routing Benes Network and Parallel Permutation Algorithms
- A model for hierarchical memory
- Hierarchical memory with block transfer
- Deterministic distribution sort in shared and distributed memory multiprocessors