DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2017.9

In-Place Parallel Super Scalar Samplesort (IPSSSSo)

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

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

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 shw that our algorithm IPSSSSo 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.

Cite as

Michael Axtmann, Sascha Witt, Daniel Ferizovic, and Peter Sanders. In-Place Parallel Super Scalar Samplesort (IPSSSSo). In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{axtmann_et_al:LIPIcs.ESA.2017.9,
  author =	{Axtmann, Michael and Witt, Sascha and Ferizovic, Daniel and Sanders, Peter},
  title =	{{In-Place Parallel Super Scalar Samplesort (IPSSSSo)}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.9},
  URN =		{urn:nbn:de:0030-drops-78542},
  doi =		{10.4230/LIPIcs.ESA.2017.9},
  annote =	{Keywords: shared memory, parallel sorting, in-place algorithm, comparison-based sorting, branch prediction}
}

Search Results

Documents authored by Axtmann, Michael

In-Place Parallel Super Scalar Samplesort (IPSSSSo)

Abstract

Cite as

Thanks for your feedback!

Could not send message