Pourquoi tous les développeurs devraient connaître le SIMD

 (mitchellh.com)
1 points par GN⁺ 2 시간 전 | 1 commentaires | Partager sur WhatsApp
  • Le SIMD n’est pas une technique complexe réservée aux logiciels ultra-performants : c’est aussi un moyen d’optimisation courant pour accélérer des boucles ordinaires en traitant des données contiguës par groupes de plusieurs valeurs
  • Un code SIMD classique suit une structure en 5 étapes : diffusion d’une constante, parcours par vecteurs, opérations en parallèle, réduction ou stockage du résultat, puis traitement scalaire de fin
  • Dans Ghostty, la boucle de recherche de points de code compare 4, 8 ou 16 u32 à la fois, avec un débit théorique pouvant aller jusqu’à 4x sur ARM NEON, 8x sur AVX2 et 16x sur AVX-512
  • Sur un desktop Intel avec AVX2, le débit global du terminal a été multiplié par environ 5 ; s’il n’y a pas de largeur de vecteur prise en charge ou s’il reste des données en entrée, la boucle scalaire existante traite l’ensemble de l’entrée ou le reliquat
  • La vectorisation automatique du compilateur peut rater des opportunités, même dans des boucles simples : il faut donc d’abord vérifier le code généré, mais pour les boucles critiques, un SIMD explicite permet de garder un comportement et des performances prévisibles

Ce que fait le SIMD

  • Le SIMD permet au CPU de traiter plusieurs valeurs en parallèle avec une seule instruction
    • Au lieu de comparer les octets un par un, on peut en comparer 4, 8 ou davantage d’un coup
    • Des boucles comme for (byte in bytes), for (character in string), for (value in array) peuvent être transformées en traitement par largeur de vecteur
  • Si les données comptent des centaines, des milliers ou des millions d’octets, on peut obtenir une accélération locale de 4x, 8x ou plus selon la largeur parallèle
  • Si les données ne contiennent que quelques éléments ou quelques dizaines, cela ne vaut pas la peine d’appliquer du SIMD
  • simdutf et simdjson utilisent des techniques SIMD complexes, mais le SIMD du quotidien n’a pas besoin d’être aussi compliqué
  • Les exemples utilisent Zig, mais la structure en 5 étapes s’applique aussi à d’autres langages, même si la prise en charge des instructions SIMD varie selon les langages

La structure récurrente en 5 étapes

  1. Diffuser les constantes nécessaires sur toutes les lanes et, si besoin, initialiser un accumulateur vectoriel
  2. Parcourir l’entrée par blocs de la taille de la largeur de vecteur
  3. Exécuter en parallèle les comparaisons ou opérations arithmétiques sur toutes les lanes
  4. Réduire ou stocker les résultats vectoriels selon l’algorithme
  5. Traiter avec la boucle existante les éléments restants qui ne remplissent pas un vecteur complet, c’est la queue scalaire (scalar tail)
  • Une fois cette structure assimilée, il devient possible de décomposer une boucle ordinaire selon ces 5 étapes, et écrire du SIMD devient presque aussi simple qu’écrire une boucle scalaire
  • Si un problème ne s’exprime pas simplement avec cette structure, il vaut mieux pour l’instant éviter d’y appliquer du SIMD

La vraie boucle de recherche de Ghostty

  • Ghostty consomme les données d’un tableau de points de code décodés jusqu’à rencontrer une valeur inférieure ou égale à 0xF
    • La majorité des données d’un terminal correspond à des caractères ordinaires à afficher, qui peuvent donc être traités par blocs
    • La boucle cherche à trouver le plus vite possible la fin de la prochaine plage affichable
  • L’implémentation scalaire d’origine inspecte les points de code un par un
while (end < cps.len and cps[end] > 0xF) end += 1;
  • L’implémentation vectorielle utilise des vecteurs génériques sans intrinsics spécifiques au CPU, et n’ajoute que 12 lignes de code par rapport à la version scalaire
  • Le gain de débit attendu correspond au nombre de lanes du vecteur
    • ARM NEON et Apple Silicon : jusqu’à 4x
    • AVX2, pris en charge par la plupart des CPU x86 modernes : jusqu’à 8x
    • AVX-512, pris en charge par certains CPU Intel et AMD Zen 4 ou plus récents : jusqu’à 16x
  • Sur un desktop Intel avec AVX2, le débit global mesuré depuis l’entrée du programme terminal jusqu’à l’état final du terminal a été multiplié par environ 5
    • Toute l’accélération théorique n’est pas atteinte à cause du travail annexe autour du SIMD
  • Des caractères de contrôle C0 existent aussi après 0xF, mais 0xF est ici le seuil utilisé dans ce chemin de code de Ghostty
    • ESC et les autres séquences de contrôle sont traités dans un autre chemin

Étape 1 : diffusion de la constante

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
  • simd.lanes(u32) dans Ghostty renvoie le nombre de u32 que le CPU cible peut traiter simultanément
    • Chaque valeur est appelée une lane
    • ARM renvoie 4, AVX2 renvoie 8, AVX-512 renvoie 16
    • S’il n’existe pas de taille de vecteur utilisable, la fonction renvoie null et le code SIMD est ignoré
  • @Vector(lanes, u32) crée un type vectoriel avec ce nombre de lanes
    • Si lanes vaut 8, un V contient 8 u32 traitables en parallèle
  • Pour comparer des vecteurs, les deux côtés doivent être vectoriels ; @splat(0xF) réplique donc 0xF sur toutes les lanes
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
  • Cet algorithme n’a pas besoin d’accumulateur vectoriel, mais d’autres algorithmes peuvent l’initialiser à cette étape

Étape 2 : parcourir un vecteur à la fois

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;
  • Si lanes vaut 8, la boucle n’entre que s’il reste au moins 8 valeurs, puis charge ces 8 valeurs dans values
  • À la fin de chaque itération, end n’augmente pas de 1 mais du nombre de lanes
  • Comme il faut pouvoir charger un vecteur complet, on ne lit pas un vecteur de 8 lanes s’il ne reste que 5 valeurs
  • Les valeurs qui ne rentrent pas dans un vecteur sont traitées par la queue scalaire de l’étape 5

Étape 3 : comparaison parallèle sur toutes les lanes

const greater_than_threshold = values > threshold;
  • Comme values et threshold sont tous deux des vecteurs, > compare chaque lane correspondante avec une seule opération vectorielle
  • Avec 8 lanes, cela exécute en parallèle 8 comparaisons équivalentes à cps[end] > 0xF
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
  • Il n’y a pas de boucle interne explicite ; le résultat est un vecteur de booléens, lane par lane
  • La même structure s’applique non seulement aux comparaisons, mais aussi aux additions, multiplications, minima, maxima et autres opérations prises en charge par les types vectoriels
  • La comparaison elle-même est une seule opération vectorielle, mais le chargement du vecteur, la réduction du résultat et la recherche de la lane en échec nécessitent des instructions supplémentaires

Étape 4 : réduction du résultat vectoriel

if (@reduce(.And, greater_than_threshold)) continue;
  • @reduce(.And, ...) combine tous les booléens avec un and pour produire un seul booléen
  • Si toutes les lanes valent true, on passe au vecteur suivant ; si l’une d’elles vaut false, on cherche la position exacte de l’échec
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
  • @bitCast convertit le vecteur de booléens en masque entier d’un bit par lane
    • 1 signifie que la valeur est supérieure à 0xF
    • 0 signifie que la comparaison a échoué
  • En inversant le masque, les comparaisons en échec deviennent des 1, et @ctz compte le nombre de bits à 0 avant le premier 1
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }
  • Dans cet exemple, @ctz(~mask) renvoie 3 et déplace end vers la lane 3, là où se trouve le premier caractère de contrôle 0x0A
  • La réduction du résultat est la partie qui varie le plus d’un algorithme à l’autre parmi les 5 étapes
    • Une somme peut réduire un accumulateur vectoriel en une valeur unique
    • Une transformation peut écrire tout le vecteur dans le buffer de sortie
    • Cette recherche produit un masque de bits pour trouver la position d’une lane donnée

Étape 5 : traitement de la queue scalaire

while (end < cps.len and cps[end] > 0xF) end += 1;
  • Si la longueur de l’entrée n’est pas un multiple exact de la largeur de vecteur, la boucle scalaire d’origine traite le reste
  • Après une boucle vectorielle à 8 lanes, il peut rester entre 0 et 7 valeurs
  • Sur un CPU où simd.lanes(u32) vaut null, la partie SIMD est ignorée et la boucle scalaire traite toute l’entrée
  • L’implémentation d’origine gère donc à la fois le reliquat et le fallback de compatibilité
  • Les vecteurs génériques suppriment la syntaxe spécifique à chaque CPU, mais pas la génération de code spécifique à chaque CPU
    • Zig traduit les opérations vectorielles vers le jeu d’instructions activé pour la cible

Ce que rate la vectorisation automatique

  • Le compilateur peut vectoriser automatiquement du code simple, par exemple des boucles arithmétiques régulières sans flux de contrôle complexe
  • Avant d’écrire du SIMD à la main, il faut compiler la version scalaire avec les options d’optimisation et vérifier le code généré
  • Les compilateurs de production ratent souvent des opportunités de vectorisation ; le sujet est étudié depuis des décennies, et des travaux récents partent encore de ce constat
  • Si une boucle est suffisamment critique pour qu’un gain de 5x compte vraiment, écrire explicitement la vectorisation permet de garder un comportement prévisible
    • Cela évite qu’une modification de code sans rapport ou une mise à jour du compilateur ne fasse repasser discrètement une boucle vectorielle en boucle scalaire

Le niveau de SIMD que les développeurs devraient maîtriser

  • Lorsqu’on identifie une boucle critique qui parcourt, compare, compte ou transforme de grandes quantités de données contiguës, il faut savoir envisager un traitement par largeur de vecteur
  • Le SIMD du quotidien suit une forme régulière : préparation des constantes, chargement des vecteurs, opération en parallèle, réduction du résultat, puis queue scalaire
  • Si le langage prend bien en charge le SIMD, il est possible d’améliorer les performances sans connaître directement l’assembleur ni les détails propres à chaque CPU
  • Le niveau nécessaire pour tous les développeurs n’est pas celui des techniques complexes à la simdutf ou simdjson, mais la capacité à reconnaître les occasions d’appliquer le SIMD et à exploiter cette structure commune

À lire aussi

1 commentaires

 
GN⁺ 2 시간 전
Avis sur Hacker News

  • Bon article, mais commencer en affirmant que SIMD est facile à comprendre et aussi facile à écrire qu’une boucle for, puis transformer dès le premier exemple une ligne de code scalaire en 12 lignes, ce n’est pas très convaincant.
    Il vaudrait mieux dire franchement que SIMD est difficile, mais que le résultat en vaut la peine. Si l’article vise les débutants, il ne faudrait pas employer dès l’étape 1 des termes propres à SIMD comme broadcast sans les expliquer ; l’étape 5, qui explique le traitement de la queue scalaire, est en revanche bien structurée.

    • SIMD et le premier exemple relèvent moins de quelque chose de difficile que d’une tâche nettement plus fastidieuse.
      Il faut déterminer combien d’éléments le matériel peut traiter à la fois, regrouper le travail selon cette taille, dépaqueter les résultats, traiter séparément les éléments restants, et même transformer les constantes en vecteurs répliqués. Chaque point n’est pas difficile en soi, mais cela augmente la quantité de travail et rend l’ensemble pénible.
    • J’ai appris Parallel-C, créé vers 1990 dans la vague d’enthousiasme autour du Transputer ; c’était un langage qui ajoutait à C des fonctionnalités de programmation parallèle.
      Ma fonctionnalité préférée était par(; ; ), qui permettait au compilateur de paralléliser automatiquement les boucles for sous certaines conditions aux limites.
    • Je suis à peu près exactement le public visé, et j’ai trouvé la lecture intéressante, mais le niveau de difficulté grimpe trop vite, au point de rappeler le fameux mème “dessiner le hibou”.
    • SIMD en soi est simple ; c’est l’usage d’opérations parallèles sur les données dans un langage scalaire qui est maladroit.
    • L’une des plus grandes erreurs dans l’enseignement technique consiste à déclarer qu’un sujet est simple pour tenter d’en dissiper la peur. Il ne faut pas dire que c’est simple, il faut le montrer réellement.
      Si le sujet est effectivement complexe, il faut le découper en parties plus petites et plus simples, puis bien organiser la progression pour aider à gravir la courbe d’apprentissage abrupte et convaincre que cela en vaut la peine.

  • Un meilleur conseil serait que tout le monde devrait connaître la programmation par tableaux. L’optimisation SIMD exige généralement cette façon de penser, et les techniques vraiment spécifiques au SIMD empaqueté sont étonnamment rares.
    La programmation par tableaux facilite l’auto-vectorisation par le compilateur et produit en général du code performant même sans écrire directement du SIMD.

    • La programmation par tableaux qui effectue d’abord toutes les comparaisons puis cherche ensuite le premier échec n’aide pas beaucoup quand la plage d’exécution est courte. Comme elle ne fournit pas intrinsèquement de sortie anticipée, elle peut perdre beaucoup de temps dans des comparaisons inutiles.
    • Je n’aime pas les langages propriétaires, et MATLAB a beaucoup de défauts, mais à l’université il était très naturel d’écrire efficacement du code vectorisé pour des simulations numériques.
      Je n’ai pas énormément d’expérience, mais Julia me semble être ce qui se rapproche le plus d’un langage plus moderne et plus expressif doté de capacités de vectorisation similaires.

  • Ces derniers jours, j’ai optimisé avec AVX-512 les opérations matricielles d’un projet de bio-informatique, et j’en suis très satisfait.
    Dans la plupart des applications, le goulot d’étranglement vient de la lecture de grands jeux de données en mémoire ; au lieu de les relire plusieurs fois pour différentes opérations, on peut tout traiter en une seule passe avec des registres AVX et des kernels fusionnés. Des accélérations par 5 sont courantes, et même si j’ai utilisé directement des intrinsèques, le crate wide rend les opérations courantes très simples : https://docs.rs/wide/latest/wide/

  • L’écrasante majorité des développeurs n’a absolument pas besoin d’apprendre SIMD. Je me demande pourquoi on laisse entendre que tout développeur devrait le connaître pour être un “vrai” développeur.

    • Il est au moins utile de connaître l’existence de SIMD et ce qu’il rend possible. Un développeur a probablement déjà écrit une boucle chaude qui additionne ou compare des valeurs simples, et savoir que le compilateur peut l’optimiser pour l’architecture CPU cible peut être utile dans bien des situations.

  • Le titre devrait plutôt être “Tout le monde devrait savoir quand SIMD n’a pas été appliqué”.
    Les compilateurs modernes vectorisent très bien, puis reviennent soudainement à du code scalaire à cause d’une hypothèse ou d’une branche dépendante des données. Savoir consulter les rapports d’optimisation du compilateur peut être plus précieux que savoir écrire du SIMD.

    • La solution à une auto-vectorisation médiocre consiste à écrire soi-même du code SIMD, donc je me demande si savoir lire les rapports d’optimisation est vraiment plus précieux que cela.
      Si l’on ne peut qu’identifier le problème, on finit simplement par se dire “dommage”.
    • C’est exactement ce qui s’est produit en pratique : https://xcancel.com/mitchellh/status/2079672171321081908#m

  • L’an dernier, en créant un synthétiseur audio, j’ai commencé à apprendre le SIMD x86 et ARM : https://github.com/seclorum/SIMDSynth
    L’architecture d’un synthétiseur multitimbral et polyphonique se prête très bien à l’apprentissage des principes SIMD, car elle applique les mêmes traitements à plusieurs flux de données. En revanche, le débogage est assez difficile : j’aurais vraiment eu besoin d’un simulateur permettant de comprendre l’état de chaque pipeline de traitement, et étudier les outils SIMD demanderait probablement encore un gros investissement.

  • L’article est bon et j’aimerais que davantage de langages prennent SIMD en charge, mais il est un peu étrange de dire que “tous les programmeurs devraient le connaître” alors que les deux langages les plus populaires ne le prennent pas en charge nativement.

    • Il est difficile de supposer que les langages les plus populaires sont ceux qu’utilisent le plus les ingénieurs logiciel visés par ce type d’article.

  • Même si l’on n’écrit pas directement du SIMD, ou si l’on prévoit de le confier à une IA, il faut savoir quelles tâches peuvent être accélérées par SIMD sur quel matériel. C’est nécessaire pour concevoir des algorithmes et structures de code compatibles avec l’application de SIMD.
    L’impact des dépendances de données, le coût de l’augmentation de la largeur des éléments vectoriels et les moyens de l’éviter, la transformation des conditions et branchements en masques, ou encore des caractéristiques comme “il n’y a pas d’instruction de division”, s’assimilent bien plus facilement après avoir utilisé ne serait-ce qu’un peu SIMD directement.

    • La question de savoir quand SIMD est plus rapide n’est pas suffisamment traitée.
      Il fonctionne bien quand on inspecte ou transforme d’un coup de grands blocs de données contigus, mais si l’on doit prendre une décision tous les quelques octets d’entrée, il peut être équivalent au scalaire, voire plus lent. SIMD n’est pas un bouton d’accélération magique.

  • Voici une vidéo utile où Casey Muratori explique comment l’équipe de développement de The Witness a résolu un vrai problème de performance avec SIMD : https://www.youtube.com/watch?v=Ge3aKEmZcqY

    • Excellente présentation, mais la vidéo est trop longue pour être recommandée à d’autres ; j’aimerais qu’il existe une version écrite centrée sur l’essentiel.
      C’est un bon exemple d’intégration verticale au service de la performance : elle montre comment, après avoir compris pourquoi les abstractions générales existent et pourquoi elles doivent être génériques, on peut, pour un cas d’usage précis, intégrer verticalement depuis la définition du problème jusqu’à SIMD et obtenir de gros gains.

  • Avant de se lancer dans des micro-optimisations comme SIMD, il faut d’abord examiner sérieusement les structures de données et les schémas d’accès.
    J’avais appliqué SIMD à un ancien code Zig, mais le modèle de structures de données allait exactement à l’encontre de l’optimisation : c’était comme monter des pneus de course haute performance sur une vieille voiture avec un moteur défectueux. C’était un cas typique d’optimisation prématurée, sans mesure des performances ni prise en compte de l’emplacement des allocations mémoire.
    Désormais, je considère les données comme des tables SQL et je conçois les structures autour des clés primaires potentielles et des schémas d’accès. Avant, j’utilisais un arbre pointant vers d’autres structures sur le tas, cumulant les défauts des listes chaînées, la fragmentation de nombreux vecteurs sur le tas et le coût élevé de création/libération ; Drop à lui seul consommait une part importante du temps d’exécution.
    Un arbre pouvant toujours être linéarisé, j’examine les schémas d’accès et d’insertion, la question de savoir s’il s’agit réellement d’un arbre ou d’un autre graphe, et s’il faut le stocker dans un Vec ou dans une structure composée de plusieurs Vec. Résultat : le code est devenu plus rapide et plus simple, les données sont regroupées en tableaux homogènes, ce qui permet au compilateur d’exploiter plus facilement les optimisations SIMD et le cache L1, et, si nécessaire, d’écrire directement du code SIMD sans branchement.
    Ressource liée : https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

    • Pour accélérer une boucle critique avec SIMD, la disposition des données et les structures favorables au cache sont essentielles.
      Dans les vrais goulets d’étranglement, il faut éviter les allocations mémoire, les recherches dans les tables de fonctions virtuelles et les indirections excessives. Même le vector de C++ n’est pas toujours le meilleur choix s’il peut déclencher des allocations imprévues.
    • C’est un problème que l’on rencontre constamment en tant qu’ingénieur performance. La performance commence par l’architecture ; sur un chemin critique dont la disposition des données est mauvaise, les gains possibles sont limités.
      À l’inverse, le code orienté données prend presque toujours facilement en charge le threading et SIMD.
    • Plus fondamentalement encore, les schémas d’accès mémoire sont importants.
      Fait intéressant, le code CPU finit lui aussi par s’écrire dans un style proche du GPU ; une approche consiste à utiliser une structure de tableaux à la manière de Parquet, plutôt qu’un tableau d’objets.
    • Les tables sont une manière efficace d’implémenter des graphes génériques et, tant qu’on ne peut pas spécialiser le graphe, c’est la meilleure représentation que je connaisse.