This is the source code for my master's thesis on Scalable Distributed String Sorting Algorithms at the Karlsruhe Institute of Technology — Institute of Theoretical Informatics, Algorithm Engineering.
String sorting algorithms have been studied extensively for sequential and shared-memory parallel models of computation. There has however been comparatively little and only very recent work covering string sorting in distributed-memory parallel systems. In this thesis, we directly build on the existing work to develop distributed algorithms that are more scalable with respect to two parameters: the number of processors used for sorting and the input size per processor in terms of characters. For the first aspect, we develop a multi-level generalization of existing multi-way string merge sort algorithms, based on a technique that has been applied successfully in atomic sorting. The developed algorithm is experimentally demonstrated to perform well for a range of inputs across a spectrum of magnitudes. We observe speedups up to five over the closest existing competitor on up to 24,576 processors.
For the second aspect, aimed at making distributed string sorting more scalable with respect to input size, we develop a space-efficient sorting framework which primarily distinguishes itself through the use of a compressed input representation. By deduplicating overlapping substrings and sorting the input in smaller chunks rather than as a whole, it is possible to create sorted permutations for inputs that would otherwise exceed the available working memory. We experimentally confirm this claim by demonstrating that an implementation of the framework is able to sort inputs of uncompressed size up to 22.4GB per processor with only 2GB memory available on average. Furthermore, an application of space-efficient sorting in suffix array construction, specifically as subroutine to DCX, is proposed. We show that our implementation is capable of sorting large difference cover samples, including for a difference cover modulo 8192, for texts comprising up to 1.23TB in size.