Acelerando a detecção de colisão com SIMD

• O Box3D aplicou SIMD wide a testes complexos de colisão entre cascas convexas 3D, reduzindo para menos da metade o tempo total de simulação de 5.120 objetos com 32 vértices e 89 arestas
• O teorema do eixo separador (SAT) em 3D verifica combinações face-vértice e aresta-aresta entre duas cascas, e no caso Boulder-Boulder o número de combinações de arestas chega a 7.921, fazendo com que o custo do loop duplo possa dominar a simulação
• Ao agrupar 4 arestas de hullB no formato SoA e testá-las ao mesmo tempo contra uma aresta de hullA, o tempo de execução com 1 thread e 500 passos caiu de 40.706ms em Scalar para SSE2 17.337ms e AVX2-Lite 15.762ms
• Mesmo com 8 threads, os resultados foram Scalar 5.292ms, SSE2 2.410ms e AVX2-Lite 2.277ms; essas medições incluem a simulação completa, com testes de aresta e o solver de contato
• Em colisões Box-Box, com apenas 12 arestas, o efeito é quase nulo por causa do custo de preparação, mas em cascas complexas usadas em efeitos de destruição a técnica é útil, e ainda há espaço para no futuro testar 8 arestas de uma vez com AVX2

---

Custo computacional do SAT e como o SIMD foi aplicado

• O SIMD wide do Box3D, ao contrário do SIMD narrow que coloca um único vetor xyz em um registrador SIMD, processa várias unidades de trabalho ao mesmo tempo
  • No solver de contato, ele resolve 4 pontos de contato de uma vez
  • O SIMD narrow também pode ser útil, mas o ganho de desempenho não é tão evidente quanto com o SIMD wide
• O benchmark Convex Pile, portado do PEEL, derruba 5.120 cascas convexas com 32 vértices cada
  • Box é composto por 8 vértices, 6 faces e 12 arestas
  • Boulder é composto por 32 vértices, 59 faces e 89 arestas
  • O Box3D também trata Box como uma casca, e em benchmarks focados em Box a narrow phase normalmente não era o principal custo
• A detecção de colisão usa o teorema do eixo separador (SAT)
  • Com SAT, obtém-se a melhor feature separadora entre os objetos e a distância de deslocamento necessária, além de calcular a normal e os pontos de contato
  • Outros motores de física às vezes combinam GJK com EPA para tratar sobreposição
• O SAT não precisa de margem de colisão, então permite posicionar os objetos em contato direto
  • A combinação de GJK e EPA às vezes afasta um pouco os objetos para manter mais tempo a região mais rápida do GJK, o que pode criar frestas visuais
  • O EPA pode ser numericamente frágil e, como também exige calcular cascas convexas a partir de entradas planas e finas, às vezes requer um segundo caminho alternativo para lidar com falhas
• O SAT 3D testa, para duas cascas A e B, face de A-vértice de B, face de B-vértice de A e aresta de A-aresta de B, apresentando complexidade quadrática
  • Box-Box tem 6 combinações face-vértice, 6 vértice-face e 144 aresta-aresta
  • Boulder-Boulder tem respectivamente 59, 59 e 7.921 combinações
  • É possível reduzir os testes de aresta com o Gauss Map, mas a verificação aresta-aresta ainda pode dominar a simulação inteira
  • Técnicas relacionadas podem ser vistas em Improvements to the Separating Axis Test
• Para o SIMD funcionar de forma eficiente, é preciso preparar os dados em estrutura de arrays (SoA), então em cascas com apenas 12 arestas o ganho não compensa muito o custo de preparação
  • Ao comparar 89 arestas de cada lado, TestCrossProduct é chamado 7.921 vezes
  • A implementação com SIMD wide testa uma aresta de hullA ao mesmo tempo contra EdgeWide, que contém 4 arestas de hullB

Resultados de benchmark e escopo de aplicação

• O AMD 7950X foi fixado em 4,42GHz e executou 500 passos com 1 a 8 threads; cada valor corresponde ao melhor resultado entre 4 execuções

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

• O SSE2 é mais de 2 vezes mais rápido que o Scalar, e as medições incluem não só os testes aresta-aresta, mas a simulação completa
  • Na coluna Scalar, o solver de contato também roda em modo Scalar
• O Box3D implementa intrínsecos SIMD próprios apenas para SSE2, mas só ativar a arquitetura AVX2 já traz ganho adicional de desempenho com AVX2-Lite
  • O Box2D também tem intrínsecos AVX2, mas havia mais usuários do que o esperado usando CPUs sem suporte a AVX2
  • No futuro, uma implementação AVX2 real poderá testar 8 arestas ao mesmo tempo
• Para manter o uso de memória pequeno, o Box3D limita cada casca a no máximo 128 arestas
  • A limitação vem do formato de armazenamento com índices de 8 bits e dois half-edges por aresta
  • Converter cascas complexas em malhas pode resolver o problema do crescimento quadrático, mas isso as torna menos adequadas para objetos dinâmicos
• Em colisões Box-Box, o efeito do teste de arestas com SIMD é quase inexistente
  • Já em cenários de destruição que usam cascas complexas, o ganho de desempenho é suficiente

[GN⁺]

Comentários no Lobste.rs

• SIMD parece difícil por causa de projetos complexos como simdutf ou simdjson, mas o padrão básico de processar um loop comum N bytes por vez é surpreendentemente simples
  Basta replicar constantes em cada lane, inicializar um acumulador vetorial, percorrer a entrada na largura do vetor fazendo comparações e operações, reduzir ou armazenar o resultado e então processar os elementos restantes com o loop escalar tradicional
  Em um projeto real, ao transformar dessa forma um loop com encerramento antecipado que procurava valores menores ou iguais a 0xF, foi obtido um aumento de throughput de 2 a 16 vezes, dependendo do hardware
  O compilador consegue vetorizar automaticamente loops aritméticos simples e regulares, mas não detecta de forma confiável transformações que combinam encerramento antecipado, máscaras de comparação, redução e busca da primeira lane com falha. Mais detalhes em https://llvm.org/docs/Vectorizers.html
  A vetorização automática vem sendo pesquisada há décadas, mas compiladores reais ainda perdem oportunidades com frequência: https://arxiv.org/abs/2406.04693
  Depois que você se acostuma com o padrão básico, dá para escrever de forma tão natural quanto um loop escalar; por isso, mais desenvolvedores deveriam aprendê-lo, e as linguagens também deveriam oferecer ferramentas para isso. O texto ampliado está em https://mitchellh.com/writing/everyone-should-know-simd
  • Fica a dúvida se, para aproveitar bem SIMD, é necessário usar estrutura de arrays (SoA) em vez de array de estruturas (AoS). Com AoS, cópias e mascaramentos extras parecem anular os ganhos, e também fica a questão de como criar uma interface SIMD única em um cenário em que cada CPU oferece instruções diferentes
    Gostaria de saber se o runtime precisa fornecer implementações para todas as instruções da arquitetura-alvo junto com uma alternativa para CPUs sem suporte a SIMD, ou se mira apenas em um conjunto específico de instruções
  • Gosto especialmente do projeto de pesquisa relacionado Halide e espero que ele seja usado em mais projetos
  • Tenho curiosidade sobre quanto das pesquisas recentes em vetorização automática chegou de fato aos compiladores
    Lembro que, no passado, muitas vezes elas ficavam restritas a provas de conceito acadêmicas ou entravam apenas em alguns compiladores Fortran, sem serem implementadas nos compiladores mainstream