KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel String Sample Sort

Bingmann, Timo; Sanders, Peter ORCID iD icon

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.


Postprint §
DOI: 10.5445/IR/1000039066
Veröffentlicht am 12.08.2019
Originalveröffentlichung
DOI: 10.1007/978-3-642-40450-4_15
Dimensions
Zitationen: 19
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 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 Verlag
Seiten 169-180
Serie Lecture Notes in Computer Science ; 8125
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page