Show simple item record

A Parallel Sorting Algorithm With an Experimental Study

dc.contributor.authorHelman, David R.en_US
dc.contributor.authorBader, David A.en_US
dc.contributor.authorJaJa, Josephen_US
dc.date.accessioned2004-05-31T22:35:23Z
dc.date.available2004-05-31T22:35:23Z
dc.date.created1995-12en_US
dc.date.issued1998-10-15en_US
dc.identifier.urihttp://hdl.handle.net/1903/768
dc.description.abstractPrevious 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 two rounds of regular all-to-all personalized communication in a scheme that yields very good load balancing with virtually no overhead. This algorithm was implemented in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, the IBM SP-2, 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 are consistent with the theoretical analysis and illustrate the efficiency and scalability of our algorithm across different platforms. In fact, it seems to outperform all similar algorithms known to the authors on these platforms, and its performance is invariant over the set of input distributions unlike previous efficient algorithms. Our results also compare favorably with those reported for the simpler ranking problem posed by the NAS Integer Sorting (IS) Benchmark. (Also cross-referenced as UMIACS-TR-95-102)en_US
dc.format.extent3241805 bytes
dc.format.mimetypeapplication/postscript
dc.language.isoen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3549en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-95-102en_US
dc.titleA Parallel Sorting Algorithm With an Experimental Studyen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record