前回
第3回では、Icarus上でdirect解法をできる限り加速させてみました。
最大ケース処理時間予測値は、第1回の約8時間50分から6分33秒まで短縮することができています。
公式解説解法のNTTも試しました。
しかし残念ながら、Verilog / Icarusでは、最大ケース予測 ≈ 55分でした。
ここで NTTの実装が悪いのか、Icarusが苦手なのか を切り分けるため、ほぼ同じ処理構造をnative C++へ移しました。
結果は、1.854秒で700万要素の処理が終わっています。
Icarus版の約55分から一気に2秒弱。
そして公式解説ページには、もう一つ気になる実装があります。
AVX-512を使ったSIMD解法です。
direct解法を極めてみようか、という方針で、これを C++ / CPU SIMDで処理してみます。
今回もコード実装やテストレポート生成にはCodexの全面的なサポートを受けながらの実装試験です。
※ 今回のコードや実装資料はGithubに上げてあります。文末のリンクからご参照ください。
※ 本記事のテストや測定はすべて筆者のローカル環境(Win 11, i7-12700H, MEM 64GB)で行っています。
まずはそのまま持っていってみる
今回はまず、
Icarusで最後まで鍛えたdirect版を、できるだけ同じ構造のままAVX2へ持っていく
ところから始めます。
そもそもAVX2って何？
手元の実機に載っているCPUはIntel Core i7-12700Hです。
このCPUではAVX2が使えます。
AVX2には256bit幅のSIMD registerがあり、256bitぶんのデータをまとめて論理演算できます。
簡単に言ってしまえば、256bit分の情報をCPUで並列処理できる仕組みですね。
今回のdirect解法では、1bitを一つのkレーンに対応させています。
ですから、
256bit SIMD register
↓
256個のkレーンをまとめて処理
ができるはずです。
最大K=2300なら、
2300bit
↓
9本の __m256i
で全部収まります。
Icarusで2300bitのbitsetとして扱っていたものを、現実のCPUでは9本の256bit registerへ分けるわけです。
まずIcarus最終版をAVX2へそのまま持っていく
第3回のdirect最終版は、
2300bit current
↓
2-rise fusion
↓
16 pair-event
↓
CSA
↓
23bit bit-sliced counter
という構造で、処理時間予測は6分33秒でした。
これをなるべく崩さずC++/AVX2へ移植します。
2300bit current
↓
9本の __m256i
↓
AVX2 XOR / AND / OR
↓
同じ2-rise fusion
↓
同じCSA
↓
同じ23bit bit-sliced counter
つまり、算法はほぼ同じ。
実行する器だけを変えます。
結果：コピー移植でも速い
最大ケースN=7,000,000の結果は、
external ≈ 0.562秒
internal ≈ 0.549秒
でした。
ここでは、
external = OSから見たprocess起動から終了まで
internal = C++内部で測った処理本体
と考えてください。
全体性能を見るときはexternalを使います。
……。
結構速い。
Icarusでは6分33秒予測だったものが、ほぼコピー移植で実測0.562秒です。
単純比較なら約700倍。
CPU SIMD、なかなかやります。
でも参考実装は30ms台なんだよね
0.56秒なら十分速い。
でも公式解説ページのAVX-512参考実装は30ms台です。
まだずいぶん差があります。
もちろん、
AVX-512 : 512bit
AVX2 : 256bit
ですからSIMD幅の差はあります。
でも、それだけで562msから30ms台になるとは思えません。
何が処理のボトルネックになっているかを調べてみましょう。
コードに埋め込んだ処理時間カウンタを使い、今のAVX2版の内部処理時間を測ってみると、
A生成 / current生成 / pair-event
≈ 0.459秒
で、内部処理時間の約79%を使っていました。
CSAより前、AVX2への入力周辺が重い。
Icarus版のデータの持ち方を、そのままAVXへ持ち込んだ影響があるのでしょうか。
ここで、公式SIMD版のコードをもう少しちゃんと読んでみます。
公式SIMD版をちゃんと読んでみる
細部はかなり高度ですが、見覚えのある部分もあります。
2-rise fusion
↓
CSAでpair-eventを圧縮
ここは第3回でIcarus向けに使った方法とよく似ています。
では、さっき79%も使っていたcurrent生成はどうしているのでしょう。
公式SIMD版を見ると、Vの持ち方そのものが違います。
毎回任意のbit位置からcurrentを組み立てるのではなく、SIMD registerへそのままloadしやすいよう、Vを先に並べ直しています。
どうやら、Icarus版をそのままAVX2命令へ置き換えただけでは足りないようです。
まずは、実測でも遅さが目立ったcurrent生成を真似してみます。
Aとして受けた入力を、V[A'[i]]の大量並列bitsetにどうやって変換するか、という部分の話ですね。
Icarusでは簡単だったのに、AVX2では簡単じゃない
第2回では、Vを2個つないで、
V || V
という最大4600bitのbitsetを作りました。
Verilogなら、Aが11のとき、VVの11bit目から2300bitくださいと命令を書けます。
Verilogにとっては、こういうbit単位の切り出しは自然な操作です。
ところがCPUのSIMD registerへ持ってくると話が変わります。
AVX2は256bitをまとめて処理できますが、メモリに11bit目から256bitくださいとお願いすることはできません。
CPUからメモリ上のアドレスを指定するときはbyte（= 8bit）単位です。
現状のAVX2版では、Vを64bitずつのwordに詰めて持っています。
メモリ上のwordから必要な64bitを4本組み立て、それを256bitのAVX2 registerへ詰めて処理する、という方式です。
1 byte = 8 bit
1 word = 64 bit = 8 byte （今回の実装）
AVX2 register = 256 bit = 32 byte = 4 word
ここでV[11]から始まる256 bitが必要な場合の処理を考えます。
V[11]から連続する64bitを作るには、隣り合うwordを使って、
最初のwordを読む
↓
そのwordから、V[11]～V[63]をbitシフトで取り出す
↓
ひとつ後ろのwordを読む
↓
そのwordから、V[64]～V[74]をbitシフトで取り出す
↓
64bitになるようbit位置を合わせて二つをOR
↓
V[11]から始まる64bitが完成
という操作が必要になります。
これを4本ぶん行って、ようやく256bitのcurrentです。
つまり、Verilogでは簡単に記述できる、任意bit位置からデータを切り出すという操作が、AVX2にとっては結構手間のかかる処理になっています。
Icarusに都合のよかったデータ配置を、そのままCPUへ持ってきたのがまずいのかも。
公式SIMD版がVの並べ方そのものを変えている理由が見えてきました。
8 alignment bankを作る
毎回bit shiftして位置を合わせるのが重い。
だったら、最初から必要な256bitをそのまま読み出せるように、準備をしておけばよさそうです。
元のV || Vを、先頭位置だけ1bitずつずらして、
bank 0 : 0bitずらした V||V
bank 1 : 1bitずらした V||V
bank 2 : 2bitずらした V||V
...
bank 7 : 7bitずらした V||V
という8種類のbitsetを先に作っておきます。
例えばbank 3をbyteごとに見ると、
byte 0 : V[3] V[4] ... V[10]
byte 1 : V[11] V[12] ... V[18]
byte 2 : V[19] V[20] ... V[26]
...
となります。
A=11なら、bank 3のbyte 1から読めば、先頭がちょうどV[11]です。
さっきはbyteの途中にいたV[11]が、今度はbyteの先頭に来ています。
32byteをそのまま読めば、
V[11] ... V[266]
の256bitが一発で取れます。
例えばAにXという入力が来たら、
start_byte = X / 8;
select_bank = X % 8;
を計算するだけで、「どのバンクの何バイト目から32byteを取り出すか」がわかりますから、
_mm256_loadu_si256(...)
の1回のAVX2 load命令で256個のcurrentを取れます。
大掛かりなことをしているように見えますが、狙いは逆です。
AVX2にとって本当に単純な操作、つまり「並んだ32byteをそのままloadする」だけにする。
そのために、最初に数KBぶん余計にデータを並べておきます。
せっかくなので256bitのまま流す
currentが256bitで一発で取れるようになりました。
だったら、その先もできるだけ256bitのまま処理します。
わざわざ2300bit相当の巨大な中間表現へ戻しません。
中間の2-rise fusionとCSAは再利用
ここは第3回とほぼ同じです。
連続するcurrentをP0, P1, P2とすると、
D1 = ~P0 & P1
D2 = ~P1 & P2
pair = D1 | D2
です。
同じlaneでD1とD2が同時に1になることはありません。
AVX2ではこれを256bitまとめて実行します。
CSAも、
sum = a XOR b XOR c
carry = majority(a,b,c)
という論理演算です。
公式SIMD版でも、ここで使っている基本部品は同じCSAです。
ここは、Icarus向けに見つけた方法がCPU SIMDでもそのまま使えます。
さて、この状態で、最大ケースN=7,000,000の処理時間を測ってみます。
結果発表：8 alignment bankは効いた？
最大700万入力ケースでの結果は、
8 alignment bank
+ 256bit block処理
+ 従来の16 pair-event CSA / 23bit counter
external ≈ 184.341 ms
internal ≈ 174.244 ms
でした。
Icarus最終版を忠実移植したコードでは
external ≈ 562.332 ms
internal ≈ 549.376 ms
でしたから、約3.05倍高速化。
算法も、2-rise fusionも、CSAも、最後の23bit counterも変えていません。
変えたのは、
CPUが読みやすいように、データの置き方と流し方を変えたこと。
ほぼそれだけで大きなパフォーマンス改善が達成できました。
やっぱり「計算機に合わせて見せ方を変える」は効く
第2回では、FPGA向けに考えた回路をそのままIcarusへ処理させるのではなく、
Icarusが処理しやすい形へ回路を変える
工夫で大きく高速化しました。
今回は逆です。
Icarusで扱いやすかった
任意bit位置からの切り出し
↓
CPUでは面倒
CPUが扱いやすい
byte境界から256bitをそのままload
↓
先にalignment bankを作っておく
同じdirect解法でも、計算機が変われば都合のよいデータの持ち方も変わります。
そして、最大ケース処理時間は184 msまで来ました。
かなり速くなりました。
でも、公式AVX-512参考実装は30ms台です。
もちろん、
AVX-512 : 512bit
AVX2 : 256bit
ですから、SIMD幅だけ見ても同じ速さになるとは思っていません。
それでも、まだ速度向上のネタはありそうです。
入口の怪獣は倒しました。
……でも、どうやら奥にもう一匹います😂
次回
今の実装をもう一度眺めて、まだ残っている重い処理を探します。
次回、さらにもう少し掘ってみます。
前回：
仮想理想FPGAでAtCoderを解く(3) - ABC471G③ - 続・Fly! Icarus, Fly High!
次回：
仮想理想FPGAでAtCoderを解く(5) - ABC471G⑤ - direct解法をAVX2で実装してみる（後編）
コード全文と実装資料：(コード実装やドキュメント作成は生成AIの助けを借りています)
第4回コード全文と実装資料