Efficient out-of-core sorting algorithms for the Parallel Disks Model |
| |
Authors: | Vamsi Kundeti Sanguthevar Rajasekaran[Author vitae] |
| |
Affiliation: | aDepartment of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA |
| |
Abstract: | 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 . We verify experimentally our dirty sequence idea with the standard R-Way merge and show that our idea can reduce the number of parallel I/Os to sort on the PDM significantly. |
| |
Keywords: | Algorithms External memory Sorting Massive data sets Parallel disk model Disk sorting Randomized algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|