分岐予測

条件分岐命令は、平均的には5命令に1回程度の出現頻度であり、条件が確定してから分岐命令を実行し、さらに分岐先の命令をフェッチしてきてデコードできる状態になるまでには、命令フェッチが1次キャッシュにヒットしたとしても5サイクル程度は掛かってしまう。

これは1命令ずつ実行するプロセサでも問題であるが、並列に命令を実行するスーパスカラプロセサでは、より大きな性能制約となる。最大では4命令を並列にデコードできるプロセサでも各種の発行制約が存在するので、1サイクルに並列に発行できる命令数を平均2.5命令程度である。しかし、条件分岐命令は平均的に5命令に1回程度の出現頻度であるので、2サイクルに1回は条件分岐命令が含まれることになる。そして、分岐確率が半々とみてその半分で分岐が起こり、ここで5サイクルの待ちが発生すると、平均的には9サイクルで10命令の発行となってしまう。1命令ずつ順次処理するプロセサでも上手くやれば0.7~0.8命令/サイクルが達成できるので、4命令並列処理のハードウェアを作って、1.1命令/サイクルでは元が取れない。

このため、条件分岐命令によるストールを減らすことは、コンピュータアーキテクチャの歴史上、重要課題であり、古くは1961年に作られた「IBM7030」では、条件分岐は常に不成立と予測して後続の命令をフェッチするという制御が採用された。

また、1966年発表の超大型機である「IBM System 360 Model 91」では、分岐条件の確定しない前方分岐(ループの終わりなど)に遭遇すると、条件不成立で分岐しない主方向の命令フェッチに加えて、分岐先の命令も16バイト分をフェッチするという二股をかけて条件分岐によるロスを減らしていた。また、System 360 Model 91は、前方分岐の距離が64バイト以内の場合は、主方向の命令バッファにループ全体を収容するように制御して、メモリからの再度の命令フェッチを不要としていた。

分岐予測の考え方

次のようなループでは、

CMP(Compare:比較)命令でR1とR2の内容を比較し、次のBR(Branch)命令で、CMP命令の結果がZero(R1とR2の内容が等しい)場合には、次の命令としてLabel1のSUB命令を実行し、Zero以外の場合にはBR命令の次のADD命令を実行する。

この命令列を実行する時、条件が成立して分岐するか、あるいは条件が不成立で次の命令を実行するかは、CMP命令の結果が出なければ分からない。しかし、このシリーズの131回で説明したように、パイプラインが長い場合は、BR命令の実行開始時点ではCMP命令の比較結果は間に合わず、ストールが発生する。また、分岐が起こる場合は、次の命令としてLabel1のSUB命令を実行する必要があるが、この命令はキャッシュ、あるいは最悪の場合は、メインメモリから持ってくる必要がある。そして、この命令の読み出しの間、プロセサはストールしてしまう。

C言語ではfor文やwhile文、FORTRANではDO文などを用いるループは、プログラムでは良く用いられる構文である。

の場合は、まず、i=1として一連の実行命令を実行し、最後にiの値がNであるかどうかを判定し、N未満の場合はiを+1して、一連の実行命令の最初に戻る。このプログラムをFORTRANコンパイラでコンパイルするとおおよそ次のような命令列となる。

ここで、一般にはNの値はある程度大きいので、CMPの次のBR命令は条件が成立する場合が多く、条件が不成立になるのは、ループを抜ける最後の1回だけである。

つまり、この例では、ループの終わりにBR命令があり、ループを廻る場合は、分岐が発生する。一般的にこのようなケースが多いので、分岐予測の一番簡単で効果的なやり方は、プログラムの前方への分岐は実行(Taken)されると予測するものである。そうすると、この例では、N回の実行のうちのN-1回は予測が当たることになる。

一方、C言語の

の場合は、Cの言語の仕様上、最初にi<nを判定する必要があるので、次のようなコードになる。

この場合は、最初のBR Lp2、GE命令はループの最後の回だけしかTakenにならず、後方分岐はNot Taken(分岐せず)と予測すれば、これもN回の実行のうち、N-1回は予測が当たることになる。

このように前方分岐はTaken、後方分岐はNot Takenという簡単な予測方法でも、ループ回数が多い場合はかなり良い予測的中率が得られるが、プログラムにはループ以外の条件分岐も多く存在するので、この分岐方向によるTaken、Not Taken予測を、もう一段改良したのが、条件分岐命令に予測ビットをつける方式である。一例として、SPARC V9アーキテクチャでは条件分岐命令に予測ビットが設けられており、コンパイラが、分岐が成立する確率が大きいと判断すると、このビットをセットした機械語命令を生成する。そして、ハードウェアはこの予測ビットをみて分岐のTaken、Not Takenを判断すれば、単純な"前方分岐は常にTaken"よりも良い予測的中率が得られる。