Engineering parallel string sorting

DOI10.1007/S00453-015-0071-1zbMATH Open1359.68056arXiv1403.2056OpenAlexW1574212840MaRDI QIDQ513306FDOQ513306

Authors: Timo Bingmann, Andreas Eberle, Peter Sanders 

Publication date: 6 March 2017

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (2)

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

Uses Software

• MCSTL
• Quicksort
• GitHub

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)