A Randomized Parallel Sorting Algorithm with an Experimental Study

David R. Helman, David A. Bader, Joseph Jájá

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

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 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, 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, 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.

Original languageEnglish (US)
Pages (from-to)1-23
Number of pages23
JournalJournal of Parallel and Distributed Computing
Volume52
Issue number1
DOIs
StatePublished - Jul 10 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Keywords

  • Generalized sorting
  • Integer sorting, sample sort, parallel performance
  • Parallel algorithms

Fingerprint

Dive into the research topics of 'A Randomized Parallel Sorting Algorithm with an Experimental Study'. Together they form a unique fingerprint.

Cite this