gshare分岐予測器というのは、単純な構造の分岐予測器の中では最も性能が良い分岐予測器であり、1993年に発表されました。
このgshare分岐予測器について、あまり教科書に書いていないことを調べたので、まとめておきます。
この記事には、以下のものが含まれます。
- gshareの適切なインデックスの作り方
- 容量ごとに最適なグローバル分岐履歴とその理由
以下では、分岐予測器の簡単な仕組みおよびbimodal分岐予測器（per Address 2-bit saturating counter scheme）についての知識を前提とします。
gshare分岐予測器とは
bimodal分岐予測器は、単にその分岐命令の分岐方向の偏りだけを頼りに分岐方向を予測します。 分岐命令のアドレス（の下位Nビット）をインデックスとし、パターンヒストリーテーブル(PHT)という飽和二ビットカウンターの配列にアクセスすることで、予測を行います。
それに対しgshare分岐予測器は、グローバル分岐履歴（直近いくつかの条件分岐命令の分岐方向の系列）を利用し、他の分岐命令の分岐方向との相関をもとらえることで予測精度を向上させる手法です。 分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴をxorしたものをインデックスとし、PHTにアクセスすることで予測を行います。 xorした場合情報が失われてしまいますが、使われていないPHTエントリを有効活用できるようになります。
ちなみに、分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴を連結したものをインデックスとする分岐予測器はgselect分岐予測器と呼ばれますが、利用されるPHTエントリに偏りが生じるため、gshare分岐予測器のほうが性能が良いとされています。
正しいインデックスの作り方
分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴をxorするという手法は有名ですが、具体的にどのようにxorするのかについて、詳細に書かれた教科書を見たことがありません。
実は、ここでのxorの仕方は結構重要です。複数の異なる分岐命令＆グローバル分岐履歴が同じインデックスになってしまう（エイリアスが起こる）場合、破壊的な学習が行われ、予測精度が低下してしまいます。
理想的なハッシュ関数を使えばエイリアス頻度を最小限に抑えることができます。しかし、xorするだけという単純なハッシュ関数を用いて理想的なエイリアス頻度を達成するには、少し工夫が必要です。
【間違い】分岐命令の下位アドレスとグローバル分岐履歴をxor
| PC9 | PC8 | PC7 | PC6 | PC5 | PC4 | PC3 | PC2 | PC1 | PC0 |
|---|---|---|---|---|---|---|---|---|---|
| ghist3 | ghist2 | ghist1 | ghist0 |
このようにしてしまうと、頻繁にエイリアスが発生してしまいます。なぜなら、プログラムの多く実行される部分は狭い範囲に集中していることが多く、そこに含まれる分岐命令のPCの上位ビットは似ていることが多いからです。
【正解】分岐命令の上位アドレスとグローバル分岐履歴をxor
| PC9 | PC8 | PC7 | PC6 | PC5 | PC4 | PC3 | PC2 | PC1 | PC0 |
|---|---|---|---|---|---|---|---|---|---|
| ghist3 | ghist2 | ghist1 | ghist0 |
このようにすることで、近くに存在する分岐命令との狭い範囲にある分岐命令がお互いにエイリアスの関係になってしまう事態が避けられます。 当然遠い位置にある特定の分岐命令との間でエイリアスが起こる可能性は残されるのですが、理想的なハッシュ関数と比べそのような事態が発生する頻度が高いということはないはずです。
【最良】直近の分岐履歴を分岐命令の上位アドレスとxor
| PC9 | PC8 | PC7 | PC6 | PC5 | PC4 | PC3 | PC2 | PC1 | PC0 |
|---|---|---|---|---|---|---|---|---|---|
| ghist0 | ghist1 | ghist2 | ghist3 | ghist4 | ghist5 | ghist6 |
もし使用するグローバル分岐履歴長が長めである場合、順番を逆にし、直前の分岐履歴がPCの最上位ビットとxorされるようにするほうがやや良い性能を示すようです。 一般に、直近の分岐履歴のほうが需要であることが原因であると思われます。
PHTの容量と分岐履歴長毎の予測性能
一般に、bimodal分岐予測器もgshare分岐予測器も、PHTの容量を増やせば増やすほど予測性能が向上します。もちろん、エイリアスが十分発生しなくなる容量まで増やすと、性能向上は頭打ちとなります。
gshare分岐予測器では、グローバル分岐履歴長を伸ばせば伸ばすほど遠い分岐命令との相関もとらえられるようになります。しかし、それに伴い以下の二種類の問題が発生するため、グローバル分岐履歴長を伸ばせば伸ばすほど予測性能が上がるわけではありません。
- 学習するべきパターンが増加し、エイリアスの可能性が増加する（グローバル分岐履歴長3であれば、一つの分岐アドレスにつき最大で8パターン覚える必要がある*1）
- 遠い過去の分岐履歴との相関がない分岐について、初見のパターンである割合が増加する（bimodal分岐予測器なら前に見たことのある分岐命令アドレスで当てられたのに、というケース）
実測
分岐予測器の世界的な大会である、cbp5のルールに従って、各手法の分岐予測ミス率を測りました。cbp5では、分岐命令の系列（トレース）が440個*2公開されており、付属のシミュレータを使うと千命令当たりの予測ミス回数（misp./KI）が出力されます。440個のトレースについて、その平均をとることで、いろいろな分岐パターンを当てることができるかを評価します。
440回もシミュレータを動かす必要があるため、データを取るには10時間以上かかります。
図1は、PHTのエントリ数を変更したときの、各分岐予測器（bimodal, gshareでグローバル分岐履歴長が1, 2, 4, 8, 12, 16, 22, 28のもの）の予測ミス率を表しています*3。
測定の結果わかったことは、
- PHTエントリ数が256未満なら、gshareを使わずにbimodalを使ったほうが良い
- PHTエントリ数が256～64 Kiくらいの時、容量を二倍にするごとにグローバル分岐履歴長を2増やすくらいがよい。グローバル分岐履歴長を伸ばしすぎるとかえって性能が低下する
- PHTエントリ数が64 Ki～4 Miくらいの時、PHTのインデックスのビット数と同じだけのグローバル分岐履歴長が良い*4
- PHTエントリ数が4 Mi以上ある場合でも、グローバル分岐履歴長を22より大きくするのは性能を低下させる
なぜそうなるのか
PHTエントリ数が256未満なら、gshareを使わずにbimodalを使ったほうが良い
PHTエントリ数が非常に小さいため、エイリアスの可能性が非常に高く、容量性ミスが発生しています。したがって、学習するべきパターン数を抑えることが重要です。
PHTエントリ数が256～64 Kiくらいの時、容量を二倍にするごとにグローバル分岐履歴長を2増やすくらいがよい。グローバル分岐履歴長を伸ばしすぎるとかえって性能が低下する
PHTエントリ数は標準的な数ですが、エイリアスの可能性がそれなりにあり、競合性ミスが発生しています。したがって、破壊的な競合の発生確率を下げるためにグローバル分岐履歴長をほどほどに抑えることが重要です*5
PHTエントリ数が64 Ki～4 Miくらいの時、PHTのインデックスのビット数と同じだけのグローバル分岐履歴長が良い
PHTエントリ数は非現実的な数になってきており、十分なエントリ数があります。したがって、遠くの分岐との相関を捉えるため、グローバル分岐履歴長をなるべく長くすることが重要です。
PHTエントリ数が4 Mi以上ある場合でも、グローバル分岐履歴長を22より大きくするのは性能を低下させる
PHTエントリ数は事実上無限大とみなせます。グローバル分岐履歴が長すぎる場合、「過去の分岐との相関はないが、分岐方向は偏っている分岐」を当てるために非常に多くのパターンを学習する必要があります。つまり、"初期参照ミス"の発生が支配的な領域です。したがって、"初期参照ミス"の数を減らすため、グローバル分岐履歴長をむやみに長くしないことが重要です。
エントリー数4 GiのPHTを使用したときの、分岐履歴長毎のgshare分岐予測器の性能の比較
分岐履歴長22のところで最小値を取っていることがわかります。
bimodal分岐予測器と、容量ごとに最適な分岐履歴長を使用したgshare分岐予測器の性能の比較
分岐予測器としてよく使われる1KiB～64KiBの範囲で、効率よく性能向上が得られています。 特に、容量をつぎ込んだbimodal分岐予測器の限界10.397 misp./KIをたったの512 Byteで実現できます。
また、どれだけ容量をつぎ込んだとしても、5.585 misp./KI止まりです。 gshare分岐予測器には先ほど見たような複数のトレードオフが存在するため、容量をつぎ込めば性能が上がるというわけではありません。
まとめ
gshare分岐予測器について、xorでインデックスを作るといってもエイリアスが起こりにくい作り方をするためには一工夫いることがわかりました。
また、シミュレータで非現実的な大きさまでのgshare分岐予測器の実験を行うことにより、最適なグローバル分岐履歴長の選び方と、なぜそうなるのかの理由がわかりました。
