Engineering parallel string sorting

DOI10.1007/S00453-015-0071-1MaRDI QIDQ513306zbMATH OpenOpenAlexFDO

Authors Timo Bingmann, Andreas Eberle, Peter Sanders

Publication date 6 March 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.2056

zbMATH Keywords

merge sortLCP-insertion sortLCP-merge sortparallel string sortingsample sortstring sortingsuper scalar string sample sort

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 first propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Then we focus on NUMA architectures, and develop parallel multiway LCP-merge and -mergesort to reduce the number of random memory accesses to remote nodes. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations. Comprehensive experiments on five current multi-core platforms are then reported and discussed. The experiments show that our implementations scale very well on real-world inputs and modern machines.

Recommendations

• Parallel string sample sort
• Sorting strings and constructing digital search trees in parallel
• External String Sorting: Faster and Cache-Oblivious
• Parallel External Memory Suffix Sorting
• Optimal parallel string algorithms: sorting, merging and computing the minimum

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 6472611 (Why is no real title available?)
• A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
• Algorithms – ESA 2004
• Cache-conscious sorting of large sets of strings with dynamic tries
• Cache-efficient string sorting using copying
• Engineering burstsort, toward fast in-place string sorting
• Fast priority queues for cached memory
• Managing unbounded-length keys in comparison-driven data structures with applications to online indexing
• On demand string sorting over unbounded alphabets
• Optimal Parallel Sorting Scheme by Order Statistics
• Optimal parallel string algorithms: sorting, merging and computing the minimum
• Parallel Merge Sort
• Parallel string sample sort
• Power balance and apportionment algorithms for the United States Congress
• Quicksort
• Replacing suffix trees with enhanced suffix arrays
• Samplesort: A Sampling Approach to Minimal Storage Tree Sorting
• Scanning multiple sequences via cache memory
• The Parallel Evaluation of General Arithmetic Expressions

Cited in

(2)

• Parallel string sample sort
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.

Describes a project that uses

Uses Software

• GitHub
• Quicksort
• MCSTL

This page was built for publication: Engineering parallel string sorting

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