亂序執行

在電腦工程領域，亂序執行（錯序執行，英語：out-of-order execution，簡稱OoOE或OOE）是一種應用在高效能微處理器中來利用指令周期以避免特定類型的延遲消耗的範式。在這種範式中，處理器根據輸入資料的可用性確定執行指令的順序，而不是根據程式的原始資料決定。在這種方式下，可以避免因為取得下一條程式指令所引起的處理器等待，取而代之的處理下一條可以立即執行的指令。

歷史

亂序執行是一種受限的資料流架構計算的方式，在20世紀70年代至80年代資料流架構計算是電腦架構的重要研究領域。在這個課題上重要的學術研究是由Yale Patt以及他的HPSm模擬器所領導。一篇由James E. Smith和A.R. Pleszkun在1985年所發表的論文通過精確的描述了在亂序執行的機器上會發生的異常行為，從而完善了該模式。

通常認為第一台使用亂序執行的電腦是CDC 6600（1964），使用了scoreboard來處理衝突。在現代的實現方式中，這種的記分板被認為是順序執行的組成部分，而不是亂序執行，儘管這樣的機器等待第一個寫後讀的衝突。嚴格的說，這樣的機器啟動在順序執行的方式下，但是有可能結束於亂序執行之中。

大約三年後，IBM的360/91（1966）引入了Tomasulo演算法，從而支援了完全的亂序執行。

在1990年，IBM發布了第一個支援亂序執行的微處理器，POWER1，儘管亂序執行被限制於浮點數計算上。

在整個20世紀90年代中，亂序執行變得更加普遍並且在IBM/Motorola PowerPC 601（1993）, Fujitsu/HAL SPARC64（1995）, Intel Pentium Pro（1995）, MIPS R10000（1996）, HP PA-8000（1996）, AMD K5（1996）和DEC Alpha 21264（1998）中被使用。較為知名的未採用亂序執行的處理器有Sun UltraSPARC, HP/Intel Itanium, Transmeta Crusoe, Intel Atom，以及IBM POWER6。

亂序執行模式的邏輯複雜度是造成該技術在20世紀90年代之前沒有成為電腦的主流的原因。許多低階的處理器受限於市場成本仍然未採用該範式，因為製造亂序執行的電腦需要大型的矽片。低能耗是另一種難以用亂序執行設計所實現的目標。

基本概念

循序執行

主條目：指令周期

在早期的處理器中，指令的執行一般在以下的步驟中完成：

1. 指令取得。
2. 如果輸入的運算對象是可以取得的（比如已經存在於暫存器中），這條指令會被傳送到合適的功能單元。如果一個或者更多的運算對象在當前的時鐘周期中是不可取得的（通常需要從主記憶體取得），處理器會開始等待直到它們是可以取得的。
3. 指令在合適的功能單元中被執行。
4. 功能單元將運算結果寫回暫存器。

亂序執行

這種範式通過以下步驟挑選可執行的指令先執行：

1. 指令取得。
2. 指令被傳送到一個指令序列中（也稱執行緩衝區或者保留站）。
3. 指令將在序列中等待直到它的資料運算對象是可以取得的。然後指令被允許在先進入的（較舊的）指令之前離開序列緩衝區。
4. 指令被分配給一個合適的功能單元並由之執行。
5. 結果被放到一個序列中。
6. 僅當所有在該指令之前的指令都將他們的結果寫入暫存器後，這條指令的結果才會被寫入暫存器中。這個過程被稱為畢業或者退休周期。

亂序執行的重要概念是實現了避免電腦在用於運算的對象不可取得時的大量等待。在上述文字的要點中，亂序執行處理器避免了在順序執行處理器處理過程第二步中當指令由於運算資料未到位所造成的等待。

例如

1. b = a * 5
2. v = *b
3. c = a + 3

由於1與3可並行執行，而2之b無法隨即獲得，因此可以先計算乘法1與加法3，再執行2。

亂序執行使用其他「可以執行」的指令來填補了時間的空隙，然後再在結束時重新排序運算結果來實現指令的順序執行中的執行結果。指令在原始電腦代碼中的順序被稱為程式順序，在處理器中他們被按照資料順序中被處理，這種順序中，資料，運算子，在電腦暫存器中變得可以取得。一般來說亂序執行需要複雜的電路來實現轉換一種順序到另一種順序並且維護在輸出時的邏輯順序；而處理器本身就好像是隨機執行的樣子。

亂序執行所帶來的益處隨著指令管道的加深和主記憶體（或者快取）和處理器間的速度差的變大而增長。在現代電腦中，處理器的運算速度大大超越了主記憶體速度，所以在順序執行處理器等待資料的過程中，亂序執行處理器能夠執行大量的指令。

傳送以及分配的分離實現了亂序執行

一個由新的範式所造成的區別是傳送步驟從分配步驟中分離的序列的產生和畢業周期從執行周期中分離的產生。這種範式的一個早期的名稱是"分離架構"。在早期的順序執行處理器中，這些周期在一種相對固定的，管道化的方式中被執行。

為了避免錯誤的運算對象造成的指令亂序的減少，一種被稱作暫存器重新命名的技術被採用了。在這種模式中，將會有更多的暫存器被架構所定義。物理暫存器被加上標籤從而不同架構的暫存器可以同時存在。

執行和寫回的分離允許程式重新開始

結果序列是解決分支預測錯誤以及異常/中斷的必要部分。結果序列允許程式程式在一個異常後重新開始，這需要指令在程式順序中被完成。結果序列允許結果由於一個錯誤的分支預測以及發在在舊代碼上的異常被丟棄。

把指令分配到過去的分支的能力解決了預測執行。

微架構的選擇

• 執行應該被傳送到一個集中的序列還是分布的序列中？

IBM PowerPC處理器採用了分布在不同的功能單元中的序列而其他的處理器採用了集中式的序列。IBM使用了術語「reservation stations」來描述他們的分散式序列。

• 是否有一種即時的結果序列或者運算結果否則可以直接被寫回暫存器？對於後者，序列的功能是由暫存器對映所處理，暫存器對映可以處理用於每條指令過程中的存器重新命名資訊。

早期的英特爾亂序處理器使用一種名為re-order buffer的結果序列，同時大部分之後的亂序處理器都使用了暫存器對映表。

更精確的說：英特爾P6類型的微處理器都同時具有一個ROB re-order buffer和一個暫存器對映表的機制。ROB主要是由分支錯誤預測恢復所推動。

英特爾P6類型的處理器是最早期的亂序執行處理器之一，但是被Intel Pentium 4 Willamette微架構所替代。多年後Intel Pentium 4 Willamette被證明是一個錯誤的由於效能和發熱的問題，這一點迫使英特爾回到了P6架構設計並重新開始。結果便是誕生了酷睿，酷睿2和Sandy Bridge系列處理器以及Ivy Bridge系列。

參見

• Scoreboarding
• Tomasulo algorithm
• Replay system
• Dataflow architecture

深度閱讀

• Smith; Pleszkun. Implementation of precise interrupts in pipelined processors. Proceeding ISCA '85 Proceedings of the 12th annual international symposium on Computer architecture. 1985. doi:10.1145/327010.327125.