About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IPPS 1995
Conference paper
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.