충돌 검출에 SIMD를 붙이면 왜 복잡한 형상에서만 두 배 빨라질까

물리 엔진의 성능 최적화는 대개 '반복적으로 같은 계산을 얼마나 병렬로 몰아서 처리하느냐'의 싸움이다. Box2D의 저자가 3D 버전인 Box3D에서 충돌 검출 단계에 SIMD를 적용한 실험 결과를 공개했다. 핵심 메시지는 단순명료하다. 32개 정점을 가진 복잡한 볼록 형상(convex hull)을 다룰 때 SSE2 기반 SIMD가 스칼라 대비 전체 시뮬레이션 시간을 절반 이하로 줄였다는 것이다. 다만 이 이득이 모든 상황에 고르게 나타나지는 않는다는 점이 이 글의 실무적 핵심이다.

넓은 SIMD와 좁은 SIMD

저자는 SIMD 활용 방식을 두 갈래로 구분한다. 하나는 '좁은 SIMD(narrow SIMD)'로, xyz 3-벡터 하나를 SIMD 레지스터에 담고 일반적인 벡터 연산을 인트린식으로 표현하는 방식이다. 직관적이지만 이득이 뚜렷하지 않다. 다른 하나는 '넓은 SIMD(wide SIMD)'로, 서로 독립적인 여러 작업 단위를 한꺼번에 처리한다. 접촉 솔버에서는 네 개의 접촉점을 동시에 푸는 식이다. 저자가 이전 글에서 다룬 그래프 컬러링(graph coloring)으로 큰 성능 향상을 얻은 것도 이 넓은 SIMD 접근이었고, 같은 사고방식이 Box3D에도 그대로 이어진다. 넓은 SIMD가 제대로 작동하려면 데이터가 구조체 배열(AoS)이 아니라 배열 구조체(SoA) 형태로 정렬돼 있어야 한다는 전제가 붙는다.

SAT를 고른 이유와 그 대가

Box3D는 충돌 검출에 분리축 정리(Separating Axis Test, SAT)를 쓴다. 많은 물리 엔진이 거리 계산 알고리즘인 GJK와, 겹침 상황에서의 대체 알고리즘인 EPA를 조합해 쓰는 것과는 다른 선택이다. 저자가 SAT를 선호하는 이유는 충돌 여백(collision margin)이 필요 없다는 점이다. 형상이 서로 직접 맞닿아 쉴 수 있어 시각적 틈이 생기지 않는다. 반면 GJK/EPA 조합은 GJK가 유효한 영역에 머물기 위해 형상을 살짝 떨어뜨려 두는 경향이 있고, EPA 자체가 수치적으로 불안정해 실패 시 대체 알고리즘을, 그리고 그 대체의 대체까지 준비해야 하는 경우가 많다. EPA는 본질적으로 볼록 형상을 계산하는 알고리즘인데 입력이 납작한 조각(sliver)일 때 특히 취약하기 때문이다.

그러나 SAT에는 명확한 대가가 있다. 3D에서 SAT는 이차 복잡도를 가진다. 두 형상 A와 B가 있을 때 A의 면과 B의 정점, B의 면과 A의 정점, 그리고 A의 모서리와 B의 모서리를 모두 검사해야 한다. 앞의 두 검사는 관리할 만하지만, 모서리 대 모서리(edge-edge) 조합은 정점 수가 늘수록 이차적으로 폭증한다. 가우스 맵(Gauss Map)을 이용해 모서리 검사를 줄이는 기법이 있긴 하지만, 그래도 이 부분이 시뮬레이션 전체 비용을 압도하기 쉽다.

형상이 복잡해질수록 커지는 이득

바로 이 지점에서 SIMD가 힘을 발휘한다. 저자는 PEEL에서 이식한 convex pile 벤치마크를 사용했다. 32개 정점을 가진 볼록 형상 5120개를 떨어뜨리는 시나리오다. 이 형상은 모서리가 89개에 달해, 모서리 대 모서리 검사만 7921회 호출된다. 저자는 이를 '바위(boulder)'라 부른다. 넓은 SIMD를 적용하면 A의 모서리 하나를 B의 모서리 네 개와 동시에 검사할 수 있다. 결과적으로 AMD 7950X를 4.42GHz에 고정하고 500스텝, 1~8스레드로 측정했을 때 SSE2 버전이 스칼라 대비 두 배 이상 빨랐다. 이 수치는 모서리 검사만이 아니라 접촉 솔버까지 포함한 시뮬레이션 전체 시간이라는 점에서 의미가 크다.

반대로 모서리가 12개 정도밖에 없는 단순한 형상에서는 SIMD가 큰 이득이 되지 못한다. SoA 정렬 등 SIMD 준비 작업 자체의 비용이 상대적으로 커지기 때문이다. 실제로 저자는 박스 대 박스(box-box) 충돌에서는 SIMD 모서리 검사가 거의 효과가 없었다고 밝힌다. Box3D는 박스도 형상으로 취급하고 많은 벤치마크가 박스를 쓰는데, 이 경우 대부분의 비용이 애초에 좁은 위상(narrow phase)에 몰려 있지 않기 때문이다. 결국 이 최적화는 복잡한 형상에만 선택적으로 작동한다.

한계와 실무적 함의

Box3D는 현재 SSE2 인트린식만 구현하고 있다. Box2D에는 AVX2 구현이 있지만 AVX2를 지원하지 않는 CPU를 쓰는 사용자가 의외로 많았다는 것이 저자의 경험이다. 다만 아키텍처만 AVX2로 켜도 'AVX2-Lite'라 표기된 무료에 가까운 성능 향상이 나왔고, 향후 모서리 8개를 동시에 검사하는 본격 AVX2 구현도 검토 대상이다. 또한 Box3D에는 모서리 128개라는 하드 리밋이 존재하는데, 이는 SIMD 때문이 아니라 8비트 인덱스와 반쪽 모서리(half-edge) 두 개로 형상 저장을 촘촘하게 유지하기 위한 기존 제약이다. 정점 수가 그 이상으로 늘면 복잡한 형상을 메시로 변환해 이차 증가 문제를 피할 수 있지만, 그러면 동적 물체로서의 적합성이 떨어진다.

정리하면, 충돌 검출에 SIMD를 붙일지 말지는 다루는 형상의 성격에 달려 있다. 파괴(destruction) 시뮬레이션처럼 정점이 많은 복잡한 볼록 형상이 등장하는 시나리오라면 두 배 이상의 이득을 기대할 수 있지만, 박스나 단순 형상이 대부분인 게임에서는 준비 비용만 늘 뿐 체감이 거의 없다. 물리 엔진을 통합하거나 성능을 튜닝하는 실무자라면, SIMD 도입 여부를 일괄로 결정하기보다 자신의 콘텐츠가 실제로 만들어내는 형상 분포를 먼저 프로파일링하는 것이 옳은 순서다.