Asynchronous parallel disk sorting
Authors:
Open Access
- 7 June 2003
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 138-148
Abstract
We develop an algorithm for parallel disk sorting, whose I/O cost approaches the lower bound and that guarantees almost perfect overlap between I/O and computation. Previous algorithms have either suboptimal I/O volume or cannot guarantee that I/O and computations can always be overlapped. We give an efficient implementation that can (at least) compete with the best practical implementations but gives additional performance guarantees. For the experiments we have configured a state of the art machine that can sustain full bandwidth I/O with eight disks and is very cost effective.Keywords
This publication has 16 references indexed in Scilit:
- Columnsort lives! an efficient out-of-core sorting program2001
- Fast priority queues for cached memoryACM Journal of Experimental Algorithmics, 2000
- javax.XXL2000
- Near-Optimal Parallel Prefetching and CachingSIAM Journal on Computing, 2000
- Minimizing stall time in single and parallel disk systems1998
- Simple randomized mergesort on parallel disksParallel Computing, 1997
- Implementation and performance of integrated application-controlled file caching, prefetching, and disk schedulingACM Transactions on Computer Systems, 1996
- Greed sortJournal of the ACM, 1995
- Algorithms for parallel memory, I: Two-level memoriesAlgorithmica, 1994
- AlphaSort1994