elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Fast and Robust Vectorized In-Place Sorting of Primitive Types

Blacher, Mark and Giesen, Joachim and 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-3-95977-185-6. ISSN 1868-8969.

[img] PDF
1MB

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

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.

Item URL in elib:https://elib.dlr.de/142624/
Document Type:Conference or Workshop Item (Speech)
Title:Fast and Robust Vectorized In-Place Sorting of Primitive Types
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Blacher, Markmark.blacher (at) uni-jena.deUNSPECIFIED
Giesen, Joachimjoachim.giesen (at) uni-jena.deUNSPECIFIED
Kühne, LarsLars.Kuehne (at) dlr.deUNSPECIFIED
Date:June 2021
Journal or Publication Title:19th International Symposium on Experimental Algorithms (SEA 2021)
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Volume:190
DOI :10.4230/LIPIcs.SEA.2021.3
Page Range:3:1-3:16
Publisher:Schloss Dagstuhl — Leibniz-Zentrum für Informatik
Series Name:Leibniz International Proceedings in Informatics (LIPIcs)
ISSN:1868-8969
ISBN:978-3-95977-185-6
Status:Published
Keywords:Quicksort, Sorting Networks, Vectorization, SIMD, AVX2
Event Title:19th International Symposium on Experimental Algorithms (SEA 2021)
Event Location:Online
Event Type:international Conference
Event Dates:06.-07. Jun. 2021
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:other
DLR - Research area:Raumfahrt
DLR - Program:R - no assignment
DLR - Research theme (Project):R - no assignment
Location: Jena
Institutes and Institutions:Institute of Data Science
Deposited By: Kühne, Lars
Deposited On:08 Jun 2021 11:06
Last Modified:14 Jun 2021 03:00

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.