A Simple and Efficient Parallel Disk Mergesort |
| |
Authors: | R D Barve J S Vitter |
| |
Affiliation: | (1) Winphoria Networks, c/o B23 Swagat Mahakali Caves Road, Andheri, Mumbai 400 093, India rbarve@winphoria.com, IN;(2) Center for Geometric and Biological Computing, Department of Computer Science, Duke University, Durham, NC 27708-0129, USA jsv@cs.duke.edu, US |
| |
Abstract: | External sorting—the process of sorting a file that is too large to fit into the computer's internal memory and must be stored
externally on disks—is a fundamental subroutine in database systemsG], IBM]. Of prime importance are techniques that use
multiple disks in parallel in order to speed up the performance of external sorting. The simple randomized merging (SRM ) mergesort algorithm proposed by Barve et al. BGV] is the first parallel disk sorting algorithm that requires a provably
optimal number of passes and that is fast in practice. Knuth K,Section 5.4.9] recently identified SRM (which he calls ``randomized
striping') as the method of choice for sorting with parallel disks.
In this paper we present an efficient implementation of SRM, based upon novel and elegant data structures. We give a new
implementation for SRM's lookahead forecasting technique for parallel prefetching and its forecast and flush technique for buffer management. Our techniques amount to a significant improvement in the way SRM carries out the parallel, independent disk accesses necessary to read blocks of input runs efficiently during external merging. Our implementation is based on
synchronous parallel I/O primitives provided by the TPIE programming environmentTPI]; whenever our program issues an I/O read (write)
operation, one block of data is synchronously read from (written to) each disk in parallel.
We compare the performance of SRM over a wide range of input sizes with that of disk-striped mergesort (DSM ), which is widely used in practice. DSM consists of a standard mergesort in conjunction with striped I/O for parallel disk
access. SRM merges together significantly more runs at a time compared with DSM, and thus it requires fewer merge passes.
We demonstrate in practical scenarios that even though the streaming speeds for merging with DSM are a little higher than
those for SRM (since DSM merges fewer runs at a time), sorting using SRM is often significantly faster than with DSM (since
SRM requires fewer passes).
The techniques in this paper can be generalized to meet the load-balancing requirements of other applications using parallel
disks, including distribution sort and multiway partitioning of a file into several other files. Since both parallel disk
merging and multimedia processing deal with streams that get ``consumed' at nonuniform and partially predictable rates, our
techniques for lookahead based upon forecasting data may have relevance in video server applications.
Received June 28, 2000, and in revised form June 5, 2001. Online publication April 8, 2002. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|