Concevoir des algorithmes SIMD à partir de zéro

Conception d’algorithmes SIMD

• Explication de l’optimisation SIMD : SIMD signifie Single Instruction, Multiple Data et demande de raisonner comme un concepteur de circuits.
• Le SIMD est souvent mentionné à propos des performances et du HPC (calcul haute performance), mais ce n’est pas un sujet familier pour les débutants.
• Dans la plupart des langages de programmation, les API de programmation SIMD sont difficiles à utiliser.
• Les algorithmes SIMD sont difficiles à comprendre avec une approche de programmation procédurale, et la programmation fonctionnelle peut aider.
• Le texte porte sur vb64, une implémentation d’un codec base64 utilisant la bibliothèque std::simd de Rust.

Limites physiques

• Les ordinateurs existent dans le monde réel et sont soumis aux lois de la physique.
• Aux débuts de l’informatique, on pouvait améliorer les performances en achetant un nouvel ordinateur.
• L’effet du Dennard scaling s’est effondré : des transistors plus petits impliquent une consommation d’énergie plus élevée.
• Augmenter le nombre de cœurs est devenu la nouvelle tendance. On peut améliorer les performances CPU via le multithreading, mais cela entraîne un surcoût de synchronisation.

Lenteur du code procédural

• Les cœurs de processeurs modernes n’exécutent pas le code ligne par ligne.
• Grâce au parallélisme au niveau des instructions, plusieurs opérations peuvent être effectuées simultanément en l’absence de dépendances de données.
• Le parallélisme augmente lorsque le compilateur peut résoudre les risques de dépendance.
• Les branchements et les opérations mémoire provoquent des stalls, ce qui ralentit le code.

SIMD et lanes

• SIMD et vecteur sont souvent utilisés comme synonymes.
• Les instructions SIMD utilisent comme unité de base des vecteurs, c’est-à-dire des tableaux de nombres de taille fixe.
• Chaque élément d’un vecteur est appelé une lane, et les vecteurs SIMD sont généralement de petite taille.

Opérations sur de vrais vecteurs

• Les vecteurs SIMD offrent des opérations plus complexes que les registres ordinaires.
• Les registres vectoriels prennent en charge diverses opérations, comme les opérations bit à bit, l’arithmétique par lane, les comparaisons par lane et les shuffles.
• Les shuffles sont essentiels en programmation SIMD pour déplacer les données vers les bonnes positions.

Fonctions intrinsèques et sélection d’instructions

• Lorsqu’on écrit du code SIMD, les opérations disponibles varient selon l’architecture.
• Le compilateur résout le problème de sélection d’instructions, c’est-à-dire choisir quelles instructions utiliser pour les opérations demandées par l’utilisateur.
• Écrire du code SIMD portable est complexe, mais la détection des fonctionnalités à l’exécution permet de générer le code optimal sur différents processeurs.

Analyse syntaxique avec SIMD

• Il est possible d’utiliser le SIMD pour analyser du texte, et cela peut être extrêmement rapide.
• L’implémentation d’un décodage base64 en SIMD peut servir d’exemple.
• Supprimer toutes les branches est la clé du processus de création d’une version SIMD.

L’avis de GN⁺

Le point le plus important de cet article est que la programmation SIMD, contrairement à la programmation procédurale classique, peut améliorer les performances en traitant les données en parallèle. Le SIMD est très important dans le domaine du calcul haute performance et, en particulier, comprendre comment l’utiliser efficacement dans des langages de programmation modernes comme Rust peut être un sujet très intéressant pour les ingénieurs logiciel. En effet, le SIMD permet d’apprendre à optimiser des algorithmes complexes et à surmonter les limites du matériel réel.

[GN⁺]

Discussion sur Hacker News

• Excellent article pour voir un cas d’usage de SIMD portable. En reproduisant le benchmark sur un système Zen 3, on constate le même gain de vitesse. Sur un M1 mbp, l’amélioration des performances augmente progressivement jusqu’à un maximum de 2x pour une longueur d’entrée de 110 octets. Le gain est moindre que sur x86_64, mais on peut considérer que l’objectif est atteint. Cela confirme toutefois que Rust présente quelques aspects peu pratiques pour le travail autour de SIMD et des pointeurs, ainsi que pour l’ingénierie de performance en général.
• Il est parfois surprenant de voir qu’en essayant de programmer au mieux en C++, une version utilisant SIMD peut tout de même être plus de 10 fois plus rapide. Le code est moins portable, mais on aimerait que le compilateur fasse mieux l’auto-vectorisation. Il serait souhaitable que le langage ajoute un support via des annotations permettant de réorganiser l’ordre de certaines opérations.
• Il est souligné que le compilateur n’a pas réussi à optimiser une certaine implémentation de popcount en une seule instruction, alors que cela peut être possible pour d’autres implémentations.
• _mm256_cvtps_epu32 n’est pas une instruction AVX2 mais AVX-512, et en AVX1 les entiers existent sous forme signée, la bonne instruction étant _mm256_cvtps_epi32.
• La petite minimap à droite plaît beaucoup.
• ISPC est jugé meilleur que l’ajout de SIMD à C++ ou Rust. Il prend aussi en charge le dispatch dynamique, une fonctionnalité difficile à implémenter soi-même.
• Une question est posée sur la comparaison avec fastbase64, avec l’idée de partager l’optimisme de l’auteur au sujet des bibliothèques SIMD portables.
• Un excellent article, qui laisse l’impression qu’on ne pourra jamais devenir aussi intelligent soi-même.
• Le premier exemple d’implémentation de popcnt non vectorisée est présenté comme générant « un code franchement ridicule », mais en compilant en mode release pour le CPU cible natif, la fonction semble finalement être assez bien vectorisée.
• Une assez bonne tentative autour de Rust Simd. Une question est posée sur la particularité la plus surprenante observée lors de l’inspection du code généré.