CPU 與指令執行（進階）：亂序、重新命名與 Tomasulo

一條 add 指令到了現代 CPU 手裡，為什麼會被「拆開」再「重排」？

入門篇裡，我們把 CPU 想成一條乖巧的生產線：依程式計數器(PC, Program Counter)取出指令、解碼、執行，一條接一條，井然有序。這個畫面很適合建立直覺，卻和今天桌上型晶片內部真正發生的事相去甚遠。

真實情況更像一座吵雜的調度場：你寫下的指令一進處理器就被拆解成更細的微操作(micro-op)、貼上臨時編號、丟進一個共享的等待池，誰的輸入先備齊誰就先跑——跑完的順序甚至可能和你寫的順序完全不同。最後再有一個專門的單位負責「假裝一切都是照順序發生的」，把結果按程式原本的次序提交出去。

這篇進階文章要回答一個核心問題：現代 CPU 如何在「對外看起來嚴格照順序執行」與「對內瘋狂亂序、平行、推測」之間取得平衡？ 我們會從指令集架構(ISA)與微架構的分野出發，一路走到暫存器重新命名(register renaming)、Tomasulo 演算法、重排序緩衝區(ROB)，以及分支預測器的內部結構。

兩層抽象：ISA 與微架構

入門篇談的「機器語言」其實對應到一個正式名詞：指令集架構(ISA, Instruction Set Architecture)。它是硬體與軟體之間的契約，規定了有哪些指令、有幾個程式可見暫存器、記憶體如何定址、例外如何處理。x86-64、ARMv8(AArch64)、RISC-V 都是 ISA。

關鍵在於：ISA 只規定「行為」，不規定「怎麼做到」。同一套 x86-64 ISA，Intel 與 AMD 的實作天差地別；同一家公司不同世代的晶片實作也完全不同。這個「怎麼做到」的層次，叫做微架構(microarchitecture)。

這個分野之所以重要，是因為它讓底下的工程師可以為所欲為：只要對外行為符合 ISA 契約，內部要拆指令、亂序、推測、快取都隨意。學習者要建立的核心心智模型是——ISA 是「程式語意」，微架構是「執行策略」，兩者解耦。

CISC 的指令會先被翻成 micro-op

x86 是典型的複雜指令集(CISC)，一條指令可能同時做「從記憶體讀、做運算、寫回記憶體」好幾件事。現代 x86 處理器並不直接執行這種複雜指令，而是在前端(front-end)先把它解碼成一條或多條精簡的微操作(micro-op / µop)，這些 µop 長得很像精簡指令集(RISC)的單純指令。

x86 指令:        add  [rax], rbx     ; 把 rbx 加到記憶體 [rax] 的內容

解碼後的 µop:    load   t1 ← [rax]   ; 讀記憶體到臨時值
                add    t2 ← t1, rbx  ; 相加
                store  [rax] ← t2    ; 寫回記憶體

換句話說，現代「CISC」處理器的執行核心其實是一個 RISC 式的引擎。理解這點，後面所有亂序機制就都建立在「處理器真正調度的是 µop，不是你寫的指令」這個前提上。

真相位元：為什麼要「重新命名暫存器」

入門篇提過資料危障(data hazard)：後一條指令需要前一條的結果。但還有一類危障更隱蔽，它根本不是真正的相依，而是因為暫存器名字不夠用造成的假相依。看這段：

(1) add  r1 ← r2, r3
(2) mul  r4 ← r1, r5     ; 真相依：要等 (1) 的 r1     —— RAW
(3) add  r1 ← r6, r7     ; r1 被重複使用，和 (1) 撞名 —— WAW
(4) sub  r8 ← r1, r9     ; 用的是 (3) 的 r1，不是 (1)  —— WAR / RAW

• RAW（讀後寫，Read-After-Write）：(2) 讀 (1) 寫的 r1。這是真相依(true dependency)，無法消除，本質上資料就是要流過去。
• WAW（寫後寫） 與 WAR（寫後讀）：(3) 又寫了 r1，純粹是因為這顆 ISA 只有 16 個架構暫存器(architectural register)，編譯器被迫重複使用同一個名字。這兩者叫假相依(false / name dependency)——資料其實沒有流動關係，只是名字撞了。

解法是暫存器重新命名(register renaming)：處理器內部其實有遠多於架構暫存器的實體暫存器(physical register)（現代核心常有 100～200 個以上）。每次有指令「寫」一個架構暫存器，就分配一個全新的實體暫存器給它，並更新一張對照表(Register Alias Table, RAT)。

重新命名後（p 開頭是實體暫存器）:
(1) add  p10 ← p2, p3     ; r1 映射到 p10
(2) mul  p11 ← p10, p5    ; 讀 p10（真相依保留）
(3) add  p12 ← p6, p7     ; r1 改映射到 p12 —— 和 (1) 的 p10 完全無關了！
(4) sub  p13 ← p12, p9    ; 讀 p12

WAW 與 WAR 假相依瞬間消失，因為 (1) 和 (3) 現在寫的是不同的實體暫存器。這就是亂序執行能成立的關鍵前置處理：先把名字洗乾淨，剩下的只有真正不可違背的資料流。

Tomasulo 演算法：讓「準備好的」先跑

名字洗乾淨後，µop 被送進保留站(reservation station)——一個等待池。每個 µop 在站裡等它的運算元(operand)到齊；一旦兩個輸入都備妥、又有空閒的功能單元(functional unit)，它就被發射(issue)出去執行，完全不管它在程式裡排第幾。

這套機制源自 1967 年 IBM System/360 Model 91 的 Robert Tomasulo，至今仍是所有亂序處理器的骨架。它的精妙在於用一條共同資料匯流排(CDB, Common Data Bus) 廣播結果：任何功能單元算完，就把「我是 p11、我的值是 42」廣播到所有保留站；正在等 p11 的 µop 一聽到，立刻抓值、湊齊運算元、準備發射。

保留站快照（某個時脈週期）:
┌────┬────────┬───────────┬───────────┐
│ 站 │ 操作   │ 運算元1    │ 運算元2    │
├────┼────────┼───────────┼───────────┤
│ RS1│ mul    │ p10 ✓ =7  │ p5  ✓ =2  │ ← 都到齊，可發射
│ RS2│ add    │ 等 p11    │ p9  ✓ =1  │ ← 卡在 p11，先等
│ RS3│ sub    │ p12 ✓ =5  │ p9  ✓ =1  │ ← 都到齊，可發射
└────┴────────┴───────────┴───────────┘
RS1 與 RS3 可同時發射到兩個 ALU；RS2 等 CDB 廣播 p11 後才動。

注意 RS3（程式中較後面的 sub）可以比 RS2（較前面的 add）先執行——這就是亂序執行(out-of-order execution) 的字面意思。處理器讓資料流(dataflow)決定執行順序，而非程式碼順序。

對外保持秩序：重排序緩衝區(ROB)

問題來了：如果指令亂序完成，萬一中間有一條觸發了例外(exception)、或某個分支預測錯了，怎麼辦？我們不能讓「程式順序上還沒輪到、卻已經搶先算完並改了記憶體」的指令造成不可逆的後果。

解法是重排序緩衝區(ROB, Reorder Buffer)：一個 FIFO 佇列，µop 進入執行前按程式順序在 ROB 尾端登記一個位置，但完成順序任意。一條 µop 即使算完，也只是把結果暫放在自己的 ROB 條目裡，標記為「完成」但尚未提交。

只有當一條 µop 走到 ROB 的最前端（head）、且確認它前面所有指令都已正確提交時，它才被退役(retire / commit)——這一刻它的結果才正式寫進架構狀態（程式可見暫存器、記憶體）。退役嚴格按程式順序進行。

亂序執行，順序退役:

執行完成的時間順序:  C  A  D  B   (亂)
                     ↓
ROB（按程式順序排隊）: A → B → C → D
退役順序:             A  B  C  D   (照程式順序，一個都不能跳)

這個設計達成一個漂亮的雙重目標：內部極致亂序求效能，外部嚴格順序求正確。它也讓「精確例外(precise exception)」成為可能——若 B 發生分頁錯誤(page fault)，處理器只要丟棄 ROB 中 B 之後（C、D）尚未退役的所有結果，狀態就乾淨地停在「A 已完成、B 出錯」，彷彿從未亂序過。

動手算一下：亂序到底快多少

考慮一段有長延遲載入的程式碼。假設 load 要 4 個週期（快取失誤更久），ALU 運算 1 個週期：

(1) load r1 ← [r2]      ; 4 週期
(2) add  r3 ← r1, r4    ; 真相依於 (1)，必須等
(3) mul  r5 ← r6, r7    ; 與 (1)(2) 完全無關
(4) sub  r8 ← r6, r9    ; 與前面都無關

順序執行(in-order)：嚴格照順序，(2) 卡住等 (1) 的 4 個週期時，(3)(4) 只能乾等。

週期:   1   2   3   4   5   6   7
(1)    [--- load 4 週期 ---]
(2)                        add
(3)                             mul
(4)                                  sub
總計約 7 個週期

亂序執行(out-of-order)：(2) 在等 (1) 時，獨立的 (3)(4) 趁機填補空檔先跑：

週期:   1   2   3   4   5
(1)    [--- load 4 週期 ---]
(3)     mul
(4)         sub
(2)                        add
總計約 5 個週期

加速並非來自指令變快，而是來自把因相依而閒置的空檔(bubble)用獨立指令填滿。能填多滿，取決於程式裡有多少指令級平行度(ILP, Instruction-Level Parallelism)可挖。這也解釋了為何亂序窗口(ROB 大小)是現代核心的關鍵規格——窗口越大，越能往後看到更多獨立指令來填空。

分支預測：賭對了免費，賭錯了很貴

入門篇提過控制危障：在分支(branch)解出方向前，不知道下一條該取哪裡。亂序機器的管線又深又寬，一次預測失敗要清掉的 µop 多達數十條，懲罰極重。所以現代 CPU 的分支預測器(branch predictor) 做得極其精巧，準確率常達 95% 以上。

最基礎的構件是 2 位元飽和計數器(2-bit saturating counter)。它用四個狀態記錄「最近這個分支傾向跳或不跳」，避免單次反例就立刻翻盤：

狀態機（每個分支位址配一個計數器）:

  強烈不跳 ⇄ 弱不跳 ⇄ 弱跳 ⇄ 強烈跳
   (00)      (01)    (10)    (11)
   預測:不跳         |  預測:跳

跳了 → 往右移一格（更傾向跳）
不跳 → 往左移一格（更傾向不跳）

關鍵設計：要連續猜錯兩次才會改變「跳/不跳」的預測方向。對一個跑 1000 次、只有最後一次跳出的迴圈，2 位元計數器全程只錯 1 次（最後跳出那次），遠優於「看上一次」的 1 位元預測器。

現代預測器更進一步引入歷史關聯：用一個全域歷史暫存器(GHR, Global History Register)記錄最近 N 個分支的實際走向，把這段歷史與分支位址雜湊後，去查一張型樣歷史表(PHT, Pattern History Table)。這樣即使是相關聯的分支（例如 if (x>0) ... if (x>0) ...）也能被準確預測。實務上的 TAGE、感知器(perceptron)預測器都屬此類進階設計。

預測對了，目標位址由分支目標緩衝區(BTB, Branch Target Buffer) 提供，管線無縫往下走；預測錯了，沿錯誤路徑推測執行(speculative execution)的 µop 全部從 ROB 中作廢，回到正確路徑重來——這就是入門篇提到的清空(flush)懲罰。

重點回顧

• ISA 與微架構解耦：ISA 是對外的行為契約（x86、ARM、RISC-V），微架構是內部實作策略；同一 ISA 可有天差地別的實作。
• 現代處理器把指令（尤其 CISC）拆成 µop 來調度，執行核心本質上是 RISC 式引擎。
• 暫存器重新命名消除 WAW/WAR 假相依，把問題化約為不可違背的真資料流，是亂序執行的前提。
• Tomasulo + 保留站 讓運算元到齊的 µop 先發射，由資料流而非程式順序決定執行次序；ROB 則保證退役嚴格按程式順序，達成「內部亂序、外部有序、例外精確」。
• 分支預測器（2 位元飽和計數器、GHR+PHT、BTB）讓深管線在面對控制危障時仍能高吞吐運行，預測錯誤的代價是管線清空。

深入探討（研究所視角）

把上述機制串起來，現代高效能核心的真實面貌是：前端（取指、分支預測、解碼成 µop）→ 重新命名（RAT 分配實體暫存器）→ 亂序引擎（保留站、ROB、多個功能單元）→ 退役（按序提交）。值得在研究所層次延伸的幾個方向：

記憶體亂序與一致性(memory consistency)。 暫存器的相依靠重新命名解得很乾淨，但記憶體位址要到執行期才算得出來，使得 load/store 之間的相依變成模糊問題。處理器用載入/儲存佇列(load/store queue) 與記憶體相依預測(memory dependence prediction) 來推測「這個 load 是否與前面某個未完成的 store 撞址」，猜錯就得回滾。更深一層，不同 ISA 定義了不同的記憶體模型(memory model)：x86 採較強的 TSO(Total Store Order)，ARM/RISC-V 採較弱的鬆散順序(weak ordering)，這直接影響多執行緒程式何時需要插入記憶體屏障(memory barrier / fence)。這是並行程式設計正確性的硬體根基，連結到 C++/Java 的記憶體模型與 std::atomic 的記憶體序語意。

超純量與 SMT。 入門篇提到超純量(superscalar)可在單週期發射多條指令；當單執行緒的 ILP 被榨乾、功能單元仍有空閒時，同時多執行緒(SMT, Simultaneous Multithreading；Intel 稱 Hyper-Threading) 讓兩個硬體執行緒共享同一套執行資源，用執行緒級平行(TLP)填補 ILP 留下的空檔。代價是共享資源（快取、保留站）的競爭，以及——如下——安全邊界的模糊。

推測執行的安全代價，再訪。 入門篇點到 Spectre/Meltdown。從本篇的機制看會更透徹：問題正出在「推測執行的 µop 即使最終在 ROB 被作廢、架構狀態完好回滾，它在快取等微架構結構留下的痕跡卻不會回滾」。攻擊者誘導處理器沿錯誤路徑推測載入機密資料、用它索引一塊陣列，再透過快取時序(cache timing)側通道把值還原出來。這揭示一個深刻的張力：ISA 契約只保證架構狀態的正確，卻從未承諾微架構狀態不洩漏資訊。後續的緩解（如推測載入硬化、站點隔離）與新研究方向（不可見推測, invisible speculation）都圍繞這條縫隙。理解這類議題的價值在於建立正確的系統設計與防禦觀念，相關探究應於合法、受控的研究環境中進行。

效能上限與 Amdahl 視角。 亂序窗口、發射寬度、預測準確率三者共同決定可達 IPC，但回報遞減：把 ROB 從 200 加到 400 條目，能多挖到的獨立指令越來越少（程式內在 ILP 有限）。這把效能戰場從「單核更寬更深」推向「多核 + 向量(SIMD) + 異質運算(GPU/NPU)」。你會發現入門篇結尾那句話再次應驗——「如何讓更多單元同時忙碌、又維持正確性」這個命題，從單條管線、到亂序窗口、到多核一致性、到資料中心級的分散式系統，只是換了尺度反覆登場。掌握本篇的 µop 調度與 ROB 退役模型，等於拿到了一把能貫穿所有尺度去思考「平行 vs. 正確」的鑰匙。