暫存器重新命名與 Tomasulo 演算法

必須尊重的真相依，可以化解的假相依

從上一篇你已經知道，亂序執行的目標是：誰的資料先備齊就先跑誰，但結果仍要照程式順序產出。擋路的是相依——但相依並非生而平等。真相依是真正的資料流動：一條指令寫出某個值，後面的指令要讀它。這就是寫後讀相依，再怎麼聰明也不可能在值還沒生出來之前就讀到它。真相依是神聖的，你只能等。

但看看這段類 RISC-V 的小序列。上下兩半其實毫不相干——卻為了 x1 這個名字而打架。指令 2 讀 x1（對指令 1 是真相依，沒問題），但指令 3 想再次寫 x1，而它必須等到指令 2 把舊的 x1 讀完才能動手。這個停頓跟資料流動毫無關係，純粹是搶同一個暫存器名字。這就是假相依——編譯器只是用光了架構暫存器的名字，回頭把一個拿來重用而已。

1:  add  x1, x2, x3     ; x1 = x2 + x3      (writes x1)
2:  mul  x4, x1, x5     ; x4 = x1 * x5      (TRUE dep on 1 via x1)
3:  add  x1, x6, x7     ; x1 = x6 + x7      (wants to reuse the NAME x1)
4:  sub  x8, x1, x9     ; x8 = x1 - x9      (true dep on 3, not on 1)

  Instr 3 & 4 are an independent computation -- only the
  recycled name 'x1' chains them artificially behind 1 & 2.

解開一切的關鍵洞見是：假相依是命名的意外，不是計算的本質。如果指令 3、4 的那個 x1 改用別的暫存器，這兩段計算就能並行。我們不能改程式——架構暫存器 x1 由 ISA 合約釘死了。但硬體內部藏著的實體暫存器，遠比 ISA 對外露出的多。那就讓它悄悄發配全新的實體名字吧。這招就是暫存器重新命名。

暫存器重新命名：每個寫手都拿一個全新的名字

暫存器重新命名握有一池私房實體暫存器——比方說 128 個——遠多於程式設計師看得到的那 32 個架構名字。硬體還維護一張小小的對照表：「現在，架構 x1 住在實體暫存器 p37」。每當一條指令寫某個暫存器，重新命名就配給一個全新的實體暫存器並更新對照表；每當一條指令讀某個暫存器，就查表找出此刻是哪個實體暫存器握著那個值。

看看我們的例子會怎樣。指令 1 寫 x1，於是拿到 p37；對照表現在說 x1 = p37。指令 2 讀 x1，一查，相依於 p37——真相依被原封保留，完全正確。接著指令 3 又寫 x1，但重新命名給它一個全新的 p52，並把對照表更新成 x1 = p52。指令 4 讀 x1，查到 p52，於是只相依於指令 3。兩段計算之間那條假鎖鏈消失了：指令 1-2 在 p37 上幹活，3-4 在 p52 上幹活，完全並行。我們一條指令也沒刪——只是不再讓它們為了一個名字而相撞。

保留站：由資料而非順序說了算的候車室

重新命名拿掉了假相依，但指令仍得等齊自己的真輸入。它們在哪裡等？不是排在一條死板的隊伍裡——那等於把順序又塞回來。取而代之，每個功能單元（ALU、浮點單元、載入／儲存單元）前面都擺著幾個保留站：一個個小格子，存著一條等待中的指令連同它的運算元。回想上一篇的廚房比喻——保留站就是一張備料檯，攥著一張訂單的點菜單，食材一到就慢慢把碗填滿，等最後一樣落定的那一刻立刻開火。

保留站的每個格子，對每個運算元，存的要嘛是值本身（如果已經知道），要嘛是日後會生出它的那個實體暫存器的名字（一個「標籤」）。指令就坐在它的站裡，直到兩個運算元都拿到真實的值，然後「點火」——被送往功能單元去執行。因為點火是由資料就緒觸發，而非由程式位置觸發，一條深埋在程式後段的指令，可以越過前面那條還卡在慢吞吞記憶體載入上的指令。這種由資料驅動的點火，正是動態排程的心臟。

Tomasulo 演算法：標籤、共同資料匯流排，與一次安靜的廣播

把重新命名與保留站綁在一起，你就得到Tomasulo 演算法，由 Robert Tomasulo 在 1967 年為 IBM 360/91 設計，至今仍是亂序核心的觀念核心。它的妙處在於：一個算完的結果如何送達每一個等它的人。當功能單元生出一個值，它不會只寫到某一處、再讓卡住的指令去輪詢。它會把那個值連同它的標籤廣播到一條共用線上，叫做共同資料匯流排。每個保留站同時聆聽；任何等著那個標籤的格子，在同一個週期就抓走那個值。

1. 發射（依序）：取下一條指令，把它的目的暫存器重新命名為一個全新的實體暫存器，放進一個空的保留站——把已備妥的運算元抄進去，對還沒備妥的則記下其生產者的標籤。
2. 等待並監聽：指令坐在站裡，盯著共同資料匯流排。每個週期，只要廣播的標籤對上它正在等的某個標籤，它就把那個值擷取進自己的格子。
3. 執行（亂序）：一旦兩個運算元都握著真實的值、且功能單元有空，指令便點火開算——不管它原本排在程式何處。
4. 寫回結果：把值連同標籤廣播到共同資料匯流排，讓每個等待的保留站——以及暫存器檔——都能一次接住。

這換來什麼，又老實說換不到什麼

把這一切合起來，一條卡住的載入再也不會凍結整台機器。當一條指令在等記憶體時，重新命名與保留站讓它後面的獨立工作得以流經功能單元，把超純量核心真正的指令級平行推高到遠超「只靠前遞的單純依序管線」所能企及。實際上，硬體是在替你的程式即時重新排程，每個週期一次，用的是編譯器永遠拿不到的資訊——每個運算在執行期的真實延遲。

不過要老實面對代價。這整套機械——重新命名對照表、每個站都得監聽的寬幅共同資料匯流排、那些相聯比較、重排序緩衝區——都吃電晶體、吃面積、吃大量功率，而且當你把視窗加寬時，它的成長比線性還糟。它對一條長長的真相依鏈也無能為力：若每條指令都要前一條的結果，根本就沒有平行可挖，再聰明的亂序引擎也快不過依序引擎。正如最後一篇會說明的，這種報酬遞減與功率攀升，正是把整個產業推向多核的ILP 極限。