Kollisionserkennung mit SIMD beschleunigen

• Box3D wendet breites SIMD auf komplexe 3D-Kollisionstests mit konvexen Hüllen an und reduziert damit die gesamte Simulationszeit für 5.120 Objekte mit 32 Punkten und 89 Kanten auf weniger als die Hälfte
• Die 3D-Trennachsenmethode (SAT) prüft Fläche-Punkt- und Kante-Kante-Kombinationen zweier Hüllen; bei Boulder-Boulder gibt es 7.921 Kantenkombinationen, sodass die Kosten der Doppelschleife die Simulation dominieren können
• Werden 4 Kanten von hullB im SoA-Format gebündelt und gleichzeitig mit einer Kante von hullA geprüft, sinkt die Laufzeit bei 1 Thread und 500 Schritten von Scalar 40.706ms auf SSE2 17.337ms und AVX2-Lite 15.762ms
• Auch mit 8 Threads wurden Scalar 5.292ms, SSE2 2.410ms und AVX2-Lite 2.277ms erreicht; dabei handelt es sich um Messwerte der gesamten Simulation einschließlich Kantenprüfung und Contact Solver
• Bei Box-Box-Kollisionen mit nur 12 Kanten ist der Effekt wegen der Einrichtungskosten gering, für komplexe Hüllen etwa in Zerstörungseffekten ist er jedoch nützlich, und künftig könnte AVX2 8 Kanten gleichzeitig prüfen

---

Rechenkosten von SAT und Einsatz von SIMD

• Das breite SIMD von Box3D verarbeitet im Unterschied zu schmalem SIMD, bei dem ein einzelner xyz-Vektor in ein SIMD-Register gelegt wird, mehrere Arbeitseinheiten gleichzeitig
  • Im Contact Solver werden 4 Kontaktpunkte auf einmal gelöst
  • Schmales SIMD kann ebenfalls nützlich sein, der Leistungsgewinn ist jedoch nicht so eindeutig wie bei breitem SIMD
• Der aus PEEL portierte Convex-Pile-Benchmark lässt 5.120 konvexe Hüllen mit jeweils 32 Punkten fallen
  • Eine Box besteht aus 8 Vertices, 6 Flächen und 12 Kanten
  • Ein Boulder besteht aus 32 Vertices, 59 Flächen und 89 Kanten
  • Box3D behandelt auch Boxen als Hüllen; in Box-zentrierten Benchmarks war die Narrow Phase normalerweise nicht der Hauptkostenfaktor
• Für die Kollisionserkennung wird die Trennachsenmethode (SAT) verwendet
  • SAT bestimmt die besten Merkmale zur Trennung der Objekte und die dafür nötige Verschiebung und berechnet außerdem Kontaktnormale und Kontaktpunkte
  • Andere Physik-Engines kombinieren teils GJK mit EPA zur Behandlung von Überlappungen
• SAT benötigt keinen Kollisionsabstand und erlaubt daher, Objekte direkt aneinander zu platzieren
  • Kombinationen aus GJK und EPA lassen Objekte teils etwas auf Abstand, um den schnelleren GJK-Bereich zu erhalten, was sichtbare Lücken erzeugen kann
  • EPA kann numerisch fragil sein, und weil konvexe Hüllen aus flachen und dünnen Eingaben berechnet werden müssen, ist mitunter ein zweiter Fallback-Pfad für Fehlerfälle nötig
• 3D-SAT prüft für zwei Hüllen A und B die Kombinationen Fläche von A–Punkt von B, Fläche von B–Punkt von A sowie Kante von A–Kante von B und zeigt damit quadratische Komplexität
  • Box-Box hat 6 Fläche-Punkt-, 6 Punkt-Fläche- und 144 Kante-Kante-Kombinationen
  • Boulder-Boulder hat entsprechend 59, 59 und 7.921 Kombinationen
  • Mit der Gauss Map lassen sich Kantenprüfungen verringern, doch die Kante-Kante-Prüfung kann weiterhin die gesamte Simulation dominieren
  • Verwandte Techniken werden in Improvements to the Separating Axis Test beschrieben
• Damit SIMD effizient arbeitet, müssen die Daten als Structure of Arrays (SoA) vorbereitet werden; bei Hüllen mit 12 Kanten ist der Gewinn gegenüber den Einrichtungskosten daher gering
  • Beim Vergleich von jeweils 89 Kanten wird TestCrossProduct 7.921-mal aufgerufen
  • Die breite SIMD-Implementierung prüft eine Kante von hullA gleichzeitig mit EdgeWide, das 4 Kanten von hullB enthält

Benchmark-Ergebnisse und Einsatzbereich

• Getestet wurde auf einem AMD 7950X mit fest auf 4,42GHz gesetztem Takt, mit 1 bis 8 Threads und 500 Schritten; jeder Wert ist das beste Ergebnis aus 4 Durchläufen

Threads	Scalar	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 ist mehr als doppelt so schnell wie Scalar, und die Messwerte umfassen nicht nur die Kante-Kante-Prüfung, sondern die gesamte Simulation
  • In der Scalar-Spalte läuft auch der Contact Solver im Scalar-Modus
• Box3D implementiert SIMD-Intrinsics direkt nur für SSE2, doch schon die Aktivierung der AVX2-Architektur bringt zusätzlichen Leistungsgewinn bei AVX2-Lite
  • Box2D verfügt auch über AVX2-Intrinsics, aber es gab mehr Nutzer mit CPUs ohne AVX2-Unterstützung als erwartet
  • Mit einer echten AVX2-Implementierung könnten künftig 8 Kanten gleichzeitig geprüft werden
• Um den Speicherbedarf klein zu halten, begrenzt Box3D die Zahl der Kanten pro Hülle auf maximal 128
  • Diese Grenze ergibt sich aus dem Speicherlayout mit 8-Bit-Indizes und zwei Half-Edges pro Kante
  • Eine Umwandlung komplexer Hüllen in Meshes kann das Problem des quadratischen Wachstums lösen, ist für dynamische Objekte jedoch weniger geeignet
• Bei Box-Box-Kollisionen bringt die SIMD-Kantenprüfung kaum Wirkung
  • In Zerstörungsszenarien und anderen Fällen mit komplexen Hüllen liefert sie dagegen ausreichend Leistungsgewinn

[GN⁺]

Lobste.rs-Kommentare

• SIMD wirkt wegen komplexer Projekte wie simdutf oder simdjson schwierig, aber das grundlegende Muster, eine gewöhnliche Schleife N Byte auf einmal zu verarbeiten, ist überraschend einfach
  Man repliziert Konstanten in jede Lane, initialisiert einen Vektorakkumulator, durchläuft die Eingabe in Schritten der Vektorbreite, vergleicht und verarbeitet, reduziert oder speichert das Ergebnis und behandelt anschließend die übrigen Elemente mit der bestehenden skalaren Schleife
  In einem realen Projekt wurde eine Schleife mit frühem Abbruch, die nach Werten kleiner oder gleich 0xF sucht, auf diese Weise umgestellt, was je nach Hardware 2- bis 16-fach höheren Durchsatz brachte
  Der Compiler kann einfache und regelmäßige arithmetische Schleifen automatisch vektorisieren, aber Umformungen, bei denen früher Abbruch, Vergleichsmasken, Reduktion und die Suche nach der ersten fehlschlagenden Lane zusammenkommen, erkennt er nicht zuverlässig. Details unter https://llvm.org/docs/Vectorizers.html
  Obwohl zur automatischen Vektorisierung seit Jahrzehnten geforscht wird, verpassen reale Compiler noch immer häufig solche Chancen: https://arxiv.org/abs/2406.04693
  Wenn man sich erst einmal an das Grundmuster gewöhnt hat, kann man es genauso natürlich schreiben wie skalare Schleifen, daher sollten es mehr Entwickler lernen und Sprachen sollten dafür Werkzeuge bereitstellen. Ein erweiterter Artikel steht unter https://mitchellh.com/writing/everyone-should-know-simd
  • Ich frage mich, ob man für die richtige Nutzung von SIMD statt Array of Structs (AoS) eher Struct of Arrays (SoA) braucht. Bei AoS scheint der Vorteil durch zusätzliches Kopieren und Maskieren verloren zu gehen, und ich frage mich auch, wie man eine einheitliche SIMD-Schnittstelle aufbaut, wenn jede CPU andere unterstützte Instruktionen hat
    Ich würde gern wissen, ob die Runtime Implementierungen für jede Instruktion des Zielsystems plus eine Ersatzimplementierung für CPUs ohne SIMD zusammen mitliefern muss oder ob man nur auf bestimmte Befehlssätze abzielt
  • Ich mag das verwandte Forschungsprojekt Halide besonders und würde es gern in mehr Projekten eingesetzt sehen
  • Mich interessiert, wie viel von der jüngeren Forschung zur automatischen Vektorisierung tatsächlich in reale Compiler eingeflossen ist
    Soweit ich mich erinnere, blieb das früher oft bei Machbarkeitsnachweisen für die Forschung oder landete nur in einigen Fortran-Compilern, ohne in Mainstream-Compiler implementiert zu werden