Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Fast Sorting Algorithms using AVX-512 on Intel Knights Landing

Abstract : This paper describes fast sorting techniques using the recent AVX-512 instruction set. Our implementations benefit from the latest possibilities offered by AVX-512 to vectorize a two-parts hybrid algorithm: we sort the small arrays using a branch-free Bitonic variant, and we provide a vectorized partitioning kernel which is the main component of the well-known Quicksort. Our algorithm sorts in-place and is straightforward to implement thanks to the new instructions. Meanwhile, we also show how an algorithm can be adapted and implemented with AVX-512. We report a performance study on the Intel KNL where our approach is faster than the GNU C++ sort algorithm for any size in both integer and double floating-point arithmetics by a factor of 4 in average.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01512970
Contributor : Bérenger Bramas <>
Submitted on : Monday, April 24, 2017 - 2:23:08 PM
Last modification on : Monday, November 16, 2020 - 10:34:04 AM

File

avxsort.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01512970, version 1

Citation

Berenger Bramas. Fast Sorting Algorithms using AVX-512 on Intel Knights Landing. 2017. ⟨hal-01512970v1⟩

Share

Metrics

Record views

181

Files downloads

5420