Accélérer la détection de collision avec le SIMD

• Box3D applique le SIMD large aux tests de collision de coques convexes 3D complexes, réduisant à moins de la moitié le temps total de simulation pour 5 120 objets composés de 32 points et 89 arêtes
• Le théorème de l’axe séparateur (SAT) en 3D teste les combinaisons face-sommet et arête-arête entre deux coques ; dans Boulder-Boulder, le nombre de combinaisons d’arêtes atteint 7 921, au point que le coût de la double boucle peut dominer la simulation
• En regroupant 4 arêtes de hullB au format SoA pour les tester simultanément avec une arête de hullA, le temps d’exécution sur 1 thread et 500 étapes passe de 40 706 ms en scalaire à 17 337 ms avec SSE2 et 15 762 ms avec AVX2-Lite
• Sur 8 threads, les mesures sont de 5 292 ms en scalaire, 2 410 ms avec SSE2 et 2 277 ms avec AVX2-Lite ; il s’agit de mesures de la simulation complète, incluant à la fois les tests d’arêtes et le solveur de contacts
• Les collisions Box-Box, avec seulement 12 arêtes, tirent peu de bénéfice du fait du coût de préparation, mais l’approche est utile pour les coques complexes utilisées par exemple dans les effets de destruction, avec la possibilité future de tester 8 arêtes à la fois via AVX2

---

Coût de calcul du SAT et méthode d’application du SIMD

• Le SIMD large de Box3D traite plusieurs unités de travail en parallèle, contrairement au SIMD étroit qui place un seul vecteur xyz dans un registre SIMD
  • Dans le solveur de contacts, 4 points de contact sont résolus en une seule fois
  • Le SIMD étroit peut aussi être utile, mais son gain de performance est moins net que celui du SIMD large
• Le benchmark Convex Pile, porté depuis PEEL, fait tomber 5 120 coques convexes contenant chacune 32 points
  • Une Box se compose de 8 sommets, 6 faces et 12 arêtes
  • Un Boulder se compose de 32 sommets, 59 faces et 89 arêtes
  • Box3D traite aussi les Box comme des coques, et dans les benchmarks centrés sur les Box, la narrow phase n’était généralement pas le principal coût
• La détection de collision utilise le théorème de l’axe séparateur (SAT)
  • Le SAT permet de trouver les meilleures caractéristiques séparatrices entre objets ainsi que le déplacement nécessaire, puis de calculer la normale de contact et les points de contact
  • D’autres moteurs physiques combinent parfois GJK et EPA pour le traitement des recouvrements
• Le SAT n’a pas besoin de marge de collision, ce qui permet de placer les objets directement au contact
  • Les combinaisons GJK + EPA laissent parfois un léger écart entre les objets afin de rester dans la zone plus rapide de GJK, ce qui peut créer un interstice visible
  • EPA peut être fragile numériquement et, comme il faut calculer une coque convexe à partir d’entrées plates et fines, un second chemin de secours est parfois nécessaire en cas d’échec
• En 3D, le SAT teste, pour deux coques A et B, les faces de A contre les sommets de B, les faces de B contre les sommets de A, et les arêtes de A contre les arêtes de B, avec une complexité quadratique
  • Box-Box représente 6 combinaisons face-sommet, 6 sommet-face et 144 arête-arête
  • Boulder-Boulder représente respectivement 59, 59 et 7 921 combinaisons
  • La Gauss Map peut réduire le nombre de tests d’arêtes, mais les tests arête-arête peuvent malgré tout dominer la simulation complète
  • Voir Improvements to the Separating Axis Test pour des techniques connexes
• Pour que le SIMD fonctionne efficacement, les données doivent être préparées en structure de tableaux (SoA), ce qui limite l’intérêt pour des coques de seulement 12 arêtes à cause du coût de préparation
  • Avec 89 arêtes à comparer de chaque côté, TestCrossProduct est appelé 7 921 fois
  • L’implémentation SIMD large teste une arête de hullA simultanément contre un EdgeWide contenant 4 arêtes de hullB

Résultats de benchmark et périmètre d’application

• Les mesures ont été réalisées sur un AMD 7950X fixé à 4,42 GHz, avec 500 étapes sur 1 à 8 threads, et chaque valeur correspond au meilleur résultat sur 4 exécutions

Threads	Scalaire	SSE2	AVX2-Lite
1	40,706ms	17,337ms	15,762ms
2	20,799ms	8,857ms	8,131ms
3	13,789ms	5,946ms	5,471ms
4	10,324ms	4,509ms	4,084ms
5	8,359ms	3,675ms	3,361ms
6	6,958ms	3,106ms	2,843ms
7	6,006ms	2,697ms	2,477ms
8	5,292ms	2,410ms	2,277ms

• SSE2 est plus de deux fois plus rapide que le scalaire, et ces mesures couvrent la simulation complète, pas seulement les tests arête-arête
  • Dans la colonne scalaire, le solveur de contacts s’exécute lui aussi en mode scalaire
• Box3D n’implémente directement des intrinsics SIMD que pour SSE2, mais la simple activation de l’architecture AVX2 apporte déjà le gain supplémentaire observé avec AVX2-Lite
  • Box2D dispose aussi d’intrinsics AVX2, mais davantage d’utilisateurs qu’attendu utilisent encore des CPU non compatibles AVX2
  • Une véritable implémentation AVX2 pourrait à l’avenir tester 8 arêtes à la fois
• Pour limiter l’empreinte mémoire, Box3D plafonne à 128 arêtes maximum par coque
  • Cette limite vient du stockage avec des index sur 8 bits et deux demi-arêtes par arête
  • Convertir des coques complexes en meshes peut résoudre le problème de croissance quadratique, mais c’est moins adapté aux objets dynamiques
• Dans les collisions Box-Box, le SIMD appliqué aux tests d’arêtes a peu d’effet
  • En revanche, dans des scénarios de destruction utilisant des coques complexes, le gain de performance est suffisant

[GN⁺]

Avis sur Lobste.rs

• SIMD peut sembler difficile à cause de projets complexes comme simdutf ou simdjson, mais le schéma de base consistant à traiter une boucle ordinaire par blocs de N octets à la fois est en réalité assez simple
  Il suffit de dupliquer les constantes dans chaque lane, d’initialiser l’accumulateur vectoriel, puis de parcourir l’entrée par largeur de vecteur en effectuant comparaisons et opérations, avant de réduire ou stocker le résultat, puis de traiter les éléments restants avec la boucle scalaire classique
  Dans un projet réel, le fait de transformer ainsi une boucle avec sortie anticipée qui cherche une valeur inférieure ou égale à 0xF a apporté un gain de débit de 2 à 16 fois selon le matériel
  Le compilateur peut auto-vectoriser des boucles arithmétiques simples et régulières, mais il ne parvient pas à détecter de manière fiable des transformations combinant sortie anticipée, masques de comparaison, réduction et recherche de la première lane en échec. Plus de détails ici : https://llvm.org/docs/Vectorizers.html
  L’auto-vectorisation fait l’objet de recherches depuis des décennies, et malgré cela les compilateurs réels ratent encore souvent des opportunités : https://arxiv.org/abs/2406.04693
  Une fois familiarisé avec ce schéma de base, on peut l’écrire aussi naturellement qu’une boucle scalaire, donc davantage de développeurs devraient l’apprendre et les langages devraient fournir des outils pour cela. Version développée : https://mitchellh.com/writing/everyone-should-know-simd
  • Je me demande si, pour vraiment bien exploiter SIMD, il faut une structure of arrays (SoA) plutôt qu’un array of structures (AoS). Avec AoS, j’ai l’impression que l’avantage risque de disparaître à cause des copies supplémentaires et du masquage, et je me demande aussi comment construire une interface SIMD unique alors que les instructions prises en charge diffèrent selon les CPU
    J’aimerais savoir si le runtime doit embarquer à la fois une implémentation pour chaque jeu d’instructions de l’architecture cible ainsi qu’une implémentation de secours pour les CPU sans SIMD, ou s’il vise seulement certains jeux d’instructions précis
  • J’aime particulièrement le projet de recherche connexe Halide et j’aimerais le voir utilisé dans davantage de projets
  • Je me demande dans quelle mesure les recherches récentes sur l’auto-vectorisation ont été réellement déployées dans les compilateurs
    Dans mon souvenir, cela restait souvent au stade de preuve de concept académique ou n’arrivait que dans certains compilateurs Fortran, sans être implémenté dans les compilateurs grand public