EFFICIENT IMPLEMENTATION OF SORTING ALGORITHMS ON ASYNCHRONOUS DISTRIBUTED-MEMORY MACHINES

B. B. ZHOU, R. P. BRENT, AND A. TRIDGELL

Abstract

The problem of merging two sequences of elements which are stored separately in two processing elements (PEs) occurs in the implementation of many existing sorting algorithms. We describe efficient algorithms for the merging problem on asynchronous distributed-memory machines. The algorithms reduce the cost of the merge operation and of communication, as well as partly solving the problem of load balancing. Experimental results on a Fujitsu AP1000 are reported.

Comments

Only the Abstract is given here. The full report appeared as [2]. For related work, see [1].

References

[1] 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. rpb140.

[2] B. B. Zhou, R. P. Brent and A. Tridgell “Efficient Implementation of Sorting Algorithms on Asynchronous Distributed-Memory Machines”, Proc. 1994 International Conference on Parallel and Distributed Systems (Hsinchu, Taiwan, December 1994), IEEE Computer Society Press, Los Alamitos, California, 1994, 102-106. Also Technical Report TR-CS-93-06, Computer Sciences Laboratory, ANU, March 1993 (revised May 1993), 7 pp. rpb142, rpb142tr.

Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200

E-mail address: {bing,rpb,tridge}@cslab.anu.edu.au

1991 Mathematics Subject Classification. Primary 68P10; Secondary 68Q22. Key words and phrases. Parallel sorting, sorting, merging, communication cost, parallel algorithms, distributed

memory.

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