チョット分け合ってA64FXのマニュアルを読みなおしている。分岐予測について調べたかったのでもう一度読み直してまとめている。
条件分岐予測には私の理解では大きく2種類があって、
局所分岐予測：条件分岐命令毎に分離した履歴バッファを利用する。つまり条件分岐命令のPCアドレスを使用して、この命令の場合はこの履歴、別の命令の場合は別の履歴、というようにテーブルを作って管理する。
- ただし無尽蔵に巨大なテーブルを作ることは出来ないため、PCのアドレスに基づいて1024～4096程度のエントリを持ち、それぞれのPC値に基づいてテーブル情報のアップデートを行う。
広域分岐予測：局所分岐予測では、異なる分岐命令間の相関関係を使って予測することができないため、プログラムのシーケンス中で分岐がどのような順番で実行されるのかについて記録を行いその情報に基づいて予測を行う。この場合プログラムシーケンス中に有意な相関関係がない場合、高い精度を持つことができない。
- この分岐予測のためには、Global History Register (GHR) が必要になる。GHRのビット数が
mならば、過去のm回の分岐予測の結果を記録している。
- この分岐予測のためには、Global History Register (GHR) が必要になる。GHRのビット数が
A64FXのマニュアルを見る限り、フロントエンドが採用しているのは、
Small Taken Chain Predictor (S-TCP) :
- グローバル分岐予測
- Takenのチェインを作りループが発生すればそれをループと検出する。ループを検出すると実行パスに従って分岐予測を行う。
- これ、もとになる論文が見つからなかった。参考文献はあるのだろうか？
Loop Prediction Table (LPT) :
- ローカル分岐予測
- Taken、Not Takenが連続した回数を記録し、その履歴をもとに分岐方向を予測する。
- LPTは8エントリで構成され、分岐命令を8命令まで記録できる。
- これはつまり、「Takenが10回なら次はNot Taken」「Not Takenが10回続けば次はTaken」といった予測をするのだろうか？記録できる種類は1エントリにつき1種類かな？カウント回数とそれに基づくTaken / Not Takenの情報か。
Branch Weight Table (BWT)
- Branch Weight TableとGlobal History Register (GHR)に基づく分岐予測方式。
- ここではPiecewise linearアルゴリズムに基づいて分岐予測をすると書いてあるが、Piecewise linearというのは「区分線形関数」というらしいが、ここはあまり気にしなくても良い気がする。重要なのは線形関数によって予測が計算されているということである。
- 分岐予測の方法、以下の線形関数を用いてPredictionを行う。図では乗算として書いてあるがもちろん乗算は使っていないだろう。NとTが1と-1なので符号反転して加算しているだけであると思われる。あとはWeight Tableがどの程度のビット幅であるのかが気になるくらい。
- Branch Weight Tableのアップデート方法、図では乗算として書いてあるがもちろん乗算は使っていないだろう。これがどういう理屈でこのようになっているのかについては良く分からない。
- Branch Target Buffer (BTB)
- これは分岐予測における分岐先のアドレスを記録するためのバッファで、分岐方向を記録しているわけではない。A64FXの場合は4-way、2048エントリの構成となっている。
- 相対分岐予測の場合は分岐先アドレスをその場で計算できる。
- 間接分岐命令については分岐先アドレスが異なる可能性があるため、Rehashと呼ばれる機構を採用している。
- 分岐方向履歴
- ターゲットヒストリレジスタ（つまりこれは間接分岐命令におけるジャンプ先アドレスのことらしい）
- をhashし、アドレス予測に使用しているらしい。
