-CS-TR-3670, UMIACS-TR-96-54.
-To appear in Journal of Experimental Algorithmics.
We introduce a new deterministic parallel sorting algorithm
based on the regular sampling approach. The algorithm uses
only two rounds of regular all-to-all personalized communication in a
scheme that yields very good load balancing with virtually no overhead.
Moreover, unlike previous variations, our algorithm efficiently handles
the presence of duplicate values without the overhead of tagging each
element with a unique identifier. This algorithm was implemented in
Split-C and run on a variety of platforms,
including the Thinking Machines CM-5, the IBM SP-2-WN, and the Cray 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 efficiency and
scalability of our
algorithm across different platforms.
In fact, the performance compares closely to that of our random sample sort
algorithm, which seems to outperform
all similar algorithms known to the authors on these platforms.
Together, their performance is nearly invariant over the set of input
distributions, unlike previous efficient algorithms.
However, unlike our randomized sorting algorithm, the performance and memory
requirements of our regular sorting algorithm can be deterministically
guaranteed.
HTML
or
PostScript
or
Compressed PostScript
Version of this report.
Click here to download this sorting code (.tar.Z)
For more infomation on any of the these topics, click on the hotlink.
Any queries, comments, or inquiries to:
David R. Helman
E-mail: helman@umiacs.umd.edu
Office phone: (301)405-6757
FAX: (301)314-9658
Return to the Experimental Parallel Algorithmics page.