A RANDOMIZED PARALLEL SORTING ALGORITHM WITH AN EXPERIMENTAL-STUDY

Previous schemes for sorting on general-purpose parallel machines have had to choose between poor load balancing and irregular communication or multiple rounds of all-to-all personalized communication. In this paper, we introduce a novel variation on sample sort which uses only t wo rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. More over, unlike previous variations, our algorithm efficiently handles th e presence of duplicate values without the overhead of tagging each el ement with a unique identifier. This algorithm was implemented in SPLI T-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2, and the Gray Research T3D. We ran our code using widely different benchmarks to examine the dependence of our algorithm on the input distribution. Our experimental results illustrate the ef ficiency and scalability of our algorithm across different platforms. In fact, it seems to outperform all similar algorithms known to the au thors on these platforms, and its performance is invariant over the se t of input distributions unlike previous efficient algorithms. Our res ults also compare favorably with those reported for the simpler rankin g problem posed by the NAS Integer Sorting (IS) Benchmark. (C) 1998 Ac ademic Press, Inc.