KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel String Sample Sort

Bingmann, Timo; Sanders, Peter

Abstract (englisch):
We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we propose string sample sort. The algorithm makes eective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations.

Open Access Logo


Postprint §
DOI: 10.5445/IR/1000039066
Veröffentlicht am 12.08.2019
Originalveröffentlichung
DOI: 10.1007/978-3-642-40450-4_15
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2013
Sprache Englisch
Identifikator ISBN: 978-3-642-40449-8
ISSN: 0302-9743
KITopen-ID: 1000039066
Erschienen in Algorithms - 21st Annual European Symposium (ESA'13), Sophia Antipolis, France, September 2-4, 2013 - Proceedings. Ed.: H.L. Bodlaender
Verlag Springer, Berlin
Seiten 169-180
Serie Lecture Notes in Computer Science ; 8125
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page