Fast Sorting Algorithms using AVX-512 on Intel Knights Landing - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2017

Fast Sorting Algorithms using AVX-512 on Intel Knights Landing

Résumé

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.
Fichier principal
Vignette du fichier
avxsort.pdf (608.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01512970 , version 1 (24-04-2017)
hal-01512970 , version 2 (02-11-2017)

Identifiants

  • HAL Id : hal-01512970 , version 1

Citer

Berenger Bramas. Fast Sorting Algorithms using AVX-512 on Intel Knights Landing. 2017. ⟨hal-01512970v1⟩
342 Consultations
6709 Téléchargements

Partager

Gmail Facebook X LinkedIn More