อัลกอริทึม SIMD ที่ออกแบบตั้งแต่ต้น

การออกแบบอัลกอริทึม SIMD

• คำอธิบายเกี่ยวกับการทำ SIMD optimization: SIMD หมายถึง Single Instruction, Multiple Data และจำเป็นต้องคิดแบบผู้ออกแบบวงจร
• SIMD มักถูกพูดถึงบ่อยในด้านประสิทธิภาพและ HPC (การประมวลผลสมรรถนะสูง) แต่ไม่ใช่หัวข้อที่คุ้นเคยสำหรับผู้เริ่มต้น
• ในภาษาโปรแกรมส่วนใหญ่ API สำหรับการเขียนโปรแกรม SIMD ใช้งานได้ค่อนข้างยาก
• อัลกอริทึม SIMD ทำความเข้าใจได้ยากด้วยแนวคิดแบบ procedural programming และ functional programming สามารถช่วยได้
• เนื้อหาหลักกล่าวถึง vb64 ซึ่งเป็นการติดตั้งใช้งาน base64 codec โดยใช้ไลบรารี std::simd ของ Rust

ข้อจำกัดทางกายภาพ

• คอมพิวเตอร์มีอยู่ในโลกจริงและถูกจำกัดด้วยกฎทางฟิสิกส์
• ในยุคเริ่มต้นของการประมวลผล สามารถเพิ่มประสิทธิภาพได้ด้วยการซื้อคอมพิวเตอร์เครื่องใหม่
• เมื่อผลของ Dennard scaling พังทลายลง ทรานซิสเตอร์ที่เล็กลงจึงหมายถึงการใช้พลังงานมากขึ้น
• การเพิ่มจำนวนคอร์กลายเป็นแนวโน้มใหม่ สามารถเพิ่มประสิทธิภาพของ CPU ได้ด้วย multithreading แต่ต้องแลกกับ synchronization overhead

ความช้าของโค้ดเชิงกระบวนการ

• คอร์ของคอมพิวเตอร์สมัยใหม่ไม่ได้รันโค้ดทีละบรรทัด
• ผ่าน instruction-level parallelism จึงสามารถทำหลายการคำนวณพร้อมกันได้หากไม่มี data dependency
• ความขนานจะเพิ่มขึ้นเมื่อคอมไพเลอร์สามารถแก้ data hazards ได้
• การแตกแขนงและงานด้านหน่วยความจำทำให้เกิด stall ซึ่งทำให้โค้ดช้าลง

SIMD และ lane

• SIMD และเวกเตอร์มักถูกใช้แทนกันในความหมายเดียวกัน
• คำสั่ง SIMD ใช้เวกเตอร์ซึ่งเป็นอาร์เรย์ของตัวเลขขนาดคงที่เป็นหน่วยพื้นฐาน
• แต่ละองค์ประกอบของเวกเตอร์เรียกว่า lane และเวกเตอร์ SIMD โดยทั่วไปมักมีขนาดเล็ก

การดำเนินการกับเวกเตอร์จริง

• เวกเตอร์ SIMD ให้การดำเนินการที่ซับซ้อนกว่ารีจิสเตอร์ทั่วไป
• vector register รองรับการดำเนินการหลากหลาย เช่น การดำเนินการระดับบิต, arithmetic แบบแยกตาม lane, การเปรียบเทียบแยกตาม lane และ shuffle
• shuffle มีความสำคัญใน SIMD programming สำหรับการย้ายข้อมูลไปยังตำแหน่งที่เหมาะสม

intrinsic และการเลือกคำสั่ง

• การดำเนินการที่ใช้ได้ในการเขียนโค้ด SIMD จะแตกต่างกันไปตามสถาปัตยกรรม
• คอมไพเลอร์ต้องแก้ปัญหา instruction selection เพื่อเลือกว่าจะใช้คำสั่งใดสำหรับการดำเนินการที่ผู้ใช้ร้องขอ
• การเขียนโค้ด SIMD แบบพกพาเป็นเรื่องซับซ้อน แต่สามารถสร้างโค้ดที่เหมาะสมที่สุดสำหรับโปรเซสเซอร์หลายแบบได้ผ่าน runtime feature detection

การพาร์สด้วย SIMD

• สามารถใช้ SIMD เพื่อพาร์สข้อความได้ และอาจทำงานได้รวดเร็วมาก
• ตัวอย่างหนึ่งคือการติดตั้งใช้งานการถอดรหัส base64 ด้วย SIMD
• หัวใจสำคัญของการสร้างเวอร์ชัน SIMD คือการกำจัดการแตกแขนงทั้งหมด

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

สิ่งที่สำคัญที่สุดในบทความนี้คือ SIMD programming มีความสามารถในการเพิ่มประสิทธิภาพด้วยการประมวลผลข้อมูลแบบขนาน ซึ่งแตกต่างจากวิธีการเขียนโปรแกรมเชิงกระบวนการแบบเดิม SIMD มีความสำคัญอย่างมากในงานด้านการประมวลผลสมรรถนะสูง และโดยเฉพาะอย่างยิ่ง การทำความเข้าใจวิธีใช้ SIMD อย่างมีประสิทธิภาพในภาษาโปรแกรมสมัยใหม่อย่าง Rust เป็นหัวข้อที่น่าสนใจมากสำหรับวิศวกรซอฟต์แวร์ เพราะช่วยให้เรียนรู้วิธีปรับแต่งอัลกอริทึมที่ซับซ้อนและก้าวข้ามข้อจำกัดของฮาร์ดแวร์จริงได้

[GN⁺]

ความคิดเห็นบน Hacker News

• เป็นบทความที่ยอดเยี่ยมสำหรับดูกรณีใช้งานของ portable SIMD ลองทำซ้ำเบนช์มาร์กบนระบบ Zen 3 แล้วก็ยืนยันได้ว่าได้ความเร็วเพิ่มขึ้นเท่าเดิม บน M1 mbp ประสิทธิภาพเพิ่มขึ้นอย่างค่อยเป็นค่อยไปจนได้สูงสุด 2 เท่าที่ความยาวอินพุต 110 ไบต์ แม้จะได้ประโยชน์น้อยกว่า x86_64 แต่ก็นับว่าบรรลุเป้าหมาย อย่างไรก็ตามก็ยืนยันได้ว่า Rust ยังมีจุดที่ใช้งานไม่ค่อยสะดวกสำหรับงานที่เกี่ยวกับ SIMD และพอยน์เตอร์ รวมถึงงานวิศวกรรมประสิทธิภาพโดยรวม
• บางครั้งก็น่าทึ่งที่ต่อให้พยายามเขียน C++ ให้ดีที่สุดแล้ว เวอร์ชันที่ใช้ SIMD ก็ยังเร็วกว่าเกิน 10 เท่า แม้ความพกพาของโค้ดจะลดลง แต่ก็หวังว่าคอมไพเลอร์จะทำ automatic vectorization ได้ดีกว่านี้ อยากให้ภาษาเพิ่มการรองรับผ่าน annotation เพื่อให้สามารถจัดเรียงลำดับของโอเปอเรชันบางอย่างใหม่ได้
• มีการชี้ว่าคอมไพเลอร์ไม่สามารถปรับแต่ง popcount implementation บางแบบให้เป็นคำสั่งเดี่ยวได้ แต่กับ implementation อื่นก็มีกรณีที่ทำได้
• _mm256_cvtps_epu32 ไม่ใช่คำสั่งของ AVX2 แต่เป็นของ AVX-512 และใน AVX1 จำนวนเต็มจะอยู่ในรูป signed ดังนั้นคำสั่งที่เกี่ยวข้องคือ _mm256_cvtps_epi32
• ชอบมินิแมปเล็กๆ ทางขวามาก
• มองว่า ISPC ดีกว่าการเพิ่ม SIMD เข้าไปใน C++ หรือ Rust และยังรองรับ dynamic dispatch ด้วย ซึ่งเป็นความสามารถที่ถ้าทำเองจะค่อนข้างยาก
• มีคำถามว่าเมื่อเทียบกับ fastbase64 แล้วเป็นอย่างไร พร้อมทั้งแสดงความเห็นว่าอยากแบ่งปันทัศนะเชิงบวกของผู้เขียนที่มีต่อไลบรารี portable SIMD
• เป็นบทความที่ยอดเยี่ยมและให้ความรู้สึกว่าตัวเองคงไม่มีวันฉลาดได้ถึงระดับนี้
• แม้จะมีการบอกว่าตัวอย่างแรกของ popcnt implementation ที่ไม่ถูกเวกเตอร์ไรซ์สร้าง "โค้ดที่พูดตรงๆ ว่าน่าขัน" แต่เมื่อคอมไพล์ใน release mode สำหรับ target CPU แบบ native ก็ดูเหมือนว่าฟังก์ชันนี้ถูกเวกเตอร์ไรซ์ได้ค่อนข้างดี
• นับว่าเป็นความพยายามที่ดีมากสำหรับ Rust Simd มีการตั้งคำถามว่าสิ่งผิดปกติที่น่าประหลาดใจที่สุดคืออะไรเมื่อได้ตรวจดูโค้ดที่สร้างขึ้น