ダイナミックに分岐方向を予測する

ダイナミックな分岐予測

しかし、最近のプロセサでは、プログラム実行中の振る舞いから、ダイナミックに分岐方向を予測するハードウェアを持つというのが主流となってきている。基本的な考え方は、分岐命令ごとにTaken(分岐成立)、Not Taken(不成立)の履歴をモニタし、Takenが続いていれば、次回もTakenであろうと予測するという方法である。我々の実生活でも、同じ条件で過去にどうなったかを元に、今後、どうなるかを予測するというのは普通に行われていることである。

プロセサの場合は各分岐命令に対応して飽和型のカウンタを設け、実行結果がTakenの場合は+1、Not Takenの場合は-1する。一般には2ビット程度の飽和型カウンタが使われ、値が3になると+1しても3に留まり、値が0になると-1しても0のままという動作をする。そして、このカウンタの値は

3:Strongly Taken
2:Weakly Taken
1:Weakly Not Taken
0:Strongly Not Taken

を意味し、値が2以上の場合は分岐はTakenと予測する。

分岐予測機構の具体的な構造は図7.1のようになり、命令デコード時にその命令が条件分岐命令であると判明すると、その命令のアドレスをインデックスとして分岐予測テーブルを読み出す。そして、その値が2以上であれば、その条件分岐命令はTakenであると予測する。そして、その条件分岐命令がコミットする時点で、コミット側のポートを使ってカウンタ値を読み、(上記のように飽和型カウントで)分岐が行われた場合(Taken)は+1、分岐しなかった場合(Not Taken)は-1を行い、分岐予測テーブルに書き戻す。なお、この図で、命令アドレスがbit2からとなっているのは、32ビット長のRISC命令を想定しており、バイト単位の命令アドレスの最下位2ビットは常にゼロだからである。

なお、この図の構成で処理できるのは1つの条件分岐命令だけであり、複数の条件分岐命令を並列にデコードする場合は、各分岐命令に1つのリードポートと1つのリードライトポートが必要となる。しかし、 平均的には条件分岐命令の頻度は5命令に1回程度であるので、複数の条件分岐命令が4命令の並列デコードに含まれる確率は少なく、1サイクルに処理する条件分岐命令は1命令だけというように制限し、2個目の条件分岐命令が出てくると次サイクルに廻すようにしているプロセサもある。しかし、4命令中に条件分岐命令が3つ4つ出現するというケースは非常に稀であるが、2つ存在するケースは無視できない程度に存在するので、最初の条件分岐命令の予測がNot Takenの場合は、さらに先の命令をデコードし、上限の4命令に達するまでに2番目の条件分岐命令に出会うとその命令も含めて1サイクルで処理するというプロセサもある。

プログラムでよく用いられるループ構造の最後の条件分岐命令は、N回ループバックの前方分岐のTakenが起こった後、Not Takenでループを抜けることになる。この方式では、Takenが続くとカウンタは飽和して3のStrongly Takenとなり、その条件分岐命令の次回の実行はTakenと予測するので、最初の1回(カウンタの初期値が1の場合)を除いて予測が当たることになる。

そしてループを抜ける最後の回は予測外れとなり、カウンタは-1されて2となってループを抜ける。しかし、次にこのループに戻ってきたときにはカウンタが2であるので、最初の回の予測も当たるということで、2ビットカウンタは、単純に前回と同じとみなすという1ビットのカウンタより上手く働く。

また、理論的には、3ビット以上のカウンタも可能であるが、3ビット以上に長くしても、あまりメリットが見られないということで、一般的に2ビットの飽和カウンタが使われている。