Paper Info
Title
PARADIS: an efficient parallel algorithm for in-place radix sort
Abstract
AbstractIn-place radix sort is a popular distribution-based sorting algorithm for short numeric or string keys due to its linear run-time and constant memory complexity. However, efficient parallelization of in-place radix sort is very challenging for two reasons. First, the initial phase of permuting elements into buckets suffers read-write dependency inherent in its in-place nature. Secondly, load balancing of the recursive application of the algorithm to the resulting buckets is difficult when the buckets are of very different sizes, which happens for skewed distributions of the input data. In this paper, we present a novel parallel in-place radix sort algorithm, PARADIS, which addresses both problems: a) "speculative permutation" solves the first problem by assigning multiple non-continuous array stripes to each processor. The resulting shared-nothing scheme achieves full parallelization. Since our speculative permutation is not complete, it is followed by a "repair" phase, which can again be done in parallel without any data sharing among the processors. b) "distribution-adaptive load balancing" solves the second problem. We dynamically allocate processors in the context of radix sort, so as to minimize the overall completion time. Our experimental results show that PARADIS offers excellent performance/scalability on a wide range of input data sets.
Year
DOI
Venue
2015
10.14778/2824032.2824050
Hosted Content
Field
DocType
Volume
Counting sort,Comparison sort,Computer science,Parallel computing,American flag sort,Radix sort,Selection sort,Bucket sort,Sorting algorithm,Proxmap sort
Journal
8
Issue
ISSN
Citations 
12
2150-8097
14
PageRank 
References 
Authors
1.08
25
6
Name
Order
Citations
PageRank
Minsik Cho155534.74
D. Brand229284.65
Rajesh Bordawekar371597.17
Ulrich Finkler4658.62
Vincent KulandaiSamy5141.41
Ruchir Puri651571.90