DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2021.3

Fast and Robust Vectorized In-Place Sorting of Primitive Types

Authors: Mark Blacher, Joachim Giesen, and Lars Kühne

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

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.

Cite as

Mark Blacher, Joachim Giesen, and Lars Kühne. Fast and Robust Vectorized In-Place Sorting of Primitive Types. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SEA.2021.3},
  URN =		{urn:nbn:de:0030-drops-137758},
  doi =		{10.4230/LIPIcs.SEA.2021.3},
  annote =	{Keywords: Quicksort, Sorting Networks, Vectorization, SIMD, AVX2}
}

Search Results

Documents authored by Kühne, Lars

Fast and Robust Vectorized In-Place Sorting of Primitive Types

Abstract

Cite as

Thanks for your feedback!

Could not send message