Accession Number : ADA253638
Title : Implementation of Parallel Algorithms
Descriptive Note : Quarterly rept 1 Jan-30 Jun 1992
Corporate Author : DUKE UNIV DURHAM NC
Personal Author(s) : Reif, John H.
PDF Url : ADA253638
Report Date : 30 JUN 1992
Pagination or Media Count : 10
Abstract : Randomization has been demonstrably useful both in simplifying and in improving the efficiency of sorting algorithms on actual parallel machines. Flashsort [RV83,86] and Samplesort [HC83] are related parallel sorting algorithms that have been proposed in the literature. Both utilize a sophisticated randomized sub-sampling technique with over-sampling to form a splitter set, but Samplesort differs from Flashsort in that it distributes all the splitters to each processor while Flashsort uses splitter-directed routing. In this paper we present B-Flashsort, a new batched-routing variant of Flashsort designed to sort N values using P processors with N > P. Like the randomized sorts to which it is related, B-Flashsort performs N/P log N parallel comparisons. The algorithm can be implemented on a wide variety of networks, but in this paper we concentrate on its implementation on a d-dimensional toroidal mesh. The algorithm requires only constant space in addition to the input and output.
Descriptors : *ALGORITHMS, *PARALLEL PROCESSORS, *SORTING, INPUT, OUTPUT, MESH, SAMPLING, PAPER, ADDITION, ROUTING, MACHINES, CONSTANTS, NETWORKS, COMPARISON, EFFICIENCY
Subject Categories : Computer Hardware
Distribution Statement : APPROVED FOR PUBLIC RELEASE