分岐予測の仕組み ─ 2bitカウンタからTAGEまで

なぜ分岐を「予測」しなければならないか

パイプライン化されたCPUは、ある命令を実行している最中に後続命令のフェッチ・デコードを先行して進めます。ところが条件分岐は、その条件がパイプラインの後段（実行ステージ）で計算されて初めて方向が確定します。フェッチ段から見れば「次にどのアドレスを取りに行くか」が、数サイクル先まで分からないわけです。

ここで分岐の確定を待って止まれば、毎回その分のサイクルが空きます。プログラムの数命令に1回は分岐があるため、待っていてはパイプラインが頻繁に空転します。そこで分岐予測で結末を当て、当たった前提で投機的にフェッチを続けます。当たれば停止ゼロ、外れたら後述のフラッシュで取り消す――この賭けの精度こそが実効IPCを左右します。

誤予測のコストが精度を要求する

予測を外すと、誤った経路で投機実行した命令をすべて破棄し、正しい経路から取り直します。これがパイプラインフラッシュです。

精度が性能をどう削るかは概算できます。分岐の頻度を5命令に1回、誤予測ペナルティを15サイクルとすると、予測精度が95%なら命令あたり 0.2 × 0.05 × 15 = 0.15 サイクルの損失、99%なら 0.2 × 0.01 × 15 = 0.03 サイクルです。わずか4ポイントの精度差が、5倍の浪費差になります。だからこそ予測器は1%を削るために複雑化してきました。

2bit飽和カウンタ ── 予測の最小単位

最も基本的な予測は、分岐ごとに2bit飽和カウンタを持つ方式です。値は「強Not-Taken／弱Not-Taken／弱Taken／強Taken」の4状態で、Takenなら+1、Not-Takenなら−1し、両端で飽和（それ以上動かない）します。上位ビットが予測（Takenかどうか）です。

00 強NT ─Taken→ 01 弱NT ─Taken→ 10 弱T ─Taken→ 11 強T
 ↑__NotTaken___|___NotTaken___|___NotTaken___|
予測 = 上位ビット（0:NotTaken / 1:Taken）

1bit（直前の結果をそのまま予測）だと、ループの最後で1回外し、次のループ初回でまた外す「二重ミス」が起きます。2bitなら1回の例外では予測が反転しないため、ループのような偏った分岐に強くなります。この履歴を集めた表を**PHT（Pattern History Table）**と呼びます。

履歴で索引する ── gshareと相関予測

2bitカウンタは「この分岐は普段どうか」しか見ません。しかし実際の分岐は、直前の他の分岐がどうだったかと相関することが多くあります（例：if (x) ... if (x) ... のように同じ条件が連動する場合）。

そこで**グローバル履歴レジスタ（GHR）**に直近N個の分岐結果をビット列として保持し、これをPHTの索引に使います。gshareは、分岐アドレスとGHRを XOR して索引を作る代表的な方式です。

index = (分岐PC) XOR (グローバル履歴GHR)
PHT[index] の2bitカウンタで予測

アドレスと履歴を混ぜることで、同じ履歴でも分岐ごとに別エントリへ散らし、限られた表を有効活用します。ただしXORは衝突（別々の分岐が同じエントリを共有するエイリアシング）を完全には防げず、これが精度の頭打ちの一因になります。

トーナメント予測 ── 得意を使い分ける

分岐には、自身の履歴（ローカル）が効くものと、他分岐との相関（グローバル）が効くものが混在します。どちらか一方では取りこぼします。

トーナメント予測は、ローカル予測器とグローバル予測器を両方走らせ、**メタ予測器（選択器）**が「この分岐では最近どちらが当たっているか」を2bitカウンタで覚えて採用側を切り替えます。Alpha 21264が採用したことで知られ、単一方式の弱点を補い合う構成として広く影響を与えました。

TAGE ── 可変長履歴を競わせる

現代の高性能コアの主力が**TAGE（TAgged GEometric history length）**です。核心は、幾何級数的に異なる長さの履歴で索引する複数のテーブルを並べ、最も信頼できるものを選ぶ点にあります。

各テーブルは「短い履歴で索引する表」「やや長い履歴の表」…と、履歴長が 4, 8, 16, 32, … のように伸びていきます。各エントリは予測カウンタに加えてタグ（その履歴に本当に対応するかの照合用）と**有用度（useful）**ビットを持ちます。

予測時:
  ベース予測器（履歴なしの2bit表）が既定値を出す
  各TAGEテーブルをタグ照合し、ヒットした中で
  「最も長い履歴で索引した表」の予測を採用する
学習時:
  外したら、より長い履歴の表に新エントリを割り当てて
  次回はその長い文脈で当てにいく

短い履歴で足りる分岐は短い表で当て、長い文脈が要る難しい分岐だけ長い履歴の表に任せる――この長い履歴ほど優先という原理で、必要な分岐にだけ長文脈を使い、表を無駄なく配分します。タグ照合で誤った文脈の流用（エイリアシング）を抑えられるのも、gshareに対する大きな改善点です。

方向だけでなく「飛び先」も当てる

方向（Taken/Not-Taken）を当てても、Takenならどこへ飛ぶかが分からなければフェッチを続けられません。これを供給するのが次の2つです。

• BTB（Branch Target Buffer）：分岐PCをキーに、その分岐の飛び先アドレスをキャッシュする表。フェッチ段で「この命令は分岐か、飛び先はどこか」を1サイクルで引けるようにする。BTBミスやキャッシュ同様の容量制約は、それ自体が遅延要因になる。
• RAS（Return Address Stack）：関数の戻り先専用の小さなLIFOスタック。call で戻り先をプッシュ、return でポップして飛び先を予測する。戻り先は呼び出し元ごとに変わるためBTBでは当てにくく、専用スタックが効く。

まとめ

• 分岐方向は後段でしか確定しないため投機実行が必要で、誤予測のフラッシュ（十数サイクル）がIPCを直接削る。精度1%の差が浪費を大きく変える。
• 予測は2bit飽和カウンタ（PHT）を起点に、グローバル履歴で索引するgshare、得意を使い分けるトーナメント、可変長履歴を競わせるTAGEへと精度を高めてきた。
• 方向予測に加え、飛び先をBTBが、関数の戻り先をRASが供給し、間接分岐にはITTAGE等を使う。これらが揃って投機実行が成立する。
• 予測器の改良はエイリアシング削減と長相関の安価な捕捉に集約され、深いパイプラインと広い投機を支える土台になっている。