SIMD ile çarpışma algılamayı hızlandırmak

• Box3D, karmaşık 3D dışbükey zarf çarpışma testlerine wide SIMD uygulayarak, 32 nokta ve 89 kenara sahip 5.120 nesnenin toplam simülasyon süresini yarıdan aza indirdi
• 3D ayıran eksen teoremi (SAT) iki zarfın yüz-düğüm ve kenar-kenar kombinasyonlarını test eder; Boulder-Boulder’da kenar kombinasyonları 7.921’e ulaştığı için iç içe döngü maliyeti simülasyona hâkim olabilir
• hullB’nin 4 kenarı SoA biçiminde gruplanıp hullA’nın bir kenarıyla eşzamanlı test edildiğinde, 1 iş parçacığı ve 500 adımlık çalışma süresi Scalar 40.706ms’den SSE2 17.337ms ve AVX2-Lite 15.762ms’ye düştü
• 8 iş parçacığında da Scalar 5.292ms, SSE2 2.410ms, AVX2-Lite 2.277ms ölçüldü; bunlar hem kenar testlerini hem de temas çözücüyü içeren toplam simülasyon ölçümleri
• Yalnızca 12 kenarlı Box-Box çarpışmalarında kurulum maliyeti nedeniyle etkisi çok sınırlı, ancak yıkım efektleri gibi alanlarda kullanılan karmaşık zarflar için yararlı; gelecekte AVX2 ile 8 kenarı aynı anda test etme olanağı da var

---

SAT’nin hesaplama maliyeti ve SIMD uygulama yöntemi

• Box3D’nin wide SIMD yaklaşımı, tek bir xyz vektörünü SIMD yazmacına koyan narrow SIMD’den farklı olarak birden fazla iş birimini aynı anda işler
  • Temas çözücüde 4 temas noktası tek seferde çözülür
  • Narrow SIMD de yararlı olabilir, ancak performans artışı wide SIMD kadar belirgin değildir
• PEEL’den taşınan Convex Pile benchmark’ı, her biri 32 noktaya sahip 5.120 dışbükey zarfı düşürür
  • Box; 8 tepe noktası, 6 yüz ve 12 kenardan oluşur
  • Boulder; 32 tepe noktası, 59 yüz ve 89 kenardan oluşur
  • Box3D, Box’ları da zarf olarak işler; Box merkezli benchmark’larda narrow phase genelde ana maliyet değildi
• Çarpışma algılamada ayıran eksen teoremi (SAT) kullanılır
  • SAT ile nesneleri ayıracak en iyi özellik ve gerekli hareket mesafesi bulunur; temas normali ve temas noktaları da hesaplanır
  • Diğer fizik motorları GJK ile örtüşme işleme için EPA kombinasyonunu da kullanabilir
• SAT, çarpışma payı gerektirmediği için nesnelerin doğrudan birbirine temas edecek şekilde yerleştirilmesine olanak tanır
  • GJK ve EPA kombinasyonu, daha hızlı GJK bölgesini korumak için nesneleri biraz ayırabildiğinden görsel boşluklar oluşabilir
  • EPA sayısal açıdan kırılgan olabilir; ayrıca düz ve ince girdilerle dışbükey zarf hesaplamak gerektiğinden, başarısızlığa karşı ikinci bir yedek yol gerekebilir
• 3D SAT, iki zarf A ve B için A’nın yüzü-B’nin tepe noktası, B’nin yüzü-A’nın tepe noktası ve A’nın kenarı-B’nin kenarı testlerini yapar; ikinci dereceden karmaşıklık gösterir
  • Box-Box’ta 6 yüz-tepe noktası, 6 tepe noktası-yüz ve 144 kenar-kenar kombinasyonu vardır
  • Boulder-Boulder’da bunlar sırasıyla 59, 59 ve 7.921 kombinasyondur
  • Gauss Map ile kenar testleri azaltılabilir, ancak kenar-kenar testleri toplam simülasyona hâkim olabilir
  • İlgili tekniklere Improvements to the Separating Axis Test üzerinden bakılabilir
• SIMD’nin verimli çalışması için verilerin dizi yapısı (SoA) olarak hazırlanması gerekir; bu yüzden 12 kenarlı zarflarda kurulum maliyetine kıyasla kazanç büyük değildir
  • 89 kenarın 89 kenarla karşılaştırılmasında TestCrossProduct 7.921 kez çağrılır
  • Wide SIMD uygulaması, hullA’nın tek bir kenarını hullB’nin 4 kenarını içeren EdgeWide ile eşzamanlı test eder

Benchmark sonuçları ve uygulama kapsamı

• AMD 7950X 4,42GHz’e sabitlenerek 1–8 iş parçacığında 500 adım çalıştırıldı; her değer 4 çalıştırma içindeki en iyi sonuçtur

İş parçacığı	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’dan 2 kattan fazla hızlıdır; ölçümlere yalnızca kenar-kenar testi değil, toplam simülasyon da dahildir
  • Scalar sütununda temas çözücü de Scalar modunda çalışır
• Box3D’nin doğrudan uyguladığı SIMD intrinsic’leri yalnızca SSE2 olsa da, yalnızca AVX2 mimarisini etkinleştirmek AVX2-Lite tarafında ek performans artışı sağlar
  • Box2D’de AVX2 intrinsic’leri de var, ancak AVX2 desteklemeyen CPU kullananların sayısı beklenenden fazlaydı
  • Gelecekte gerçek bir AVX2 uygulamasıyla 8 kenar aynı anda test edilebilir
• Box3D, depolama alanını küçük tutmak için zarf başına kenar sayısını en fazla 128 ile sınırlar
  • Bu sınır, 8 bit indeksler ve kenar başına iki half-edge kullanan depolama yönteminden kaynaklanır
  • Karmaşık zarfları mesh’e dönüştürmek ikinci dereceden artış sorununu çözebilir, ancak dinamik nesneler için daha az uygun hâle gelir
• Box-Box çarpışmalarında SIMD kenar testlerinin etkisi çok azdır
  • Karmaşık zarfların kullanıldığı yıkım senaryoları gibi durumlarda yeterli performans kazancı sağlar

[GN⁺]

Lobste.rs yorumları

• SIMD, simdutf veya simdjson gibi karmaşık projeler yüzünden zor görünebilir; ancak sıradan bir döngüyü tek seferde N bayt işleyecek şekilde kuran temel desen şaşırtıcı derecede basittir
  Sabitleri her lane’e kopyalayıp vektör akümülatörlerini başlattıktan sonra, girdiyi vektör genişliği kadar adımlarla dolaşıp karşılaştırma/işlem yapar, sonucu indirger veya saklar, ardından kalan öğeleri mevcut skaler döngüyle işlersiniz
  Gerçek bir projede 0xF ve altındaki değerleri bulan erken çıkışlı bir döngüyü bu yöntemle değiştirerek donanıma bağlı olarak 2 ila 16 kat verim artışı elde ettik
  Derleyici basit ve düzenli aritmetik döngüleri otomatik olarak vektörleştirebilir; ancak erken çıkış, karşılaştırma maskesi, indirgeme ve ilk başarısız lane’i bulmanın birleştiği dönüşümleri güvenilir biçimde yakalayamaz. Ayrıntılar https://llvm.org/docs/Vectorizers.html adresinde
  Otomatik vektörleştirme onlarca yıldır araştırılıyor olsa da gerçek derleyiciler hâlâ fırsatları sık sık kaçırıyor: https://arxiv.org/abs/2406.04693
  Temel desene alışınca skaler döngüler kadar doğal yazılabildiği için daha fazla geliştiricinin bunu öğrenmesi ve dillerin de buna yönelik araçlar sunması gerekiyor. Genişletilmiş yazı https://mitchellh.com/writing/everyone-should-know-simd adresinde
  • SIMD’den düzgün yararlanmak için yapı dizisi (AoS) yerine dizi yapısı (SoA) gerekip gerekmediğini merak ediyorum. AoS’de ek kopyalama ve maskeleme yüzünden avantaj ortadan kalkacak gibi; ayrıca her CPU’nun farklı komutları desteklediği bir ortamda tek bir SIMD arayüzünün nasıl tasarlanacağı da soru işareti
    Çalışma zamanının hedef mimarinin tüm komutlarına özel uygulamaları ve SIMD desteklemeyen CPU’lar için yedek uygulamayı birlikte mi sağlaması gerektiğini, yoksa yalnızca belirli bir komut kümesini mi hedeflediğini bilmek isterim
  • İlgili araştırma projesi Halide’ı özellikle seviyorum ve daha fazla projede kullanılmasını umuyorum
  • Son dönemdeki otomatik vektörleştirme araştırmalarının gerçek derleyicilere ne kadar dağıtıldığını merak ediyorum
    Eskiden bunların çoğu zaman araştırma amaçlı kavram kanıtı olarak kaldığını ya da yalnızca bazı Fortran derleyicilerine girdiğini, ana akım derleyicilerde uygulanmadığını hatırlıyorum