การประมวลผลนอกลำดับ

การประมวลผลนอกลำดับ (out-of-order execution) ช่วยให้หน่วยประมวลผลสามารถประมวลผลคำสั่งได้ทันทีที่ตัวถูกดำเนินการ (operands) พร้อมใช้งาน แทนที่จะเรียงตามลำดับโปรแกรมอย่างเคร่งครัด โดยใช้การเปลี่ยนชื่อรีจิสเตอร์ (register renaming) และการบัฟเฟอร์ (buffering) เพื่อเปิดเผยความขนาน (parallelism) ในขณะที่ยังคงสร้างผลลัพธ์ตามลำดับ

Definition

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

Scope

หัวข้อนี้ครอบคลุมการจัดตารางเวลาแบบไดนามิก (dynamic scheduling): สถานีสำรอง (reservation stations), การเปลี่ยนชื่อรีจิสเตอร์เพื่อขจัดความขึ้นต่อกันที่ผิดพลาด (false dependencies), บัฟเฟอร์จัดเรียงใหม่ (reorder buffer) ที่บังคับใช้การคอมมิตตามลำดับ (in-order commit) และการกู้คืนการประมวลผลแบบคาดเดา (speculative execution recovery) ซึ่งสร้างขึ้นโดยตรงจากอัลกอริทึมของ Tomasulo ไม่รวมถึงการคาดการณ์ทิศทางของสาขา (branch prediction) และแนวคิดที่กว้างขึ้นเกี่ยวกับปริมาณความขนานที่มีอยู่ (instruction-level parallelism) โดยมุ่งเน้นไปที่กลไกการจัดเรียงใหม่เอง

Core questions

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

Key concepts

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

Key theories

อัลกอริทึมของ Tomasulo

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

ข้อยกเว้นที่แม่นยำผ่านการคอมมิตตามลำดับ

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

Mechanisms

คำสั่งที่ถอดรหัสแล้วจะถูกเปลี่ยนชื่อไปยังรีจิสเตอร์ทางกายภาพ (physical registers) และวางไว้ในสถานีสำรองหรือคิวคำสั่ง (issue queue) ซึ่งจะรอตัวถูกดำเนินการที่ถูกส่งผ่านบัสผลลัพธ์ (result bus) เมื่อพร้อม คำสั่งเหล่านั้นจะถูกประมวลผลบนหน่วยฟังก์ชัน (functional units) ที่ว่างอยู่ตามลำดับใดก็ได้ บัฟเฟอร์จัดเรียงใหม่จะติดตามลำดับโปรแกรมดั้งเดิมและคอมมิตผลลัพธ์ตามลำดับ โดยจะทิ้งผลลัพธ์ที่คาดเดาไว้เมื่อเกิดการคาดการณ์ผิดพลาด (misprediction) หรือข้อยกเว้น (exception) เพื่อให้สถานะทางสถาปัตยกรรม (architectural state) มีความแม่นยำเสมอ

Clinical relevance

การประมวลผลนอกลำดับเป็นกลไกหลักของซีพียูประสิทธิภาพสูง โดยซ่อนความล่าช้าของหน่วยความจำและการประมวลผลโดยการค้นหางานอิสระที่จะทำ นอกจากนี้ยังมีความหมายด้านความปลอดภัย: เนื่องจากการทำงานแบบคาดเดาและนอกลำดับสามารถเข้าถึงข้อมูลชั่วคราวก่อนที่จะถูกยกเลิก ทำให้เกิดการโจมตีแบบช่องสัญญาณข้างเคียงทางสถาปัตยกรรมไมโคร (microarchitectural side-channel attacks) ในตระกูล Spectre และ Meltdown

History

Tomasulo ได้นำเสนอการจัดตารางเวลาแบบไดนามิกใน IBM System/360 Model 91 ในปี 1967 การรวมกันกับบัฟเฟอร์จัดเรียงใหม่สำหรับข้อยกเว้นที่แม่นยำ (precise exceptions) ซึ่งพัฒนาขึ้นในช่วงทศวรรษ 1980 ทำให้การประมวลผลนอกลำดับเป็นไปได้จริงสำหรับหน่วยประมวลผลวัตถุประสงค์ทั่วไป และกลายเป็นมาตรฐานในการออกแบบประสิทธิภาพสูงตั้งแต่กลางทศวรรษ 1990 เป็นต้นมา

Debates

ประสิทธิภาพเทียบกับความซับซ้อน พลังงาน และความปลอดภัย

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

Key figures

• Robert Tomasulo
• Yale Patt
• James E. Smith
• John L. Hennessy

Seminal works

• tomasulo1967
• hennessy2019

Frequently asked questions

หากคำสั่งประมวลผลนอกลำดับ โปรแกรมยังคงถูกต้องได้อย่างไร?

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

การเปลี่ยนชื่อรีจิสเตอร์คืออะไร?

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