コンピュータアーキテクチャの話 (172) Gshare方式とハイブリッド予測

　Gshare方式

　グローバル履歴は、履歴の長さを伸ばすと良い予測が可能であるが、長い履歴と高い命令アドレス分解能を得ようとするとPHTのエントリ数が1ビット伸ばすごとに倍増するので、大きなテーブルが必要になるという問題がある。

　この問題の解決法として提案されたのが、分岐履歴と条件分岐命令の中位アドレスのXORを取り、それに比較的少ないビット数の条件分岐命令アドレスを付加するという図7.4に示した方式である。

　図7.4 Gshare方式の分岐予測機構

　ある命令アドレスの条件分岐命令に着目すると、その命令に至るグローバル履歴は比較的一定であり、すべてのパターンのグローバル履歴分のPHTエントリを持つのは無駄が多いので、命令の中位アドレスとグローバル履歴のXORを取る事により、下位アドレスが同一の条件分岐命令間でPHTのエントリをシェアして使うことにより、オリジナルのグローバル履歴予測法のPHTの利用効率が悪い点を改良し、長い履歴と現実的なPHTサイズを両立させている。なお、図7.4は12ビットのグローバル履歴と6ビットの下位命令アドレスをPHTのインデックスとして使う構成を示している。

　この方式はグローバル履歴であるが、複数の条件分岐命令でPHTをシェアするため、「Gshare方式」と呼ばれる。各種ベンチマークでは、Gshare方式は比較的高い予測ヒット率を示すので、最近のプロセサではこのGshare方式の分岐予測を用いるものが多い。

ハイブリッド予測

　平均値としてはGshareは良い方式であるが、これまで見てきたように、分岐予測方式はプログラムの振る舞いに大きく依存するので、どのプログラムに対してもGshareが一番良いとは限らない。また、1つのプログラムの中でも、ローカル履歴が上手く働く部分もあるし、グローバル履歴を使うGshareが上手く行く部分もあるということが起こる。

　そこで、2つ、あるいはそれ以上の予測機構を実装し、さらに、それぞれの予測機構の予測の成功、不成功の星取表を持ち、勝率の高い方の機構の予測を用いるという図7.5に示すようなハイブリッド方式を採用したプロセサも現れた。

　図7.5 ハイブリッド分岐予測機構

　この星取表であるが、分岐予測のPHTのように命令アドレスの下位ビットをインデックスとしてアクセスされる2～3ビットの飽和カウンタで構成され、両方の予測が一致した場合にはそのまま、Gshare側の予測が正しかった場合は+1、ローカル予測が正しかった場合は-1というようにカウントを更新する。そして、デコード時の予測値が2ビットカウンタの場合は2以上(3ビットカウンタの場合は4以上)であればGshareを使い、それ以下の場合はローカル予測を使うというように予測アルゴリズムを選択する。論文では、トータルのテーブルのビット数を一定としても、どちらか一方のアルゴリズムを用いるよりも、ハイブリッド予測の方が予測精度が高いとのことである。