Mempercepat Deteksi Tabrakan dengan SIMD

• Box3D menerapkan wide SIMD pada pemeriksaan tabrakan cangkang cembung 3D yang kompleks, memangkas waktu simulasi total untuk 5.120 objek dengan 32 titik dan 89 sisi menjadi kurang dari setengahnya
• Separating Axis Theorem (SAT) 3D memeriksa kombinasi muka-titik dan sisi-sisi dari dua cangkang, dan pada Boulder-Boulder jumlah kombinasi sisi mencapai 7.921 sehingga biaya loop ganda dapat mendominasi simulasi
• Dengan mengelompokkan 4 sisi dari hullB dalam format SoA dan memeriksanya sekaligus terhadap satu sisi dari hullA, waktu eksekusi 1 thread·500 step turun dari Scalar 40.706ms menjadi SSE2 17.337ms dan AVX2-Lite 15.762ms
• Pada 8 thread, hasilnya juga tercatat sebagai Scalar 5.292ms, SSE2 2.410ms, dan AVX2-Lite 2.277ms; ini adalah pengukuran seluruh simulasi yang mencakup pemeriksaan sisi dan contact solver
• Tabrakan Box-Box yang hanya memiliki 12 sisi hampir tidak mendapat manfaat karena biaya setup, tetapi pendekatan ini berguna untuk cangkang kompleks yang dipakai pada efek destruksi, dan ke depan masih ada peluang memeriksa 8 sisi sekaligus dengan AVX2

---

Biaya komputasi SAT dan cara penerapan SIMD

• Wide SIMD di Box3D memproses beberapa unit kerja sekaligus, berbeda dari narrow SIMD yang menaruh satu vektor xyz ke dalam register SIMD
  • Pada contact solver, 4 titik kontak diselesaikan sekaligus
  • Narrow SIMD juga bisa berguna, tetapi peningkatan performanya tidak sejelas wide SIMD
• Benchmark Convex Pile yang dipindahkan dari PEEL menjatuhkan 5.120 cangkang cembung yang masing-masing memiliki 32 titik
  • Box terdiri dari 8 vertex, 6 muka, dan 12 sisi
  • Boulder terdiri dari 32 vertex, 59 muka, dan 89 sisi
  • Box3D juga memperlakukan Box sebagai cangkang, dan pada benchmark yang berfokus pada Box, narrow phase umumnya bukan biaya utama
• Untuk deteksi tabrakan digunakan Separating Axis Theorem (SAT)
  • Dengan SAT, fitur optimal untuk memisahkan objek dan jarak perpindahan yang diperlukan dapat dihitung, begitu juga normal kontak dan titik kontak
  • Mesin fisika lain kadang menggabungkan GJK dengan EPA untuk menangani overlap
• SAT tidak memerlukan collision margin sehingga objek bisa ditempatkan saling bersentuhan langsung
  • Kombinasi GJK dan EPA kadang memberi sedikit jarak antarbenda untuk mempertahankan objek tetap berada di area GJK yang lebih cepat, sehingga bisa menimbulkan celah visual
  • EPA bisa rapuh secara numerik, dan karena perlu menghitung cangkang cembung dari input yang datar dan tipis, kadang diperlukan jalur fallback kedua untuk mengantisipasi kegagalan
• SAT 3D untuk dua cangkang A dan B memeriksa muka A-vertex B, muka B-vertex A, dan sisi A-sisi B, sehingga memiliki kompleksitas kuadratik
  • Box-Box memiliki 6 kombinasi muka-titik, 6 titik-muka, dan 144 sisi-sisi
  • Boulder-Boulder masing-masing memiliki 59, 59, dan 7.921 kombinasi
  • Pemeriksaan sisi dapat dikurangi dengan Gauss Map, tetapi pemeriksaan sisi-sisi tetap dapat mendominasi seluruh simulasi
  • Teknik terkait bisa dilihat di Improvements to the Separating Axis Test
• Agar SIMD bekerja efisien, data harus disiapkan dalam structure of arrays (SoA), sehingga pada cangkang dengan 12 sisi manfaatnya tidak besar dibanding biaya setup
  • Saat membandingkan 89 sisi melawan 89 sisi, TestCrossProduct dipanggil 7.921 kali
  • Implementasi wide SIMD menguji satu sisi dari hullA secara bersamaan terhadap EdgeWide yang berisi 4 sisi dari hullB

Hasil benchmark dan cakupan penerapan

• AMD 7950X dikunci pada 4,42GHz dan menjalankan 500 step pada 1~8 thread, dan setiap angka adalah hasil terbaik dari 4 kali pengujian

Thread	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 lebih dari 2x lebih cepat daripada Scalar, dan hasil pengukuran ini mencakup seluruh simulasi, bukan hanya pemeriksaan sisi-sisi
  • Pada kolom Scalar, contact solver juga berjalan dalam mode Scalar
• SIMD intrinsic yang diimplementasikan langsung oleh Box3D baru sebatas SSE2, tetapi mengaktifkan arsitektur AVX2 saja sudah memberi peningkatan tambahan pada AVX2-Lite
  • Box2D juga memiliki intrinsic AVX2, tetapi jumlah pengguna yang memakai CPU tanpa dukungan AVX2 ternyata lebih banyak dari perkiraan
  • Ke depan, implementasi AVX2 yang sesungguhnya dapat memungkinkan pemeriksaan 8 sisi sekaligus
• Untuk menjaga ukuran penyimpanan tetap kecil, Box3D membatasi jumlah sisi per cangkang hingga maksimum 128
  • Batas ini berasal dari cara penyimpanan yang memakai indeks 8-bit dan dua half-edge per sisi
  • Mengubah cangkang kompleks menjadi mesh bisa mengatasi pertumbuhan kuadratik, tetapi menjadi kurang cocok untuk objek dinamis
• Pada tabrakan Box-Box, efek SIMD pada pemeriksaan sisi nyaris tidak ada
  • Namun pada skenario destruksi yang memakai cangkang kompleks, pendekatan ini tetap memberi keuntungan performa yang berarti

[GN⁺]

Komentar di Lobste.rs

• SIMD tampak sulit karena proyek-proyek kompleks seperti simdutf atau simdjson, tetapi pola dasarnya—memproses loop biasa sebanyak N byte sekaligus—ternyata cukup sederhana
  Cukup replikasi konstanta ke tiap lane, inisialisasi akumulator vektor, lalu telusuri input selebar vektor sambil melakukan perbandingan/operasi, kemudian reduksi atau simpan hasilnya, dan proses elemen tersisa dengan loop skalar seperti biasa
  Dalam proyek nyata, loop dengan terminasi dini untuk mencari nilai 0xF ke bawah diubah dengan cara ini dan memperoleh peningkatan throughput 2–16 kali, tergantung hardware
  Compiler bisa melakukan auto-vectorization pada loop aritmetika yang sederhana dan teratur, tetapi tidak dapat secara andal menemukan transformasi yang menggabungkan terminasi dini, mask perbandingan, reduksi, dan pencarian lane pertama yang gagal. Detailnya ada di https://llvm.org/docs/Vectorizers.html
  Auto-vectorization sudah diteliti selama puluhan tahun, tetapi compiler nyata masih sering melewatkan peluang: https://arxiv.org/abs/2406.04693
  Setelah terbiasa dengan pola dasar ini, kita bisa menulisnya senatural loop skalar, jadi lebih banyak developer sebaiknya mempelajarinya dan bahasa pemrograman juga perlu menyediakan alat untuk itu. Tulisan yang diperluas ada di https://mitchellh.com/writing/everyone-should-know-simd
  • Saya penasaran apakah untuk memanfaatkan SIMD dengan benar diperlukan structure of arrays (SoA) alih-alih array of structures (AoS). Pada AoS, manfaatnya tampaknya akan hilang karena penyalinan tambahan dan masking; saya juga bertanya-tanya bagaimana menyusun satu antarmuka SIMD ketika instruksi yang didukung berbeda-beda di tiap CPU
    Saya ingin tahu apakah runtime harus menyediakan implementasi untuk semua instruksi pada arsitektur target sekaligus implementasi fallback untuk CPU tanpa dukungan SIMD, atau hanya menargetkan set instruksi tertentu
  • Saya sangat menyukai proyek riset terkait, Halide, dan berharap lebih banyak proyek memanfaatkannya
  • Saya penasaran sejauh mana riset auto-vectorization terbaru sudah diterapkan di compiler nyata
    Dulu, seingat saya, banyak yang berhenti sebagai proof of concept riset atau hanya masuk ke sebagian compiler Fortran, dan tidak diimplementasikan di compiler arus utama