Title :
A fast, storage-efficient parallel sorting algorithm
Author :
Brent, Richard P. ; Tridgell, Andrew
Author_Institution :
Comput. Sci. Lab., Australian Nat. Univ., Canberra, ACT, Australia
Abstract :
A parallel sorting algorithm is presented for storage-efficient internal sorting on MIMD machines. The algorithm first sorts the elements within each node using a serial based algorithm, then a two-phase parallel merge. It requires additional storage of order of the square root of the number of elements in each node. Performance of the algorithm on two general-purpose MIMD machines, the Fujitsu AP1000 and the Thinking Machines CM5, is examined. The algorithm is suitable for implementation on special-purpose parallel machines, e.g., parallel database machines
Keywords :
parallel algorithms; parallel machines; sorting; special purpose computers; Fujitsu AP1000; MIMD machines; Thinking Machines CM5; parallel database machines; serial based algorithm; special-purpose parallel machines; storage-efficient parallel sorting algorithm; two-phase parallel merge; Australia; Concurrent computing; Database machines; Laboratories; Memory management; Parallel machines; Random number generation; Sorting; Speech recognition;
Conference_Titel :
Application-Specific Array Processors, 1993. Proceedings., International Conference on
Conference_Location :
Venice
Print_ISBN :
0-8186-3492-8
DOI :
10.1109/ASAP.1993.397158
