ชิป ARM ทำลายสถิติความเร็วสำหรับอัลกอริทึมการบีบอัดข้อมูล

ในโลกของการบีบอัดข้อมูล เทคนิคเดลตาโค้ดดิ้งเป็นเทคนิคพื้นฐานที่ถูกใช้มายาวนานเพื่อทำให้ข้อมูลมีขนาดเล็กลงและจัดเก็บได้อย่างมีประสิทธิภาพมากขึ้น กระบวนการนี้แปลงลำดับของตัวเลขให้เป็นความแตกต่างระหว่างค่าที่อยู่ติดกัน สร้างรูปแบบที่สามารถบีบอัดได้อย่างมีประสิทธิภาพ อย่างไรก็ตาม การย้อนกลับกระบวนการนี้ ซึ่งก็คือการสร้างข้อมูลเดิมกลับมาผ่านการดำเนินการที่เรียกว่า prefix sum นั้น โดย傳統แล้วเป็นจุดติดขัดด้านการคำนวณ เนื่องมาจากการพึ่งพาอาศัยกันแบบอนุกรม การวิจัยใหม่เปิดเผยว่าการเทคนิคการเพิ่มประสิทธิภาพที่สร้างสรรค์บนสถาปัตยกรรม Neoverse V2 ล่าสุดของ ARM กำลังทำลายอุปสรรคด้านประสิทธิภาพที่มีมาสำหรับการดำเนินการพื้นฐานนี้

จุดติดขัดที่ซ่อนอยู่ในการคลายการบีบอัดข้อมูล

ในขณะที่เดลตาโค้ดดิ้งเองทำงานได้อย่างมีประสิทธิภาพที่ 41 GB/s บนฮาร์ดแวร์สมัยใหม่ การดำเนินการย้อนกลับยังคงมีความเร็วที่น้อยกว่าอย่าง упряم ปัญหาอยู่ที่ธรรมชาติทางคณิตศาสตร์ของ prefix sum: ค่าผลลัพธ์แต่ละค่าขึ้นอยู่กับการคำนวณทั้งหมดก่อนหน้านี้ สิ่งนี้สร้างสิ่งที่นักออกแบบคอมพิวเตอร์เรียกว่าห่วงโซ่การพึ่งพา (dependency chain) ซึ่งโปรเซสเซอร์ต้องรอให้การดำเนินการแต่ละครั้งเสร็จสิ้นก่อนจึงจะเริ่มดำเนินการถัดไปได้ วิธีการดั้งเดิมเช่น อัลกอริทึม FastPFoR ที่เป็นที่ยอมรับนั้น ให้ผลการทำงานที่แย่กว่าการนำเสนอแบบสเกลาร์อย่างง่ายบนโปรเซสเซอร์ Graviton4 ของ ARM โดยทำได้เพียง 7.7 GB/s เทียบกับ 10.8 GB/s สำหรับวิธีการแบบง่าย

ฉันคิดว่าตอนแรกมันเป็นข้อผิดพลาดในการพิมพ์ แต่มันกลับถูกต้อง วิธีการแบบง่ายกลับเร็วกว่าวิธีการที่ 'ดีกว่า' นี่เป็นการสาธิตอีกครั้งว่าการทดสอบวัดประสิทธิภาพจริงบนแพลตฟอร์มเป้าหมายนั้นสำคัญแค่ไหน!

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

ทำลายห่วงโซ่การพึ่งพา

ความก้าวหน้าครั้งสำคัญเกิดขึ้นจากการปรับโครงสร้างการคำนวณใหม่เพื่อลดการพึ่งพาแบบอนุกรมเหล่านี้ แทนที่จะนำผลรวมสะสมไปใช้กับค่าใหม่แต่ละค่าทันที วิธีการใหม่นี้จะประมวลผลข้อมูลเป็นบล็อกและเลื่อนขั้นตอนการสะสมออกไป สิ่งนี้ทำให้ฮาร์ดแวร์การทำงานนอกลำดับ (out-of-order execution) ของโปรเซสเซอร์สามารถทำงานหลายๆ การดำเนินการพร้อมกันได้ แทนที่จะรอผลลัพธ์จากแต่ละครั้ง เทคนิคนี้แลกเปลี่ยนกับการเพิ่มขึ้นเล็กน้อยของจำนวนคำสั่งทั้งหมด เพื่อ换取การทำงานแบบขนานที่改善อย่างมาก โดยทำได้ที่ 19.8 GB/s — เกือบสองเท่าของประสิทธิภาพของการนำเสนอแบบง่าย และเร็วกว่า FastPFoR 2.6 เท่า

วิธีการนี้ขยายเกินกว่า prefix sum อย่างง่าย ไปยังการแปลงรูปแบบที่ซับซ้อนมากขึ้น เช่น เดลตาออฟเดลตาโค้ดดิ้ง (มีประสิทธิภาพสำหรับลำดับการประทับเวลา) และ การเข้ารหัส XOR-with-previous (ถูกใช้ในแผนการบีบอัดข้อมูลทศนิยมเช่น Gorilla) สำหรับการย้อนกลับเดลตาออฟเดลตา เทคนิคการไปป์ไลน์ให้ความเร็วที่เพิ่มขึ้น 2.2 เท่า ในขณะที่การดำเนินการ XOR ได้รับประโยชน์จากวิธีการแบบอื่น based on transpose ที่ปรับปรุงประสิทธิภาพได้ 2.0 เท่า

คำอธิบายแนวคิดทางเทคนิคที่สำคัญ

• Delta Coding: การเก็บค่าความแตกต่างระหว่างค่าที่ต่อเนื่องกันแทนที่จะเก็บตัวเลขดิบ ทำให้เกิดรูปแบบที่สามารถบีบอัดได้มากขึ้น
• Prefix Sum: การดำเนินการย้อนกลับที่สร้างค่าเดิมขึ้นมาใหม่โดยการสะสมค่าความแตกต่าง
• Dependency Chain: เมื่อการคำนวณแต่ละครั้งขึ้นอยู่กับผลลัพธ์ก่อนหน้า ทำให้ต้องประมวลผลแบบเรียงลำดับ
• SIMD Intrinsics: ฟังก์ชันเฉพาะของโปรเซสเซอร์ที่สามารถทำงานกับข้อมูลหลายส่วนพร้อมกันได้
• Neoverse V2: สถาปัตยกรรม CPU ระดับเซิร์ฟเวอร์รุ่นล่าสุดของ ARM ที่ใช้ในโปรเซสเซอร์ AWS Graviton4

การถกเถียงระหว่าง CPU กับ GPU ในเวิร์กโหลดจริง

การอภิปรายขยายออกไปตามธรรมชาติว่าการ์ดจอ GPU สามารถเร่งการดำเนินการเหล่านี้ได้มากไปกว่าหรือไม่ ในขณะที่ GPU เก่งในการคำนวณแบบขนาน ต้นทุนโสหุ้ยในการถ่ายโอนข้อมูลระหว่างหน่วยความจำระบบ (system RAM) และ หน่วยความจำ GPU (GPU memory) มักจะลบล้างข้อได้เปรียบทางทฤษฎีสำหรับเวิร์กโหลดการบีบอัดข้อมูลในโลกจริง ดังที่ผู้แสดงความคิดเห็นหนึ่งระบุไว้ว่า หากข้อมูลอยู่ในหน่วยความจำ GPU อยู่แล้ว ใช่ มันทำได้ ไม่อย่างนั้นคุณจะถูกจำกัดโดยจุดติดขัดของหน่วยความจำ DRAM←→VRAM

การวิเคราะห์ความคุ้มค่าต่อประสิทธิภาพเผยให้เห็นการแลกเปลี่ยนที่น่าสนใจ จากการเปรียบเทียบราคาอินสแตนซ์บนคลาวด์ อินสแตนซ์ m8g.8xlarge ที่ใช้ ARM พร้อม 32 คอร์ ให้แบนด์วิธหน่วยความจำ 175 GB/s ในราคา 1.44 ดอลลาร์สหรัฐ ต่อชั่วโมง ในขณะที่อินสแตนซ์ GPU ที่มีแบนด์วิธทางทฤษฎีใกล้เคียงกันมีราคาสูงกว่า สำหรับฐานข้อมูลอนุกรมเวลา (time-series databases) และเวิร์กโหลดการวิเคราะห์ทั่วไป ซึ่งข้อมูลผ่านการแปลงรูปแบบหลายครั้งขณะที่ถูกเก็บไว้ในหน่วยความจำ CPU วิธีการของ ARM แสดงให้เห็นถึงประสิทธิภาพที่น่าสนใจ

การเปรียบเทียบประสิทธิภาพบน AWS Graviton4 (Neoverse V2)

เงื่อนไขการทดสอบ: ชุดงานขนาด 4 KiB, 20,000 รอบ, single-threaded, L1 cache hot

เกินกว่าประสิทธิภาพทางทฤษฎี

การอภิปรายในชุมชนเปิดเผยข้อพิจารณาเชิงปฏิบัติที่ขยายเกินกว่าตัวเลขความเร็วในการถ่ายโอนข้อมูลดิบ ผู้แสดงความคิดเห็นหลายคนชี้ให้เห็นว่าการแทรกค่าสัมบูรณ์ (absolute values) เป็นช่วงๆ ภายในสตรีมที่เข้ารหัสด้วยเดลตาสามารถทำให้เกิดการทำงานแบบขนานสมบูรณ์ได้ แม้ว่าสิ่งนี้จะลดทอนประสิทธิภาพการบีบอัดลงก็ตาม บางคนแบ่งปันประสบการณ์จากการนำอัลกอริทึมที่คล้ายกันไปใช้ในระบบที่ใช้งานจริง โดยระบุว่าวิธีการที่เหมาะสมที่สุดขึ้นอยู่กับรูปแบบการเข้าถึงข้อมูลและความถี่ในการอัปเดตเป็นอย่างมาก

เทคนิคที่อธิบายไว้ไม่จำกัดอยู่แค่จำนวนเต็ม 32 บิต — มันขยายไปสู่ประเภทข้อมูล 8, 16 และ 64 บิต โดยธรรมชาติ ทำให้สามารถนำไปใช้กับสถานการณ์การบีบอัดข้อมูลที่หลากหลาย ตั้งแต่ระบบฐานข้อมูลไปจนถึงการคำนวณทางวิทยาศาสตร์ การนำเสนออ้างอิงใช้คำสั่ง SIMD intrinsics ซึ่งโดยพื้นฐานแล้วคือคำสั่งแอสเซมบลีที่ถูกห่อหุ้มในฟังก์ชันภาษา C ช่วยให้สามารถควบคุมความสามารถของโปรเซสเซอร์ได้อย่างละเอียด

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

อ้างอิง: NEON Delta Coding