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 5 . 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 5 ) 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 5 with real-world input sets on modern machines.

Zusammenfassung

In dieser Bachelorarbeit wird ein mehrwegiger LCP-Merge eingeführt, parallelisiert und für den Aufbau eines parallelen LCP-Mergesorts, sowie einer NUMA optimierten pS 5 Implementierung, angewandt. Als Weiterentwicklung des binären LCP-Mergesortes, wird ein mehrwegiger LCP-fähiger Tournament Tree eingeführt und parallelisiert. Zur Aufteilung der Arbeitspakete, welche für eine dynamische Lastverteilung benötigt wird, werden eine bekannte, sowie zwei neu eingeführte Strategien, genutzt. Neben der Einführung eines parallelisierten LCP-Mergesortes, wird der weitere Fokus auf NUMA Architekturen gelegt. Im Zuge dessen, wird ‘parallel Super Scalar String Sample Sort’ (pS 5 ), durch Anwendung des parallelen LCP-Merges, auf die besonderen Eigenschaften dieser Systeme angepasst. Zusätzlich führt dies zu einem effizienten und generischen Ansatz um sequentielle Sortieralgorithmen zu parallelisieren und bereits parallele Algorithmen um NUMA-Fähigkeit zu erweitern. Weiterhin werden einige Optimierungen, welche für praktische Implementierungen wichtig sind, sowie ausgiebige Experimente auf zwei aktuellen NUMA Plattformen, erläutert und diskutiert. Die Experimente belegen mit realistischen Eingabedaten die gute Skalierbarkeit der vorgestellten Algorithmen und besonders die enormen Verbesserungen des pS5 Algorithmus auf NUMA Systemen.