- Box3D ने जटिल 3D convex hull collision checks पर wide SIMD लागू करके, 32 points और 89 edges वाली 5,120 objects की पूरी simulation time को आधे से भी कम कर दिया
- 3D Separating Axis Theorem (SAT) दो hulls के face-vertex और edge-edge combinations की जांच करता है, और Boulder-Boulder में edge combinations 7,921 तक पहुंचते हैं, जिससे double loop की लागत simulation पर हावी हो सकती है
- hullB के 4 edges को SoA format में group करके hullA के एक edge के साथ एक साथ test करने पर, 1 thread・500 steps execution time Scalar 40,706ms से घटकर SSE2 17,337ms, AVX2-Lite 15,762ms हो गया
- 8 threads पर भी Scalar 5,292ms, SSE2 2,410ms, AVX2-Lite 2,277ms दर्ज हुआ, और ये पूरी simulation के measurements हैं जिनमें edge checks और contact solver दोनों शामिल हैं
- सिर्फ 12 edges वाले Box-Box collision में setup cost की वजह से असर लगभग नहीं है, लेकिन destruction effects आदि में इस्तेमाल होने वाले complex hulls के लिए यह उपयोगी है, और आगे AVX2 से 8 edges को एक साथ check करने की संभावना भी है
SAT की computational cost और SIMD लागू करने का तरीका
- Box3D का wide SIMD, narrow SIMD से अलग है जिसमें एक xyz vector को SIMD register में रखा जाता है; यह कई work units को एक साथ process करता है
- contact solver में 4 contact points को एक साथ solve किया जाता है
- narrow SIMD भी उपयोगी हो सकता है, लेकिन performance improvement wide SIMD जितना स्पष्ट नहीं है
- PEEL से port किया गया Convex Pile benchmark, 32 points वाले convex hulls 5,120 को गिराता है
- Box में 8 vertices, 6 faces, और 12 edges होते हैं
- Boulder में 32 vertices, 59 faces, और 89 edges होते हैं
- Box3D, Box को भी hull के रूप में process करता है, और Box-केंद्रित benchmarks में आम तौर पर narrow phase मुख्य लागत नहीं था
- collision detection के लिए Separating Axis Theorem (SAT) का उपयोग किया जाता है
- SAT में collision margin की जरूरत नहीं होती, इसलिए objects को सीधे एक-दूसरे से सटा कर रखा जा सकता है
- GJK और EPA combination में तेज GJK region बनाए रखने के लिए objects को थोड़ा अलग रखा जाता है, जिससे visual gap दिख सकता है
- EPA numerically fragile हो सकता है, और flat व thin inputs से convex hull calculate करना पड़ता है, इसलिए failures के लिए कभी-कभी दूसरा fallback path जरूरी होता है
- 3D SAT दो hulls A और B के लिए A के face-B के vertex, B के face-A के vertex, और A के edge-B के edge को test करता है, जिससे quadratic complexity दिखती है
- Box-Box में face-vertex 6, vertex-face 6, और edge-edge 144 combinations होते हैं
- Boulder-Boulder में ये क्रमशः 59, 59, और 7,921 combinations होते हैं
- Gauss Map से edge checks घटाए जा सकते हैं, लेकिन edge-edge checks पूरी simulation पर हावी हो सकते हैं
- संबंधित technique Improvements to the Separating Axis Test में देखी जा सकती है
- SIMD को efficiently काम करने के लिए data को Structure of Arrays (SoA) में तैयार करना पड़ता है, इसलिए 12-edge hulls में setup cost की तुलना में लाभ बड़ा नहीं होता
- 89 edges की आपस में तुलना करने पर
TestCrossProduct7,921 बार call होता है - wide SIMD implementation hullA के एक edge को hullB के 4 edges वाले
EdgeWideके साथ एक साथ test करता है
- 89 edges की आपस में तुलना करने पर
benchmark results और applicability
- AMD 7950X को 4.42GHz पर fixed रखकर 1~8 threads पर 500 steps चलाए गए, और हर संख्या 4 runs में best result है
| 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, Scalar से 2x से ज्यादा तेज है, और measurements में सिर्फ edge-edge checks नहीं बल्कि पूरी simulation शामिल है
- Scalar column में contact solver भी Scalar mode में चलता है
- Box3D ने खुद सिर्फ SSE2 SIMD intrinsics implement किए हैं, लेकिन AVX2 architecture enable करने भर से AVX2-Lite की अतिरिक्त performance improvement मिलती है
- Box2D में AVX2 intrinsics भी हैं, लेकिन AVX2 support न करने वाले CPU इस्तेमाल करने वाले users उम्मीद से ज्यादा थे
- भविष्य में actual AVX2 implementation से 8 edges को एक साथ test किया जा सकता है
- Box3D storage footprint छोटा रखने के लिए प्रति hull edges को maximum 128 तक limit करता है
- यह limit 8-bit indices और प्रति edge दो half-edges इस्तेमाल करने वाली storage scheme से आती है
- complex hulls को mesh में convert करने से quadratic growth problem हल हो सकती है, लेकिन dynamic objects के लिए यह कम suitable हो जाता है
- Box-Box collision में SIMD edge checks का असर लगभग नहीं है
- complex hulls इस्तेमाल करने वाले destruction scenarios आदि में यह पर्याप्त performance gain देता है
1 टिप्पणियां
Lobste.rs की टिप्पणियाँ
constants को हर lane में replicate करें, vector accumulator initialize करें, फिर vector width के हिसाब से input पर iterate करते हुए compare/operate करें, result को reduce या store करें, और बचे हुए elements को पुराने scalar loop से handle करें
एक वास्तविक project में
0xFया उससे कम value खोजने वाले early-exit loop को इस तरीके से बदलकर hardware के अनुसार 2–16 गुना throughput improvement मिलाcompiler सरल और नियमित arithmetic loops को auto-vectorize कर सकता है, लेकिन early exit, comparison masks, reduction, और पहले failed lane को खोजने का combination वाली transformation को भरोसेमंद ढंग से नहीं पहचान पाता। details https://llvm.org/docs/Vectorizers.html पर हैं
दशकों की research के बाद भी वास्तविक compilers अक्सर auto-vectorization के मौके चूक जाते हैं: https://arxiv.org/abs/2406.04693
basic pattern की आदत हो जाए तो इसे scalar loops जितनी सहजता से लिखा जा सकता है, इसलिए ज्यादा developers को इसे सीखना चाहिए और languages को इसके लिए tools देने चाहिए। विस्तृत लेख https://mitchellh.com/writing/everyone-should-know-simd पर है
जानना चाहूंगा कि runtime को target architecture की हर instruction-specific implementation और SIMD support न करने वाले CPUs के लिए fallback implementation साथ में देनी चाहिए, या केवल किसी specific instruction set को target करना चाहिए
याद है कि पहले यह अक्सर research proof-of-concept तक सीमित रह जाती थी या सिर्फ कुछ Fortran compilers में आती थी, और mainstream compilers में implement नहीं होती थी