Parameterized round-robin partitioned algorithm for parallel external sort

Abstract

In this paper, we present a new parameterized parallel sort algorithm, called Round-Robin Partitioned (or RRP), for the message passing (shared-nothing) architecture. This is a parameterized sort algorithm because a parameter is provided which can be used to determine the amount of memory used and to allocate differing amounts of work to different sets of sites. We utilize pipelining to hide disk I/O time, exploit high degrees of parallelism at all phases, apply sampling to determine the partition key values and use less memory than previous known methods while requiring the minimum number of physical I/Os. The basic version of the RRP algorithm is simple in terms of coding and complexity. It does not require disk I/O parallelism or data prefetch within a single process. We develop an analytical model for our algorithm and compare our sort algorithm with four other classes of external parallel sort algorithms. The RRP algorithm are shown to be superior to the other algorithms for almost all configurations.