AN IMPLEMENTATION OF A GENERAL-PURPOSE PARALLEL SORTING ALGORITHM

ANDREW TRIDGELL AND RICHARD P. BRENT

Abstract

A parallel sorting algorithm is presented for general purpose internal sorting on MIMD machines. The algorithm initially sorts the elements within each node using a serial sorting algorithm, then proceeds with a two-phase parallel merge. The algorithm is comparison-based and requires additional storage of order the square root of the number of elements in each node. Performance of the algorithm on the Fujitsu AP1000, Thinking Machines CM5, and nCUBE2 is discussed. The performance is good: efficiencies of 0.8 to 0.9 are typical when sorting a large number of elements.

Comments

Only the Abstract is given here. The full report appeared as [4] and a shorter version appeared as [2]. For related work, see [1, 3, 5, 6].

References

1. G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. J. Smith and M. Zagha, “A comparison of sorting algorithms for the Connection Machine CM-2”, Proc. Symposium on Parallel Algorithms and Architectures, Hilton Head, South Carolina, July 1991.

2. R. P. Brent and A. Tridgell, “A fast, storage-efficient parallel sorting algorithm”, Proc. International Conference on Application-Specific Array Processors held at Venice, Italy, Oct. 1993 (edited by L. Dadda and B. Wah), IEEE Computer Society Press, Los Alamitos, California, 1993, 369–379. ISBN 0-8186-3492-8. rpb140.

3. K. Thearling and S. Smith, “An Improved Supercomputing Sorting Benchmark”, Proc Supercomputing 92, IEEE Press, 1992, 14–19.

4. A. Tridgell and R. P. Brent, An Implementation of a General-Purpose Parallel Sorting Algorithm, Technical Report TR-CS-93-01, Computer Sciences Laboratory, ANU, February 1993, 24 pp. rpb140tr.

5. B. B. Zhou, R. P. Brent and A. Tridgell Efficient Implementation of Sorting Algorithms on Asynchronous Distributed-Memory Machines, Technical Report TR-CS-93-06, Computer Sciences Laboratory, ANU, May 1993, 7 pp. rpb142.

6. A. Tridgell and R. P. Brent, “A general-purpose parallel sorting algorithm”, International J. of High Speed Computing 7 (1995), 285-301. rpb158.

Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200 E-mail: {tridge,rpb}@cslab.anu.edu.au

1980 Mathematics Subject Classification (1985 Revision). Primary Primary 68P10; Secondary 68Q22. Key words and phrases. Batcher’s merge-exchange sort, distributed memory, Fujitsu AP1000,

nCUBE2, parallel sorting, sorting, Thinking Machines CM5.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1993, the authors. rpb140a typeset using AMS-L^{A}TEX.