Discussion :

[Bruno]

Intel publie la bibliothèque open source de fichiers d'en-tête C++ pour le tri rapide AVX-512,
des tris 10 à 17x plus rapides dans NumPy

Intel a récemment publié une bibliothèque open source de fichiers d'en-tête C++ pour le tri haute performance basé sur SIMD, qui se concentre initialement sur la fourniture d'une implémentation rapide du quicksort Advanced Vector Extensions 512 (Intel AVX-512). À ce jour, ce code a été intégré à Numpy et permetrait des accélérations de 10 à 17 fois plus rapides.

NumPy est un projet open source axé sur la communauté et développé par un groupe diversifié de contributeurs. La direction de NumPy s'est fermement engagée à créer une communauté ouverte et inclusive. Intel Advanced Vector Extensions 512 est un ensemble de nouvelles instructions permettant d'accélérer les performances pour des charges de travail et des utilisations telles que les simulations scientifiques, les analyses financières, l'intelligence artificielle (IA)/apprentissage profond, la modélisation et l'analyse 3D, le traitement des images et de l'audio/vidéo, la cryptographie et la compression des données.

Vers la fin de l'année dernière, Intel a mis à disposition x86-simd-sort via son compte GitHub. Il s'agit d'une bibliothèque de fichiers d'en-tête C++ pour le tri SIMD haute performance, bien que dans sa forme actuelle, elle se concentre uniquement sur une implémentation de tri rapide AVX-512.

La bibliothèque de fichiers d'en-tête C++ pour le tri de types de données 16 bits, 32 bits et 64 bits basé sur SIMD sur les processeurs x86. Les fichiers d'en-tête source sont disponibles dans le répertoire src. Actuellement, Intel ne dispose que d’une implémentation de quicksort basée sur AVX-512. Ce dépôt comprend également une suite de tests qui peut être construite et exécutée pour tester l'exactitude des algorithmes de tri. Il y a aussi du code de benchmarking pour comparer ses performances par rapport à [C=c++]std::sort[C=Rust].

Les idées et le code sont basés sur deux articles de recherche : Fast and Robust Vectorized In-Place Sorting of Primitive Types et A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake.

Tri vectoriel en place rapide et robuste de types primitifs

Les processeurs modernes fournissent des instructions SIMD (single instruction-multiple data). Les instructions SIMD traitent simultanément plusieurs éléments d'un type de données primitif dans des vecteurs de taille fixe. Les algorithmes de tri classiques ne sont pas directement exprimables en instructions SIMD.

Accélérer les algorithmes de tri avec des instructions SIMD est donc un effort créatif. Une approche prometteuse pour le tri avec des instructions SIMD consiste à utiliser des réseaux de tri pour les petits tableaux et Quicksort pour les grands tableaux. Dans Fast and Robust Vectorized In-Place Sorting of Primitive Types, les chercheurs améliorent les techniques de vectorielles pour les réseaux de tri et Quicksort.

En particulier, ils montrent comment utiliser la pleine capacité des registres vectoriels dans les réseaux de tri et comment rendre le Quicksort vectorisé robuste par rapport à différentes distributions de clés. Pour démontrer la performance des techniques, ils implémentent un algorithme de tri hybride in-place pour le type de données int avec les intrinsèques AVX2. L’implémentation serait au moins 30 % plus rapide que les alternatives de tri haute performance de l'état de l'art.

L'idée est de vectoriser le partitionnement quicksort en utilisant les instructions AVX-512 compressstore. Si la taille du tableau est < 128, alors on utilise un réseau de tri Bitonic implémenté sur des registres de 512 bits. Les définitions précises du réseau dépendent de la taille du dtype et sont définies dans des fichiers séparés : avx512-16bit-qsort.hpp, avx512-32bit-qsort.hpp et avx512-64bit-qsort.hpp. L'article est une bonne ressource pour le réseau de tri bitonique. Les implémentations principales des fonctions qsort vectorisées avx512_qsort.

(T*, int64_t) sont des versions modifiées de avx2 quicksort présentées dans l'article.

Un nouvel algorithme hybride de tri rapide vectorisé à l'aide d'AVX-512 sur Intel Skylake

La conception de l'unité centrale moderne, qui est composée d'une mémoire hiérarchique et de capacités SIMD/vectorisation. le potentiel de transformation des algorithmes en implémentations efficaces.

La sortie de l'AVX-512 a radicalement changé les choses, et nous a motivés à rechercher un algorithme de tri efficace qui puisse en tirer parti. Dans cet article, nous décrivons Dans cet article, nous décrivons la meilleure stratégie que nous avons trouvée, qui est un nouveau tri hybride à deux parties, basé sur l'algorithme bien connu Quicksort.

L'opération centrale de partitionnement est effectuée par un nouvel algorithme, et les les petites partitions/réseaux sont triés à l'aide d'un tri Bitonique sans branche. Cette étude illustre également la façon dont les algorithmes classiques peuvent être adaptés et améliorés par l'extension AVX-512.

Les performances de l’approche sont évaluées sur un sur un Intel Xeon Skylake moderne et évaluons les différentes couches de l’implémentation en triant/partitionnant des entiers, des nombres à double virgule flottante et des paires clé/valeur d'entiers. Les résultats démontrent que notre approche est plus rapide que deux bibliothèques de de référence : l'algorithme de tri GNU C++ par un facteur d'accélération de 4, et la bibliothèque Intel IPP par un facteur de 1,4.

Ce projet x86-simd-sort n'a pas fait l'objet d'une grande couverture médiatique et la page GitHub elle-même ne parle pas beaucoup du potentiel de performance rapide d'AVX-512 pour le tri... Mais aujourd'hui, par le biais du projet open source Numpy, largement utilisé, il y a une utilisation importante de cette technologie et des résultats stupéfiants sont obtenus.

Le PR 22315 a été intégré aujourd'hui à Numpy pour vectoriser le quicksort pour les types de données 16 et 64 bits en utilisant AVX-512. Sur un système Intel Tigerlake, le tri des int 16 bits a été accéléré de 17 fois, celui des float 64 bits de près de 10 fois pour les tableaux aléatoires et celui des types de données 32 bits de 12 à 13 fois.

Exemple pour inclure et construire ceci dans un code C++

Exemple de code main.cpp

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "src/avx512-32bit-qsort.hpp"
 
int main() {
    const int ARRSIZE = 10;
    std::vector<float> arr;
 
    /* Initialize elements is reverse order */
    for (int ii = 0; ii < ARRSIZE; ++ii) {
        arr.push_back(ARRSIZE - ii);
    }
 
    /* call avx512 quicksort */
    avx512_qsort<float>(arr.data(), ARRSIZE);
    return 0;
}

Compilation avec gcc

gcc main.cpp -mavx512f -mavx512dq -O3
Il s'agit d'une bibliothèque de fichiers d'en-tête uniquement et aucune vérification à la compilation et à l'exécution n’est fournie. Une version légèrement modifiée de ce code source a été intégrée à NumPy.

Source : Intel

Et vous ?

Quel est votre avis sur le sujet ?

Voir aussi :

Intel va investir jusqu'à 100 milliards de dollars pour construire le "plus grand site de fabrication de puces de la planète" dans l'Ohio, afin de rétablir la domination d'Intel dans le domaine

Intel serait sur le point de racheter Granulate, une startup spécialisée dans l'optimisation du cloud, pour quelque 650 millions de dollars