gshare分岐予測器について - よーるの補足です。
分岐命令の上位アドレスとグローバル分岐履歴をxor、について
吉瀬 謙二, 片桐 孝洋, 本多 弘樹, 弓場 敏嗣:「高性能プロセッサのための代表的な分岐予測器の実装と評価」Technical Report UEC-IS-2003-2, Version 2003-05-0
http://www.arch.cs.titech.ac.jp/~kise/SimAlpha/doc/uec-is-2003-02.pdf
という論文に書いてありました。
直近の分岐履歴を分岐命令の上位アドレスとxor、について
直近の分岐履歴を分岐命令の下位アドレスとxorする場合、以下のようなパターンでインデックスが衝突してしまう可能性があります。 従って、直近の分岐履歴を分岐命令の下位アドレスとxorする場合、理想的なハッシュ関数を使った場合と比べて衝突が増えます。
- PCαは、分岐方向履歴とは無関係に、予測不可能な分岐をする。
- PCαがtakenだった場合、いくつかの当てられる分岐が来た後、PCβが予測の難しい（しかし分岐方向履歴を見れば当てられる）分岐である。
- PCαがnot-takenだった場合、いくつかの当てられる分岐が来た後、PCγが予測の難しい（しかし分岐方向履歴を見れば当てられる）分岐である。
- PCβとPCγは同じ関数内の近い位置にあり、その上位アドレスは一致している。
直近の分岐履歴を分岐命令の上位アドレスとxorする場合、このようなプログラムの構造（taken側とnot-taken側のPCのビット表現が似ていることが多い）が原因で生じる理想的なハッシュ関数とのずれは、かなり低く抑えられます。
cbp5の分岐トレースが440個、について
443個ありうち3個壊れています、と書きましたが、どうやら壊れているのではなくあまりにも予測が簡単すぎてmisp. /KIが0.0000になっているようです。 集計用スクリプトの書き方が甘く、misp. /KIが0.0000のものはエラー落ちしたものとみなしているのが原因だったようです。
グローバル分岐履歴長を22より大きくするのは性能を低下させる、について
グローバル分岐履歴長22というのは具体的に意味のある数字ではなく、どのようなトレースを選ぶかに大きく依存します。 cbp5の分岐トレースの中には、23回周期のループを回っているだけのようなトレース（SHORT_MOBILE-53、上で壊れていると勘違いしたトレース）が存在します。 これはグローバル分岐履歴長を22以上にすると完璧に当てることができるようになるため、少し無理してでもグローバル分岐履歴長22を確保したほうがよいという結論が得られています。
無限に容量がある場合でもgshare分岐予測器で取り扱うことのできるグローバル分岐履歴長はそれほど大きくできないということは、一般論として事実です。
分岐履歴を折りたたむことでより長い分岐履歴を使ったほうが良いか、について
エントリ数2Mi（512KiB、インデックスは21bit）の時、グローバル分岐履歴長22を使うほうがやや性能が高くなりました。 同様の現象は、この事例以外には見つかりませんでした。
