コンピュータアーキテクチャの話 (171) グローバル履歴を使う分岐予測

　グローバル分岐予測

　ローカル履歴は、短いループのループバックを行う条件分岐命令などが一定のパターンでTaken、Not Takenを繰り返す状況を捕まえることにより予測成功率を改善するものであるが、条件分岐には別のパターンもある。

　If (A==TRUE)
　　　　　then …1
　if (B==TRUE)
　　　　　then …2
　if　(A or B)!=TRUE
　　　　　then …3
　次の命令
　

　のようなプログラムなプログラムの場合、最初のA==TRUE、あるいは2番目のB==TRUEの両方かどちらかの一方が成立していれば、3番目の(A or B)!=TRUEは成立しない。このように、以前の条件分岐命令の条件の成立、不成立が次の条件分岐命令のTaken、Not Takenに影響するというパターンがあり、個々の条件分岐命令の過去のTaken/Not takenの履歴ではなく、その条件分岐命令に至る前のn個の分岐命令のTaken/Not Takenの履歴も加えて、予測を行うという方式が提案された。このように着目する条件分岐命令に至る複数の条件分岐命令のTaken/Not Takenを利用する方式を、グローバル履歴を使う分岐予測と呼ぶ。

　グローバル履歴を用いる方法では、単純に命令列の実行中に出てきた条件分岐命令のTaken/Not Takenの履歴をシフトレジスタに記憶し、その履歴と予測する条件分岐命令の下位アドレスを用いてPHTをアクセスするという方法がとられる。

　前述のローカル履歴の説明で使った

　Do i=1,M
　　　Do j=1,4
　　　　　一連の命令
　　　Enddo
　Enddo
　

　という2重ループの場合、内側のループバックの条件分岐命令の履歴はT、T、T、NTとなり、次に外側のループバックの条件分岐命令がTとなるというパターンが繰り返される。したがって、グローバル履歴でNT、T、T、T、Tとなったときに、内側ループバックの条件分岐命令をNTと予測してやれば、ローカル履歴による分岐予測と同じことができ、グローバル履歴は、ローカル履歴が上手くいくケースのかなりの部分をカバーする。

　このグローバル履歴を用いる分岐予測機構を図7.3に示す。

　図7.3 グローバル履歴を用いる2レベル分岐予測機構

　グローバル履歴の場合は、履歴を記憶するシフトレジスタは1個で良いので、多数のBHTエントリを必要とするローカル履歴を用いる分岐予測より簡単でハードウェアも少なくて済むように見えるが、必ずしもそうではない。

　先に述べた2重ループのケースでは、グローバル履歴は実行された条件分岐命令の実行結果を記憶するのであるから、内側の4回のループで4ビットの履歴を使ってしまう。このため、より広い範囲の複数の条件分岐命令間の分岐パターンを認識するためには、グローバル履歴の長さは、ローカル履歴よりもかなり長くする必要がある。ということで、ローカル履歴が3～4ビットであるのに対して、グローバル履歴では8～16ビット程度の長さが用いられる。

　これに条件分岐命令の下位アドレスを付け加えるので、PHTのエントリ数が多く必要になる。また、コミット時にPHTの更新を行う必要があるが、グローバル履歴は条件分岐命令のコミットによって変わっていくので、 PHTのアクセスのために、命令デコード時のグローバル履歴シフトレジスタの状態、あるいは、更新すべきPHTのエントリ番号をコミット機構に覚えておく必要がある。

　しかし、一番やっかいな問題は、ある条件分岐命令のデコード時には、まだ、先行する条件分岐命令の分岐方向が確定していない場合があり、正確なグローバル履歴が分からないことである。予測する条件分岐命令の前のすべての条件分岐命令がコミットしてから予測を行えば問題ないのであるが、これでは予測できる時点が遅くなって、予測の意味がほとんど無くなってしまう。

　これに関しては、条件分岐命令の発行時には、先行する条件分岐命令は予測された分岐方向に分岐する(予測成功)と仮定して、そのTaken/Not Takenをグローバル履歴に書き込むという方法が使われる。そして、その分岐の方向が確定した時点で、予測が間違っていればグローバル履歴を訂正する。

　ローカル履歴を利用するPA方式に対してグローバル履歴を用いる方式はGA方式と呼ばれ、図7.3のような構成はGAsと呼ばれる。そして、図7.3の構成から条件分岐命令の下位アドレスを無くしてしまってグローバル履歴レジスタの内容だけをインデックスとしてPHTをアクセスする構成をGAgと呼ぶ。