分岐予測

コンピュータ・アーキテクチャにおける分岐予測（ぶんきよそく、Branch Prediction、ブランチプレディクション）とは、プログラム実行の流れの中で条件分岐命令が分岐するかしないかを予測することにより、命令パイプラインの効果を可能な限り維持し、性能を高めるためのCPU内の機能である。

概要

2方向分岐は一般に条件分岐命令で実装されている。条件分岐は、分岐せず (not taken) に分岐命令直後に続く命令の流れをそのまま実行し続ける場合と、分岐して (taken) プログラム内の異なる位置に分岐してそこから命令実行を続行する場合がある。

図 1: 4段パイプラインの例。色つきの四角形が命令を表している。

条件分岐命令が分岐するかしないかは、分岐条件を計算し、条件分岐命令が実行ステージ（図1の Stage: 3）を過ぎるまでわからない。

分岐予測を行わない場合、条件分岐命令が実行ステージを過ぎるまで次にフェッチすべき命令が定まらず、プロセッサはパイプラインのフェッチステージで待つことになる。分岐予測は条件分岐命令が分岐しそうかしそうでないかを推測することで、この無駄な時間を排除しようと試みる。分岐予測の結果に基づいて次に実行されそうな命令をフェッチし投機的に実行する。後で予測が間違っていたことが判明したら、投機的に実行した、あるいは実行途中だった命令は捨てられ、パイプラインは改めて正しい分岐で処理を再開する。その際、遅延が生じる。実際のプログラムの大半では、ループ処理や例外処理など各分岐先への分岐比率は偏りが大きいため、分岐予測によるメリットが分岐予測失敗によるデメリットを上回ることが多い。つまり分岐予測の的中率は、使用するアプリケーションと、分岐予測に採用した技法次第である。また、どこまで精緻な予測を行うべきかは、デメリット（CPU実装コスト、分岐予測処理のオーバーヘッド）とメリット（期待されるスループット向上）とのバランスとなる。

分岐予測が失敗して無駄になった時間は、パイプラインのフェッチステージから実行ステージまでの段数に等しい。最近のマイクロプロセッサではパイプラインは非常に長く、分岐予測が失敗した場合の遅延は10から20クロックサイクルとなる。パイプラインが長くなるほど、分岐予測の精度が要求されるようになる。

ある条件分岐命令を初めて実行するとき、分岐予測の基盤となる情報がほとんどない。しかし、分岐予測機構は条件分岐命令毎に分岐したか否かを記録しておく。過去に実行したことがある条件分岐命令を再び実行しようとしたとき、記録しておいた履歴に基づいて予測できる。例えば、分岐予測機構は、ある条件分岐命令は分岐する確率が高いとか、分岐しなかった次の実行では常に分岐するなどの振る舞いを認識することもできる。

分岐予測は分岐先予測と同じではない。分岐予測は条件分岐で分岐するかどうかを予測するが、分岐先予測は無条件分岐も含めて分岐アドレスが実際に決定される前にそれを推定するものである。分岐予測と分岐先予測はまとめて同じ回路で構成されることが多い。

実装

静的予測

静的予測は最も単純な分岐予測技法であり、コード実行時の動的な履歴を情報として必要としない。その代わり、分岐命令の内容にのみ基づいて分岐予測を行う。

SPARCとMIPS（最初の2つの商用RISCアーキテクチャ）で初期に実施された分岐予測は単純なものだった。それは、常に分岐しないと予測して命令順に実行を行おうとするものである。実際に分岐すると判明した時点（分岐命令の解釈フェーズ）で不連続なアドレスへの分岐を準備する。

これらのCPUはデコード段階で分岐命令を評価し、1サイクルで命令をフェッチする。従って分岐アドレスの命令をフェッチするには2サイクルかかり、その間にどうしても分岐命令の次の命令をフェッチしてしまう。これを有効利用するために、これらのアーキテクチャでは分岐遅延スロットを定義した。

より複雑な静的予測方式では、プログラムの流れる方向とは逆行する分岐命令（＝前に戻る分岐命令）をループを繰り返すための分岐と見なし、分岐する（＝ループする）可能性大と予測する。逆にプログラムの流れる方向に分岐する命令（＝先に進む分岐命令）はループからの脱出や例外的な処理と見なして、分岐しない可能性大と予測する。

また、静的予測方式には、何らかの静的な分岐予測情報（分岐命令に付与されたヒントビット等）に基づいて、分岐する/分岐しないを予測する方式もある。インテルの Pentium 4 では分岐予測ヒントを付与する方式だったが、後継のプロセッサではこれを採用していない。

静的予測は、動的分岐予測を使用するプロセッサの予備の技術（動的予測のためのどのような情報もない時の予備手段）として使われる。モトローラMPC7450 (G4e)とインテルPentium 4は予備手段としてこの技術を使っている。

次ライン予測

いくつかのスーパースケーラプロセッサ（MIPS R8000, DEC Alpha 21264 と Alpha 21464 (EV8)）では、一次命令キャッシュの各ライン毎に次に実行すべきキャッシュラインへのポインタを持つ。この次ライン予測は分岐予測だけでなく分岐先予測も兼ねている。

次ライン予測は位置合わせされた命令グループ（2個、4個、8個の命令）を示すので、分岐先は通常その先頭の命令ではない。単純に分岐先が一様に分布すると仮定すれば、使われない命令の平均はそれぞれ、0.5個、1.5個、3.5個となる。また、分岐命令もキャッシュラインの最後とは限らないので、こちらも使われない命令としてそれぞれ0.5個、1.5個、3.5個が捨てられる。

一般に命令はキャッシュライン単位にキャッシュに取り込まれるが、次ライン予測が特殊なのは、予測結果に従って次ラインの先頭からフェッチし、分岐命令の評価結果に従って、フェッチ済みの命令を捨てることにある。

飽和カウンター

飽和カウンター (saturating counter) または2モードカウンター (bimodal counter) は、つぎの4状態を持つ状態機械である。

図 2: 2ビット飽和カウンターの状態遷移図

• 分岐しない（可能性大） - Strongly not taken
• 分岐しない（可能性小） - Weakly not taken
• 分岐する（可能性小） - Weakly taken
• 分岐する（可能性大） - Strongly taken

分岐を評価したとき、対応する状態機械が更新される。評価によって分岐しなかった場合、状態は "strongly not taken" の方へ遷移し、評価によって分岐した場合、状態は "strongly taken" の方向へ遷移する。2ビットカウンターが1ビット方式より優れているのは、条件分岐の予測が変化するのに、過去2回ぶんの余裕を持たせている点である。例えば、ループを何度も反復していると対応する状態機械は "strongly taken" となり、最後にループを終了する際に分岐予測に失敗して "weakly taken" となるが、1ビット方式では単に「分岐しない」状態となる。すると、次に同じループを実行しようとしたとき、2ビットカウンターでは "weakly taken" なので分岐すると予測して成功するが、1ビット方式では「分岐しない」と予測して再度失敗する。つまり、分岐予測を失敗する回数が半分になる。

最初のMMXに対応していない Intel Pentium プロセッサは飽和カウンターを採用していたが、実装は不完全だった。

全ての分岐命令がそれぞれ独立したカウンターに対応している場合、SPEC89のベンチマークを実行したときの飽和カウンターの予測性能は最終的に93.5%となる。

予測テーブルは命令アドレスのビット列によってインデックス付けされるため、これをキャッシュ化して命令フェッチと同時にテーブルの内容も取ってくることが可能である。

2レベル適応型分岐予測

図 3: 2レベル適応型分岐予測。パターン履歴テーブルの各エントリは、図2で示されるタイプの2ビット飽和カウンターになっている。

2回目には常に分岐する条件分岐（例えばポインタがNULLかどうかで分岐し、NULLならリソースを確保し、さもなくば単にポインタの指すリソースにアクセスするという場合）や他の規則的に繰り返すパターンを持つ条件分岐は、飽和カウンターだけではうまく予測できない。2レベル適応型分岐予測 (two-level adaptive branch prediction) は、各条件分岐命令の過去 n 回の履歴を記憶しておき、2ⁿ ある履歴パターンそれぞれに飽和カウンターを対応させる。図3がその概念図である。

n = 2 の場合を例として考えてみよう。過去2回の分岐命令実行の際に分岐したか否かを2ビットのシフトレジスタに格納する。この分岐履歴レジスタは二進法で4種類の異なる値、00、01、10、11 のいずれかの値となる。ここで、0 は「分岐せず」、1 は「分岐した」を意味する。パターン履歴テーブルは4エントリで、各エントリのインデックスが 2ⁿ = 4 種類のパターンのいずれかと対応している。パターン履歴テーブルの各エントリの中身は図2で示したような2ビット飽和カウンターである。ある分岐命令の履歴が 00 なら、パターン履歴テーブルの最初のカウンターを使用する。履歴が 11 なら最後のエントリのカウンターを使用する。

ある条件分岐が3回に1回のパターンで分岐するとする。すると分岐シーケンスは 001001001… となる。この場合 00 の後に必ず 1 が来るので、パターン履歴テーブルのエントリ 00 での飽和カウンターの状態は "strongly taken" となる。同様に 01 の後には必ず 0 が来るので、エントリ 01 は "strongly not taken" となる。エントリ 10 も同様で、エントリ 11 はこの分岐命令では決してパターンとして出現しないため使われない。

一般にnビットの履歴を持つ2レベル適応型分岐予測は、全てのnビットの部分シーケンスが異なるなら、どのような間隔で反復するシーケンスでも予測可能である。

2レベル適応型分岐予測の利点は、任意の反復するパターンについて素早く予測を学習できる点である。この方式はミシガン大学の T.-Y. Yeh とエール・パットが発明した。1991年に発表され、広く採用された。現代のマイクロプロセッサの多くがこの方式から派生した方式を採用している。

局所分岐予測

局所分岐予測 (local branch prediction) では、個々の条件分岐命令ごとに分離した履歴バッファを使用する。2レベル適応型分岐予測を使うこともある。履歴バッファは個々の条件分岐命令ごとに分離しており、パターン履歴テーブルもそれに対応して別々になっていることもあるし、全ての条件分岐で共有することもある。

インテルの Pentium MMX、Pentium II、 Pentium III は、局所4ビット履歴と16エントリの局所パターン履歴テーブルを条件分岐ごとに持つ局所分岐予測を採用している。

SPEC89のベンチマークで、非常に大型の局所分岐予測を行うと予測成功率は最終的に97.1%となる。

広域分岐予測

広域分岐予測 (global branch prediction) は、個々の条件分岐の履歴を個別に保持しない。その代わり全ての条件分岐で履歴を共有する。履歴を共有することの利点は、多くの分岐命令のふるまいが直近の他の分岐命令のふるまいと強く相関するという事実を利用できる点である。欠点は、異なる条件分岐間で相関がない場合、無関係な情報によって履歴が希釈される点と、あまりにも多くの条件分岐があると同じ条件分岐命令の履歴が残らない可能性が高くなる点である。2レベル適応型分岐予測を利用することがある。

この方式はテーブルが大きければ飽和カウンターよりもよい結果を示すが、局所分岐予測と同程度の結果を示すことはめったにない。予測結果を改善するには履歴バッファを長くする必要がある。パターン履歴テーブルは履歴バッファの大きさに対して指数関数的に増大する。したがって、巨大なパターン履歴テーブルを全ての条件分岐命令で共有せざるを得ない。

広域的に共有される履歴バッファとパターン履歴テーブルを持つ2レベル適応型分岐予測機構で、広域履歴と分岐命令のPCをXORして使用する場合を "gshare" 予測器 と呼び、それらを連結して使用する場合を "gselect" 予測器と呼ぶ。広域分岐予測は、AMDのマイクロプロセッサ、インテルの Pentium M、Core、Core 2 で採用されている。

SPEC89のベンチマークで、非常に大型の予測器を使用すると、正しい予測は最終的に96.6%となる（大型の局所分岐予測よりほんの少し悪い）。

結合分岐予測

結合分岐予測 (alloyed branch prediction) は、局所の分岐履歴と広域の分岐履歴を連結することで局所分岐予測と広域分岐予測を統合する方式で、そこにプログラムカウンタの一部ビット列も含めることもある。VIA Nano プロセッサは、評価によってこの技法を採用しているのではないかとも言われている。

合意予測

合意予測 (agree prediction) は、広域的な履歴バッファとパターン履歴テーブルを使った2レベル適応型分岐予測の一種で、局所飽和カウンターを追加している。局所分岐予測と広域分岐予測の結果をXORして、最終的な予測結果とする。2つの条件分岐命令がパターン履歴テーブルの同じエントリを共有していて予測結果が異なる場合の衝突をなるべく低減することを目的としている。

初期の Pentium 4 で採用されたが、その後のモデルでは使われていない。

ハイブリッド分岐予測

ハイブリッド分岐予測 (hybrid branch prediction) は統合分岐予測 (combined branch prediction) とも呼ばれ、複数の分岐予測機構を実装したものである。最終的な予測は過去にどの予測器が最も成績がよかったかを記憶しているメタ予測器が決定するか、奇数個の予測器を使って多数決で予測を決定するものなどがある。

Scott McFarling は 1993年の論文で統合分岐予測 (Combined branch prediction) を提案した。

SPEC89のベンチマークで、統合分岐予測はほぼ局所分岐予測と同じ成績となる。

gshareのような分岐予測方法では、ひとつの分岐命令に対応するテーブルエントリが複数存在することになる。それは逆に同じエントリで複数の分岐命令が競合することを意味し、結果として分岐予測精度を悪化させる。従って、複数の分岐予測手法を統合する際には、このエントリ競合パターンがそれぞれの手法で異なっているように設計することが重要である。そうすれば、どれかひとつは競合していないエントリで予測することができる確率が高まる。このような考え方で統合された分岐予測をgskew分岐予測と呼ぶ。この名称は skewed cache からの類推から来ている（skewed cache とは連想度が複数のキャッシュについて、ウェイ毎に別のハッシュ関数を用いる手法）。

ループの予測

ループを構成する条件分岐を最もよく予測するループ専用予測器がある。ループ最後尾の条件分岐は、N 回反復する場合には N-1 回分岐し、1回だけ分岐しない。条件分岐がループ先頭にある場合、N-1 回は分岐せず、1回だけ分岐する。したがって、何度も分岐の一方を通り、稀に別の方を通る条件分岐はループを形成していると判断できる。そのような条件分岐は単純なカウンターで容易に予測できる。ループ予測器はハイブリッド分岐予測の一部として実装され、メタ予測器がその条件分岐がループのような振る舞いをしているかを検出するのに使う。

最近のマイクロプロセッサの多くがループ予測器を実装している。

分岐予測の上書き

分岐予測の高速性と予測性能はトレードオフの関係にあり、両立のために2つの分岐予測器を持つことがある。1つめの分岐予測器は高速かつ単純である。2つめの分岐予測器は低速で複雑であり、大きなテーブルを使用し、1つめの分岐予測器が間違っていればそれを上書きして訂正する。

Alpha 21264 とEV8コアは、高速な（1サイクル動作の）次ライン分岐予測を実施している。しかし次ライン分岐予測は大雑把であり、命令単位での予測はコストが高くつく。そこでこれらのプロセッサでは2サイクルかかる別の分岐予測機構を用意し、次ライン分岐予測の結果を上書きするようになっている。これによって最悪でも1命令だけフェッチした命令を捨てるだけでよくなり、性能が向上する。4命令以上を同時にフェッチすると、複数の分岐命令が含まれる可能性がある。そのため、上書きに際しては次の命令が分岐するかしないかを予測する必要がある。通常、分岐命令を評価して分岐アドレスを求める。

Intel Core i7 は2つの分岐ターゲットバッファを持ち、2つかそれ以上の分岐予測器を備えている。

ニューラル分岐予測

ニューラル分岐予測（Neural Branch Prediciton）は、ルーマニアの Lucian Vintan が論文 "Towards a High Performance Neural Branch Predictor" で最初に提唱した (Proceedings of The International Joint Conference on Neural Networks - IJCNN '99, Washington DC, USA, 1999)。その後、アメリカのラトガース大学で Daniel Jimenez が研究を進めた。2001年、ハードウェア実装が可能な最初のパーセプトロン予測器 (perceptron predictor) が登場した。

ニューラル分岐予測の主な利点は、線形なリソース量の増大だけで長い履歴を扱える点である。古典的な分岐予測では、履歴量の増大はリソース量の指数関数的増大を招いていた。Jimenez は McFarling の統合分岐予測に対して 5.7% の向上が得られたことを報告している。

パーセプトロン分岐予測の問題は、レイテンシが大きいことである。様々な技法を凝らして高速化しても、深いパイプラインを持つマイクロアーキテクチャのクロックに比較すると、計算レイテンシが長い。レイテンシを低減するため、Jimenez は2003年に fast-path neural predictor を提案した。これは、分岐命令のアドレスではなく、分岐経路によって重み付けする方式である。他にも同様の方式を提案している者が何人もいる（A. Seznec、M. Monchiero、Tarjan & Skadron、V. Desmet、Akkary et al など）。

ニューラル分岐予測はかなり見込みがあると考えられている。最先端の分岐予測機構の多くは、パーセプトロン分岐予測器を用いている（インテルの "Championship Branch Prediction Competition" を参照）。インテルは既に IA-64 シミュレータにこのアイデアを実装している (2003)。

歴史

歴史的にはパイプラインも分岐予測も、マイクロプログラム方式のCISCプロセッサで生まれ発達した技術であり、RISCを含むマイクロプロセッサでの分岐予測は最初は簡単なものであった。なお「マイクロプログラム方式のプロセッサは分岐予測を必要としなかった」という説があるが間違いである。一般論としてRISCの方がパイプラインの効果が発揮しやすい（逆に言えばパイプラインが乱れると性能劣化が大きい）ため、結果的に分岐予測が重要というだけである。

IBM 7030 (Stretch) は1950年代末に設計され、インデックスレジスタに依存する全ての無条件分岐と全ての条件分岐を事前評価する。他の条件分岐については、最初の2つの生産モデルで「分岐しない」という静的予測を実装していたが、その後のモデルでは（今日の条件コードに相当する）インジケータビットの現在値に基づく分岐予測を実装している。設計の早い段階で、分岐命令にヒントビットを持たせることも検討されたが、最終的にはやめている。予測失敗時のリカバリは先読みユニットで行ったが、このリカバリに時間がかかったことが性能が目標に達しなかった一因だとされた。その後のIBMの大型機は分岐予測と投機的実行を行わず、再び実装したのは1985年の IBM 3090 からである。

2ビット飽和カウンターは1977年、Tom McWilliams と Curt Widdoes が考案しローレンス・リバモア国立研究所の S-1 というスーパーコンピュータで採用した、また、CDCの Jim Smith がそれとは独立に1979年に考案している。

1960年代から1980年代までマイクロプログラム方式のプロセッサが主流で、1命令の実行に複数サイクルかかるため、分岐予測はそれほど重要ではなかった。しかし IBM 3090 以外にもマイクロプログラム方式で分岐予測を行う設計がいくつか存在した。

Burroughs B4900 はマイクロプログラム方式のCOBOLマシンで、1982年ごろリリースされた。パイプライン化されており、分岐予測も行う。B4900の分岐予測のための履歴情報は、プログラム実行中にメモリ上の命令に書き戻される。B4900では分岐命令の命令コード内の2ビットを分岐予測のための4状態を表すのに使っている。ハードウェアは特定の分岐命令の予測が外れた場合にメモリ上の命令を書き換えて予測状態を更新する。この方式で予測成功率は93%だった。

1989年に発表された VAX 9000 はマイクロプログラム方式でパイプラインを使っており、何らかの分岐予測を行っていた。

最初の商用RISCプロセッサであるMIPS（R2000とR3000）とSPARCは単純な「常に分岐しない」という分岐予測だけをした。これらは分岐遅延スロットを使い、1サイクルに1命令をフェッチするだけだったため、性能損失は全くなかった。後のR4000でも同様の予測方式だったが、分岐命令の評価に4サイクルかかったため分岐が発生すると2サイクルを無駄にすることになった。

分岐予測はインテル Pentium、DEC Alpha 21064、MIPS R8000、IBM POWERのようなパイプライン化されたスーパースケーラプロセッサでは重要な問題となった。これらのプロセッサは単純な1ビットあるいは2ビット分岐予測を使用している。

DEC Alpha 21264 (EV6)は、次ライン分岐予測を基本とし、局所分岐予測と広域分岐予測を統合した分岐予測で上書きを行う（統合には飽和カウンターを使用）。

AMD K8 は飽和カウンターと広域分岐予測を統合しており、統合時の選択には別の飽和カウンターを使用している。このプロセッサは、ECCとして使われていた二次キャッシュ内のビット群を分岐予測に代用する。結果として分岐予測テーブルとして大容量を使用可能となり、キャッシュに関してはECCではなくパリティビットを使用することになる。キャッシュエラー（ECCエラーやパリティエラー）が発生したらいずれにしてもそのキャッシュラインを無効化してメモリから読み直すので、この選択は非常に効果的と思われる。

Alpha 21464（EV8、後に設計段階で開発中止）では分岐予測が失敗した場合に最低でも14サイクルかかった。複雑だが高速な次ライン予測を基本とし、飽和カウンターと多数決型分岐予測を統合して上書きする。多数決は、飽和カウンターと2つのgskew分岐予測の間で行う。

関連項目

• 分岐先予測

外部リンク

• Seznec et al. (1996). "Multiple-Block Ahead Branch Predictors" — demonstrates prediction accuracy is not impaired by indexing with previous branch address.
• Seznec et al. (2002). "Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor" — describes the Alpha EV8 branch predictor. This paper does an excellent job discussing how they arrived at their design from various hardware constraints and simulation studies.
• Jimenez (2003). "Reconsidering Complex Branch Predictors" — describes the EV6 and K8 branch predictors, and pipelining considerations.
• Fog, Agner (2009年). “The microarchitecture of Intel, AMD and VIA CPUs”. 2009年10月1日閲覧。
• Andrews, Jeff (2007年10月30日). “Branch and Loop Reorganization to Prevent Mispredicts”. Intel Software Network. 2008年4月17日時点のオリジナルよりアーカイブ。2008年8月20日閲覧。