最初はGolden Coveの方向分岐予測器を調べていたのですが、規則的な分岐履歴系列を与えても正答率が100%に張り付かないなど、あまりにもアナログで複雑な挙動を示すのであきらめました。それと比べてZen2の方向分岐予測器は、正答率が0%や100%に張り付く非常にデジタルな動作をするようで、中身を推測しやすそうです。

測定環境

AMD EPYC 7702 64-Core Processor
gcc (GCC) 7.3.1 20180303 (Red Hat 7.3.1-5)
- スタティックリンクを用いた
perf version 3.10.0-1160.15.2.el7.x86_64.debug

使用される分岐履歴の長さの推定

単純なループの例

まずは、以下のアセンブリを実行した際の分岐予測ミス数を調べてみます。

        .text
        .intel_syntax noprefix
        .globl main
main:
        mov rcx, 20000000
        mov rax, 1
.p2align 6, 0x90
L0:
        sub rax, 1
        jne L1
        mov rax, （パターン長）
L1:
        sub rcx, 1
        jne L0
        ret

すると、パターン長が33回、39回、44回、45回、47回以上、の時に分岐予測ミスが（20000000÷パターン長）回程度発生します。この分岐予測ミスは、jne L1部分に由来するとみて間違いないでしょう。

しかし、ここから分岐履歴長は90程度である、と結論付けるのは危険です。もう少し調査してみましょう。

分岐命令のアドレスを変更してみると

以下のように、NOPをいくつか挿入することで、分岐命令のアドレスを変化させてみます。

        .text
        .intel_syntax noprefix
        .globl main
main:
        mov rcx, 20000000
        mov rax, 1
.p2align 6, 0x90
L0:
        （nopを何個か）
        sub rax, 1
        jne L1
        mov rax, （パターン長）
L1:
        sub rcx, 1
        jne L0
        ret

すると、分岐予測ミス数は以下の図のようになりました。 Excelの機能で、十分分岐予測ミス数が多かった部分を色付けしました。

この結果から、以下のことが言えます。

パターン長が47以上だと当てられない
分岐命令のアドレスによっては、パターン長が47未満でも予測を外すことがある
- 予測を外すパターン長はNOPの数により何グループかに分けられ、4NOPや8NOPを中心に対称
  - 分岐予測テーブルにアクセスする際のインデクス関数がXOR等の比較的単純なものであることを示唆

頑張れば分岐予測テーブルのアクセスに使うインデクス関数を予測出来そうです。しかしそのためにはまず、どういった種類の分岐履歴が使われているかを明らかにする必要があります。

分岐履歴の種類

分岐履歴に種類なんてあるのか、という感じですが、よく使われる分岐履歴には以下の二種類があります。

分岐方向履歴

一般的な教科書に書かれている、もっとも有名なものです。

分岐方向履歴はその名の通り、分岐方向（成立or不成立）の情報を一列に並べたものです。

成立（taken）の場合は1を、不成立（not taken）の場合は0を、ビット列の末尾に追加する、といった方法で作られます。

分岐先履歴

商用プロセッサでよく使われている[1]方法だそうです。

分岐先履歴は、分岐が成立したときのみ更新される履歴です。更新時には、その分岐命令のアドレスを分岐先のアドレスを組み合わせてハッシュ関数に通した値が使われます。

分岐先履歴の利点は以下のようにたくさんあり、商用プロセッサで使われるのも理解できます。

複数の分岐命令を並列に予測可能
- 分岐方向履歴だと、「直前の命令は分岐命令でない」「直前の命令は分岐命令で条件不成立」の二通りの可能性を考慮する必要がある
不成立の分岐を見逃しても履歴が壊れない
- 分岐方向履歴だと、「この命令は条件分岐命令か」も正しく予測する必要がある
（ハッシュ関数を通さずフルの情報が使える場合）実行経路情報を一意に特定できる
- 分岐方向履歴は、実行経路が異なっても同じになることがある

使用されている分岐履歴の種類と履歴長の推定

以下のアセンブリを実行した際の分岐予測ミス数を調べてみます。

        .text
        .intel_syntax noprefix
        .globl main
main:
        mov rcx, 20000000
        mov rax, 1
.p2align 6, 0x90
L0:
        （nopを何個か）
        sub rax, 1
        je L1
        sub rax, （パターン長）
L1:
        add rax, （パターン長）
        sub rcx, 1
        jne L0
        ret

すると前回とは違い、NOPの数によらず予測できなくなるパターン長は92以上の場合となります。

この違いは、分岐パターンの違いにあります。

最初に使ったアセンブリでは、分岐パターンは TTTTTTTT.....TTNT を繰り返すものでした（ここで、Tは条件成立（taken）、Nは条件不成立（not taken）を意味します）。一方、今回使ったアセンブリでは、分岐パターンはNTNTNTNT...NTTTを繰り返すものになっています。

つまり、分岐パターンにNが多い時は長いパターンを当てることができるようになっています。

したがって、Zen2の分岐予測器では、分岐先履歴が使われているといってよいでしょう。

また、その履歴長はおそらく91でしょう。その根拠は以下です。

最初に使ったアセンブリで、履歴長が92あればパターン長が47の時を当てられるはずだが当てられていない
今回使ったアセンブリで、履歴長が92あればパターン長が92の時を当てられるはずだが当てられていない

まとめ

Zen2の方向分岐予測器の仕組みを解析してみました。その結果、分岐先履歴が使われていること、履歴長は91であること、分岐予測テーブルにアクセスする際のインデクス関数は単純そうであること、が分かりました。

参考文献

[1] Y. Issii, et al.,"Rebasing Instruction Prefetching: An Industry Perspective", IEEE Computer Architecture Letters, 19(2), 2020.

よーる

Zen2の方向分岐予測器を調べてみる（その1）