分岐予測

パイプライン CPU は条件が未確定の分岐で次のアドレスを予測し、先に命令を取れる。外れたら誤経路の仕事を破棄して正しい経路へ戻る。分岐位置ごとの 2 ビットカウンターでも反復する結果を利用できるが、効果は履歴による。

常連の注文を予想して料理を始める場合に似ている。当たれば待ち時間を減らし、外れれば途中の仕事を捨てる。CPU の代価は判定までに進めた仕事と回復機構で決まり、本課は固定 2 サイクルで示す。

仕組み

モデルの 5 段は IF、ID、EX、MEM、WB。毎サイクル一命令を取得し、分岐は EX で判定する。分岐のフェッチ後 2 サイクルで後続二命令を取るため、順次アドレスか分岐先かを先に決めなければならない。

判定まで待つ選択なら、本モデルでは毎分岐に空の 2 サイクルを払う。予測なら正解時に続行し、不正解時だけ回復する。多くのパイプラインプロセッサーが予測を使うが、前段設計は機種による。

分岐アドレスで予測表を引く。本課は一分岐の一エントリーに絞り、同じ履歴を三方式へ渡す。

• 常に分岐成立を予測：履歴を保存しない。n 回のループ末尾では n−1 回成立し、最後だけ不成立なので、出口一回を外す。
• 1 ビット履歴：直前の結果を保存して次も予測する。変化へ速く追随するが、一度の例外でも反転する。
• 2 ビットカウンター：0–3 の飽和状態を持ち、0、1 は不成立、2、3 は成立を予測する。実際の成立で増加、不成立で減少し、端では折り返さない。強い状態から反対側へ移るには逆の結果が二回必要で、弱い状態なら一回で変わる。

このヒステリシスが、ループの一度の終了だけで成立の傾向を失うのを防ぐ。

ステップ実行

既定例は 4 周の内側ループを閉じる blt を観察し、外側から三度入る。結果は T,T,T,N の 3 反復。2 ビットは強い不成立 00 で冷開始する。各周 4 命令、予測失敗は 2 サイクルの追加だ。

1. 第 1 回：00 は N を予測するが j=1<4 で T。後ろの二命令を破棄し、2 サイクルを払い、00→01。まだ N を予測する。
2. 第 2 回：再び N 対 T で失敗し、01→10。成立側へ渡る。冷開始で二回外した。
3. 第 3 回：10 は T を予測し、実際も T。正解して 11 へ進む。
4. 第 4 回：j=4 で N、予測 T は失敗。2 サイクルを払い、11→10。成立側に残る。
5. 第 5 回：外側から再進入し T。状態 10 の予測は正しい。1 ビットなら前回の出口で N になり、ここでまた外す。2 ビットは傾向を保つ。
6. 第 6、7 回：T を正しく予測し、11 は飽和して変わらない。
7. 第 8–12 回：第 8、12 回の出口だけを外し、ほかは正しい。

12 分岐で 5 失敗。出口 3、冷開始 2 だ。基準 48 命令と追加 10 サイクルで計 58、罰則は約 17%。この時間モデルはパイプラインの充填と排出を省く。

同じ履歴で 1 ビットは 6 失敗。各出口、最初の冷開始、後の二回の再進入で外す。常に T は出口の 3 回だけで最良となる。単純なループでは静的な仮定が既に主な結果を捉える。動的履歴の利点は他の形で現れ、後の整列データでは常に T が 6、2 ビットが 2 失敗になる。

予測失敗のコスト

ここではフェッチから EX 判定まで 2 サイクルなので罰則を 2 とする。実前段は深さ、幅、回復処理により高い代価を払うことがある。罰則をパイプライン全段数や破棄命令数とそのまま同一視はできない。

画面の式は cycles = instructions + penalty × mispredictions。仮に罰則 12 なら 5 失敗で追加 60 サイクルとなる。B 回の分岐で精度が 5 ポイント落ちると 0.05×B×penalty の追加。罰則 2 から 20 への変更はその差を 10 倍にするが、全時間中の比率には分岐頻度も効く。

整列とシャッフル

二つのデータ例は同じ 12 値に v >= 128 を実行する。コード、命令数、比較数、成立数は同じで、順序だけが違う。

整列後は N 六回、T 六回で、一度だけ傾向が変わる。2 ビットの 00 は最初の六回を当て、続く最初の二つの T を外して成立側へ移る。1 ビットは最初の T だけを外し、この形では速い追随が勝つ。

指定のシャッフル列で 2 ビットは 7 失敗し、常に T の 6 より多い。各 4 命令の 12 周で、整列は 48+2×2=52、シャッフルは 48+2×7=62 サイクル。後者は約 19% 多い。結果の順序が分岐コストを変える証拠だが、整列すれば常に速くなるわけではない。一回のループだけのためのソートは節約より高くつくことがあり、コンパイラーが既に分岐なしコードにしている場合もある。

境界ケース

• 冷状態は証拠でなく初期値による。ここでは 00 が決定的に N を予測する。短い実行ほど影響し、長い実行では開始コストを分担できる。
• 既定の 4 周ループは三方式とも各出口を外し、k 回入れば出口の失敗が k 回ある。この履歴と状態の結論で、全ループへの保証ではない。実ループ予測器は周回数を学び、全体履歴も助けになる。
• 11 で T が続いても 11 のまま。累積回数でなく飽和した位置だ。
• T、N の完全交互列で 1 ビットが初期 N なら 12 回すべて外す。2 ビットはこの初期 00 では 00 と 01 を往復し、N を予測し続けて半分当てる。
• 実表では異なる分岐アドレスが同じ項目へ衝突し、互いを訓練する。ここは一項目でエイリアシングを扱わない。

よくある間違い

• 一失敗を一サイクルと数える。ここは 2、実機は判定と回復の遅延や幅などによる。
• 予測失敗をプログラム結果の誤りとする。モデルは誤経路を破棄して復旧し、最終意味を保つ。代価は追加作業だ。
• 複雑な方式が必ず勝つと考える。既定例は常に T が 3、1 ビットが 6、2 ビットが 5 失敗で、入力履歴を見る必要がある。
• 予測しにくい分岐の本体だけを最適化する。ランダムな結果には局所履歴が役立たない場合がある。データ配置、条件付き移動、比較結果の算術化、コストの受容を測定して選ぶ。前処理費用にも注意する。
• 11 を確率 75% と読む。強い成立予測で、N 二回で反転する位置を表し、確率推定ではない。

モデルの範囲

一つの分岐と予測エントリーを示す。実コアは数千項目、分岐先バッファー、複数方式、グローバル履歴を組み合わせ、分岐同士の相関も使う。

5 段、毎サイクル一命令完了、キャッシュミスとデータハザードなし、EX 判定という簡略な定常時間式を用いる。実機は幅広い発行、順序変更、多数の実行中命令を持ち得る。予測、取得、確認、破棄の仕組みは残るが、画面の数値はこの小さな機械のものだ。