ローカル履歴を使う2レベル分岐予測

しかし、図7.1の構造では、ループの最後の回の予測が外れてしまう。最後の1回の予測が外れても、全体としての予測ミス率は1/Nであり、ループ回数Nが大きい場合はあまり成功率は低下しないが、Nが小さい場合には、予測ミスの比率が大きくなってしまう。例えば、

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

のような二重ループも良く見かける構文であるが、この例では、内側のループは4回しか廻らない。しかし、外側のループにより、次はiが+1されて、また4回の内側ループを廻るという動作が繰り返される。ここで内側のループのループバックを行う条件分岐命令は、Taken、Taken、Taken、Not Takenを繰り返すことになるので、履歴がNT、T、T、Tと来れば、次はNTであり、それ以外ならTと予測すれば、外側ループの最後の1回を別とすれば、すべて予測が当たることになる。この場合の予測ミス率は1/(4*M)となり、ループ回数が多い場合と同様に、ミス率を低減して性能を上げることができる。

このループのケースのように分岐のTaken/Not takenに一定のパターンがある場合には、それぞれの分岐命令のTaken/Not takenの履歴により予測を変えるという方法が考えられる。この方法はその条件分岐命令の履歴を用いるので、ローカル履歴を用いた予測方法と呼ばれる。 ローカル履歴を用いる方法では、図7.2に示すように、分岐予測テーブルは分岐命令のアドレスでインデックスされるN回の分岐履歴を記憶するBranch History Table(BHT)と、BHTから読み出された分岐履歴と分岐命令の下位アドレスでインデックスされるPattern History Tableを用いる。この方法は、2つのテーブルを用いて2段階のプロセスで予測を行うので、2レベルの分岐予測法と呼ばれる。また、これに対して、前記の1つのテーブルを用いる方式は1レベル予測法と呼ばれる。

図7.2 ローカル履歴を用いる分岐予測機構

BHTの各エントリは条件分岐命令に対応したシフトレジスタを構成し、それぞれの命令のTaken('1')、 Not Taken('0')を順次シフトして記憶する。もちろん、プログラム中の全部の条件分岐命令分のシフトレジスタを持つのではなく、図7.2では1K個のシフトレジスタを持っている。そして、条件分岐命令のアドレスのbit11～2の10ビットをインデックスとしてエントリを選択する。また、これらのシフトレジスタは、一時にはその条件分岐命令に対応する1つのシフトレジスタだけを動作させれば良いので、ハードウェア的な実装としては記憶素子としてはSRAMなどを用いて、コミット時にその条件分岐命令に対応するエントリを読み出して、新たな履歴をシフトインしたデータに更新してSRAMに書き戻す。

一方、PHTは、前に説明した1レベルの分岐予測テーブルと同じで、2ビットの飽和カウンタからなるテーブルである。ただし、1レベル予測の場合は、PHTは命令の下位アドレスだけでインデックスされていたが、2レベルの場合は、命令の下位アドレスと前記のBHTの出力を連結したものをインデックスとして用いる。図7.2では下位アドレスが10ビット、BHTの出力が4ビットで、インデックスは14ビットとなり、PHTのサイズとしては16Kエントリが必要となる。

BHTのシフトレジスタの長さが長ければ、それだけ長いパターンを認識できるのであるが、一方、1ビット長くするごとにPHTのエントリ数が倍増し、必要なハードウェア量が急増する。また、長くしてもその効果は飽和傾向にあるので、両者のトレードオフから3～4ビットというのが一般的である。

この構造では、同じアドレスの条件分岐命令に対してBHTのローカル履歴の4ビット分、16個のPHTエントリ(2ビット飽和カウンタ)が対応する。したがって、前記の(NT、T、T、T)とこれを循環させた(T、NT、T、T)、(T、T、NT、T)、(T、T、T、NT)の4つのパターンで独立したカウントが出来るようになり、(NT、T、T、T)のカウンタはNot Taken予測になり、その他の3つのカウンタはTaken予測になることができる。

そして、条件分岐命令のコミット時に、コミット機構から命令アドレスを得て、デコード時と同様にBHTとPHTをアクセスする。コミット時には分岐がTakenであったかNot Takenであったかが分かるので、それにより、PHTのカウンタをTakenの場合は+1、Not Takenの場合は-1して更新する。また、BHTのエントリを読み出してシフトレジスタに入れ、分岐がTakenであったか、Not Takenであったかを書き込んで1bitシフトしてBHTのエントリに書き戻す。

このローカル履歴を用いる分岐予測法は、PA(Per-Address Adaptive)分岐予測方式とも呼ばれる。図7.2は、BHTの各エントリに対してすべての異なるローカル履歴分のPHTエントリを持つ構成になっているが、このような構成は、BHTをアクセスする条件分岐命令のアドレスごとに全ローカル履歴分のPHTエントリが確保されているのでper-addressということで、「PAp」と言われる。

しかし、前記の例に見られるように、4ビットのシフトレジスタの場合は、1命令に対して16個のPHTエントリのグループが対応するが、そのうちの4個のエントリしか使われていない。

PHTのアクセスに使用する条件分岐命令のアドレスビット数をBHTのアクセスよりも減らして、1グループのローカル履歴を複数の条件分岐命令で共用する構成は「PAs(per-set)」と呼ばれる。このようにして、残りのエントリが別の条件分岐命令で有効利用されれば性能向上の可能性があり、 BHTとPHTの合計ビット数を一定として比較すると、PHTのビット数に比べてBHTのビット数を多少大きめにする構成が成績が良いようである。

また、究極的にBHTの全ての条件分岐命令で1つのローカル履歴のセットを共用する(つまり、履歴のビットだけでPHTを引く)構成も考えられ、これを「PAg(global)」と呼ぶ。しかし、PAg構成は論文ではPA方式の1つの分類としては出てくるが、商用のプロセサで使用されたという話は聞かない。