# 分岐予測 パイプライン化されたプロセッサが条件分岐命令の結果を**事前に推測し**、正しいパスの命令を投機的に実行しておく機構。分岐は平均 6 命令に 1 回程度現れるため、予測なしではパイプラインが頻繁に空になる。 ## 問題の本質 深いパイプラインでは、条件分岐命令が実行ステージに達するまでに数サイクルかかる。その間に後続命令をフェッチ・デコードしなければならないが、どちらのパスを進むかは分岐結果が判明するまで不明。 **誤予測ペナルティ**: 予測が外れると投機的に処理した命令をすべてキャンセルし、正しいパスからやり直す。Pentium Pro/II/III(12 段)では 10〜15 サイクルのペナルティが生じ、90% の予測精度でも約 30% の性能損失につながった。 ## 予測手法 ### 静的分岐予測 コンパイラがコンパイル時に予測ビットを命令に埋め込む、またはヒューリスティックに従う(例:後退分岐=ループバックは「taken」と予測)。 ### 動的分岐予測 実行時の履歴をもとにハードウェアで判断する。 - **1-bit 予測器**: 直前の結果をそのまま次回の予測に使う。 - **2-bit 飽和カウンタ**: ループ末尾の「1 回だけ not-taken」で予測が反転しない。現代プロセッサの基本要素。 - **2-level 適応予測器**: 直前 n 回の分岐方向の組み合わせ(パターン)を使ってコンテキスト依存の予測。 - **gshare / gselect**: グローバルな分岐履歴を使い、離れた分岐間の相関を検出。 - **TAGE / 複合予測器**: 複数の予測器を並列動作させ、各分岐に最も精度の高い予測器を自動選択。最先端。 > [!key-insight] 予測精度の上限 > 最先端の予測器でも精度は 95〜97% 程度。残りの 3〜5% の誤予測が数十サイクルのペナルティを引き起こし、ハイエンドプロセッサの性能損失として無視できない。 ## プレディケーション(分岐の除去) 条件分岐をなくす別解。命令に**条件(プレディケート)**を付加し、条件が真のときだけ結果を確定する**条件付き命令**を使う。 ```asm ; 通常の条件分岐(2 分岐) cmp a, 7 ble L1 mov c, b ; b = c br L2 L1: mov d, b ; b = d L2: ... ; プレディケーション(分岐なし) cmp a, 7 mov c, b ; b = c (常に実行) cmovle d, b ; if le, b = d (条件付き上書き) ``` - 命令数は増えるが分岐誤予測ペナルティがなくなる。 - 小〜中規模の if/else では有効。両パスを実行する無駄があるため、大規模ブロックには不向き。 - Alpha 架から `cmov`、x86 は SSE 以降で対応。ARM は全命令プレディケーション対応(初期の短パイプライン向け)。 - Intel IA-64 は全命令プレディケーション対応だが商業的には失敗。 ## 深いパイプラインとの関係 パイプラインが深いほど、誤予測時にキャンセルすべき命令が多くなり、ペナルティが増大する。Pentium 4 の 31 段パイプラインはこの問題を極端に示した事例。→ [[パイプライン処理]]、[[Brainiac設計]] ## 横断的知見 - 今後の取り込みで、複数ソース間の関係を追記する。 ## 未解決の問い - この概念をどのソース群で継続的に検証するか。