In-place parallel super scalar samplesort (IPS^4o)

DOI10.4230/LIPICS.ESA.2017.9MaRDI QIDQ5111694zbMATH OpenOpenAlexFDO

Authors Michael Axtmann, Sascha Witt, Daniel Ferizovic, Peter Sanders

Publication date 27 May 2020

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

zbMATH Keywords

shared memoryin-place algorithmparallel sortingcomparison-based sortingbranch prediction

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Abstract: We present a sorting algorithm that works in-place, executes in parallel, is cache-efficient, avoids branch-mispredictions, and performs work O(n log n) for arbitrary inputs with high probability. The main algorithmic contributions are new ways to make distribution-based algorithms in-place: On the practical side, by using coarse-grained block-based permutations, and on the theoretical side, we show how to eliminate the recursion stack. Extensive experiments show that our algorithm IPS${}^4$o scales well on a variety of multi-core machines. We outperform our closest in-place competitor by a factor of up to 3. Even as a sequential algorithm, we are up to 1.5 times faster than the closest sequential competitor, BlockQuicksort.

Recommendations

• Algorithms – ESA 2004
• Parallel sorting by regular sampling
• Parallel string sample sort
• An efficient parallel sorting algorithm
• Robust massively parallel sorting

Cites work

• scientific article; zbMATH DE number 1984685 (Why is no real title available?)
• A simple algorithm for in-place merging
• Algorithms – ESA 2004
• An in-place sorting with O ( n log n ) comparisons and O ( n ) moves
• BlockQuicksort: avoiding branch mispredictions in Quicksort
• Engineering a cache-oblivious sorting algorithm
• How Branch Mispredictions Affect Quicksort
• In-place parallel super scalar samplesort (\(\mathrm{IPS}^4\mathrm{o}\))
• Multi-pivot quicksort: theory and experiments
• Multiway In-Place Merging
• On a model of virtual address translation
• Parallel string sample sort
• Proximity MergeSort, optimal in-place sorting in the cache-oblivious model
• Samplesort: A Sampling Approach to Minimal Storage Tree Sorting

Cited in

(5)

• BlockQuicksort: avoiding branch mispredictions in Quicksort
• Robust massively parallel sorting
• In-place parallel super scalar samplesort (\(\mathrm{IPS}^4\mathrm{o}\))
• Algorithms – ESA 2004
• Computational Science - ICCS 2004

Describes a project that uses

Uses Software

• MCSTL
• CMU Benchmarks
• Intel TBB
• Quicksort
• GitHub

This page was built for publication: In-place parallel super scalar samplesort (\(\mathrm{IPS}^4\mathrm{o}\))

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