為什麼管線化還不夠#
上一章看到管線化可以大幅提升 CPU 吞吐量，但也提到「管線越長，問題越多」。本章就把焦點放在管線上常見的三類「潛在傷害（Hazards）」，以及它們對應的解決機制——其中最關鍵的就是分支預測（Branch Prediction）。
Hazards 的三大分類#
Structural Hazards（結構性）#
在同一個 Clock Cycle 中，若 pipeline 有兩個以上的指令需要使用同一個資源（例如同一個 ALU、記憶體 port），便會產生 Structural Hazards。後面的指令必須延後放入流水線，造成處理器無法在理想狀況下運行（一個 cycle 一條指令）。這個現象又稱為流水線泡沫化（pipeline bubble）。
避免方法：
- 在處理器設計階段考慮設置兩個以上的 Data Unit 處理指令與資料的記憶體操作
- 將 Instruction 與 Data 的快取區隔開（哈佛架構式的分離）
Data Hazards（資料相依性）#
假設有兩個算術指令 ADD 與 SUB，且 SUB 的輸入是 ADD 的輸出。若 SUB 在執行時 ADD 處理的結果還沒寫回暫存器，便會造成 Data Hazards。
Forwarding（資料前推）#
若不希望兩個指令中間有太多閒置週期，可以利用 Forwarding 解決：不等到第一個指令把結果寫回，直接在第一個指令完成 Execution 時把結果傳給第二個指令的 Execution input。
Load-Use Data Hazards#
Forwarding 不能解決所有問題。若第一個指令是 Load 類型，必須等到 Memory Access 階段才能 Forward 給後一個指令的 Execution，這時仍會出現 1 個 bubble。
編譯器幫忙做 Code Re-Ordering#
我們日常開發所使用的編譯器都會對程式做 Code Re-Ordering 以減少泡沫化。簡單舉例：
int a = b + e;
int c = b + f;若按程式碼邏輯逐步執行：
- 讀取 b 變數值，放到 register 1
- 讀取 e 變數值，放到 register 2
- 把 register 1 + register 2，放到 register 3
- 把 register 3 寫回記憶體
- 讀取 f 變數值，放到 register 4
- 把 register 1 + register 4，放到 register 5
- 把 register 5 寫回記憶體
即使有 Forwarding，仍會在 2/3 之間以及 5/6 之間產生泡沫化，總共需要 13 個 Clock Cycle 才能完成。
計算方式：第一個指令需要等待完整的流水線週期 5 + 之後每個指令各需 1 個週期共 6 + 兩次泡沫化各 1 = 5 + 6 + 2 = 13。
而聰明的編譯器會做重排：
- 讀取 b 變數值，放到 register 1
- 讀取 e 變數值，放到 register 2
- 讀取 f 變數值，放到 register 4
- register 1 + register 2，放到 register 3
- register 3 寫回記憶體
- register 1 + register 4，放到 register 5
- register 5 寫回記憶體
搭配 Forwarding 就可以避免泡沫化，加速程式碼運作。
Control Hazards（控制相依性）#
Control Hazards 發生在處理器被要求做條件分支時。需要等到條件被計算出來才知道要執行的下一條指令位置——但管線早已預先 fetch 了「猜測中的下一條指令」。如果判斷錯誤，會造成暫存器資料改變需要還原，且必須對 pipeline 做清空，十分浪費效能。
這就是 Branch Prediction 出場的時機。
Branch Prediction（分支預測）#
主要分為兩類。
Static Branch Prediction#
靜態分支預測不會根據條件動態調整策略。常見規則：
- loop 一律猜測會往後跳（backward branch is taken）：因為
while、for等迴圈通常重複執行一次以上，假設它一定會向後跳轉，只要迴圈執行超過兩次就能出現成效。 - if-else 一律猜測不會跳轉（forward branch is not taken）：不論一個或多個條件分支，只有一個分支會被執行，其他不符合條件的分支都是向前跳轉。
名詞釐清：
- 向前跳轉：跳轉後的位置 > 目前指令位置
- 向後跳轉：跳轉後的位置 < 目前指令位置（也就是往回跳）
Dynamic Branch Prediction#
動態分支預測會根據不同的使用情況做出調整。假設程式碼當中用了 100 次 BEQ 條件轉跳指令，動態分支預測會為這 100 個 BEQ 指令個別建立歷史紀錄。
這麼做的原因：不同的 BEQ 比較條件不盡相同，若 100 個指令都參照同一個歷史紀錄，會造成大量錯誤預測，導致處理器需要反覆清空流水線。
二位元飽和計數器#
現今處理器多採用動態分支預測，本節以最簡單的飽和計數器（saturating counter）為例。
計數器有 4 個狀態：
| MSB | LSB | 狀態 |
|---|---|---|
| 0 | 0 | Strongly not taken |
| 0 | 1 | Weakly not taken |
| 1 | 0 | Weakly taken |
| 1 | 1 | Strongly taken |
預測規則：
- 若
MSB == 0：預測不轉跳 - 若
MSB == 1：預測會轉跳
這樣設計的好處是：不會因為犯錯一次就改變想法。假設原本預測不轉跳，必須要連續猜錯兩次才會切換到「會轉跳」這一側。
如果設計者希望計數器猜錯更多次才改變想法，可以將計數器從 2-bit 增加至 3-bit 或更多。不過，一昧增加位元不一定能帶來更好的效能，必須與工作負載特性配合。
重點整理#
- Pipeline 雖然加快吞吐，但伴隨三種 Hazards：結構性、資料、控制。
- Forwarding + Code Re-Ordering 可緩解 Data Hazards。
- Control Hazards 必須靠分支預測；現代 CPU 多用動態分支預測 + 飽和計數器，並結合 BTB（Branch Target Buffer）等結構。
- 飽和計數器的核心精神：「兩次錯才願意改主意」，避免被偶發錯誤帶歪。
原文出處#
- 原書/iThome：https://ithelp.ithome.com.tw/articles/10265705