เร่งความเร็วการตรวจจับการชนด้วย SIMD

 (box2d.org)
1 คะแนน โดย GN⁺ 4 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Box3D นำ wide SIMD มาใช้กับการตรวจสอบการชนของเปลือกนูน 3D ที่ซับซ้อน ทำให้เวลาจำลองรวมของวัตถุ 5,120 ชิ้นที่มี 32 จุดและ 89 ขอบ ลดลงเหลือน้อยกว่าครึ่ง
  • Separating Axis Theorem (SAT) แบบ 3D จะตรวจสอบชุดผสมระหว่างหน้า-จุดยอดและขอบ-ขอบของเปลือกสองชิ้น โดยในกรณี Boulder-Boulder มีชุดขอบรวมกันถึง 7,921 ชุด จนต้นทุนของลูปซ้อนอาจกลายเป็นภาระหลักของการจำลอง
  • เมื่อรวมขอบ 4 เส้นของ hullB ในรูปแบบ SoA แล้วตรวจพร้อมกันกับขอบ 1 เส้นของ hullA เวลารันแบบ 1 เธรด 500 สเต็ปลดลงจาก Scalar 40,706ms เหลือ SSE2 17,337ms และ AVX2-Lite 15,762ms
  • ที่ 8 เธรดก็วัดได้ Scalar 5,292ms, SSE2 2,410ms และ AVX2-Lite 2,277ms โดยตัวเลขนี้เป็นค่าของ การจำลองทั้งหมด ที่รวมทั้งการตรวจขอบและ contact solver
  • การชนแบบ Box-Box ที่มีขอบเพียง 12 เส้นแทบไม่ได้ประโยชน์เพราะมีต้นทุนการตั้งค่า แต่สำหรับ เปลือกที่ซับซ้อน ที่ใช้ในเอฟเฟกต์การทำลาย ฯลฯ ถือว่ามีประโยชน์ และในอนาคตยังอาจตรวจขอบพร้อมกัน 8 เส้นด้วย AVX2 ได้

ต้นทุนการคำนวณของ SAT และวิธีใช้ SIMD

  • wide SIMD ของ Box3D ต่างจาก narrow SIMD ที่ใส่เวกเตอร์ xyz เดียวลงในรีจิสเตอร์ SIMD เพราะมันประมวลผลงานหลายหน่วยพร้อมกัน
    • ใน contact solver จะจัดการจุดสัมผัส 4 จุดพร้อมกัน
    • narrow SIMD ก็อาจมีประโยชน์ แต่การเพิ่มประสิทธิภาพไม่ชัดเจนเท่า wide SIMD
  • เบนช์มาร์ก Convex Pile ที่พอร์ตมาจาก PEEL ปล่อยเปลือกนูนจำนวน 5,120 ชิ้น ที่แต่ละชิ้นมี 32 จุดลงมา
    • Box ประกอบด้วยจุดยอด 8 จุด, 6 หน้า, 12 ขอบ
    • Boulder ประกอบด้วยจุดยอด 32 จุด, 59 หน้า, 89 ขอบ
    • Box3D จัดการ Box เป็นเปลือกเช่นกัน และในเบนช์มาร์กที่เน้น Box โดยทั่วไป narrow phase ไม่ใช่ต้นทุนหลัก
  • ใช้ Separating Axis Theorem (SAT) สำหรับการตรวจจับการชน
    • SAT ใช้หา feature ที่เหมาะที่สุดในการแยกวัตถุและระยะเคลื่อนที่ที่ต้องใช้ รวมถึงคำนวณ normal และจุดสัมผัส
    • เอนจินฟิสิกส์อื่นบางตัวอาจใช้ GJK ร่วมกับ EPA สำหรับจัดการกรณีซ้อนทับ
  • SAT ไม่ต้องการช่องว่างเผื่อการชน จึงสามารถวาง ให้วัตถุสัมผัสกันโดยตรง ได้
    • การใช้ GJK ร่วมกับ EPA บางครั้งจะเว้นวัตถุให้ห่างกันเล็กน้อยเพื่อคงพื้นที่ที่ GJK ทำงานได้เร็วกว่า จึงอาจเกิดช่องว่างที่มองเห็นได้
    • EPA อาจเปราะบางในเชิงตัวเลข และเพราะต้องคำนวณเปลือกนูนจากอินพุตที่แบนและบาง จึงบางครั้งต้องมีเส้นทางสำรองชุดที่สองไว้รองรับความล้มเหลว
  • SAT แบบ 3D จะตรวจสอบหน้า A-จุดยอด B, หน้า B-จุดยอด A และขอบ A-ขอบ B ของเปลือก A และ B ทำให้มี ความซับซ้อนกำลังสอง
    • Box-Box มีชุดหน้า-จุดยอด 6 ชุด, จุดยอด-หน้า 6 ชุด และขอบ-ขอบ 144 ชุด
    • Boulder-Boulder มีอย่างละ 59, 59 และ 7,921 ชุด
    • แม้จะลดการตรวจขอบได้ด้วย Gauss Map แต่การตรวจขอบ-ขอบก็ยังอาจครองเวลาของการจำลองทั้งหมด
    • ดูเทคนิคที่เกี่ยวข้องได้ใน Improvements to the Separating Axis Test
  • เพื่อให้ SIMD ทำงานได้อย่างมีประสิทธิภาพ จำเป็นต้องเตรียมข้อมูลในรูปแบบ Structure of Arrays (SoA) ดังนั้นกับเปลือกที่มีขอบเพียง 12 เส้น ผลประโยชน์จึงไม่มากเมื่อเทียบกับต้นทุนการตั้งค่า
    • เมื่อเปรียบเทียบขอบชิ้นละ 89 เส้น TestCrossProduct จะถูกเรียก 7,921 ครั้ง
    • การทำ wide SIMD จะตรวจขอบ 1 เส้นของ hullA พร้อมกันกับ EdgeWide ที่บรรจุขอบ 4 เส้นของ hullB

ผลเบนช์มาร์กและขอบเขตการใช้งาน

  • ใช้ AMD 7950X ที่ล็อกไว้ที่ 4.42GHz รัน 500 สเต็ปบน 1~8 เธรด และทุกค่าคือ ผลดีที่สุดจากการรัน 4 ครั้ง
เธรด 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 มากกว่า 2 เท่า และค่าที่วัดได้รวมทั้งการตรวจขอบ-ขอบและการจำลองทั้งหมด ไม่ได้มีแค่ส่วนตรวจจับการชน
    • ในคอลัมน์ Scalar นั้น contact solver ก็ทำงานในโหมด Scalar ด้วย
  • แม้ SIMD intrinsics ที่ Box3D ลงมือเขียนเองจะมีแค่ SSE2 แต่เพียง เปิดใช้สถาปัตยกรรม AVX2 ก็ยังได้ประสิทธิภาพเพิ่มขึ้นของ AVX2-Lite
    • ใน Box2D มี AVX2 intrinsics ด้วย แต่มีผู้ใช้ CPU ที่ไม่รองรับ AVX2 มากกว่าที่คาดไว้
    • ในอนาคตอาจมีการทำ AVX2 จริงเพื่อให้ตรวจขอบพร้อมกันได้ 8 เส้น
  • Box3D จำกัดจำนวนขอบต่อเปลือกไว้สูงสุด 128 เส้น เพื่อให้ขนาดพื้นที่เก็บข้อมูลยังเล็ก
    • ข้อจำกัดนี้มาจากรูปแบบการเก็บข้อมูลที่ใช้อินเด็กซ์ 8 บิตและ half-edge สองตัวต่อหนึ่งขอบ
    • การแปลงเปลือกที่ซับซ้อนเป็น mesh ช่วยแก้ปัญหาการเพิ่มขึ้นแบบกำลังสองได้ แต่จะเหมาะกับวัตถุไดนามิกน้อยลง
  • สำหรับการชนแบบ Box-Box ผลของการตรวจขอบด้วย SIMD แทบไม่มี
    • แต่ใน สถานการณ์การทำลาย เป็นต้นที่ใช้เปลือกซับซ้อน ก็ให้ประโยชน์ด้านประสิทธิภาพได้มากพอ

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 4 시간 전
ความคิดเห็นบน Lobste.rs
  • SIMD อาจดูยากเพราะโปรเจกต์ซับซ้อนอย่าง simdutf หรือ simdjson แต่แพตเทิร์นพื้นฐานของการประมวลผลลูปธรรมดาทีละ N ไบต์นั้นเรียบง่ายกว่าที่คิด
    เพียงทำซ้ำค่าคงที่ลงในแต่ละเลน เริ่มต้นตัวสะสมแบบเวกเตอร์ จากนั้นวนผ่านอินพุตตามความกว้างของเวกเตอร์เพื่อเปรียบเทียบและคำนวณ ยุบรวมหรือบันทึกผลลัพธ์ แล้วจัดการองค์ประกอบที่เหลือด้วยลูปสเกลาร์แบบเดิม
    ในโปรเจกต์จริง ได้เปลี่ยนลูปแบบหยุดก่อนเมื่อพบค่าที่ไม่เกิน 0xF ด้วยวิธีนี้ และได้ throughput เพิ่มขึ้น 2–16 เท่า ขึ้นอยู่กับฮาร์ดแวร์
    คอมไพเลอร์สามารถทำ auto-vectorization ให้ลูปคำนวณที่เรียบง่ายและเป็นระเบียบได้ แต่การแปลงที่รวมการหยุดก่อน, comparison mask, reduction และการค้นหาเลนแรกที่ล้มเหลว ยังตรวจจับได้ไม่เสถียร รายละเอียดอยู่ที่ https://llvm.org/docs/Vectorizers.html
    แม้ auto-vectorization จะถูกวิจัยมาหลายสิบปีแล้ว แต่คอมไพเลอร์จริงก็ยังพลาดโอกาสบ่อยครั้ง: https://arxiv.org/abs/2406.04693
    เมื่อคุ้นเคยกับแพตเทิร์นพื้นฐานแล้ว ก็สามารถเขียนได้เป็นธรรมชาติพอ ๆ กับลูปสเกลาร์ ดังนั้นนักพัฒนาควรเรียนรู้มากขึ้น และภาษาก็ควรมีเครื่องมือรองรับสิ่งนี้ บทความขยายอยู่ที่ https://mitchellh.com/writing/everyone-should-know-simd
    • สงสัยว่าหากจะใช้ SIMD ให้ได้เต็มที่ จำเป็นต้องใช้ โครงสร้างแบบอาร์เรย์ (SoA) มากกว่า อาร์เรย์ของโครงสร้าง (AoS) หรือไม่ เพราะ AoS น่าจะทำให้ข้อดีหายไปจากการคัดลอกและการทำ masking เพิ่มเติม และยังสงสัยว่าจะออกแบบอินเทอร์เฟซ SIMD เดียวอย่างไร ในสถานการณ์ที่ CPU แต่ละรุ่นรองรับคำสั่งต่างกัน
      อยากรู้ว่า runtime ต้องมีทั้ง implementation สำหรับคำสั่งทุกแบบของสถาปัตยกรรมเป้าหมายและ implementation สำรองสำหรับ CPU ที่ไม่รองรับ SIMD หรือไม่ หรือว่าจะเลือกเจาะจงแค่ instruction set บางชุด
    • ชอบโปรเจกต์วิจัยที่เกี่ยวข้องอย่าง Halide เป็นพิเศษ และหวังว่าจะมีโปรเจกต์นำไปใช้มากขึ้น
    • สงสัยว่างานวิจัย auto-vectorization ล่าสุดถูกนำไป deploy ในคอมไพเลอร์จริงมากแค่ไหน
      จำได้ว่าในอดีตมักจบแค่ proof of concept สำหรับงานวิจัย หรือเข้าไปอยู่ในคอมไพเลอร์ Fortran บางตัวเท่านั้น และหลายครั้งไม่ได้ถูก implement ในคอมไพเลอร์กระแสหลัก