前回に引き続き、Zen2の方向分岐予測器の仕組みを明らかにしていきます。

分岐履歴の仕組み

gselect(GAs)のような単純な分岐予測器は、分岐履歴をそのまま分岐予測テーブルのインデクスの一部として利用します。 gshareのような分岐予測器であっても、分岐履歴をそのままPCとXORして分岐予測テーブルのインデクスとして利用するのが一般的です。このようなことができるのは、（分岐履歴のビット数）≦（PHTのインデクスのビット幅）が成り立つときに限ります。

一方、Zen2の方向分岐予測器の分岐履歴は、一分岐命令当たり5bit×履歴長91で合計455bitもあります。したがって、分岐予測テーブルのインデクスに分岐履歴をそのまますべて使うことは不可能です。そのため、分岐履歴同士でXORするなどして情報を圧縮することが行われているはずです。この情報圧縮に使われる関数を特定してみます。今回はまず、分岐履歴の更新方法を調べてみます。

前回までは二つの分岐命令を使って実験していましたが、今回からは三つの分岐命令を使って実験していきます。実験に使うアセンブリコードは以下の通りです。

        .text
        .intel_syntax noprefix
        .globl main
main:
        mov rcx, 200000
.p2align 6, 0x90
L0:
        mov rax, （パターン長）
        （nopを何個か）
L1:
        sub rax, 1
        jne L1 # 分岐A
        （nopを何個か）
        je L2 # 分岐B
L2:
        （nopを何個か）
        sub rcx, 1
        jne L0 # 分岐C
        ret

以下では、nopの数を具体的に示すのではなく、分岐A, B, Cの最終バイトのアドレスをα, β, γとして記述します。

実験1：情報の追い出され方

β=0x401000, γ=0x402000に固定し、パターン長およびαを変化させました。その結果、分岐予測が200000回以上外れた組み合わせは以下のようになりました。

	82	83	84	85	86	87	88	89	90	91	92	93	備考
0x400001	×	×	×	×	×	×	×	×	×	×	×	×	Addr[0]は使われない
0x400002						×	×					×	Hash_0(Addr)=Addr[1]
0x400004					×	×					×	×	Hash_1(Addr)=Addr[2]^...
0x400008				×	×					×	×	×	Hash_2(Addr)=Addr[3]^...
0x400010					×	×					×	×	Hash_1(Addr)=Addr[4]^...
0x400020				×	×					×	×	×	Hash_2(Addr)=Addr[5]^...
0x400040			×	×					×	×	×	×	Hash_3(Addr)=Addr[6]^...
0x400080				×	×					×	×	×	Hash_2(Addr)=Addr[7]^...
0x400100			×	×					×	×	×	×	Hash_3(Addr)=Addr[8]^...
0x400200		×	×					×	×	×	×	×	Hash_4(Addr)=Addr[9]^...
0x400400			×	×					×	×	×	×	Hash_3(Addr)=Addr[10]^...
0x400800		×	×					×	×	×	×	×	Hash_4(Addr)=Addr[11]^...

この実験結果から、以下のことが分かります。

分岐履歴長を超えて古い情報が一度に無くなるのではなく、だんだんなくなっていく
- 普通のローリングハッシュではなく、左シフトで追い出されていくような感じ
なくなっていく順は、Hash_4、Hash_3、Hash_2、Hash_1、Hash_0の順
分岐履歴情報が完全になくなるまでの期間という意味において、分岐履歴長はやはり91

ところで、パターン長83～88のところでは、追い出されることとは無関係の分岐予測ミスが発生しています。以下の実験ではまず、このような現象の発生しないパターン長82で実験を行っていきます。

実験2：情報の重ね合わせ方

今度はパターン長を82、α=0x401000に固定し、βとγを変化させていきます。その結果、分岐予測が200000回以上外れた組み合わせは以下のようになりました。

これらのパターン（βγαα……α）で分岐予測に失敗するのは、αが連続しているパターン（αααα……α）と区別がつかないことが原因でしょう。つまりこれらのパターンでは、分岐履歴が「αの生成する分岐履歴情報＝0b00000が連続している場合の分岐履歴」と同一になっているはずです。

この結果から最低限分かることをまとめてみます。

分岐履歴中に1が立っているビットが1つ
- Hash_2(γ)のみが1の場合、区別がつかない
- Hash_1(γ)のみが1の場合、区別がつかない
- Hash_0(γ)のみが1の場合、区別がつかない
- Hash_1(β)のみが1の場合、区別がつかない
- Hash_0(β)のみが1の場合、区別がつかない
分岐履歴中に1が立っているビットが2つ
- Hash_3(β)とHash_4(γ)のみが1の場合、区別がつかない
- Hash_3(β)とHash_0(γ)のみが1の場合、区別がつかない
- Hash_2(β)とHash_3(γ)のみが1の場合、区別がつかない
- Hash_2(β)とHash_1(γ)のみが1の場合、区別がつかない
- Hash_1(β)とHash_2(γ)のみが1の場合、区別がつかない
- Hash_1(β)とHash_0(γ)のみが1の場合、区別がつかない
- Hash_0(β)とHash_3(γ)のみが1の場合、区別がつかない
- Hash_0(β)とHash_1(γ)のみが1の場合、区別がつかない

これらを観察すると、以下の非常に規則的な組み合わせでXORされていることが分かります。

Hash_3(β)とHash_4(γ)
Hash_2(β)とHash_3(γ)
Hash_1(β)とHash_2(γ)
Hash_0(β)とHash_1(γ)

その他の不規則な区別がつかない組み合わせは、分岐予測テーブルのインデクス関数由来だと考えられます。

また、パターン長75～81で実験しても同様の規則的な区別のつかない組み合わせが存在しました。この法則性は、分岐履歴を更新する際の操作が「1ビット左シフトしてから下位ビットに分岐履歴情報をXOR」という仕組みになっているのが由来だと考えられます。パターン長75～81で実験した際の不規則な区別のつかない組み合わせの出現パターンは、これと整合します。

wire Hash_0 = BrAddress[1];
wire Hash_1 = BrAddress[4] ^ BrAddress[2];
wire Hash_2 = BrAddress[7] ^ BrAddress[5] ^ BrAddress[3];
wire Hash_3 = BrAddress[10] ^ BrAddress[8] ^ BrAddress[6];
wire Hash_4 = BrAddress[11] ^ BrAddress[9];
wire [4:0] TargetHash = { Hash_4, Hash_3, Hash_2, Hash_1, Hash_0 };

TargetHistory <= (TargetHistory << 1) ^ TargetHash;