Theoretically-efficient and practical parallel in-place radix sorting

Radix sort stands out for having a better worse case theoretical bound than any comparison-based sort, for fixed length integers. Despite the fact that radix sort can be implemented either in-place or in parallel, there exists no parallel in-place implementation for radix sort that guarantees a sub-linear worst case span. The challenge arises due to read-write races when reading from and writing to the same array. In this thesis, I introduce Regions sort and use it to implement a parallel work-efficient in-place radix sorting algorithm. To sort n integers from a range r, and a parameter K, the algorithm requires only O(K log r log n) auxiliary memory, O(n log r) work and O((N/k + log K) log r) span. Regions sort uses a divide-and-conquer paradigm. It first divides the array into sub-arrays, each of which is sorted independently in parallel. This decreases the irregularity in the input and reorders it into a set of regions, each of which has similar properties. Next, it builds a data structure, called the regions graph to represent the needed data movements to completely sort the array. Finally, Regions sort iteratively plans swaps that satisfies the required data movements. The algorithm then has to recurse on records with so-far equal keys to break ties. I compare two variants of Regions sort with the state-of-the-art sorting integer sort and comparison sort algorithms. Experiments show that the best variant of Regions sort usually outperforms other sorting algorithms. In addition, I perform different experiments showing that Regions sort maintains its superiority regardless input distribution and range. More importantly, the single-threaded implementation of Regions sort outperforms the highly optimized Ska Sort implementation for serial in-place radix sort.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Obeya, Omar.

Advisor dc:contributor.advisor

• Julian Shun.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/123040

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/123040