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

前回に引き続き、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;

まとめ

分岐履歴は91bitのシフトレジスタになっている
古い分岐履歴情報は左シフトで追い出される（ローリングハッシュ的な追い出し方ではない）
分岐履歴の更新方法は、「1ビット左シフトしてから下位ビットに分岐履歴情報をXOR」になっている

2022-05-01

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

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

分岐履歴に使われる情報

分岐元アドレス

前回と同様のアセンブリを用いて、分岐命令のアドレスのみを変化させていき、パターン長1～48の予測を当てることができるかを調べていきます。分岐命令のアドレスを変えるためには、NOPを詰める位置（分岐命令の上に置くか下に置くか）を変化させました。

その結果、以下のことが分かります。

分岐命令のアドレスが2n+1の時と2n+2の場合は正答パターンがほぼ一致
2n+1と2n+2の間で繰上りが発生することもある
- 上位ビットが同じで下位ビットが01と10の組でパターンが一致するということではなさそう

このことから、以下の仮説を立てます。

分岐命令のアドレス＋1が分岐履歴に使われる。この時、アドレスの下位1ビットは使われない。

分岐先アドレス

前回の調査の結果、パターン長が9以上で常に予測失敗する命令配置があることを知っています。このようなことが発生するのは、jne L1の生成する分岐履歴情報とjne L0の生成する分岐履歴情報が完全に一致しているからとみて間違いないでしょう。

これを利用すると、どのような分岐履歴情報を生成しているかを調べることができそうです。具体的には、jne L0の生成する分岐履歴情報を固定し、jne L1の生成する分岐履歴情報がそれと一致する場合を探索することで、法則性を見つけていきます。

以下では、手を抜いてパターン長が9の時だけ調べます。以下のアセンブリを実行したとき、分岐予測が十分多く外れる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, 9
        （nopを何個か）
L1:
        （nopを何個か）
        sub rcx, 1
        jne L0
        ret

すると、NOPを詰める量が例えば以下の値の時、分岐予測が十分多く外れることが分かります。

上	中	下	`jne L1`分岐元	`jne L1`分岐先	`jne L0`分岐元	`jne L0`分岐先
3	9	2	0x400547	0x400559	0x40055f	0x400540
3	9	3	0x400547	0x400559	0x400560	0x400540
3	8	4	0x400547	0x400558	0x400560	0x400540
3	7	5	0x400547	0x400557	0x400560	0x400540
3	6	6	0x400547	0x400556	0x400560	0x400540
3	5	7	0x400547	0x400555	0x400560	0x400540
3	4	8	0x400547	0x400554	0x400560	0x400540
3	3	9	0x400547	0x400553	0x400560	0x400540

この結果から、以下の結論を得ます。

分岐先アドレスの情報は分岐履歴に使われない

方向分岐しか存在しない場合、実行経路を一意に特定するためには分岐先アドレスは不要（間接分岐がある場合は分岐先アドレスも必要）であり、このような分岐履歴の持ち方になっていることは理解できます。

分岐元アドレスのハッシュ関数の特定

パターン長が9以上で常に予測失敗する命令配置をまとめてみました。

上	中	下	`jne L1`分岐元	`jne L0`分岐元	(A&~1)^(B&~1)	備考
1	0	0	0x400545	0x400552	0x14	前回発見
3	7	0	0x400547	0x40055b	0x14
3	8	0	0x400547	0x40055c	0x14
4	6	0	0x400548	0x40055b	0x14
4	7	0	0x400548	0x40055c	0x14
5	7	0	0x400549	0x40055d	0x14
5	8	0	0x400549	0x40055e	0x14
7	0	0	0x40054b	0x400558	0x14	前回発見
9	0	0	0x40054d	0x40055a	0x14	前回発見
3	9	2	0x400547	0x40055f	0x28
3	9	3	0x400547	0x400560	0x28
3	0	7	0x400547	0x40055b	0x14
3	0	11	0x400547	0x40055f	0x28
3	0	31	0x400547	0x400573	0x3c
3	0	123	0x400547	0x4005cf	0x9c	`jne L0`は6Byte命令
3	0	143	0x400547	0x4005e3	0xa0	`jne L0`は6Byte命令
3	0	163	0x400547	0x4005f7	0xb4	`jne L0`は6Byte命令
58	0	58	0x40057e	0x4005c5	0xb4	`jne L0`は6Byte命令
58	0	78	0x40057e	0x4005d9	0xa0	`jne L0`は6Byte命令
58	0	82	0x40057e	0x4005dd	0x9c	`jne L0`は6Byte命令
58	0	102	0x40057e	0x4005f1	0x88	`jne L0`は6Byte命令
60	0	6	0x400580	0x400593	0x14	`jne L0`は6Byte命令
60	0	26	0x400580	0x4005a7	0x28	`jne L0`は6Byte命令
60	0	46	0x400580	0x4005bb	0x3c	`jne L0`は6Byte命令
60	0	1142	0x400580	0x400a03	0xf88	`jne L0`は6Byte命令
60	0	1162	0x400580	0x400a17	0xf9c	`jne L0`は6Byte命令
60	1142	0	0x400580	0x400a07	0xf88	共に6Byte命令
60	1154	0	0x400580	0x400a13	0xf9c	共に6Byte命令
60	2542	0	0x400580	0x400f7f	0xa00	共に6Byte命令
60	2798	0	0x400580	0x40107f	0x1500	共に6Byte命令
60	3118	0	0x400580	0x4011bf	0x1440	共に6Byte命令
60	3886	0	0x400580	0x4014bf	0x1140	共に6Byte命令
60	3958	0	0x400580	0x401507	0x1088	共に6Byte命令
60	3982	0	0x400580	0x40151f	0x10a0	共に6Byte命令
60	4078	0	0x400580	0x40157f	0x1000	共に6Byte命令
60	4090	0	0x400580	0x40158b	0x1014	共に6Byte命令
60	4118	0	0x400580	0x4015a7	0x1028	共に6Byte命令
60	8174	0	0x400580	0x40257f	0x2000	共に6Byte命令
60	16366	0	0x400580	0x40457f	0x4000	共に6Byte命令
60	32750	0	0x400580	0x40857f	0x8000	共に6Byte命令

まず「分岐命令のアドレス＋1が分岐履歴に使われる」の謎が解明できました。先ほどまでの実験に使っている分岐命令は全て2Byteのものだったので＋1になっていましたが、正確には「分岐命令の最後のバイトのアドレスが使われる」ということのようです。

また、アドレスのXORで見た差分が0x14の時に分岐履歴情報が区別できないことから、アドレスの2bit目（Addr[2]）とアドレスの4bit目（Addr[4]）はXORされた形でのみ分岐履歴上に存在することが分かります。同様に、以下のような組み合わせでXORされていることが分かります。

(A&~1)^(B&~1)
0x14	Addr[2]	Addr[4]
0x28	Addr[3]	Addr[5]
0x88	Addr[3]	Addr[7]
0xa0	Addr[5]	Addr[7]
0x140	Addr[6]	Addr[8]
0x440	Addr[6]	Addr[10]
0x500	Addr[8]	Addr[10]
0xa00	Addr[9]	Addr[11]

したがって、ハッシュ関数は以下のようになっており、分岐元アドレスの情報を5bitに圧縮していることが分かります。

Hash_0(Addr) = Addr[1]
Hash_1(Addr) = Addr[2]^Addr[4]
Hash_2(Addr) = Addr[3]^Addr[5]^Addr[7]
Hash_3(Addr) = Addr[6]^Addr[8]^Addr[10]
Hash_4(Addr) = Addr[9]^Addr[11]

まとめ

分岐履歴の構築には、分岐命令の最後のバイトのアドレスが使用される
分岐履歴の構築には、分岐先のアドレスは使用されない
分岐命令の最後のバイトのアドレスの最下位ビットは使われない
- 全ての分岐命令は2Byte以上なので、最下位ビットのみ異なる分岐命令の組は通常存在しない
分岐命令の最後のバイトのアドレスの2の位～2048の位（合計11ビット）がハッシュ関数に通されて5ビットに圧縮されて使用される

2022-04-24

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

最初は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.

2022-04-03

IntelのGracemontコアの浮動小数点数演算レイテンシの測定

第12世代インテル® Core™ プロセッサーのEコア（高効率コア）はGracemontというマイクロアーキテクチャでできています。このコアで命令を実行したときのレイテンシを調べたものにuops.info - Tableがありますが、測定方法がよくなくて正しい値になっていません。そこでnanoBenchを用いて独自に測定してみました。

測定方法

sudo taskset -c 23 ./nanoBench.sh -asm "測定コード" -config configs/cfg_AlderLakeE_common.txt

測定結果

`vaddsd` および `vshufpd`

vaddsd xmm0, xmm0, xmm1 → 3.00 cycle
vaddsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1 → 6.00 cycle
vshufpd xmm0, xmm0, xmm1, 0 → 1.00 cycle
vshufpd xmm0, xmm0, xmm1, 0; vshufpd xmm0, xmm0, xmm1, 0 → 2.00 cycle
vaddsd xmm0, xmm0, xmm1; vshufpd xmm0, xmm0, xmm1, 0 → 7.00 cycle
vaddsd xmm0, xmm0, xmm1; vshufpd xmm0, xmm0, xmm1, 0; vaddsd xmm0, xmm0, xmm1; vshufpd xmm0, xmm0, xmm1, 0 → 14.00 cycle
vaddsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1; vshufpd xmm0, xmm0, xmm1, 0; vshufpd xmm0, xmm0, xmm1, 0 → 11.00 cycle

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

vaddsd命令のレイテンシは 3 cycle
vshufpd命令のレイテンシは 1 cycle
vaddsd命令とvshufpd命令を行き来すると、往復で 3 cycle のペナルティ
- uops.info の測定はこのペナルティを考慮できていないため間違い

`vmulsd` および `vfmadd132sd`

vmulsd xmm0, xmm1, xmm1 → 4.00 cycle
vmulsd xmm0, xmm0, xmm1; vmulsd xmm0, xmm0, xmm1 → 8.00 cycle
vmulsd xmm0, xmm0, xmm1; vshufpd xmm0, xmm0, xmm1, 0 → 7.00 cycle
vfmadd132sd xmm0, xmm1, xmm2 → 6.00 cycle
vfmadd132sd xmm0, xmm1, xmm2; vshufpd xmm0, xmm0, xmm1, 0 → 10.00 cycle
vmulsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1 → 6.08 cycle
vmulsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1 → 9.08 cycle
vmulsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1; vmulsd xmm0, xmm0, xmm1 → 10.08 cycle
vmulsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1; vmulsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1 → 12.16 cycle
vmulsd xmm0, xmm0, xmm1; vmulsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1 → 13.08 cycle
vfmadd132sd xmm0, xmm1, xmm2; vmulsd xmm0, xmm0, xmm1; vaddsd xmm0, xmm0, xmm1 → 12.08 cycle
vfmadd132sd xmm0, xmm1, xmm2; vaddsd xmm0, xmm0, xmm1; vmulsd xmm0, xmm0, xmm1 → 13.00 cycle

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

vmulsd命令のレイテンシは 4 cycle
vfmadd132sd命令のレイテンシは 6 cycle
vmulsd命令とvshufpd命令と行き来すると往復で 2 cycle のペナルティ
vfmadd132sd命令とvshufpd命令と行き来すると往復で 3 cycle のペナルティ
- uops.info の測定はこのペナルティを考慮できていないため間違い
vmulsd命令からvaddsd命令にフォワーディングするとき、1 cycle 得することがある（92%ほど発生）

浮動小数点数演算命令と`vshufpd`の行き来はどこにペナルティがあるか

movq rax, xmm0; movq xmm0, rax → 10.00 cycle
vshufpd xmm0, xmm0, xmm1, 0; movq rax, xmm0; movq xmm0, rax→ 11.00 cycle
vaddsd xmm0, xmm0, xmm1; movq rax, xmm0; movq xmm0, rax → 13.00 cycle

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

movq rax, xmm0; movq xmm0, rax命令列で移動させると合計で 10 cycle かかる
この命令列を使った場合、vshufpd命令やvaddsd命令と組み合わせてもペナルティは発生しない

これを使って以下のような実験を行うと、どこでペナルティが発生するかを特定することができます。

vaddsd xmm0, xmm0, xmm1; vshufpd xmm0, xmm0, xmm1, 0; movq rax, xmm0; movq xmm0, rax → 17.00 cycle
vshufpd xmm0, xmm0, xmm1, 0; vaddsd xmm0, xmm0, xmm1; movq rax, xmm0; movq xmm0, rax → 14.00 cycle

したがって、以下のことが分かります。

vaddsd命令からvshufpd命令にフォワーディングするとき、3 cycle のペナルティが発生する
vshufpd命令からvaddsd命令にフォワーディングするときは、ペナルティが発生しない

vmulsd命令、vfmadd132sd命令についても同じ実験を行うことで、どこでペナルティが発生するかを特定することができます。

vmulsd xmm0, xmm0, xmm1; vshufpd xmm0, xmm0, xmm1, 0; movq rax, xmm0; movq xmm0, rax → 17.00 cycle
vshufpd xmm0, xmm0, xmm1, 0; vmulsd xmm0, xmm0, xmm1; movq rax, xmm0; movq xmm0, rax → 15.00 cycle
vfmadd132sd xmm0, xmm1, xmm1; vshufpd xmm0, xmm0, xmm1, 0; movq rax, xmm0; movq xmm0, rax → 20.00 cycle
vshufpd xmm0, xmm0, xmm1, 0; vfmadd132sd xmm0, xmm1, xmm1; movq rax, xmm0; movq xmm0, rax → 17.00 cycle

したがって、以下のことが分かります。

vmulsd命令からvshufpd命令にフォワーディングするとき、2 cycle のペナルティが発生する
vfmadd132sd命令からvshufpd命令にフォワーディングするとき、3 cycle のペナルティが発生する

まとめ

vshufpd命令のレイテンシは 1 cycle
vaddsd命令のレイテンシは 3 cycle
vmulsd命令のレイテンシは 4 cycle
vfmadd132sd命令のレイテンシは 6 cycle
vmulsd命令からvaddsd命令にフォワーディングするとき、1 cycle 得することがある
vaddsd命令からvshufpd命令にフォワーディングするとき、3 cycle のペナルティが発生する
vmulsd命令からvshufpd命令にフォワーディングするとき、2 cycle のペナルティが発生する
vfmadd132sd命令からvshufpd命令にフォワーディングするとき、3 cycle のペナルティが発生する

2021-12-26

IntelのFast Adder (FADD)について

第12世代インテル® Core™ プロセッサーのPコア（高性能コア）はGolden Coveというマイクロアーキテクチャでできていますが、Golden CoveにはFADD演算器が新規搭載されました。 FADD演算器は、浮動小数点数加算を高速に行う演算器であり、そのレイテンシは2 cycleになっています。これは今まで浮動小数点数加算が4 cycleだったのと比べると、2倍速くなったことになります。

浮動小数点数演算器はパイプライン化されているため、レイテンシが改善されてもスループットとピーク性能は変わりませんが、浮動小数点数加算を多く用いるプログラムの高速化が期待できます。（浮動小数点数乗算をあまり含まないのにもかかわらず）浮動小数点数加算を多く用いるプログラムとしては、倍倍精度（疑似四倍精度、double-doubleとも）を用いたプログラムが挙げられるでしょう。実際、倍倍精度の計算を行うプログラムは、かなり高速化するようです。

この記事では、FADD演算器に関連することを特にまとめずいろいろ書いていきたいと思います。

測定環境

Intel Core i9 12900K (Alder Lake-S)
- 5.1 GHzくらいで動いている
Ubuntu 20.04.3 LTS on WSL2 (Windows 11)

浮動小数点数演算レイテンシの歴史（AVX以降）

Golden Cove以外の情報は、uops.infoで公開されているものを利用しました。

マイクロアーキテクチャ	浮動小数点数加算	浮動小数点数乗算	浮動小数点数積和演算
Sandy Bridge/Ivy Bridge	3	5	N/A
Haswell/Broadwell	3	5	5
Skylake以降	4	4	4
Golden Cove	2or3	4	4
Zen+	3	4	5
Zen2	3	3	5
Zen3	3	3	4

スループットなどの情報は、AVX/AVX2によるFMA - Qiitaがまとまっていておすすめです。

スケジューラの戦略

zmmを使わない場合

FADD演算器はPort1とPort5に配置されています。スケジューラは、vaddsd命令（丸めモード指定があってもよい）やzmmを使わないvaddpd命令を必ずPort1かPort5に割り当てます。したがって、プログラム上なにも工夫しなくても、浮動小数点数加算は低レイテンシで実行されます。

zmmを使う場合

zmmを使うvaddpd命令*1がどのポートに割り当てられるかはよくわかりません。平均的なレイテンシが整数にならないため、レイテンシが異なる複数のポートで実行されるものと思われます。

Port0を埋めるために無駄なシフト命令*2を挿入すると、以下の現象が起こります。

レイテンシが改善することがある。3.2cycleが2.4 cycleになる
スループットが改善することがある。最良で1.5命令/cycle程度になる

Port1を埋めるために無駄な整数乗算命令を挿入すると、以下の現象が起こります。

レイテンシが改善することはない
スループットが改善することがある。最良で1.5命令/cycle程度になる

この現象から推測すると、以下のように割り当てられているのではないかと推測します。

zmmを使うvaddpd命令は、Port0, Port1, Port5に割り当てられる
Port0に割り当てられた場合、4 cycleレイテンシ
- 従来通りPort1と共同でAVX512命令を処理するパターン？
- Port1が混んでいる場合、Port0だけでも処理できる？
- Port0はAVX512命令を処理できないので、μOP二つになると思われる
Port1に割り当てられた場合、2 cycleレイテンシ
- Port0が混んでいる場合のみ？
- Port1はAVX512命令を処理できないので、μOP二つになると思われる
Port5に割り当てられた場合、2 cycleレイテンシ
- Port5は単独でAVX512命令を処理できる

いつでも2 cycleではない

vaddsd命令の連鎖を実行する場合、一命令当たりのレイテンシは2 cycleになりますが、他の命令との組み合わせだと2 cycleにならないようです。 vmulsdとvaddsdが交互に並んだ命令列では、その二命令の合計レイテンシが6 cycleとなるのが期待されるところ、実測してみると7 cycleになり一致しません。

おそらく、FADD演算器の結果をFADD演算器に渡す場合のみ2 cycleレイテンシが実現され、他の演算器に渡す場合は3 cycleレイテンシとなります。これは推測ですが、FADD演算器は演算結果を浮動小数点数で出力しないことで2 cycleレイテンシを実現しているのではないでしょうか。具体的には、FADD演算器は加算器の出力とシフト量をそのまま出力しているのではないでしょうか。浮動小数点数加算器の入力側には必ずシフタがあるので、FADD演算器の結果が浮動小数点数加算器に使われるのであれば、そのシフタで一緒にシフトしてしまえば問題ありません*3。このようにすることで、シフタを通す回数が一回減るため、浮動小数点数加算を繰り返すループの計算時間が削減できます。一方、浮動小数点数乗算器の入力側にはシフタがないため、そういった演算器に渡す際のデータ整形のために1 cycleのペナルティを受けると考えられます*4。

浮動小数点数加算ばかりやりたい場合

Golden CoveのPort0は、Haswell/Broadwellと同様に、浮動小数点数加算命令を受け取らず浮動小数点数積和演算命令を受け取るポートになっています。したがって、このポートを活用すると実質的な浮動小数点数加算命令のスループットを2命令/cycleから3命令/cycleに増やすことができます。もちろん、Port0を使った浮動小数点数加算はレイテンシが4 cycleになります。

vfmaddsd命令はPort0かPort1のどちらかに割り当てられる可能性があります*5が、Port0に割り当ててくれる*6ため、実際にスループットとして一サイクル当たり3つの浮動小数点数加算を行うことが可能です。

倍倍精度演算が速くなる

倍倍精度演算には、浮動小数点数乗算を含まない浮動小数点数加算の連鎖が多く出現します。したがって、FADD演算器の追加の恩恵を大きく受けるプログラムであると思われます。

ちょうど最近、以下のような四則演算を網羅したベンチマークが提案されていました。

https://t.co/BVpPsVP4x8
加減乗除を一つずつ含んで無限に繰り返せるループが面白かったので、少しアレンジしてみた。
・初期値を0.4〜0.6の間に取るとずっとその間で乱数っぽく動く。
・べったりと依存性のある計算で、部分的な並列化ができない。
・FMA命令を使えそうなところがない。 pic.twitter.com/hNP5NICgwZ
— kashi (@mkashi) 2021年12月3日

このベンチマークをfloatとdoubleとdouble-doubleで実行してみたところ、floatの場合4.0秒、doubleの場合4.6秒、kv::ddの場合18.2秒（-DKV_USE_TPFMAなしだと22.6秒）となりました。 double-doubleを使った場合のオーバーヘッドがdoubleを使った場合の四倍未満という結果になりました。

Intel Core i7 9700を用いた実験（変なベンチマークテスト - kashiの日記）では、オーバーヘッドは五倍程度という結果だったので、（FADD演算器の追加だけの効果であるかは確認していませんが）最新のCPUでは倍倍精度演算はかなり速いと言えそうです。

*1:AVX512の命令はEコア（高効率コア）を無効にした時のみ使えます

*2:シフト命令はPort6でも実行されるが、Port6はSIMD命令を取り扱えないポートなので省略

*3:計算結果をIEEE754に従うように丸める必要はあります

*4:実際はFMA演算器の加算入力に渡しても3 cycleレイテンシだったので、他の演算器には手を加えていないのだと思われます

*5:ポート割り当ては他アーキテクチャと同じと仮定

*6:Port1が混んでいることを見抜いているのか、単にPort0が優先なのかは不明

2021-12-12

gccにおけるクラス階層ナビゲーションバグ

以下の問題で時間を溶かしたので、メモを残しておきます。

概略

おかしなusing宣言がコンパイラを混乱させ、壊れたバイナリの生成を引き起こすことがあります。 static_castするとポインタの値が変わるような継承構造を持つクラス*1では、基底クラス由来のメンバ関数を呼び出すときにthisポインタの値に適切なオフセットを加減算する機械語コードをコンパイラが生成する必要がある場合がありますが、その計算が正しくないバイナリが生成されます。

呼び出し先の関数ではthisがずれているため、メンバ変数の値が完全におかしく見えます。例えばポインタであるメンバ変数からその先をたぐってメモリアクセス保護違反になったり、仮想関数を呼び出そうとしたときに仮想関数テーブルを正しく引けずメモリアクセス保護違反になったりします。

デバッグの仕方

ポインタの値がずれると、デバッガからはメモリ破壊バグのように見えます。しかし、実際にメモリ破壊しているわけではないので、gdbのwatchpoint・valgrind（memcheckおよびexp-sgcheck）・ -fsanitize=addressといったメモリアクセス検査ツールではバグなしと判定されてしまいます。 this周辺のメモリダンプをしてみると、thisポインタの値がずれているのではないかと推測できます。

バグの簡易な説明

仮想関数を含むクラスを二つ以上継承しているクラス*2において、直接の親クラス以外にある仮想関数を対象にusing宣言を行うと、当該仮想関数を呼び出すときのthisポインタずらし計算がバグる、といった感じのようです。

（2021/12/13 6:00ごろ：もともとは「無意味なusing宣言」と書いていましたが、それがないとコンパイルが通らないようなusing宣言であってもこの問題が発生することを確認したため、記述を変更しました。具体的には、基底クラスと同じ名前の関数をオーバーロード *3したが基底クラスの関数を隠すことを意図していない、というときに使うusing宣言で発生することを確認しました。）

問題の発生するgccバージョン

gcc 10.2.0（自分でビルドしたもの、およびコンパイラエクスプローラーで確認）
gcc 10.3.0（コンパイラエクスプローラーで確認）
gcc 11.1.0（コンパイラエクスプローラーで確認）

問題の発生しないコンパイラ

網羅的に調べたわけではありませんが、おそらく以下のコンパイラでは問題が発生しなさそうです。

gcc 10.1.0 以前
gcc 11.2.0 以降
clang すべて

問題の発生するオプション

最適化をかけてもかけなくても発生します。そもそも、機械語生成の誤りというよりはC++コードの解釈の誤りという感じがするので、C++フロントエンドのバグ*4と思われます。

最小再現コード

（2021/12/13 6:00ごろ：さらに短いソースコードでも再現することを確認したので差し換えました。もともと提示していたコードは[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯです。）

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

#include <iostream>

struct IF1 { virtual ~IF1(){} };
struct IF2 {
    virtual void f(){
        std::cout << __PRETTY_FUNCTION__ << ": this=" << this << std::endl;
    }
};

struct Base : IF1, IF2 {
    void f() {
        std::cout << __PRETTY_FUNCTION__ << ": this=" << this << std::endl;
        IF2::f();
    }
};

struct Derived : Base {
    using IF2::f; // This confuses compilers.

    virtual ~Derived() {
        std::cout << __PRETTY_FUNCTION__ << ":"
                  << " this="        << this
                  << " (Base*)this=" << (Base*)this
                  << " (IF1*)this="  << (IF1*)this
                  << " (IF2*)this="  << (IF2*)this
                  << std::endl;
        f();
    }
    // If you want to define below overload, the using declaration is essentially needed.
    // void f(int){}
};

Derived d;

int main() {}

仮想関数を含むクラスを一つだけ継承している場合、この問題は発生しません。これは、gccが基底クラスの配置を宣言順と逆転させることで仮想関数テーブルへのポインタを統合しようと努力することによります。例えば、このコードのIF1を仮想関数を持たずintのみ含むクラスにしてみると、(Base*)thisと(IF2*)thisが一致しこのバグは発生しなくなります。なお、IF1にintを入れずからっぽにするとEBOが効くようになるので、すべてのクラスのアドレスが同じになり、やはりこのバグは発生しなくなります。

期待される答え

virtual Derived::~Derived(): this=0x601c50 (Base*)this=0x601c50 (IF1*)this=0x601c50 (IF2*)this=0x601c58
virtual void Base::f(): this=0x601c50
virtual void IF2::f(): this=0x601c58

Baseクラスの関数を呼ぶので、Baseクラスの中でのthisは、Derivedクラスの中で(Base*)thisとした値になっていると期待します。

実際の答え

virtual Derived::~Derived(): this=0x601c50 (Base*)this=0x601c50 (IF1*)this=0x601c50 (IF2*)this=0x601c58
virtual void Base::f(): this=0x601c58
virtual void IF2::f(): this=0x601c60

Baseクラスの中でのthisの値が、なぜかDerivedクラスの中で(IF2*)thisとした値と一致してしまいました。

おそらく、gccはusing IF2::f;に騙されてしまったのでしょう。

なお、Base::f()の中でthisがBase*からIF2*に変換されるときの差分（+8 Byte）は正しいですが、Base*の時点でずれてしまっているのでIF2の中でのthisの値もおかしくなっています。

まとめ

直接の親クラス以外のメンバ関数をusing宣言するのは、プログラマにとっても*5 コンパイラにとっても混乱の原因になります。やめましょう。

*1:つまり、多重継承しており、かつEBO(empty base optimization)が効かない場合です。なお、仮想関数を持つクラスを継承している場合、基底クラスは仮想関数テーブルへのポインタを持つため、EBOが効くことはありません。

*2:正確な条件は不明です。仮想関数テーブルへのポインタ（vptrやvfptrと称される）がまとめられないことが条件でしょうか。

*3:オーバーロードとは、引数の型が異なる関数を定義することです。オーバーライドの誤記ではありません。

*4:どのような挙動が正しいのか、私はわかりません。他のコンパイラやgccの古いバージョンと新しいバージョンではこの問題が発生しないため、gccに一時的に埋め込まれたバグであると判断しました。

*5:私はそのソースコードの意図も何が起こるのかもわかりませんでした。直接の親クラスのメンバ関数をusing宣言する場合ですら意図が分かりづらいので「基底クラスのこの関数が使えることを明示（usingなしでも動くけれどヘッダファイルだけ見た時に分かりやすいように）」「基底クラスにこの関数があることをチェック（usingなしだと素通ししてADLで誤爆するかもしれないので）」「privateの下でusingすることで基底クラスの関数を使えなくする」「同名関数をオーバーロードしたが基底クラスの関数も隠したくないため」等のコメントを入れるべきでしょう。

2021-12-05

安全で便利なstd::bit_castを使おう

この記事は C++ Advent Calendar 2021の5日目の記事です。

2021年ももうすぐ終わりそうですが、みなさんはC++20を使っているでしょうか？ C++20では、符号付き整数型のビット表現が二の補数であると規定されました。また、ビット表現を保ったまま別の型に変換する関数であるstd::bit_castが標準ライブラリに実装されました。これら二つの機能追加により、値のビット表現に依存したプログラムを書くことが非常に容易になりました。

この記事では、なぜstd::bit_castを使わなければならないかを説明します。もちろん、それ以外の時にstd::bit_castを使うべきではないということではありません。ビット表現を保ったまま別の型に変換したい時にはいつでもstd::bit_castを使う、という方針もありでしょう。

`std::bit_cast`を使わなければならない場合

std::bit_castを使わなければいけない場合は、以下の二つです*1。

タイプパンニングによる未定義動作を防ぐため
符号付き整数のオーバーフローによる未定義動作を防ぐため

以下では、これら二つを詳しく説明していきます。

タイプパンニングによる未定義動作

タイプパンニングとは、本来の型とは互換性のない型としてデータにアクセスすることです。たとえば、floatのビット表現を得たいのでfloat f = 1.0f; std::uint32_t u = *(std::uint32_t*)&f;とかやってしまうことです。これは strict aliasing rules に反する未定義動作になります。

こういう場合は、std::uint32_t u = std::bit_cast<std::uint32_t>(1.0f);とやると良いでしょう。 std::bit_castの代わりに使ってしまいがちな、以下の二つはいずれも未定義動作になります。

共用体（union）の片方のメンバに代入し、もう片方のメンバで読み出す
- C言語の場合は未定義動作ではないが未規定（C17の規格書で確認）
float f = 1.0f; return *(std::uint32_t*)&f;のように互換性のないポインタに無理やりキャストして読みだす

なお、以下のようにstd::memcpyを使うというのは問題ありません。

float f = 1.0f;
uint32_t u;
std::memcpy(&u, &f, sizeof u);

しかし、std::memcpyを使うのではなくstd::bit_castを使ったほうがよいです。 std::bit_castを使うべき理由は、以下の三つです。

意図が明瞭になる
型のサイズがあっているかのチェックが働く
- 移植不可能な場合はコンパイルエラーになってくれる
未初期化変数があらわれない
- const変数に束縛できる
- デフォルト構築可能でなくても使える
- constexpr文脈でも使える

std::memcpyではできるのにstd::bit_castではできないのは以下の四つの場合ですが、いずれもそもそもやるべきではないものばかりです。

変換元、変換先、それらの中に含まれるメンバ等が……
- 共用体（union）の場合
  - 最後にアクセスしたメンバの種類、というのが明瞭ではなくなる
- ポインタ（メンバポインタ含む）や参照の場合
  - 継承関係のナビゲーションがされなくなる。static_castやdynamic_cast、どうしても必要な時であってもreinterpret_castやconst_castを使うべき
- volatile変数の場合
コピーが自明でない場合

符号付き整数のオーバーフローによる未定義動作

符号付き整数のオーバーフローは未定義動作です。一方、符号無し整数の計算は2^Nを法とした計算になると定義されており、未定義動作になりません。したがって、二の補数表現であることを利用したオーバーフローを含む計算をしたい時、以下の手順を踏むことで未定義動作を回避することを考えます。

一旦符号無し整数に変換する
符号無し整数でオーバーフローを含む計算を行う
答えを符号付き整数に変換する

ここで、手順1と手順2は未定義動作を含みません。しかし、手順3はstatic_castなどを使ってしまうと未定義動作になる可能性があります。こういうとき、std::bit_castを使うと良いでしょう。

なお、対称性を高めるために手順1にもstd::bit_castを使うというのもよいでしょう。以下のような方法を使っても未定義動作が発生しないという意味において問題ありませんが、「私は二の補数表現を前提に符号無し整数に変換することを意図している」という情報がくみ取れなくなるかもしれません。

暗黙変換を使う（読解が困難なうえに意図がわかりづらいのでやめてほしい）
- 符号無し変数への代入
- 符号無し整数との整数演算・ビット毎論理演算
- 関数の引数に渡す
Cスタイルキャストを使う（短くてわかりやすいが、Cスタイルキャストは邪悪と考えるプログラマもいる）
static_castを使う（仰々しいと感じるが、Cスタイルキャストが厳禁の場合に）
std::memcpyを使う（まずやらないと思いますが）
タイプパンニングを使う（signedとunsignedの違いは互換性があるので問題ない。まさかやることはないと思いますが）

まとめ

未定義動作を防ぐため、std::bit_castを使おう
std::bit_castが有用なのは以下の場合
- タイプパンニングを行いたい場合
  - 浮動小数点数のビット表現を手に入れたい場合など
- 符号付き整数のオーバーフローを含む計算を行いたい場合
  - C++20で符号付き整数型のビット表現が二の補数であると規定されたため移植性が上がった
使う必要性がなくても、「ビット表現を保ったまま別の型に変換したい」という意思表明に利用してもよいかもしれない
- 二の補数表現を前提に符号付き整数を符号無し整数に変換したい場合など

*1:私はこの二つしか知りません。ほかにありましたら、コメント等をいただけると助かります

分岐履歴の仕組み

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

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

まとめ

分岐履歴に使われる情報

分岐元アドレス

分岐先アドレス

分岐元アドレスのハッシュ関数の特定

まとめ

測定環境

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

単純なループの例

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

分岐履歴の種類

分岐方向履歴

分岐先履歴

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

まとめ

参考文献

測定方法

測定結果

vaddsd および vshufpd

vmulsd および vfmadd132sd

浮動小数点数演算命令とvshufpdの行き来はどこにペナルティがあるか

まとめ

測定環境

浮動小数点数演算レイテンシの歴史（AVX以降）

スケジューラの戦略

zmmを使わない場合

zmmを使う場合

いつでも2 cycleではない

浮動小数点数加算ばかりやりたい場合

倍倍精度演算が速くなる

概略

デバッグの仕方

バグの簡易な説明

問題の発生するgccバージョン

問題の発生しないコンパイラ

問題の発生するオプション

最小再現コード

期待される答え

実際の答え

まとめ

std::bit_castを使わなければならない場合

タイプパンニングによる未定義動作

符号付き整数のオーバーフローによる未定義動作

まとめ

`vaddsd` および `vshufpd`

`vmulsd` および `vfmadd132sd`

浮動小数点数演算命令と`vshufpd`の行き来はどこにペナルティがあるか

`std::bit_cast`を使わなければならない場合