- Box3D áp dụng wide SIMD cho kiểm tra va chạm của các bao lồi 3D phức tạp, giúp giảm tổng thời gian mô phỏng của 5.120 vật thể có 32 điểm và 89 cạnh xuống còn chưa tới một nửa
- Định lý trục phân tách (SAT) trong 3D kiểm tra các tổ hợp mặt-đỉnh và cạnh-cạnh của hai bao; với Boulder-Boulder, số tổ hợp cạnh lên tới 7.921, khiến chi phí vòng lặp lồng nhau có thể chi phối mô phỏng
- Khi gom 4 cạnh của hullB theo dạng SoA để kiểm tra đồng thời với một cạnh của hullA, thời gian chạy 1 luồng·500 bước giảm từ Scalar 40.706ms xuống SSE2 17.337ms, AVX2-Lite 15.762ms
- Ngay cả với 8 luồng, kết quả lần lượt là Scalar 5.292ms, SSE2 2.410ms, AVX2-Lite 2.277ms; đây là số đo của toàn bộ mô phỏng, bao gồm cả kiểm tra cạnh và contact solver
- Va chạm Box-Box chỉ có 12 cạnh nên hầu như không hiệu quả do chi phí thiết lập, nhưng hữu ích với các bao phức tạp dùng trong hiệu ứng phá hủy, và về sau vẫn có khả năng kiểm tra đồng thời 8 cạnh bằng AVX2
Chi phí tính toán của SAT và cách áp dụng SIMD
- Wide SIMD của Box3D, khác với narrow SIMD vốn đưa một vector xyz vào thanh ghi SIMD, xử lý đồng thời nhiều đơn vị công việc
- Trong contact solver, nó giải 4 điểm tiếp xúc cùng lúc
- Narrow SIMD cũng có thể hữu ích, nhưng mức tăng hiệu năng không rõ rệt bằng wide SIMD
- Benchmark Convex Pile được chuyển từ PEEL thả 5.120 bao lồi, mỗi bao có 32 điểm
- Box gồm 8 đỉnh, 6 mặt, 12 cạnh
- Boulder gồm 32 đỉnh, 59 mặt, 89 cạnh
- Box3D cũng xử lý Box như một bao, và trong các benchmark tập trung vào Box, narrow phase thường không phải là chi phí chính
- Phát hiện va chạm sử dụng định lý trục phân tách (SAT)
- SAT không cần khoảng hở va chạm, nên có thể đặt các vật thể tiếp xúc trực tiếp với nhau
- Tổ hợp GJK và EPA đôi khi đặt vật thể cách nhau một chút để duy trì vùng GJK nhanh hơn, có thể tạo ra khe hở thị giác
- EPA có thể yếu về mặt số học, và vì phải tính bao lồi từ đầu vào phẳng, mỏng, đôi khi cần một đường dự phòng thứ hai phòng khi thất bại
- SAT 3D kiểm tra mặt của A-đỉnh của B, mặt của B-đỉnh của A, cạnh của A-cạnh của B cho hai bao A và B, thể hiện độ phức tạp bậc hai
- Box-Box có 6 tổ hợp mặt-đỉnh, 6 tổ hợp đỉnh-mặt, 144 tổ hợp cạnh-cạnh
- Boulder-Boulder có lần lượt 59, 59, 7.921 tổ hợp
- Có thể giảm kiểm tra cạnh bằng Gauss Map, nhưng kiểm tra cạnh-cạnh vẫn có thể chi phối toàn bộ mô phỏng
- Có thể xem kỹ thuật liên quan tại Improvements to the Separating Axis Test
- Để SIMD hoạt động hiệu quả, dữ liệu phải được chuẩn bị theo cấu trúc mảng (SoA), nên với bao chỉ có 12 cạnh, lợi ích so với chi phí thiết lập không lớn
- Khi so sánh các bao có 89 cạnh,
TestCrossProductđược gọi 7.921 lần - Bản triển khai wide SIMD kiểm tra đồng thời một cạnh của hullA với
EdgeWidechứa 4 cạnh của hullB
- Khi so sánh các bao có 89 cạnh,
Kết quả benchmark và phạm vi áp dụng
- AMD 7950X được cố định ở 4,42GHz và chạy 500 bước trên 1~8 luồng; mỗi con số là kết quả tốt nhất trong 4 lần chạy
| Luồng | 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 nhanh hơn Scalar hơn 2 lần, và số đo bao gồm toàn bộ mô phỏng, không chỉ kiểm tra cạnh-cạnh
- Ở cột Scalar, contact solver cũng chạy ở chế độ Scalar
- Các hàm intrinsic SIMD do Box3D tự triển khai chỉ có SSE2, nhưng chỉ cần kích hoạt kiến trúc AVX2 cũng đem lại mức tăng hiệu năng bổ sung của AVX2-Lite
- Box2D cũng có intrinsic AVX2, nhưng số người dùng dùng CPU không hỗ trợ AVX2 nhiều hơn dự kiến
- Trong tương lai, bản triển khai AVX2 thực sự có thể kiểm tra đồng thời 8 cạnh
- Box3D giới hạn số cạnh tối đa 128 trên mỗi bao để giữ dung lượng lưu trữ nhỏ
- Đây là giới hạn xuất phát từ cách lưu trữ dùng chỉ mục 8-bit và hai half-edge cho mỗi cạnh
- Chuyển các bao phức tạp thành mesh có thể giải quyết vấn đề tăng trưởng bậc hai, nhưng kém phù hợp hơn với vật thể động
- Trong va chạm Box-Box, kiểm tra cạnh bằng SIMD hầu như không có tác dụng
- Trong các kịch bản phá hủy dùng bao phức tạp, nó mang lại lợi ích hiệu năng đủ lớn
1 bình luận
Ý kiến trên Lobste.rs
Chỉ cần sao chép hằng số vào từng lane, khởi tạo bộ tích lũy vector, duyệt đầu vào theo bề rộng vector để so sánh và tính toán, rồi rút gọn hoặc lưu kết quả, sau đó xử lý các phần tử còn lại bằng vòng lặp vô hướng hiện có
Trong một dự án thực tế, tôi đã chuyển một vòng lặp thoát sớm tìm giá trị nhỏ hơn hoặc bằng
0xFsang cách này và đạt được mức cải thiện thông lượng 2~16 lần tùy phần cứngTrình biên dịch có thể tự động vector hóa các vòng lặp số học đơn giản và đều đặn, nhưng thường không ổn định trong việc nhận ra các phép biến đổi kết hợp thoát sớm, mặt nạ so sánh, rút gọn và tìm lane lỗi đầu tiên. Chi tiết tại https://llvm.org/docs/Vectorizers.html
Dù tự động vector hóa đã được nghiên cứu suốt hàng chục năm, các trình biên dịch thực tế vẫn thường xuyên bỏ lỡ cơ hội: https://arxiv.org/abs/2406.04693
Khi đã quen với mẫu cơ bản này thì có thể viết nó tự nhiên gần như vòng lặp vô hướng, nên sẽ tốt hơn nếu nhiều lập trình viên học nó và các ngôn ngữ cũng cung cấp công cụ cho việc này. Bài viết mở rộng ở https://mitchellh.com/writing/everyone-should-know-simd
Tôi muốn biết liệu runtime có phải cung cấp đồng thời các triển khai cho mọi tập lệnh của kiến trúc đích cùng một triển khai thay thế cho CPU không hỗ trợ SIMD hay không, hay chỉ nhắm tới một tập lệnh cụ thể
Tôi nhớ trước đây nhiều trường hợp chỉ dừng ở mức proof-of-concept cho nghiên cứu hoặc chỉ xuất hiện trong một số trình biên dịch Fortran, chứ không được triển khai trong các trình biên dịch chủ đạo