前回

前回は、Icarus向けに作ったdirect版をAVX2へほぼそのまま移しました。

最大ケースでの処理時間測定は、external ≈ 562.332 msでした。

そこから公式SIMD版を参考に、Vの生成方法をSIMDに都合よく変えました。

8 alignment bankの採用です。

結果は、external ≈ 184.341 ms、約3.05倍高速化。

入口の怪獣は倒しました。

……でも、公式AVX-512参考実装は30ms台中盤です。

まだずいぶん差があります。

AVX2なんだから2倍くらいは遅くても仕方ない？

もちろん、こちらはAVX2です。

AVX-512に比べて、SIMD幅は半分です。

実際の速度差がきれいに2倍になるわけではありませんが、目安として、

AVX2なら2倍くらい遅くても不思議ではないよね。

と考えることにします。

ところが今は、184 msです。

AVX2だから遅い、だけでは説明しにくい。

どうやら前回倒した怪獣の奥に、もう一匹いそうです😂

AtCoder公式解説ページのHBitさんSIMD解法参考実装を参考にさらに高速化を進めていきます。

尚、今回もコード実装やテストレポート生成にはCodexの全面的なサポートを受けています。

※ 今回のコードや実装資料はGithubに上げてあります。文末のリンクからご参照ください。
※ 本記事のテストや測定はすべて筆者のローカル環境(Win 11, i7-12700H, MEM 64GB)で行っています。

今の実装をもう一度眺める

前回の入口改善版で、Aの入力から並列処理までの区間は、かなりCPU SIMD向けになっています。

では最後の、並列立ち上がりカウンタの実装はどうでしょうか。

公式ページの参考実装コードをよく読むと、同じCSAでもその構成がかなり違っているようです。

まずは、現状の実装をおさらいしてみます。

現状の実装：入力ペア16本ごとに「23桁の足し算」

現在の実装でも、pair-eventは、一回ごとにcounterへ足しているわけではありません。

まず16回の入力ペアを一時保存した上で、

3:2 Compressorで各レーンの16bitパラレルを5bitバイナリに変換 (CSA)
↓
カウンタに並列加算処理

しています。

この並列加算処理ですが、データの持ち方を並列処理に特化させていることが理由で、いわゆる一般的な加算命令とは違う仕組みを実装しています。

最大700万のカウンタ、つまり23bitカウンタを23枚の桁ごとのbitプレーンに分割し、桁ごとにXOR / ANDを使い、その桁の更新値と上位桁へのcarryを算出する、という方式です。

つまり、

16本のpair-eventをためて処理する
↓
23枚のbitプレーンをまたいで順次carry処理を伝搬させる

というサイクルを繰り返しています。

前回の最大ケースでは、1 blockあたり、

pair-event              3,500,000本
16 pair-event batch       218,750回

でした。

CSAで16本に1回まで減らしても、23段並列加算装置は、218,750回も処理を行うことになります。

AVX2は2300bit分のkを9回に分けて処理しますから、23段 x 21.9万回 x 9回 ≈ 4500万回の処理です。

CPUが4.5GHzクロックで動いていると仮定しても、1回の処理に5クロック必要だとすると50ms、10クロックかかれば100msの処理時間になります。

これは無視できないですね。

たとえば普通の整数へ戻せばいい？

このカウンタ加算処理を効率化する方針として一つ考えられるのは、

bit-sliced counter
↓
普通の整数へ並べ直す
↓
CPUの整数ADDで加算処理

です。

そうすれば繰り上がりなどの処理はCPUの効率的なハードウェア加算器へ任せられます。

ただし今度は、256個のcounterをbit-slice表現から普通の整数へ並べ直す必要があります。

しかも、その後も256bit SIMDで処理を続けたいなら、また都合のよい形へ戻す必要があります。

この変換も安くはなさそうです。

今回はこの方法を実測していません。

だったら最後までCSAにため込めば？

また別の効率化方針として、

CSAでせっかく加算を先送りできるなら、最後までCSAのまま持てばいいのでは？

というアイデアが思い浮かびます。

最大ケースではpair-eventは350万本です。

だったら、

350万本のpair-eventを全部ためる
↓
3:2 Compressorで3,499,977回圧縮
↓
最後に23本まで減らす

という力技も、理論的には成立します。

ただし、350万本のpair-eventをそのまま保持すると、

3,500,000 × 2,300 bit
≈ 960 MiB

です。

AtCoderのメモリ制限は1GiB。

生データだけでほぼ使い切ります😂

さらに、23bitぶんのbit-sliced状態への遷移を考えながら巨大な圧縮処理を組むとなると、コードもかなり大きくなりそうです。

理論的には成立する。

でも、

メモリはギリギリ、実装も大仕事。

うーん。イマイチですね。

では、公式ページのSIMD実装はどうしているのでしょう。

公式ページのSIMD実装をよく見てみる

公式コードを見ると、大量のpair-eventをため込んではいません。

16ペア単位で処理しながら、カウンタへの加算は行わず、別のCSAに繰上り情報を渡す、というしくみです。

つまり、

大量にため込まない
+
小さな単位で処理するが、カウンタ加算はしない
+
4bit単位に分割して実装する

という構成です。

メモリはほとんど増やさず、実装も小さな部品に分けることでコードをシンプルにできる。

さすがです。

小さなCSAを階層化する

公式ページSIMD版では、大きなCSAを一つ作るのではなく、

4bit相当の小さなCSA状態をlevelとして、そのlevelを何段も重ねています。

各levelでは、現在の実装と同じように16本のbit入力をCSAでまとめます。

ただし、既に保持している4bit状態にも加え、あふれたcarryだけを次のlevelへ渡します。

つまり、

現在の4bit状態
+
16本の入力
↓
下位4bitはそのlevelへ残す
+
上位へのcarryを1本だけ返す

という最上位bitの扱いです。

つまりcarryにあたる5bit目を次のレベルのCSAに渡す処理をしています。

この、

4bitの状態へ16本の入力を押し込んで、上位へのcarryだけ返す

部品が、公式ページSIMDコードのcompress16です。

ただしコードをさらに追うと、一番下位桁を担当するlevel 0だけは少し違う実装になっています。

level 0だけはstreaming

level 0は、すべてのpair-eventが最初に通る一番忙しい場所です。

公式ページの参考実装コードでは、

pair-eventが2本来たら、1の位の値と2の位へのcarryを計算
↓
pair-eventが4本来たら、1の位の値と2の位へのcarryを計算、さらに2の位の値と4の位へのcarryを計算
↓
pair-eventが8本来たら、1の位..., 2の位..., 4の位の値と8の位へのcarryを計算
↓
...

という処理で進めています。

最終的な処理の結果はcompress16と同じです。

でも実装は、

level 0
pair-event生成とCSAを融合したstreaming処理

level 1以降
carryを16本ためてからcompress16

と使い分けています。

level階層は6段構成

この小さな4bit CSAを6段重ねたのが、公式ページSIMD実装です。

level 0 : bit  0～ 3
              ↓ carry
level 1 : bit  4～ 7
              ↓ carry
level 2 : bit  8～11
              ↓ carry
level 3 : bit 12～15
              ↓ carry
level 4 : bit 16～19
              ↓ carry
level 5 : bit 20～23

6段合わせれば24bitぶん。

しかも上位levelは、下位からcarryが16本たまったときだけcompress16を行います。

24bit分の保存能力は持っているのに、24bit全部を毎回動かさなくていい。

現在の23bit counterでは、16 pair-eventごとに大きな精算を行っていました。

今回は、

CSAで始めた「加算の先送り」を、最後まで続ける。

という構造です。

でも、なぜlevel 0だけ別方式？

ここで一つ気になりました。

なぜlevel 0だけpair-event 2本ごとに処理を行うstreaming方式なのでしょう。

第3回では、入力をまとめて3:2 Compressorへ入れる方式がかなりよく働きました。

だったら、

level 0も16本ためてcompress16へ入れた方が速いんじゃない？

level 0だけ2種類作って比較測定してみる

比較するのは、この部分だけです。

公式型
pair-event生成
↓
2ペアごとに処理
↓
carry

対して、

比較版
pair-eventを16本保持
↓
compress16
↓
carry

他の部分は全く同じコードとします。

結果発表：level 0は公式型Streamingとcompress16ではどちらが早い？

700万要素の最大ケースで両者を比較します。

まず9 blockのSIMD処理部分だけを見ると、

公式型streaming     42.0560 ms
16本compress16      40.8778 ms

でした。

局所的には、16本ためる方が約2.8%高速。

ところが、externalの値でprocess全体の実時間を見ると、

公式型streaming     68.5196 ms
16本compress16      69.4565 ms

です。

こちらは公式型streamingの方がわずかに高速でした。

ということで、

最終版は公式型streamingを採用します。

細かな測定条件やraw値はGitHubのREPORTへ置いてあります。

結果発表：小型CSAの階層型接続は効いた？

最大ケースで、ここまでのAVX2版を比較してみます。

Icarus構造を忠実移植
external ≈ 562.332 ms

8 alignment bank + 従来counter
external ≈ 184.341 ms

公式型hierarchyまで採用
external ≈ 68.520 ms

前回の184.341msから、さらに約2.7倍高速化。

最初の562.332msから見ると、約8.2倍高速化です。

同じAVX2。

同じdirect解法。

違うのは、データの持ち方と計算の流し方です。

公式ページSIMD解法の34msと比べてみる

記事の最初では、

公式AVX-512     約34 ms
AVX2なら       その2倍くらい？
                ↓
               約68 ms

と、かなり乱暴な目安を置きました。

今回の最終採用値は、

68.520 ms

です。

ほぼ68msじゃん😂

もちろん、AVX-512の半分幅だから必ず2倍、という話ではありません。

CPUも命令セットも実装条件も違います。

それでも、ゴールの目安として置いた数字にほぼ到達しました。

公式コード、強い。

ここで終わってもよさそうです

Icarus final directの最大ケース予測は、

約392.7秒

でした。

同じdirect解法をCPU SIMD向けに組み直したら、

約0.069秒

です。

十分すぎるほど速くなりました。

かなり満足のいく結果ですね。

……。

いや、待てよ。

俺のPC、GPU載ってるよな

手元のラップトップには、

NVIDIA GeForce RTX 3060 Laptop GPU

が載っています。

AVX2では256bit registerへ仕事をまとめました。早くなりました。

しかしGPUには、もっと大量の並列計算資源があります。

だったら、

処理レーンそのものを、もっと大量に並べたら？

仮想理想FPGAで最初にやった、

2300個なら2300個並べればいい

を、今度は現実のGPU threadでやれるかもしれません。

CUDA、動くかな？

まずは小さなkernelで、

H2D
kernel
D2H

を確認します。

動きました。

RTX 3060 Laptop、使えそうです。

だったら次は、

GPUで本当に2300並列してみよう。

次回

第6回はCUDAです。ABC471G最終回の予定でもあります。

まずは、素直に2300並列を実装してパフォーマンスを見てみます。

AVX2が約68.5msなら、GPUはどこまで行くのか。

試してみましょう。

次回をお楽しみに。

前回：
仮想理想FPGAでAtCoderを解く(4) - ABC471G④ - direct解法をAVX2で実装してみる（前編）

次回：
仮想理想FPGAでAtCoderを解く(6) - ABC471G⑥ - RTX 3060 Laptopで超並列してみる

コード全文と実装資料：(コード実装やドキュメント作成は生成AIの助けを借りています)
第5回コード全文と実装資料