現代プロセッサにおける分岐予測

仕組みと種類

分岐予測技術は、大きく静的予測と動的予測に分類される。静的予測器は、コンパイル時の情報または単純なヒューリスティックを使用する。例えば、後方分岐は分岐すると予測し、前方分岐は分岐しないと予測する。動的予測器は過去の結果を記録し、プログラムの実行時の挙動に適応する。

• 単純なカウンタ: 初期の動的方式では、各分岐について1ビットまたは2ビットの飽和カウンタを用い、直近の結果を記録する。
• グローバル履歴とローカル履歴: 予測器は、単一分岐の最近の履歴（ローカル）または直近の分岐全体の履歴（グローバル）を参照し、パターンを検出できる。
• Gshare、バイモーダル、二段階、トーナメント予測器: 履歴情報と複数の表を組み合わせ、異なるコードパターンに対する精度を高める、よく知られた動的設計である。
• リターン予測器: リターンアドレススタックなどの専用構造は、通常は呼び出しと復帰の規律に従う関数からの復帰を処理する。

ハードウェア構造

実装は複数のオンチップ構造に依存する。分岐先バッファ（BTB）は、最近実行された分岐の分岐先アドレスをキャッシュし、フェッチユニットが次の命令アドレスを迅速に取得できるようにする。パターン履歴表は、分岐の識別子またはグローバル履歴で索引付けされたカウンタを格納する。リターンアドレススタック（RAS）は、入れ子になった呼び出しに対する予測復帰アドレスを保持する。高度な予測器では、複数の表を組み合わせ、各静的分岐位置に最適な結果を選ぶ選択ロジックを用いる場合がある。

歴史と発展

パイプラインが深くなり、プロセッサがスーパースカラ化および投機的実行に対応するにつれて、分岐予測は発展した。初期のマイクロプログラム方式CPUは、性能要件が比較的控えめであったため、しばしば高度な予測を行わず逐次実行していた。命令パイプラインの長大化と並列実行の増加により、分岐予測ミスのコスト、すなわち無駄になった処理とパイプラインのフラッシュが重大になった。このことが、より優れた予測方針と構造に関するハードウェアおよびコンパイラの研究を促した。

用途、トレードオフとセキュリティ

予測器はプロセッサのスループットとエネルギー効率に直接影響する。高精度な予測はアイドルサイクルを減らす一方、ハードウェアの複雑さと消費電力を増加させる。コンパイラは、予測器の挙動を改善するためにヒントを与えたり命令を並べ替えたりでき、実行時プロファイリングは静的予測の指針となる。予測によって可能となる投機的実行の重要な帰結として、微妙なサイドチャネルを生じうる点がある。広く知られた一部の脆弱性は、投機的経路を悪用して情報を漏えいさせるものであり、ハードウェアとソフトウェアの双方で緩和策が必要とされている。

実用上の考慮点と区別

すべての分岐が同じではない。条件付き直接分岐、無条件分岐、間接分岐、復帰は、それぞれ異なる予測上の要求を持つ。間接分岐は多数のアドレスを分岐先にできるため予測が難しく、専用の間接分岐予測表がしばしば使用される。精度は通常、予測率として測定されるが、実用的な利点はパイプラインの深さと予測ミスから回復する際のペナルティに左右される。設計者は、コスト、面積、消費電力の目標を満たすため、予測器のサイズ、アクセス時間、複雑さの均衡を図る。

関連するプロセッサ概念については、命令フェッチと制御フロー、スーパースカラ実行、および一般的なパイプライン化の技法に関する資料も参照。