License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2021.3
URN: urn:nbn:de:0030-drops-137758
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13775/
Blacher, Mark ;
Giesen, Joachim ;
Kühne, Lars
Fast and Robust Vectorized In-Place Sorting of Primitive Types
Abstract
Modern CPUs provide single instruction-multiple data (SIMD) instructions. SIMD instructions process several elements of a primitive data type simultaneously in fixed-size vectors. Classical sorting algorithms are not directly expressible in SIMD instructions. Accelerating sorting algorithms with SIMD instruction is therefore a creative endeavor. A promising approach for sorting with SIMD instructions is to use sorting networks for small arrays and Quicksort for large arrays. In this paper we improve vectorization techniques for sorting networks and Quicksort. In particular, we show how to use the full capacity of vector registers in sorting networks and how to make vectorized Quicksort robust with respect to different key distributions. To demonstrate the performance of our techniques we implement an in-place hybrid sorting algorithm for the data type int with AVX2 intrinsics. Our implementation is at least 30% faster than state-of-the-art high-performance sorting alternatives.
BibTeX - Entry
@InProceedings{blacher_et_al:LIPIcs.SEA.2021.3,
author = {Blacher, Mark and Giesen, Joachim and K\"{u}hne, Lars},
title = {{Fast and Robust Vectorized In-Place Sorting of Primitive Types}},
booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)},
pages = {3:1--3:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-185-6},
ISSN = {1868-8969},
year = {2021},
volume = {190},
editor = {Coudert, David and Natale, Emanuele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13775},
URN = {urn:nbn:de:0030-drops-137758},
doi = {10.4230/LIPIcs.SEA.2021.3},
annote = {Keywords: Quicksort, Sorting Networks, Vectorization, SIMD, AVX2}
}
