Parallel string sample sort

DOI10.1007/978-3-642-40450-4_15MaRDI QIDQ2849308zbMATH OpenOpenAlexFDO

Authors Timo Bingmann, Peter Sanders

Publication date 17 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1157, https://publikationen.bibliothek.kit.edu/1000039066

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10) Algorithms on strings (68W32)

Abstract: 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 effective 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.

Recommendations

• Engineering parallel string sorting
• Sorting strings and constructing digital search trees in parallel
• Parallel String Matching
• Parallel sorting by regular sampling
• On the versatility of parallel sorting by regular sampling

Cited in

(6)

• Sorting strings and constructing digital search trees in parallel
• Parallel sorting for GPUs
• In-place parallel super scalar samplesort (\(\mathrm{IPS}^4\mathrm{o}\))
• Engineering parallel string sorting
• Algorithms – ESA 2004
• Scalable distributed string sorting

This page was built for publication: Parallel string sample sort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849308)