分岐予測
出典: フリー百科事典『ウィキペディア（Wikipedia）』
コンピュータ・アーキテクチャにおける分岐予測(ぶんきよそく、Branch Prediction)とは、プログラム実行の流れの中で条件分岐命令が分岐するかしないかを予測するCPU内の機能である。分岐予測はスーパースケーラ型プロセッサにおいては高性能を実現するために重要である。分岐するかしないかが実際に決まる前に分岐予測によって命令をフェッチして実行することが可能となる。
パイプライン処理プロセッサは、パイプラインを途切れさせないようにするために命令を次々にフェッチする必要がある。そのため、多かれ少なかれ分岐予測を行っている。マイクロプログラム方式のCPUでは命令の流れが途切れても性能的に問題とはならないため、分岐予測も必要とされなかった。
分岐予測は分岐先予測と同じではない。分岐予測は条件分岐で分岐するかどうかを予測するが、分岐先予測は分岐アドレスが実際に決定される前にそれを推察するものである。
目次 |
[編集] 単純予測
SPARCとMIPS(最初の2つの商用RISCアーキテクチャ)で初期に実施された分岐予測は単純なものだった。それは、常に分岐しないと予測して命令順に実行を行おうとするものである。実際に分岐すると判明した時点(分岐命令の解釈フェーズ)で不連続なアドレスへの分岐を準備する。
これらのCPUはデコード段階で分岐命令を評価し、1サイクルで命令をフェッチする。従って分岐アドレスの命令をフェッチするには2サイクルかかり、その間にどうしても分岐命令の次の命令をフェッチしてしまう。これを有効利用するために、これらのアーキテクチャでは分岐遅延スロットを定義した。
[編集] 静的予測
静的予測を行うプロセッサでは、プログラムの流れる方向とは逆行する分岐命令をループの最後にある分岐と見なして、必ず分岐すると予測する。逆にプログラムの流れる方向に分岐する命令はループからの脱出や例外的な処理と見なして、分岐しないと予測する。
この方式ではループ実行の最後の分岐(つまりループの正常な終了)を誤予測する。
静的予測は、動的分岐予測を使用するプロセッサの予備の技術(動的予測のためのどのような情報もない時の予備手段)として使われる。モトローラMPC7450 (G4e)とインテルPentium 4はこの技術 1 を使っている。
[編集] 次ライン予測
いくつかのスーパースケーラプロセッサ(MIPS R8000、DEC AlphaEV6/EV8)では、一次命令キャッシュの各ライン毎に次に実行すべきキャッシュラインへのポインタを持つ。この次ライン予測は分岐予測だけでなく分岐先予測も兼ねているので、他の分岐予測方式と単純に比較することはできない。
次ライン予測は位置合わせされた命令グループ(2個、4個、8個の命令)を示すので、分岐先は通常その先頭の命令ではない。単純に分岐先が一様に分布すると仮定すれば、使われない命令の平均は、0.5個、1.5個、3.5個となる。また、分岐命令もキャッシュラインの最後とは限らないので、こちらも使われない命令として0.5個、1.5個、3.5個が捨てられる。
一般に命令はキャッシュライン単位にキャッシュに取り込まれるが、次ライン予測が特殊なのは、予測結果に従って次ラインの先頭からフェッチし、分岐命令の評価結果に従って、フェッチ済みの命令を捨てることにある。
[編集] 2レベル分岐予測
2レベル分岐予測は2ビットの飽和カウンターのテーブルを持ち、そのテーブルは命令アドレスの最下位桁ビット群によってインデックス付けされる。命令キャッシュとは異なり、2レベル分岐予測のテーブルはタグを持っていない。従ってテーブルの各エントリーは異なる複数の分岐命令に対応する可能性がある(これを分岐妨害とか分岐の別名と呼ぶ)。複数の分岐命令に対応したカウンターは正しい予測をしない。各カウンターは以下のような4つの状態を表す。
- 分岐する(可能性大)：Strongly taken
- 分岐する(可能性小)：Weakly taken
- 分岐しない(可能性小)：Weakly not taken
- 分岐しない(可能性大)：Strongly not taken
分岐命令が評価される際に対応するカウンターが更新される。分岐しない場合、対応するカウンターはデクリメントされ、「分岐しない(可能性大)」の方向に状態が移行する。この2ビット飽和カウンターの利点は、ループの最後の分岐命令を常に分岐するものと予測することである。R8000のような1ビットの方式ではループの最初と最後の分岐時に誤予測となる。2ビット方式では最後の分岐だけが誤予測となる。ほとんど常に分岐する命令で分岐しないことがあった場合、1ビット方式では2回誤予測する(一度分岐しなかった場合に1ビット方式では「分岐しない」とされてしまうため)が、2ビット方式では誤予測は1回である(ただし、Weakly(可能性小)の際の動作によって性能が変化する)。
全ての分岐命令がそれぞれ独立したカウンターに対応している場合、SPEC89のベンチマークを実行したときの2レベル予測の予測性能は最終的に93.5%となる。(一般に分岐予測は繰り返し実行されることを前提としており、あるプログラムを実行開始した直後の予測成功確率はもっと低い。)
2レベルカウンターテーブルが命令アドレスのビット群によってインデックス付けされるため、これをキャッシュ化して命令フェッチと同時にテーブルの内容も取ってくることが可能である。さらにコンパイル時の予測値を実行ファイルに格納すれば、最初の実行のときからある程度の正しい予測を行うことが可能となる。
[編集] 局所分岐予測
2レベル分岐予測はすべてのループの終了を誤予測する。毎回ループ回数が同じになる傾向があるループについては、もっとよい予測方法が存在する。
局所分岐予測では2つのテーブルを使用する。ひとつは局所分岐履歴テーブルである。これは、分岐命令のアドレスの最下位桁ビット群によってインデックス付けされ、最近の n回の分岐命令実行の履歴(分岐したかしないか)を記録する。
もうひとつのテーブルはパターン履歴テーブルである。2レベル予測のように、このテーブルは2レベルカウンターから構成される。ただしそのインデックスは上記の局所分岐履歴テーブルから生成される。分岐を予測するために分岐履歴を参照し、その内容から 2レベルカウンターを参照して予測を行う。
SPEC89のベンチマークで、非常に大型の局所分岐予測を行うと正しい予測は最終的に97.1%となる。
局所分岐予測は2つのテーブル参照をしなければならないため、2レベル分岐予測よりも重い。高速さを求めた実装では、2レベルカウンターを別途用意して2レベル分岐予測と組み合わせて使用する。これらのテーブルは冗長ではなく、各カウンターはひとつの分岐命令のふるまいを格納することを前提としている。
[編集] 広域分岐予測
広域分岐予測は多くの分岐命令のふるまいが最近の他の分岐命令のふるまいと強く相関するという事実を利用する。ひとつのシフトレジスタで最近実行した分岐命令のふるまいの履歴を保持し、この内容を2レベルカウンターテーブルへのインデックス値として使用する。この方式自体はテーブルが大きければ2レベル分岐予測よりよい結果を示すが、局所分岐予測には敵わない。
ひとつのシフトレジスタではなく、命令アドレスの数ビットをインデックスとしたシフトレジスタのテーブルを使う方式を gselect分岐予測と呼ぶ。gselect はテーブルの小さい局所分岐予測よりもよい結果を示し、局所分岐予測はテーブルが1Kバイト以上になってもあまり予測結果が向上しない。
分岐命令アドレスを広域履歴とXORすると gselect よりも若干効率がよくなる。これを gshare と呼び、テーブルサイズが 256バイト以上ならば gselect よりもよい結果となる。
SPEC89のベンチマークで、非常に大型のgshare分岐予測値を実施すると、正しい予測は最終的に96.6%となる(大型の局所分岐予測よりほんの少し悪い)。
gselect と gshare は分岐命令当たりのテーブル参照が一回で済むので、局所分岐予測よりも軽い。2レベル分岐予測と併用してテーブル参照と命令フェッチを並行して行うこともできる。
[編集] 統合分岐予測
Scott McFarling は 1993年の論文で統合分岐予測(Combined branch prediction)を提案した。この方式は2レベル分岐予測と同じくらい正確で、広域分岐予測と同じくらい高速である。
統合分岐予測は並列に3つの予測値を使う。それは 2レベル分岐予測と gshare 分岐予測と、分岐命令毎にその二つのどちらを選択するかを示す2レベルカウンターテーブルを使った予測である。最後のものを選択分岐予測と呼び、このテーブルのインデックスは命令アドレスの最上位桁ビット群を使用する。このテーブルは2レベル分岐予測と gshare 分岐予測が食い違ったときに更新され、どちらが正しかったかを示す。
SPEC89のベンチマークで、統合分岐予測はほぼ局所分岐予測と同じ成績となる。
分岐予測を統合する他の方法として、例えば3種類の分岐予測を使って多数決を行うことが考えられる。実際、インテルはそのような方式を採用している。
gshare のような分岐予測方法では、ひとつの分岐命令に対応するテーブルエントリが複数存在することになる。それは逆に同じエントリで複数の分岐命令が競合することを意味し、結果として分岐予測精度を悪化させる。従って、複数の分岐予測手法を統合する際には、このエントリ競合パターンがそれぞれの手法で異なっているように設計することが重要である。そうすれば、どれかひとつは競合していないエントリで予測することができる確率が高まる。このような考え方で統合された分岐予測を gskew 分岐予測と呼ぶ。この名称は skewed cache からの類推から来ている(skewed cache とは連想度が複数のキャッシュについて、ウェイ毎に別のハッシュ関数を用いる手法)。
[編集] 合意予測
パターン履歴テーブルの中で破壊的なエントリ競合を減らす別の技術として「合意予測(agree predictor)」がある。2レベル分岐予測や分岐命令にヒントビットを付与することで若干静的な予測を基本として行う。そして、別の分岐予測機構(例えば gskew)でも予測を行うが、それは分岐するかしないかではなく、基本の予測に合意するかしないかを予測する。
意図しているのは、gskew 分岐予測による予測に対して静的なバイアスを与えることである。容量の小さいパターン履歴テーブルでの競合を削減するのに有効であるが、基本となる静的予測の精度に性能が依存する。
合意予測は統合分岐予測と組み合わせるとうまく機能する。というのも統合分岐予測では一般に2レベル分岐予測を内包しており、それを基本の予測として使用できるからである。ただし分岐する/しないの傾向が特にない分岐命令についてはうまく機能しない(基本の予測結果が一定しないため)。従って、合意予測は3種類の分岐予測の組合せの一部として使用するのが最善である。
[編集] 分岐予測の上書き
EV6とEV8コアは、高速な(1サイクル動作の)次ライン分岐予測を実施している。しかし次ライン分岐予測は大雑把であり、命令単位での予測はコストが高くつく。そこでこれらのプロセッサでは2サイクルかかる別の分岐予測機構を用意し、次ライン分岐予測の結果を上書きするようになっている。これによって最悪でも1命令だけフェッチした命令を捨てるだけでよくなり、性能が向上する。
4命令以上を同時にフェッチすると、複数の分岐命令が含まれる可能性がある。そのため、上書きに際しては次の命令が分岐するかしないかを予測する必要がある。通常、分岐命令を評価して分岐アドレスを求める。
[編集] 歴史
マイクロプログラム方式のプロセッサでは一命令に複数サイクルかかっていたため、分岐予測を必要としなかった。VAX 9000はマイクロプログラム方式でパイプラインを使っていたが、何らかの分岐予測を行っていたと思われる。
最初の商用RISCプロセッサ MIPSとSPARCは単純な「常に分岐しない]という分岐予測だけをした。これらは分岐遅延スロットを使い、1サイクルに1命令をフェッチするだけだったため、性能損失は全くなかった。後にR4000でも同様の予測方式だったが、分岐命令の評価に4サイクルかかったため分岐が発生すると2サイクルを無駄にすることになった。
分岐予測はIntel Pentium、DEC Alpha 21064、MIPS R8000、IBM POWERのようなパイプライン化されたスーパースケーラプロセッサでは重要な問題となった。これらのプロセッサは単純な1ビットあるいは2レベル分岐予測を使用している。R10000 は2レベル分岐予測を採用した初期のプロセッサのひとつである。
DEC Alpha EV6 2は、次ライン分岐予測を基本とし、局所分岐予測と広域分岐予測を 2レベル分岐予測で統合した分岐予測で上書きを行う。Alpha EV8(後に設計段階で開発中止)では分岐予測が失敗した場合に最低でも14サイクルかかった。
AMD K8 は2レベル分岐予測と広域分岐予測を統合しており、統合時の選択には別の2レベル分岐予測を使用している。このプロセッサは、ECCとして使われていた二次キャッシュ内のビット群を分岐予測に代用する。結果として分岐予測テーブルとして大容量を使用可能となり、キャッシュに関してはECCではなくパリティビットを使用することになる。キャッシュエラー(ECCエラーやパリティエラー)が発生したらいずれにしてもそのキャッシュラインを無効化してメモリから読み直すので、この選択は非常に効果的と思われる。
[編集] 外部リンク
- 1 - ArsTechnica の Pentium 4 に関する文章(英語)
- 2 - Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor - Seznec et al - 2002 - Alpha EV8 の分岐予測の解説。どのようにしてそう設計するに至ったかを詳述している貴重な論文(英語)
- 早稲田大学の研究(2005年) PDF形式。
