การคาดคะเนการแยกสายงาน (Branch Prediction)

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

Definition

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

Scope

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

Core questions

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

Key concepts

• การคาดคะเนแบบสถิตเทียบกับแบบไดนามิก
• ตัวนับแบบอิ่มตัวหนึ่งและสองบิต
• ประวัติการแยกสายงานและความสัมพันธ์
• ตัวคาดคะเนแบบทัวร์นาเมนต์
• บัฟเฟอร์เป้าหมายการแยกสายงาน
• ค่าปรับจากการคาดคะเนผิดพลาด
• การดึงข้อมูลแบบคาดเดา

Key theories

การคาดคะเนแบบไดนามิกที่อิงตามประวัติ

ผลลัพธ์ของการแยกสายงานมีความสัมพันธ์สูงกับพฤติกรรมในอดีตของตนเองและของสาขาอื่น ๆ; ตัวคาดคะเนที่บันทึกประวัติในตัวนับแบบอิ่มตัวและรวมประวัติแบบท้องถิ่นและแบบโดยรวม (ตัวคาดคะเนแบบสัมพันธ์และแบบทัวร์นาเมนต์) มีความแม่นยำสูงมาก

Mechanisms

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

Clinical relevance

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

History

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

Key figures

• James E. Smith
• Yale Patt
• Tse-Yu Yeh
• John L. Hennessy

Seminal works

• hennessy2019
• patterson2020

Frequently asked questions

เกิดอะไรขึ้นเมื่อการแยกสายงานถูกคาดคะเนผิดพลาด?

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

ตัวคาดคะเนการแยกสายงานสมัยใหม่มีความแม่นยำเพียงใด?

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