SIMDで衝突検出を高速化する

• Box3Dは複雑な3D凸包の衝突判定にワイドSIMDを適用し、32個の点と89本の辺を持つ物体5,120個の全体シミュレーション時間を半分以下に短縮
• 3Dの**分離軸定理（SAT）**は2つの包の面-頂点と辺-辺の組み合わせを検査し、Boulder-Boulderでは辺の組み合わせが7,921個に達するため、二重ループのコストがシミュレーションを支配する可能性がある
• hullBの辺4本をSoA形式でまとめ、hullAの辺1本と同時に検査したところ、1スレッド・500ステップの実行時間はScalar 40,706msからSSE2 17,337ms、AVX2-Lite 15,762msに減少
• 8スレッドでもScalar 5,292ms、SSE2 2,410ms、AVX2-Lite 2,277msを記録し、これは辺検査と接触ソルバーの両方を含む全体シミュレーションの測定値
• 辺が12本しかないBox-Box衝突ではセットアップコストのため効果はほとんどないが、破壊エフェクトなどで使われる複雑な包には有用で、今後AVX2で8本の辺を同時に検査できる余地もある

---

SATの計算コストとSIMDの適用方法

• Box3DのワイドSIMDは、xyzベクトル1つをSIMDレジスタに入れるナローSIMDとは異なり、複数の作業単位を同時に処理する
  • 接触ソルバーでは接触点4つをまとめて解決する
  • ナローSIMDも有用な場合はあるが、性能向上はワイドSIMDほど明確ではない
• PEELから移植したConvex Pileベンチマークは、それぞれ32個の点を持つ凸包5,120個を落下させる
  • Boxは頂点8個、面6個、辺12本で構成される
  • Boulderは頂点32個、面59個、辺89本で構成される
  • Box3DはBoxも包として扱い、Box中心のベンチマークでは通常ナローフェーズは主要なコストではなかった
• 衝突検出には分離軸定理（SAT）を使用する
  • SATで物体を分離する最適な特徴と必要な移動距離を求め、接触法線と接触点も計算する
  • 他の物理エンジンではGJKと、重なり処理用のEPAを組み合わせることもある
• SATは衝突マージンを必要としないため、物体を互いに直接接触するように配置できる
  • GJKとEPAの組み合わせでは、より高速なGJK領域を維持するために物体を少し離す場合があり、視覚的な隙間が生じる可能性がある
  • EPAは数値的に脆弱な場合があり、平たく薄い入力で凸包を計算しなければならないため、失敗に備えた第2のフォールバック経路が必要になることもある
• 3D SATは2つの包AとBについて、Aの面-Bの頂点、Bの面-Aの頂点、Aの辺-Bの辺を検査し、二次複雑度を示す
  • Box-Boxは面-頂点6個、頂点-面6個、辺-辺144個の組み合わせ
  • Boulder-Boulderはそれぞれ59個、59個、7,921個の組み合わせ
  • Gauss Mapで辺検査を減らせるが、辺-辺検査が全体シミュレーションを支配する可能性がある
  • 関連手法はImprovements to the Separating Axis Testで確認できる
• SIMDを効率的に動作させるにはデータを**配列構造（SoA）**として用意する必要があるため、辺12本の包ではセットアップコストに対する利得は大きくない
  • 辺89本ずつを比較すると、TestCrossProductが7,921回呼び出される
  • ワイドSIMD実装は、hullAの辺1本を、hullBの辺4本が入ったEdgeWideと同時に検査する

ベンチマーク結果と適用範囲

• AMD 7950Xを4.42GHzに固定し、1〜8スレッドで500ステップを実行した。各数値は4回実行中の最高結果

スレッド	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はScalarより2倍以上高速で、測定値には辺-辺検査だけでなく全体シミュレーションが含まれる
  • Scalar列では接触ソルバーもScalarモードで実行される
• Box3Dが直接実装したSIMD組み込み関数はSSE2のみだが、AVX2アーキテクチャを有効化するだけでもAVX2-Liteの追加の性能向上が得られる
  • Box2DにはAVX2組み込み関数もあるが、AVX2をサポートしないCPUを使うユーザーが予想より多かった
  • 将来的には実際のAVX2実装で8本の辺を同時に検査できる
• Box3Dは保存領域を小さく保つため、包ごとの辺を最大128本に制限している
  • 8ビットインデックスと、辺ごとに2つのハーフエッジを使う保存方式に由来する制限
  • 複雑な包をメッシュに変換すれば二次増加の問題を解決できるが、動的物体にはあまり適さなくなる
• Box-Box衝突ではSIMDによる辺検査の効果はほとんどない
  • 複雑な包を使う破壊シナリオなどでは十分な性能利得を提供する

[GN⁺]

Lobste.rs の意見

• SIMD は simdutf や simdjson のような複雑なプロジェクトのせいで難しく見えるが、普通のループを一度に N バイトずつ処理する基本パターンは意外と単純
  定数を各レーンに複製し、ベクトル累算器を初期化したあと、ベクトル幅ごとに入力を走査して比較・演算し、結果を縮約または保存し、残った要素を従来のスカラループで処理すればよい
  実プロジェクトで 0xF 以下の値を探す早期終了ループをこの方式に置き換え、ハードウェアによって 2〜16倍のスループット向上 を得た
  コンパイラは単純で規則的な算術ループなら自動ベクトル化できるが、早期終了・比較マスク・縮約・最初の失敗レーン探索が組み合わさった変換は安定して見つけられない。詳しくは https://llvm.org/docs/Vectorizers.html を参照
  自動ベクトル化は数十年にわたって研究されてきたのに、実際のコンパイラはいまでもしばしば機会を逃している: https://arxiv.org/abs/2406.04693
  基本パターンに慣れればスカラループと同じくらい自然に書けるので、もっと多くの開発者が学ぶべきだし、言語もそのための道具を提供すべき。拡張版の記事は https://mitchellh.com/writing/everyone-should-know-simd にある
  • SIMD をきちんと活用するには、構造体配列 (AoS) より 配列構造体 (SoA) が必要なのか気になる。AoS だと追加のコピーやマスキングで利点が消えそうだし、CPU ごとに対応命令が違う状況で単一の SIMD インターフェースをどう構成するのかも疑問
    ランタイムが対象アーキテクチャの各命令向け実装と SIMD 非対応 CPU 向け代替実装をすべて一緒に提供すべきなのか、それとも特定の命令セットだけを対象にするのか知りたい
  • 関連研究プロジェクトの Halide が特に好きで、もっと多くのプロジェクトで活用されてほしい
  • 最近の 自動ベクトル化研究 が実際のコンパイラにどの程度導入されているのか気になる
    以前は研究用の概念実証にとどまるか、一部の Fortran コンパイラにだけ入って、主流コンパイラには実装されないことが多かったと記憶している