Load balanced parallel radix sort

Andrew Sohn, Yuetsu Kodama

Research output: Contribution to conferencePaperpeer-review

28 Scopus citations

Abstract

Radix sort suffers from the unequal number of input keys due to the unknown characteristics of input keys. We present in this report a new radix sorting algorithm, called balanced radix sort which guarantees that each processor has exactly the same number of keys regardless of the data characteristics. The main idea of balanced radix sort is to store any processor which has over n/P keys to its neighbor processor, where n is the total number of keys and P is the number of processors. We have implemented balanced radix sort on two distributed-memory machines IBM SP2-WN and Cray T3E. Multiple versions of 32-bit and 64-bit integers and 64-bit doubles are implemented in Message Passing Interface for portability. The sequential and parallel versions consist of approximately 50 and 150 lines of C code respectively including parallel constructs. Experimental results indicate that balanced radix sort can sort 0.5G integers in 20 seconds and 128M doubles in 15 seconds on a 64-processor SP2-WN while yielding over 40-fold speedup. When compared with other radix sorting algorithms, balanced radix sort outperformed, showing two to six times faster. When compared with sample sorting algorithms, which are known to outperform all similar methods, balanced radix sort is 30% to 100% faster based on the same machine and key initialization.

Original languageEnglish (US)
Pages305-312
Number of pages8
DOIs
StatePublished - 1998
EventProceedings of the 1998 International Conference on Supercomputing - Melbourne, Aust
Duration: Jul 13 1998Jul 17 1998

Other

OtherProceedings of the 1998 International Conference on Supercomputing
CityMelbourne, Aust
Period7/13/987/17/98

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Load balanced parallel radix sort'. Together they form a unique fingerprint.

Cite this