1991 - 分支預測：推測執行的鑰匙#

案件摘要#

1991 年，Tse-Yu Yeh 與 Yale Patt 發表 two-level adaptive branch prediction：以「分支歷史 × 模式歷史表」讓預測準確率突破 90%，後續演進至 99%+。分支是流水線的天敵——每 5–6 條指令就一個分支，預測錯了整條流水線作廢。分支預測讓推測執行（speculative execution）成為可能，現代 CPU 的性能自此起飛。

前因 -- 為什麼會有這個案子#

流水線的分支代價：分支方向要到執行後段才知道，流水線越深、mispredict penalty 越大：

\[ \text{penalty} = O(\text{pipeline depth}),\qquad \text{每 } 5\text{–}6 \text{ 條指令一個分支} \]

早期預測太笨：static（總是預測不跳）準確率約 60–70%；1-bit bimodal 在迴圈出口連錯兩次。
Tomasulo（1967）已備好引擎：亂序執行能榨 ILP，但分支方向未定時不能推測——差一把鑰匙。
關鍵推理：分支行為有規律（迴圈、錯誤處理），規律就能被學習——用歷史表記住每個分支的「脾氣」：

\[ \text{預測} = f(\underbrace{\text{分支位址}}_{\text{哪個分支}} \times \underbrace{\text{歷史模式}}_{\text{最近行為}}) \]

線索與推理 -- 數學式、程式、理論#

1. 案件現場：預測器演進譜系#

演算法	年代	準確率	原理
static	1970s	60–70%	編譯期決定（向後跳=預測跳）
1-bit bimodal	1980s	85–90%	每分支一個 bit（上次的結果）
2-bit 飽和計數器	1980s	90%	兩次錯才改變預測方向
two-level adaptive	1991	93–97%	歷史模式 × 模式表
gshare/TAGE	1990s–	97–99%+	全域歷史雜湊/標籤式幾何歷史

2. 2-bit 飽和計數器：狀態機的智慧#

每個分支配一個 2-bit 計數器，四個狀態：

\[ \text{ST(強跳)} \rightleftarrows \text{WT(弱跳)} \rightleftarrows \text{WN(弱不跳)} \rightleftarrows \text{SN(強不跳)} \]

預測跳躍當計數器在 ST/WT；執行結果跳躍則計數器加一（飽和到 ST），不跳則減一（飽和到 SN）。
兩次錯才轉向：迴圈出口要連錯兩次才放棄「跳」的預測——比 1-bit 在長迴圈中少一半錯誤。

3. Two-level adaptive：歷史的歷史#

Yeh–Patt 的洞見：分支的行為與最近的執行路徑相關——

\[ \text{PHT}[\underbrace{\text{BHR}}_{\text{最近 } k \text{ 次結果}}] \to \text{2-bit 計數器} \]

BHR（branch history register）：記錄最近 \(k\) 次分支結果的模式（如 0101）。
PHT（pattern history table）：每種模式對應一個 2-bit 計數器——同一分支在不同模式下「脾氣」不同。
例：if (i < 100) 在正常迭代時總是跳、在最後一次不跳——模式表學會分別對待。

4. BTB 與推測執行：鑰匙插進鎖裡#

BTB（branch target buffer）：記住分支的目標位址，預測階段就知道要跳去哪。
推測執行：預測後立刻沿預測路徑執行，mispredict 才回復（ROB 保證精確復原，見 1967-Tomasulo 案）：

\[ \text{IPC} = \frac{1}{1 + p \times \text{penalty}} \quad\xrightarrow{\text{準確率 99\%}}\quad \text{流水線幾乎滿載} \]

代價：推測執行的錯誤路徑會留下痕跡（cache touch）——2018 年 Spectre/Meltdown 攻擊正是從這裡偷資料。

5. Python 實作：預測器準確率比較#

def predict_static(seq):                 # 總是預測「不跳」
    return sum(1 for b in seq if b == 0) / len(seq)

def predict_bimodal1(seq):
    last, ok = 0, 0                      # 初始預測不跳
    for b in seq:
        ok += (last == b)
        last = b
    return ok / len(seq)

def predict_bimodal2(seq):
    ctr, ok = 1, 0                       # 初始弱不跳
    for b in seq:
        pred = 1 if ctr >= 2 else 0
        ok += (pred == b)
        ctr = min(3, ctr + 1) if b else max(0, ctr - 1)
    return ok / len(seq)

def predict_two_level(seq, k=4):         # Yeh–Patt two-level adaptive
    bhr, pht, ok = 0, {}, 0
    for b in seq:
        pred = (pht.get(bhr, 1) >= 2)
        ok += (pred == b)
        c = pht.get(bhr, 1)
        pht[bhr] = min(3, c + 1) if b else max(0, c - 1)
        bhr = ((bhr << 1) | b) & ((1 << k) - 1)
    return ok / len(seq)

seq = [1]*9 + [0] + [1]*9 + [0] + [1]*9 + [0] + [1]*9 + [0]   # 迴圈：9跳1不跳
for name, fn in [('static', predict_static), ('1-bit', predict_bimodal1),
                 ('2-bit', predict_bimodal2), ('two-level', predict_two_level)]:
    print(f"{name:10s} 準確率 = {fn(seq):.0%}")
# static    準確率 = 80%
# 1-bit     準確率 = 69%   ← 每次迴圈出口與入口都錯
# 2-bit     準確率 = 80%   ← 出口只錯一次
# two-level 準確率 = 89%   ← 模式表學會迴圈長度

結案 -- 後果與影響#

推測執行成為標準：Pentium Pro（1995）、PowerPC 604、Alpha 21264——分支預測 + 亂序執行 = 現代 CPU 三本柱。
準確率軍備競賽：gshare（1993）、TAGE（2010s）把準確率推到 99%+，深流水線（20+ 級）才敢建。
Spectre/Meltdown（2018）：推測執行的 side-channel 教訓——性能的鑰匙也開了安全的後門。
理論延續：ML 分支預測（感知器預測器 2001）、ML 引擎預測——源頭都在 1991 這篇論文。

關鍵人物與文獻#

Tse-Yu Yeh、Yale Patt：two-level adaptive branch prediction, ISCA 1991。
James Smith：2-bit 飽和計數器（1981）。
Scott McFarling：gshare 併合預測（1993）。
André Seznec：TAGE 標籤式幾何歷史預測器（2006–2010s）。
相關案件：1967-Tomasulo演算法.md、2002-Simultaneous多執行緒.md、2007-多核心CPU.md。