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

2方向分岐は一般に条件分岐命令で実装されている。条件分岐は、分岐せず (not taken) に分岐命令直後に続く命令の流れをそのまま実行し続ける場合と、分岐して (taken) プログラム内の異なる位置に分岐してそこから命令実行を続行する場合がある。図 1: 4段パイプラインの例。色つきの四角形が命令を表している。

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

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

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

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

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

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

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

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

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

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

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

いくつかのスーパースケーラプロセッサ（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 プロセッサは飽和カウンターを採用していたが、実装は不完全だった[2]。

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