Efficient implementation of sorting algorithms
on asynchronous distributed-memory machines
142.
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 CS Press, 1994, 102-106.
Also Report TR-CS-93-06,
CSL, ANU, May 1993, 7 pp.
Abstract:
dvi (2K),
pdf (77K),
ps (26K).
Paper:
dvi (17K),
pdf (297K),
ps (58K).
Report:
dvi (16K),
pdf (301K),
ps (61K).
Abstract
The problem of merging two sequences of elements
which are stored separately in two processing
elements 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
For related work, see [140].
Go to next publication
Return to Richard Brent's index page