elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

Fast and Robust Vectorized In-Place Sorting of Primitive Types

Blacher, Mark und Giesen, Joachim und Kühne, Lars (2021) Fast and Robust Vectorized In-Place Sorting of Primitive Types. In: 19th International Symposium on Experimental Algorithms, SEA 2021, 190, 3:1-3:16. Schloss Dagstuhl — Leibniz-Zentrum für Informatik. 19th International Symposium on Experimental Algorithms (SEA 2021), 06.-07. Jun. 2021, Online. doi: 10.4230/LIPIcs.SEA.2021.3. ISBN 978-395977185-6. ISSN 1868-8969.

[img] PDF
1MB

Offizielle URL: https://drops.dagstuhl.de/opus/volltexte/2021/13775

Kurzfassung

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.

elib-URL des Eintrags:https://elib.dlr.de/142624/
Dokumentart:Konferenzbeitrag (Vortrag)
Titel:Fast and Robust Vectorized In-Place Sorting of Primitive Types
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Blacher, Markmark.blacher (at) uni-jena.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Giesen, Joachimjoachim.giesen (at) uni-jena.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Kühne, LarsLars.Kuehne (at) dlr.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:Juni 2021
Erschienen in:19th International Symposium on Experimental Algorithms, SEA 2021
Referierte Publikation:Ja
Open Access:Ja
Gold Open Access:Nein
In SCOPUS:Ja
In ISI Web of Science:Nein
Band:190
DOI:10.4230/LIPIcs.SEA.2021.3
Seitenbereich:3:1-3:16
Verlag:Schloss Dagstuhl — Leibniz-Zentrum für Informatik
Name der Reihe:Leibniz International Proceedings in Informatics (LIPIcs)
ISSN:1868-8969
ISBN:978-395977185-6
Status:veröffentlicht
Stichwörter:Quicksort, Sorting Networks, Vectorization, SIMD, AVX2
Veranstaltungstitel:19th International Symposium on Experimental Algorithms (SEA 2021)
Veranstaltungsort:Online
Veranstaltungsart:internationale Konferenz
Veranstaltungsdatum:06.-07. Jun. 2021
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Raumfahrt
HGF - Programmthema:keine Zuordnung
DLR - Schwerpunkt:Raumfahrt
DLR - Forschungsgebiet:R - keine Zuordnung
DLR - Teilgebiet (Projekt, Vorhaben):R - keine Zuordnung
Standort: Jena
Institute & Einrichtungen:Institut für Datenwissenschaften
Hinterlegt von: Kühne, Lars
Hinterlegt am:08 Jun 2021 11:06
Letzte Änderung:18 Aug 2022 13:24

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.