เหนือกว่า NumPy matrix multiplication ด้วยโค้ด C 150 บรรทัด

 (salykova.github.io)
1 คะแนน โดย GN⁺ 2024-07-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

สรุป

บทนำ

  • matrix multiplication เป็นองค์ประกอบสำคัญของโครงข่ายประสาทสมัยใหม่
  • NumPy ทำประสิทธิภาพสูงได้ด้วยการใช้ไลบรารี BLAS ภายนอก
  • บทความนี้อธิบายวิธีสร้าง matrix multiplication ประสิทธิภาพสูงที่เรียบง่าย พกพาได้ และขยายต่อได้

ประสิทธิภาพของ NumPy

  • NumPy ใช้ OpenBLAS บน CPU ของ AMD
  • วัดประสิทธิภาพเป็น FLOP/s
  • วัดประสิทธิภาพของ NumPy แบบ single-thread และ multi-thread บน Ryzen 7 7700 CPU

ขีดจำกัดเชิงทฤษฎี

  • อธิบายลำดับชั้นหน่วยความจำของ CPU และส่วนขยาย SIMD
  • ในทางทฤษฎี ทำได้ 163 GFLOPS แบบ single-thread และ 1203 GFLOPS แบบ multi-thread

การติดตั้งใช้งานแบบง่าย

  • อธิบายอัลกอริทึม matrix multiplication พื้นฐานและวัดประสิทธิภาพของการติดตั้งใช้งานแบบง่าย
  • การติดตั้งใช้งานแบบง่ายทำได้ 2.7 GFLOPS

เคอร์เนล

  • อธิบายวิธีแก้ปัญหาโดยแบ่ง matrix multiplication ออกเป็นโจทย์ย่อยขนาดเล็ก
  • ปรับแต่งเคอร์เนลด้วยคำสั่ง SIMD
  • ใช้เคอร์เนล 16x6 เพื่อทำได้ 147 GFLOPS

การมาสก์และการแพ็ก

  • อธิบายวิธีจัดการกรณีขอบเขตเพื่อรองรับขนาดเมทริกซ์ตามต้องการ
  • ปรับประสิทธิภาพด้วยการมาสก์และการแพ็ก
  • การติดตั้งใช้งานใหม่ทำได้ 56 GFLOPS

การแคช

  • อธิบายระบบหน่วยความจำของ CPU cache
  • ใช้แคชเพื่อเพิ่มประสิทธิภาพการนำข้อมูลกลับมาใช้ซ้ำและการจัดการแคช

ความเห็นของ GN⁺

  • บทความนี้อธิบายวิธีสร้าง matrix multiplication ประสิทธิภาพสูงแบบเป็นขั้นตอน จึงให้ความรู้มาก
  • สามารถเรียนรู้วิธีปรับแต่งด้วยคำสั่ง SIMD และ CPU cache ได้
  • ช่วยให้เข้าใจการทำงานภายในของไลบรารีอย่าง NumPy มากขึ้น
  • โปรเจ็กต์อื่นที่มีความสามารถคล้ายกัน ได้แก่ Intel MKL, OpenBLAS เป็นต้น
  • เมื่อนำเทคโนโลยีใหม่หรือโอเพนซอร์สมาใช้ ควรพิจารณาทั้งประสิทธิภาพและความสามารถในการพกพา

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

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

 
GN⁺ 2024-07-05
ความเห็นจาก Hacker News

  • ซอฟต์แวร์ส่วนใหญ่ยังไม่ได้รับการปรับแต่งอย่างเหมาะสม จึงยังมีช่องว่างให้เพิ่มประสิทธิภาพได้มาก

    • การเลือกอัลกอริทึมสำคัญที่สุด
    • ควรตรวจสอบว่าสามารถลดงานที่มีต้นทุนสูงอย่างการเรียก kernel ได้หรือไม่
    • สามารถเพิ่มประสิทธิภาพได้ผ่านการทำ vectorization
    • ควรตรวจสอบว่าสามารถปรับประสิทธิภาพด้าน cache ให้ดีขึ้นได้หรือไม่
    • ควรพิจารณาความเป็นไปได้ของการปรับแต่งให้เฉพาะกับฮาร์ดแวร์

  • งานวิจัยที่อ้างอิงอยู่ในรีโพ BLIS เป็นแหล่งข้อมูลที่น่าเชื่อถือสำหรับการทำความเข้าใจหัวข้อนี้

    • ไม่เข้าใจเหตุผลที่ทำให้คิดว่า BLAS ที่ปรับแต่งแล้วมีประสิทธิภาพไม่ดี
    • ควรใช้ BLAS ของ AMD แทน numpy
    • BLIS ทำ parallelization ได้ดีกว่า OpenBLAS

  • คำสั่ง SIMD ไม่จำเป็นสำหรับการทำ vectorization ของ micro-kernel

    • หากใช้ขนาดบล็อกที่เหมาะสม micro-kernel แบบ C ล้วนของ BLIS จะให้ประสิทธิภาพได้มากกว่า 80% ของการติดตั้งใช้งานที่ปรับแต่งด้วยมือ

  • แพตเทิร์นการเขียนโค้ดส่วนใหญ่ไม่ได้ปรับให้เข้ากับฮาร์ดแวร์อย่างเต็มที่ จึงพลาดประสิทธิภาพไปมาก

    • น่าจะอ้างอิงบทความคลาสสิกด้าน CS ที่ชื่อว่า "There's plenty of room at the top"

  • การทำให้สามารถรัน benchmark ซ้ำได้ง่ายเป็นจุดที่น่าชื่นชม

    • บน Xeon CPU 16 คอร์ matmul.c ใช้เวลา 1.41 วินาทีเมื่อคอมไพล์ด้วย gcc -O3, 1.47 วินาทีเมื่อคอมไพล์ด้วย clang -O2, ส่วน NumPy ใช้เวลา 1.07 วินาที
    • เชื่อว่า kernel แบบ avx512 น่าจะเร็วกว่า
    • การใช้ pthreads แทน omp และจัดการ thread pool แบบชัดเจน อาจช่วยลด overhead ได้

  • สงสัยว่า implementation ของ numpy ใช้ multithreading จริงหรือไม่

  • อยากรู้ว่าทำไมจึงมีประสิทธิภาพดีกว่า OpenBLAS

    • มีการจัดการรายละเอียดอย่างการทำ caching
    • สงสัยว่าเป็นเพราะปรับแต่งให้เหมาะกับโปรเซสเซอร์เฉพาะรุ่นมากกว่าหรือไม่

  • การเปรียบเทียบโดยฝั่งหนึ่งเป็น Python และอีกฝั่งเป็น C นั้นไม่ยุติธรรม

    • ควรเขียนทั้งสองฝั่งด้วย C แล้วค่อยเปรียบเทียบจะดีกว่า

  • รู้สึกติดใจกับความไม่มีประสิทธิภาพของการสร้าง mask

    • มีวิธีที่มีประสิทธิภาพกว่าสำหรับการสร้างอาร์เรย์ค่าคงที่แบบ global หรือการเปรียบเทียบกับเวกเตอร์ค่าคงที่
    • แต่นี่เป็นปัญหาเล็กน้อย และในทางปฏิบัติก็น่าจะไม่ได้ต่างมาก

  • ตั้งคำถามถึงความคุ้มค่าในทางปฏิบัติของการทำ multithreading กับการคูณเมทริกซ์โดยตรง

    • multithreading น่าจะมีประโยชน์มากกว่าสำหรับอัลกอริทึมที่ใช้การคูณเมทริกซ์

  • มีการกล่าวถึง tinyBLAS ของ jart

    • มีการให้ลิงก์ที่เกี่ยวข้อง