前回

第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回コード全文と実装資料