分岐予測 (TAGE / Perceptron)（ブランチプリディクタ）
条件分岐の結果を予測するCPU回路。TAGE (Tagged Geometric History Length) / Perceptron (神経網) ベースで95-99% 精度、投機実行効率を決定する核心技術。
概要
分岐予測 (Branch Prediction) は条件分岐 (if / switch / for / while ループ) の結果 (Taken / Not Taken / 分岐先アドレス) を分岐命令確定前に予測するCPU回路。OoO 実行で投機実行を成立させる前提技術、誤予測すると ROB Flush で15-25 cycles ペナルティ→ 性能直撃するため現代CPU の最重要要素の1つ。
分岐予測世代
| 世代 | 年 | アルゴリズム |
|---|---|---|
| 静的 | 1985- | コンパイラヒント |
| 2bit Counter | 1991 | 飽和カウンタ |
| 2-level Adaptive | 1992 | BHT (Branch History Table) |
| GShare | 1993 | グローバルパターン |
| Hybrid / Tournament | 1996 | 複数予測器選択 |
| TAGE | 1999 | Tagged Geometric History |
| Perceptron | 2001 | 神経網 (線形分類器) |
| TAGE-SC-L | 2014 | TAGE + Statistical Corrector |
| ITTAGE | 2014 | 間接分岐用TAGE |
| Hashed Perceptron | 2016 | 改良神経網 |
TAGE (Tagged Geometric History Length)
Andre Seznec (INRIA Rennes) が1999年提唱した分岐予測技術。複数の幾何級数的に異なる長さの履歴 (e.g. 4 / 16 / 64 / 256 bit) を持つテーブルを並列参照、最長一致 (longest match) をベース予測に使う設計。Champions of Branch Prediction (CBP) で2014-2024 連続優勝、現代CPU の主流アルゴリズム。
Perceptron Predictor
Daniel Jiménez (UC Santa Barbara) が2001年提唱した神経網ベース予測器。分岐履歴を入力ベクトル → Perceptron (重み付線形分類器) で予測。長い履歴 (256+ bit) を扱いやすく、特定パターンで TAGE より高精度。AMD Bulldozer (2011) で初商業実装、Zen 系列で発展。
主要CPU の分岐予測
| CPU | 採用 |
|---|---|
| Apple M3 / M4 | TAGE-SC-L 系・8 KB BTB |
| Intel Lion Cove | Hashed Perceptron + ITTAGE |
| Intel Skymont (E-core) | TAGE-SC + BTB |
| AMD Zen 5 | Perceptron + TAGE Hybrid・改良版 |
| AMD Zen 4 | Perceptron + TAGE |
| ARM Neoverse V2 | TAGE + Perceptron |
予測対象 4要素
- 方向予測 (Direction): Taken / Not Taken
- 分岐先予測 (Target): Branch Target Buffer (BTB)
- 戻り先予測 (Return): Return Address Stack (RAS)
- 間接分岐 (Indirect): 関数ポインタ / vtable
誤予測ペナルティ
- 投機実行されたROB エントリ全てFlush
- フェッチパイプ Re-fill: 15-25 cycles
- 分岐密度の高いコード (インタプリタ / 仮想関数 / switch) で性能差大
- Spectre v2 緩和策 (Retpoline) は意図的 IBPB (Indirect Branch Prediction Barrier) 挿入で5-30%遅化
関連用語との違い
- vs OoO: OoO は実行・分岐予測は前段
- vs JIT: JIT は実行時最適化 / 分岐予測は HW
- vs PGO: コンパイラ最適化 / HW 動的予測
FAQ
Q1: 何%精度? A: TAGE-SC-L で95-99%。SPEC2017 平均 約96-98%。エンタープライズアプリ (Java / .NET) は分岐パターン複雑で90-95%。
Q2: Spectre 攻撃との関係? A: 投機実行で分岐先のメモリ参照が L1 キャッシュに残るのを利用したサイドチャネル攻撃。分岐予測の信頼性が裏目に。
Q3: 性能向上はどれくらい? A: 分岐予測なしで実行すると現代CPU 性能の20-30%しか出ない。IPC 8 → 2 程度に低下。