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 MIMD supercomputer is discussed.

Comments

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

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] K. Thearling and S. Smith, “An Improved Supercomputing Sorting Benchmark”, Proc Supercomputing 92, IEEE Press, 1992, 14–19.

[3] 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.

[4] 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.

[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 address: {tridge,rpb}@cslab.anu.edu.au

1991 Mathematics Subject Classification. Primary 68P10; Secondary 68Q22. Key words and phrases. Batcher’s merge-exchange sort, distributed memory, Fujitsu AP1000, nCUBE2, par-

allel sorting, sorting, Thinking Machines CM5.

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