Balanced parallel sort on hypercube multiprocessors

Publisher Website
Google Scholar
Abstract
Cataloged from PDF version of article.A parallel sorting algorithm for sorting n elements\ud evenly distributed over Zd = p nodes of a d-dimensional hypercube\ud is presented. The average running time of the algorithm\ud is O( (n log n)/p + p log2 n). The algorithm maintains a perfect\ud load balance in the nodes by determining the (kn/p)th elements\ud (k = 1,. . . , (p - 1)) of the final sorted list in advance. These\ud p - 1 keys are used to partition the sorted sublists in each node\ud to redistribute data to the nodes to be merged in parallel. The\ud nodes finish the sort with an equal number of elements (n/p)\ud regardless of the data distribution. A parallel selection algorithm\ud for determining the balanced partition keys in O(p log2 n) time\ud is presented. The speed of the sorting algorithm is further enhanced\ud by the distanced communication capability of the iPSC/2\ud hypercube computer and a novel conflict-free routing algorithm.\ud Experimental results on a 16-node hypercube computer show\ud that the new sorting algorithm is competitive with the previous\ud algorithms, and faster for skewed data distributions

This publication has 12 references indexed in Scilit: