Bachelor Thesis: Parallel Multiway LCP-Mergesort

Structure of LCP Tournament Tree

In this bachelor thesis, multiway LCP-Merge is introduced, parallelized and applied to create a fully parallel LCP-Mergesort, as well as NUMA optimized pS⁵. As an advancement of binary LCP-Mergesort, a multiway LCP-aware tournament tree is introduced and parallelized. For dynamic load balancing, one well-known and two new strategies for splitting merge work packages are utilised. Besides the introduction of fully parallel multiway LCP-Mergesort, further focus is put on NUMA architectures. Thus ‘parallel Super Scalar String Sample Sort’ (pS⁵) is adapted to the special properties of these systems by utilising the parallel LCP-Merge. Moreover this yields an efficient and generic approach for parallelizing arbitrary sequential string sorting algorithms and making parallel algorithms NUMA-aware. Several optimizations, important for practical implementations, as well as comprehensive experiments on two current NUMA platforms, are then reported and discussed. The experiments show the good scalability of the introduced algorithms and especially, the great improvements of NUMA-aware pS⁵ with real-world input sets on modern machines.

The complete bachelor thesis is available for download from here. A git repository containing the test set, including implementations of the introduced algorithms as well as several other parallel and sequential algorithms, is available from https://github.com/bingmann/parallel-string-sorting.git. Our implementations in the source code are published under the GNU General Public License v3 (GPL), which can be found in the file COPYING. Files and implementations by other authors may have different licenses, as stated in the individual source files.