以下に紹介するのは15年前の技術なので、全然最新じゃないですね。 最近の分岐予測器でも使われる優秀な技術ということでしょう。
folded history
グローバル履歴数百ビットを、高々20ビット程度に圧縮するハッシュ関数をどう作るかという問題の解決策です。 毎回数百ビットを読み込んで計算するのは大変なので、ローリングハッシュを使います。 ローリングハッシュを使えば、新しい履歴を取り込み、必要な履歴長より古くなった部分を追い出すという計算だけで済むため、計算する回路が単純化されます*1。
実際に使われるハッシュ関数のパラメータを以下のように定義します。
- olength: ハッシュ関数の入力（ghist）のビット数
- clength: 出力のビット数
普通のローリングハッシュでは乗算や剰余演算が必要ですが、回路を簡単にするため以下のような非常に単純なものを使います。
- Bを掛ける操作: ビット列を左に一ビット分ローテート
- 最新の入力を取り込む操作: 最下位ビットを入力ビットとxorする
このようにすると、各操作は逆操作が存在します。最古の入力（olength回前の入力ビット）を追い出す操作はどうなるでしょうか？
最古の入力の影響は、olength回左ローテートされた位置に存在しています。これは、下から数えてolength % clengthビット目のことです。よって、最古の入力を追い出す操作は、
- 下から数えてolength % clengthビット目を入力ビットとxorする
になります。
ただし、このままの方式は、分岐予測器に使うハッシュ関数として適してるとは言い難いものになっています。 というのも、周期がclengthと同じようなグローバル履歴パターンをこの方法でハッシュ化すると、衝突が頻繁に発生してしまいます。 たとえば、clength=6, olength=22の場合を考えてみます。 6回ごとに分岐が成立するようなプログラムの分岐を当てたいとします。すると、以下のようなパターンが現れるはずです。
000100000100000100000100100000100000100000100100000100000100000100100000100000100000100000000100000100000100000000100000100000100000
しかし、上四パターンはいずれも000000にハッシュ化されてしまいます。
そこで、複数のclengthでハッシュ化した値をxorするという方式が使われています。たとえば、TAGE-SC-L(2016)では、clength=11, 13, (17or19or21or23)を使っていました。BATAGE(2018)では、clength=6,7で作ったハッシュとclength=11,12で作ったハッシュの連結を使っています。
上で見たような、周期現象があるとハッシュの衝突が頻繁に発生し区別がつかなくなる事態は、周期がclengthの倍数である場合にのみ発生します。 複数のclengthでハッシュ化した値をxorして使う場合、どれか一つのclengthで問題が発生しても他のclengthで問題なければ大丈夫そうです。 よって、複数のclengthを使えばそれらすべての公倍数の周期でしか発生しなくなることになり、事実上発生しなくなります。
複数のclengthでハッシュ化した値をxorする時、気を付けないといけない点があります。 それは、「ビット位置をずらさずにxorしてはいけない」という点です。
olength=10だとして、その履歴がc9, c8, c7, c6, c5, c4, c3, c2, c1, c0のようになっているとします。
clength=7で畳み込むと、(c6, c5, c4, c3, c2^c9, c1^c8, c0^c7)になります。
clength=6で畳み込むと、(c5, c4, c3^c9, c2^c8, c1^c7, c0^c6)になります。
これをビット位置をずらさずにxorすると、
| clength=7 | c6 | c5 | c4 | c3 | c2^c9 | c1^c8 | c0^c7 |
|---|---|---|---|---|---|---|---|
| clength=6 | 0 | c5 | c4 | c3^c9 | c2^c8 | c1^c7 | c0^c6 |
| xorした結果 | c6 | 0 | 0 | c9 | c9^c8 | c8^c7 | c7^c6 |
のようになり、c5～c0の情報が消えてしまいました！直近の分岐履歴は重要なことが多いため、これは大問題です。
上位ビット側に位置を合わせてxorを取れば、このようなことはなくなります。
| clength=7 | c6 | c5 | c4 | c3 | c2^c9 | c1^c8 | c0^c7 |
|---|---|---|---|---|---|---|---|
| clength=6 | c5 | c4 | c3^c9 | c2^c8 | c1^c7 | c0^c6 | 0 |
| xorした結果 | c6^c5 | c5^c4 | c4^c3^c9 | c3^c2^c8 | c2^c9^c1^c7 | c1^c8^c0^c6 | c0^c7 |
こうして作ったハッシュ関数はほぼ最適なようで、ここを工夫しても分岐予測器の精度は上がらないようです。 もちろん、ハッシュ関数の入力として何を使うかは精度に大きく影響を与えます。
folded historyには、次回のハッシュ値の一部のビットが予測可能という性質があります。これは、実際のハードウェアに分岐予測器を実装する際、非常に有利な特性です。
分岐予測器は次々に予測結果を出さないといけないため、基本的にパイプライン化することができません。 しかし、直前のサイクルの影響を受けない部分があれば、その部分はパイプライン化することができることになります。 folded historyの「予測可能な一部」は、直前のサイクルの影響を受けない部分であり、この部分をパイプライン化することができます。
MIN-TAGEというハードウェアを意識した実装では、このことが使われています。
*1:ただし、ghist以外の内部状態を持つことになるため、分岐予測ミスの発生に備えてこれを保存しておく必要がある点に注意しなくてはなりません。分岐予測ミスが発生したら命令のフェッチを即座に開始する必要があるため、内部状態を再計算している時間はありません。
