Efficient out-of-core sorting algorithms for the Parallel Disks Model

In this paper,1 we present efficient algorithms for sorting on the Parallel Disks Model (PDM). Numerous asymptotically optimal algorithms have been proposed in the literature. However, many of these merge based algorithms have large underlying constants in the time bounds, because they suffer from the lack of read parallelism on the PDM. The irregular consumption of the runs during the merge affects the read parallelism and contributes to the increased sorting time. In this paper, we first introduce a novel idea called the dirty sequence accumulation   that improves the read parallelism. Next, we show analytically that this idea can reduce the number of parallel I/O’s required to sort the input close to the lower bound of Ω(logMB(NM)). We verify experimentally our dirty sequence   idea with the standard RR-Way merge and show that our idea can reduce the number of parallel I/Os to sort on the PDM significantly.

► Improved I/O parallelism during RR-Way merging with a novel concept of a ‘dirty sequence’.
► About 1.94X reduction in the parallel I/O’s when compared to a standard RR-Way merge.
► The simplicity of our idea makes it easy to realize an efficient practical implementation on the PDM.