Prism: การก้าวข้ามข้อจำกัดการอนุมานของ LLM ด้วยการเพิ่มประสิทธิภาพเชิงสัญลักษณ์แบบสุดขั้ว เพิ่มประสิทธิภาพ 1.7 เท่า

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

จาก TensorFlow ถึง TVM จาก cuDNN ถึง FlashAttention เราต้องพึ่งพากฎและเคอร์เนลที่เขียนด้วยมือโดยผู้เชี่ยวชาญมาโดยตลอดเพื่อขับเคลื่อนการก้าวกระโดดด้านประสิทธิภาพของโมเดล AI อย่างไรก็ตาม กระบวนทัศน์นี้กำลังค่อยๆ แตะเพดาน กฎที่เขียนด้วยมือสามารถครอบคลุมพื้นที่การเพิ่มประสิทธิภาพที่จำกัดเท่านั้น และเมื่อใดก็ตามที่มีโอเปอเรเตอร์หรือฮาร์ดแวร์ใหม่เกิดขึ้น การปรับให้เข้ากันมักต้องใช้แรงงานคนหลายเดือน เทคโนโลยีการเพิ่มประสิทธิภาพขั้นสูงสุด (Superoptimization) เคยถูกมองว่าเป็นความหวัง โดยพยายามค้นหาโปรแกรมที่เหมาะสมที่สุดผ่านการค้นหาอัตโนมัติ แต่การค้นหาแบบแจกแจงจะพบกับการระเบิดเชิงผสมผสาน ในขณะที่การค้นหาแบบสุ่มตัวอย่างก็ยากที่จะรับประกันว่าจะพบคำตอบที่ดีที่สุด

ซูเปอร์ออปติไมเซอร์กระแสหลักในปัจจุบันแบ่งออกเป็นสองสำนักใหญ่: แบบแจกแจง (เช่น TASO, Mirage) และแบบสุ่มตัวอย่าง (เช่น AlphaEvolve)

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

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

จากข้อมูลเชิงลึกนี้ Prism ได้开创了กระบวนทัศน์ใหม่ของการเพิ่มประสิทธิภาพขั้นสูงสุดเชิงสัญลักษณ์ โดยแบ่งกระบวนการเพิ่มประสิทธิภาพออกเป็นการค้นหาสองระดับ:

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

ผลการทดลองแสดงให้เห็นว่า บนภาระงาน LLM หลักห้ารายการ ประสิทธิภาพของ Prism สูงกว่า Mirage ซูเปอร์ออปติไมเซอร์ที่ดีที่สุดในปัจจุบันสูงสุดถึง 2.2 เท่า สูงกว่าวิธีการคอมไพเลอร์แบบดั้งเดิม (PyTorch Compiled) สูงสุดถึง 4.9 เท่า ในขณะที่เวลาในการเพิ่มประสิทธิภาพแบบ end-to-end ลดลงสูงสุด 3.4 เท่า ที่สำคัญกว่านั้น การค้นหาเชิงสัญลักษณ์ของ Prism ทำงานเพียงครั้งเดียวก็ครอบคลุมการกำหนดค่าอินพุตทั้งหมด ในขณะที่ Mirage ต้องค้นหาแยกกันสำหรับแต่ละการกำหนดค่า

บทความนี้จะเจาะลึกการออกแบบเทคโนโลยีหลักของ Prism ตั้งแต่การแสดงสัญลักษณ์ของ sGraph ไปจนถึงรายละเอียดการใช้งานการค้นหาสองระดับ จากหลักการทางคณิตศาสตร์ของการตัดแต่งเชิงสัญลักษณ์ไปจนถึงกลไกการตรวจสอบความเท่าเทียมของ e-graph เพื่อตีความอย่างครอบคลุมว่าผลลัพธ์ที่ก้าวล้ำนี้กำหนดขอบเขตของการเพิ่มประสิทธิภาพโปรแกรมเทนเซอร์ใหม่ได้อย่างไร

สารบัญ

• หนึ่ง. ข้อจำกัดของการเพิ่มประสิทธิภาพระบบ ML และวิวัฒนาการของการเพิ่มประสิทธิภาพขั้นสูงสุด
  • 1.1 ข้อจำกัดของกระบวนทัศน์การเพิ่มประสิทธิภาพแบบดั้งเดิม
  • 1.2 การเกิดขึ้นและความท้าทายของเทคโนโลยีการเพิ่มประสิทธิภาพขั้นสูงสุด
• สอง. การออกแบบหลักของ Prism: กระบวนทัศน์ใหม่ของการเพิ่มประสิทธิภาพขั้นสูงสุดเชิงสัญลักษณ์
  • 2.1 ข้อมูลเชิงลึกหลัก: จากการแจกแจงโปรแกรมสู่การเข้ารหัสตระกูลโปรแกรม
  • 2.2 sGraph: การแสดงกราฟแบบลำดับชั้นเชิงสัญลักษณ์
  • 2.3 ขั้นตอนการทำงานโดยรวมของ Prism
• สาม. การสร้าง sGraph: การค้นหาและการตัดแต่งเชิงสัญลักษณ์
  • 3.1 การจับคู่มิติเชิงสัญลักษณ์
  • 3.2 การตัดแต่งที่นำโดยนิพจน์
  • 3.3 การทำให้การแมปเป็นรูปธรรมและการทำลายสมมาตร
• สี่. การตรวจสอบ sGraph: การตรวจสอบความเท่าเทียมเชิงสัญลักษณ์โดยใช้ e-graph
  • 4.1 ภาษานิพจน์และโอเปอเรเตอร์แบบขนาน
  • 4.2 สัจพจน์ความเท่าเทียมและการเขียนซ้ำ e-graph
  • 4.3 การจัดการพิเศษสำหรับการปรับสัจพจน์
• ห้า. การทำให้พารามิเตอร์เป็นรูปธรรม: การปรับแต่งอัตโนมัติและการเพิ่มประสิทธิภาพ
  • 5.1 พื้นที่การค้นหาสำหรับการปรับแต่งอัตโนมัติ
  • 5.2 การสุ่มตัวอย่างและการคอมไพล์แบบขนาน
• หก. การประเมินผลการทดลองและการวิเคราะห์ผลลัพธ์
  • 6.1 การตั้งค่าการทดลอง
  • 6.2 ผลลัพธ์ประสิทธิภาพของเคอร์เนล
  • 6.3 ผลลัพธ์เวลาในการเพิ่มประสิทธิภาพทั้งหมด
  • 6.4 การแยกย่อยเวลาในการค้นหาและความหลากหลายของกราฟ
  • 6.5 การศึกษาแบบ Ablation: ผลกระทบของการแมปเชิงสัญลักษณ์
• เจ็ด. งานที่เกี่ยวข้อง
  • 7.1 เคอร์เนลที่ปรับให้เหมาะสมด้วยมือโดยผู้เชี่ยวชาญ
  • 7.2 คอมไพเลอร์ที่ใช้กฎ
  • 7.3 ซูเปอร์ออปติไมเซอร์
  • 7.4 การแสดงกราฟเชิงสัญลักษณ์
• แปด. บทสรุปและแนวโน้มในอนาคต
  • 8.1 สรุปผล
  • 8.2 การวิเคราะห์เชิงลึก
  • 8.3 งานในอนาคต

หนึ่ง. ข้อจำกัดของการเพิ่มประสิทธิภาพระบบ ML และวิวัฒนาการของการเพิ่มประสิทธิภาพขั้นสูงสุด

คอขวดด้านประสิทธิภาพของแอปพลิเคชัน AI สมัยใหม่ไม่ได้จำกัดอยู่แค่ที่ตัวโมเดลอีกต่อไป แต่ได้ย้ายไปที่ประสิทธิภาพการทำงานของฮาร์ดแวร์แล้ว GPU ในฐานะฮาร์ดแวร์หลักสำหรับการฝึกอบรมและการอนุมาน AI นั้น การเติบโตของพลังการคำนวณนั้น远超กว่าอัตราการปรับปรุงของแบนด์วิธหน่วยความจำและเวลาแฝง ดังนั้น วิธีการเพิ่มอัตราการใช้ทรัพยากรการคำนวณของ GPU ให้สูงสุดจึงกลายเป็นประเด็นหลักของการเพิ่มประสิทธิภาพระบบ机器学习

โปรแกรมเทนเซอร์เป็นวิธีการอธิบายมาตรฐานสำหรับโมเดล机器学习 โดยใช้กราฟแบบไม่มีวงจร (DAG) เพื่ออธิบายขั้นตอนการคำนวณ โดยโหนดในกราฟแทนโอเปอเรเตอร์เทนเซอร์ และขอบแทนข้อมูลเทนเซอร์ แกนหลักของการเพิ่มประสิทธิภาพโปรแกรมเทนเซอร์คือ การค้นหาการใช้งานโปรแกรมที่ดำเนินการได้เร็วที่สุดสำหรับฮาร์ดแวร์เฉพาะ ในขณะที่รับประกันความเท่าเทียมกันของฟังก์ชัน

1.1 ข้อจำกัดของกระบวนทัศน์การเพิ่มประสิทธิภาพแบบดั้งเดิม

กระบวนทัศน์การเพิ่มประสิทธิภาพของระบบ机器学习แบบดั้งเดิมประกอบด้วยสองประเภทหลัก: คอมไพเลอร์ที่ใช้กฎและไลบรารีเคอร์เนลที่ปรับให้เหมาะสมด้วยมือ วิธีการทั้งสองนี้ได้ขับเคลื่อนการพัฒนาอย่างรวดเร็วของแอปพลิเคชัน AI ในช่วงทศวรรษที่ผ่านมา แต่ด้วยขนาดโมเดลและความซับซ้อนของฮาร์ดแวร์ที่เพิ่มขึ้นอย่างต่อเนื่อง ข้อจำกัดของมันก็ชัดเจนมากขึ้น

คอมไพเลอร์ที่ใช้กฎ (เช่น TensorFlow XLA, PyTorch TorchInductor, TVM) ส่วนใหญ่พึ่งพากฎการเขียนกราฟและเทมเพลตการจัดตารางเวลาที่ผู้เชี่ยวชาญกำหนดไว้ล่วงหน้าเพื่อเพิ่มประสิทธิภาพโปรแกรมเทนเซอร์ กฎเหล่านี้เป็นผลึกแห่งประสบการณ์ของผู้เชี่ยวชาญ สามารถครอบคลุมรูปแบบการเพิ่มประสิทธิภาพทั่วไป เช่น การรวมโอเปอเรเตอร์ การพับค่าคงที่ การกำจัดนิพจน์ย่อยทั่วไป อย่างไรก็ตาม กฎเหล่านี้สามารถจับภาพการเพิ่มประสิทธิภาพที่มนุษย์คาดการณ์ได้เท่านั้น ไม่สามารถค้นพบกลยุทธ์การเพิ่มประสิทธิภาพแบบผสมผสานที่ไม่เป็นไปตามสัญชาตญาณได้ ตัวอย่างเช่น การรวมโอเปอเรเตอร์หลายตัวเป็นเคอร์เนลที่กำหนดเองหนึ่งตัวสามารถลดการรับส่งข้อมูลหน่วยความจำได้อย่างมาก แต่ลำดับและวิธีการรวมนั้นมีความเป็นไปได้นับไม่ถ้วน วิศวกรมนุษย์ไม่สามารถแจกแจงรูปแบบการรวมที่มีประสิทธิภาพทั้งหมดได้

ไลบรารีเคอร์เนลที่ปรับให้เหมาะสมด้วยมือ (เช่น cuDNN, cuBLAS, FlashAttention) ได้รับการปรับให้เหมาะสมอย่างที่สุดสำหรับโอเปอเรเตอร์และฮาร์ดแวร์เฉพาะ สามารถใช้ศักยภาพการคำนวณของฮาร์ดแวร์ได้อย่างเต็มที่ ตัวอย่างเช่น FlashAttention แบ่งการคำนวณ Attention เป็นบล็อกและใช้หน่วยความจำที่ใช้ร่วมกัน ลดความซับซ้อนของหน่วยความจำของโอเปอเรเตอร์ Attention จาก O(n²) เหลือ O(n) ทำให้ประสิทธิภาพเพิ่มขึ้นหลายเท่า อย่างไรก็ตาม ชุดโอเปอเรเตอร์ที่ไลบรารีเคอร์เนลที่ปรับให้เหมาะสมด้วยมือรองรับนั้นตายตัว ไม่สามารถปรับให้เข้ากับโอเปอเรเตอร์หรือโครงสร้างโมเดลใหม่ได้อย่างรวดเร็ว นอกจากนี้ การปรับให้เข้ากับฮาร์ดแวร์ใหม่ต้องใช้ความพยายามทางวิศวกรรมอย่างมหาศาล การย้าย FlashAttention ไปยังสถาปัตยกรรม GPU ใหม่มักใช้เวลาหลายเดือน

เอกสารชี้ให้เห็นอย่างชัดเจนว่ากระบวนทัศน์การเพิ่มประสิทธิภาพแบบดั้งเดิมมีข้อบกพร่องพื้นฐานสองประการ:

1. ต้นทุนทางวิศวกรรมที่สูง: การปรับให้เข้ากับโอเปอเรเตอร์ใหม่และฮาร์ดแวร์ใหม่ต้องใช้วิศวกรผู้เชี่ยวชาญจำนวนมาก ทำให้ยากต่อการก้าวให้ทันกับการ迭代อย่างรวดเร็วของโมเดล AI และฮาร์ดแวร์
2. พื้นที่การเพิ่มประสิทธิภาพที่จำกัด: สัญชาตญาณของมนุษย์ไม่สามารถจับภาพปฏิสัมพันธ์เชิงผสมผสานที่ซับซ้อนระหว่างการแปลงพีชคณิต การจัดวางข้อมูล และการจัดตารางเวลาฮาร์ดแวร์ ทำให้ศักยภาพด้านประสิทธิภาพจำนวนมากสูญเปล่า

1.2 การเกิดขึ้นและความท้าทายของเทคโนโลยีการเพิ่มประสิทธิภาพขั้นสูงสุด

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

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

Mirage ขยายการเพิ่มประสิทธิภาพขั้นสูงสุดไปยังหลายระดับของการดำเนินการ GPU (เคอร์เนล, thread block, thread) โดยใช้การแสดง μGraph เพื่อรวมการเพิ่มประสิทธิภาพในระดับต่างๆ เข้าด้วยกัน μGraph เป็นการแสดงแบบลำดับชั้น ซึ่งอธิบายโปรแกรมเทนเซอร์ในสามระดับ: กราฟเคอร์เนล, กราฟ thread block และกราฟ thread แต่ละระดับจะระบุวิธีการแบ่งพาร์ติชันหรือคัดลอกเทนเซอร์ในมิติการขนาน รวมถึงขนาดเฉพาะของกริด บล็อก และมิติลูป ผ่าน imap (การแมปอินพุต), fmap (การแมปลูป) และ omap (การแมปเอาต์พุต) การค้นหาหลายระดับของ Mirage สามารถประสานการแปลงพีชคณิตและการแปลงการจัดตารางเวลา สังเคราะห์เคอร์เนลที่กำหนดเองใหม่ทั้งหมด ซึ่งมีประสิทธิภาพ远超กว่าคอมไพเลอร์แบบดั้งเดิม

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

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

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

สอง. การออกแบบหลักของ Prism: กระบวนทัศน์ใหม่ของการเพิ่มประสิทธิภาพขั้นสูงสุดเชิงสัญลักษณ์

Prism เป็นซูเปอร์ออปติไมเซอร์เชิงสัญลักษณ์ตัวแรกของโลกสำหรับโปรแกรมเทนเซอร์ นวัตกรรมหลักคือการเสนอการแสดงกราฟสัญลักษณ์ (sGraph) ซึ่งเข้ารหัสทั้งตระกูลโปรแกรมเป็นโครงสร้างสัญลักษณ์เดียว จึงแบ่งกระบวนการเพิ่มประสิทธิภาพออกเป็นการค้นหาสองระดับ: ระดับบนสร้าง sGraph ระดับล่างทำให้เป็นรูปธรรมเป็นการใช้งานเฉพาะ

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

2.1 ข้อมูลเชิงลึกหลัก: จากการแจกแจงโปรแกรมสู่การเข้ารหัสตระกูลโปรแกรม

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

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

ในขณะที่ใน Prism โปรแกรมที่ใช้โครงสร้างการคำนวณร่วมกันเหล่านี้จะถูกเข้ารหัสเป็น sGraph เดียว โดยที่ขนาดของมิติการขนานและการแมปข้อมูลจะแสดงด้วยตัวแปรสัญลักษณ์ sGraph หนึ่งตัวสามารถแทน μGraph เฉพาะได้หลายพันหรือหลายล้านตัว จึงลดความซับซ้อนของพื้นที่การค้นหาจาก O(N * M * P) เหลือ O(N + M + P) โดยที่ N คือจำนวนโครงสร้างกราฟ M คือจำนวนการจัดสรรการแมป และ P คือจำนวนการกำหนดค่าพารามิเตอร์การขนาน

ข้อดีของวิธีการแสดงนี้ชัดเจน:

1. ลดพื้นที่การค้นหาอย่างมาก: sGraph หนึ่งตัวสามารถแทนทั้งตระกูลโปรแกรม ไม่จำเป็นต้องแจกแจงแต่ละโปรแกรม
2. การอนุมานและการตัดแต่งในระดับสัญลักษณ์: สามารถจับคู่รูปร่างและตรวจสอบความเท่าเทียมในระดับสัญลักษณ์ กำจัดตัวเลือกที่ไม่ถูกต้อง โดยไม่ต้องสร้างโปรแกรมจริง
3. การแยกส่วนความถูกต้องและประสิทธิภาพ: เมื่อ sGraph ได้รับการตรวจสอบว่าถูกต้องแล้ว การทำให้พารามิเตอร์ทั้งหมดเป็นรูปธรรมจะถูกต้องโดยอัตโนมัติ ไม่จำเป็นต้องตรวจสอบอีกครั้ง

2.2 sGraph: การแสดงกราฟแบบลำดับชั้นเชิงสัญลักษณ์

sGraph เป็นส่วนขยายเชิงสัญลักษณ์ของ μGraph ของ Mirage โดยคงโครงสร้างแบบลำดับชั้นของ μGraph (กราฟเคอร์เนล, กราฟ thread block, กราฟ thread) แต่แสดงพารามิเตอร์การขนานและการแมปข้อมูลด้วยตัวแปรสัญลักษณ์ เพื่อทำความเข้าใจการออกแบบของ sGraph ก่อนอื่นเราต้อง回顾แบบจำลองการเขียนโปรแกรม GPU และการแสดง μGraph

การคำนวณ GPU ดำเนินการในหน่วยของฟังก์ชันเคอร์เนล เมื่อเริ่มต้นฟังก์ชันเคอร์เนล จะกำหนดกริดของ thread block แต่ละ thread block จะถูกจัดตารางเวลาให้ดำเนินการบน Streaming Multiprocessor (SM) หนึ่งตัว ภายในประกอบด้วยชุดของเธรด เธรดเก็บสถานะส่วนตัวผ่านรีจิสเตอร์ เธรดภายใน thread block เดียวกันสื่อสารผ่านหน่วยความจำที่ใช้ร่วมกัน ในขณะที่การแลกเปลี่ยนข้อมูลระหว่างฟังก์ชันเคอร์เนลทำผ่านหน่วยความจำส่วนกลาง แบบจำลองการดำเนินการแบบลำดับชั้นนี้ต้องการให้การแสดงโปรแกรมเทนเซอร์สามารถจับภาพความขนานในระดับต่างๆ ได้

μGraph ที่ Mirage เสนอขึ้นเพื่อตอบสนองความต้องการนี้ μGraph เป็นการแสดงแบบลำดับชั้น ซึ่งอธิบายโปรแกรมเทนเซอร์ในสามระดับ:

1. กราฟเคอร์เนล: อธิบายการพึ่งพาระหว่างฟังก์ชันเคอร์เนล
2. กราฟ thread block: อธิบายการคำนวณของแต่ละฟังก์ชันเคอร์เนลในระดับ thread block
3. กราฟ thread: อธิบายการคำนวณของแต่ละ thread block ในระดับ thread

ในแต่ละระดับ μGraph จะระบุวิธีการประมวลผลเทนเซอร์ในมิติการขนานผ่านการแมปสามแบบ

2.2 sGraph: นามธรรมหลักเชิงสัญลักษณ์

ในกรอบงานเชิงสัญลักษณ์ของ Prism ความสัมพันธ์การแมปหลักสามแบบถูกกำหนดใหม่ในรูปแบบเชิงสัญลักษณ์:
* imap: กำหนดวิธีการแบ่งและจัดสรรเทนเซอร์อินพุตไปยังมิติการขนานต่างๆ
* fmap: ระบุว่ามิติการคำนวณแบบลูปสอดคล้องกับมิติการขนานอย่างไร
* omap: อธิบายวิธีการประกอบเทนเซอร์เอาต์พุตจากมิติการขนานต่างๆ

นอกจากนี้ μGraph ยังระบุขนาดเฉพาะของกริด บล็อก และมิติลูปอย่างแม่นยำ ตัวอย่างเช่น μGraph อาจกำหนดว่ามิติกริดเป็นค่าเฉพาะ ซึ่งหมายความว่ามิติแถวของเทนเซอร์อินพุตถูกแบ่งให้ประมวลผลบน thread block 64 ตัว

การขยายเชิงสัญลักษณ์ของ sGraph ต่อ μGraph สะท้อนให้เห็นในสองประเด็นสำคัญดังต่อไปนี้:

1. พารามิเตอร์การขนานเชิงสัญลักษณ์: ใน μGraph แบบดั้งเดิม ขนาดของมิติกริด มิติบล็อก และมิติลูปเป็นจำนวนเต็มคงที่ ในขณะที่ใน sGraph ขนาดเหล่านี้ถูกทำให้เป็นนามธรรมเป็นตัวแปรจำนวนเต็มเชิงสัญลักษณ์ ตัวอย่างเช่น ขนาดของมิติกริดไม่ใช่ตัวเลขเฉพาะอีกต่อไป แต่เป็นตัวแปรเชิงสัญลักษณ์ที่สามารถเปลี่ยนแปลงได้

2. ความสัมพันธ์การแมปเชิงสัญลักษณ์: ใน μGraph imap, fmap และ omap เป็นความสัมพันธ์การแมปเฉพาะ (เช่น imap(A, row) = grid.x) ในขณะที่ใน sGraph ความสัมพันธ์การแมปเหล่านี้แสดงผ่านตัวแปรบูลีน สำหรับแต่ละเทนเซอร์ T แต่ละมิติข้อมูล d และแต่ละมิติการขนาน p ระบบจะแนะนำตัวแปรบูลีน m_{T,d,p} เมื่อ m_{T,d,p} = 1 หมายความว่ามิติข้อมูล d ถูกแบ่งพาร์ติชันตามมิติการขนาน p เมื่อตัวแปร m ที่เกี่ยวข้องทั้งหมดเป็น 0 หมายความว่าเทนเซอร์ T ถูกคัดลอกอย่างสมบูรณ์ในมิติการขนาน p

ตัวแปรเชิงสัญลักษณ์เหล่านี้ต้องเป็นไปตามข้อจำกัดพื้นฐานสองข้อเพื่อให้แน่ใจว่าการแมปมีผล:

โดยที่ ข้อจำกัดแรกกำหนดว่า สำหรับเทนเซอร์ T ที่กำหนด แต่ละมิติการขนาน p สามารถแบ่งพาร์ติชันมิติข้อมูลได้มากที่สุดหนึ่งมิติ ข้อจำกัดที่สองกำหนดว่า แต่ละมิติข้อมูล d สามารถถูกแบ่งพาร์ติชันโดยมิติกริดได้มากที่สุดหนึ่งมิติ ข้อจำกัดทั้งสองนี้ร่วมกันทำให้แน่ใจว่าวิธีการแบ่งพาร์ติชันเทนเซอร์นั้นชัดเจนและไม่ขัดแย้งกัน

จากตัวแปรเชิงสัญลักษณ์เหล่านี้ รูปร่างของเทนเซอร์ก็กลายเป็นนิพจน์เชิงสัญลักษณ์ตามไปด้วย สำหรับมิติข้อมูล d ที่มีขนาดดั้งเดิม D ขนาดในแต่ละ thread block แต่ละ iteration สามารถแสดงเป็น:

size = D / (∏_{p} (1 - m_{T,d,p} + m_{T,d,p} * factor_p))

โดยที่ factor_p แทนจำนวนเท่าทั้งหมดที่มิติข้อมูล d ถูกแบ่งพาร์ติชันโดยมิติการขนาน p

• เมื่อ m_{T,d,p} = 1 เทอมผลคูณคือ factor_p หมายความว่ามิติข้อมูล d ถูกแบ่งพาร์ติชันโดยมิติการขนาน p
• เมื่อ m_{T,d,p} = 0 เทอมผลคูณคือ 1 หมายความว่ามิตินั้นไม่ได้ถูกแบ่งพาร์ติชันโดยมิติการขนาน p

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

เพื่อให้เข้าใจความแตกต่างระหว่าง sGraph และ μGraph ได้อย่างเป็นธรรมชาติมากขึ้น โปรดดูรูปที่ 1 ในเอกสาร:

รูปที่ 1 | การแสดงกราฟของการดำเนินการ Softmax-เมทริกซ์คูณแบบรวม (a) กราฟการคำนวณอินพุต; (b) μGraph เฉพาะที่มีการแมปและพารามิเตอร์การขนานเฉพาะ; (c) sGraph ที่เสนอนี้ ซึ่งการแมปและมิติแสดงด้วยตัวแปรเชิงสัญลักษณ์ การแสดงนี้แสดงให้เห็นถึงความแตกต่างที่สำคัญระหว่าง μGraph แบบดั้งเดิมกับนวัตกรรมหลักของ Prism อย่าง sGraph เผยให้เห็นคุณค่าหลักของการออกแบบเชิงสัญลักษณ์ μGraph แบบดั้งเดิมจะกำหนดมิติกริด มิติบล็อก และการแมปเทนเซอร์เป็นค่าตัวเลขเฉพาะ แต่ละการกำหนดค่าขนานจะสอดคล้องกับกราฟอิสระ ซึ่งนำไปสู่การระเบิดเชิงผสมผสานของพื้นที่การค้นหาตามจำนวนพารามิเตอร์โดยตรง ในขณะที่ sGraph ทำให้พารามิเตอร์การขนานและความสัมพันธ์การแมปเป็นนามธรรมเป็นตัวแปรเชิงสัญลักษณ์ กราฟเดียวสามารถแทนตระกูลของโปรแกรมเทนเซอร์ที่เทียบเท่ากันในแง่ฟังก์ชัน โดยไม่ต้องแจกแจงการกำหนดค่าเฉพาะทีละตัว การออกแบบนี้ช่วยให้ Prism สามารถดำเนินการให้เหตุผลเชิงตรรกะในระดับสัญลักษณ์ ตัดแต่งพื้นที่การค้นหาที่ไม่เหมาะสมที่สุดล่วงหน้า หลีกเลี่ยงคอขวดด้านประสิทธิภาพของวิธีการแจกแจง และวางรากฐานสำหรับการเพิ่มประสิทธิภาพทั่วไปข้ามการกำหนดค่าในภายหลัง ซึ่งเป็นการ突破สำคัญที่ทำให้การเพิ่มประสิทธิภาพขั้นสูงสุดเชิงสัญลักษณ์แตกต่างจากวิธีการในอดีต ตารางที่ 1 | สัจพจน์ความเท่าเทียมบางส่วนที่ใช้ในการตรวจสอบความเท่าเทียมของ sGraph คำอธิบายสัญลักษณ์: t แทนเทนเซอร์, v แทนเวกเตอร์ (แบบ batch), d แทนมิติข้อมูล, p แทนมิติการขนาน ตารางนี้สรุปสัจพจน์ความเท่าเทียมหลักที่ใช้ในขั้นตอนการตรวจสอบของ Prism ซึ่งเป็นรากฐานที่เป็นทางการที่รับประกันความถูกต้องของฟังก์ชันของกราฟสัญลักษณ์ สัจพจน์ครอบคลุมคุณสมบัติพีชคณิตของการคูณเมทริกซ์ กฎการสลับที่ของโอเปอเรเตอร์แบบขนาน เอกลักษณ์การหักล้าง กฎปฏิสัมพันธ์ของโอเปอเรเตอร์แบบขนาน รวมประมาณ 70 กฎ ซึ่ง刻画คุณสมบัติทางคณิตศาสตร์ของการดำเนินการเทนเซอร์และตรรกะการขนานของ GPU อย่างแม่นยำ ตัวอย่างเช่น กฎการแจกแจงของการคูณเมทริกซ์ กฎการสลับที่ของ part และ repl เอกลักษณ์ที่ comb หักล้าง part เป็นต้น ทำให้ e-graph สามารถ推导ความเท่าเทียมของนิพจน์ผ่านกฎการเขียนซ้ำแบบมีทิศทาง การออกแบบสัจพจน์ยึดหลัก “实用优先兼顾严谨” ไม่追求ความสมบูรณ์ทางทฤษฎีแต่ครอบคลุมสถานการณ์การเพิ่มประสิทธิภาพที่สำคัญ หลีกเลี่ยงกฎที่ซ้ำซ้อนซึ่งทำให้ช้าลง ในขณะที่รับประกันความน่าเชื่อถือของผลการตรวจสอบ สนับสนุนการตรวจสอบความเท่าเทียมเชิงสัญลักษณ์ที่มีประสิทธิภาพ

จากรูปที่ 1 จะเห็นว่า (a) คือกราฟการคำนวณดั้งเดิม ซึ่งรวมโอเปอเรเตอร์ Softmax และ Matmul; (b) คือ μGraph เฉพาะ ซึ่งมิติกริดเป็นค่าหนึ่ง มิติลูปเป็นอีกค่าหนึ่ง ความสัมพันธ์การแมปคือ imap(A, row) = grid.x และ omap(C, row) = grid.x; (c) คือ sGraph ที่สอดคล้องกัน ซึ่งขนาดของมิติกริดและมิติลูปถูกแทนที่ด้วยตัวแปรเชิงสัญลักษณ์ D1 และ D2 ความสัมพันธ์การแมปแสดงด้วยตัวแปรบูลีน เช่น m_{A,row,grid.x}, m_{C,row,grid.x} ใน sGraph นี้ การกำหนดค่าใดๆ ให้กับตัวแปรเชิงสัญลักษณ์ที่满足ข้อจำกัด จะสามารถสร้าง μGraph ที่ถูกต้องได้ ตัวอย่างเช่น การกำหนดค่าให้กับตัวแปรเชิงสัญลักษณ์ D1=64, D2=1, m_{A

---

⚠️ หมายเหตุ: เนื้อหาได้รับการแปลโดย AI และตรวจสอบโดยมนุษย์ หากมีข้อผิดพลาดโปรดแจ้ง

☕ สนับสนุนค่ากาแฟทีมงาน

หากคุณชอบบทความนี้ สามารถสนับสนุนเราได้ผ่าน PromptPay

SCAN TO PAY WITH ANY BANK

本文来自网络搜集，不代表คลื่นสร้างอนาคต立场，如有侵权，联系删除。转载请注明出处：https://www.itsolotime.com/th/archives/35314