KIT | KIT-Bibliothek | Impressum
Open Access Logo
DOI: 10.5445/IR/1000042457

Parallel Multiway LCP-Mergesort

Eberle, Andreas

In this bachelor thesis, multiway LCP-Merge is introduced, parallelized and applied to create a fully parallel LCP-Mergesort, as well as NUMA optimized pS5. 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 utilized. Besides the introduction of fully parallel multiway LCP-Mergesort, further focus is put on NUMA architectures. Thus 'parallel Super Scalar String Sample Sort' (pS5) 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 pS5 with real-world input sets on modern machines.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2014
Sprache Englisch
Identifikator URN: urn:nbn:de:swb:90-424572
KITopen ID: 1000042457
Abschlussart Abschlussarbeit - Bachelor
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page