前回

前回は、ABC471Gのdirect解法をRTX 3060 Laptop GPUへ持っていきました。

愚直解法をGPU向けに最適化した結果、最終構成では

GPU_COMPUTE ≈   4.515 ms
GPU_PIPELINE ≈  6.902 ms
PROGRAM ≈      86.403 ms
EXTERNAL ≈    123.339 ms

の処理時間を得ました。

計算部分だけなら、とんでもなく速い。

でもプログラム全体では、AVX2版EXTERNAL ≈ 68.5 msの方がまだ速い。

そこで、direct解法はここまでにして、今回はもう一つの解法、

NTTをGPUへ持っていったらどうなる？

を試します。

ABC471G編、最終回です。

※ 今回もコード実装やテストレポート生成にはCodexの全面的なサポートを受けています。
※ 今回のコードや実装資料はGithubに上げてあります。文末のリンクからご参照ください。
※ 本記事のテストや測定は筆者のローカル環境（Win 11, i7-12700H, RTX 3060 Laptop GPU）で行っています。

ところでNTTの戦績は？

ここで第3回を思い出します。

最大ケース予測は、

Icarus direct:　約6分33秒
Icarus NTT:     約55分

NTTの負け。

第4回、第5回のnative CPUでは、

AVX2 direct      約68.5 ms
native C++ NTT   約1.85 s

またNTTの負け。2連敗です。

でもGPUはNTTと相性が良さそうです。

8192-pointのbutterfly演算を大量に並べられる。

今度こそNTTが勝つかもしれません。

やってみましょう。

素のCUDA NTT

まずは素直なbatched radix-2 baselineを実装してみます。

8192-point
13 stages
全transform batched
global-memory stage kernels

結果: GPU_COMPUTE ≈ 33.61 ms

思ったより悪くありませんね。有望かもしれません。

そこで（少し面倒になってきたので）Codex君に、

数学は変えるな。CUDA実装は好きに速くして。

と丸投げ気味の最適化を依頼します。

CUDA NTTを本気で最適化

Codex君がテストを繰り返して得た最終回答は、

1 transform = 1 block
32KiB shared memory
13 stagesを1 kernel内へfusion
pointwiseをinverse loadへfusion
inverse scaleもstoreへfusion
1024 threads/block

という構成になりました。

結果: GPU_COMPUTE ≈ 11.95ms

約2.81倍高速化。

NTT、ちゃんと速い。

計測範囲は異なりますが、native C++ NTTと比べても大幅高速化しています。

※ なお、この実験時点ではchunk再調整前のCHUNK_SIZE=32768版を固定referenceとしていました。第6回の最後にCHUNK_SIZE=16384へ再調整したため、この記事では7Mのdirect最終値を4.514816msに統一します。

NTT、また負けました

最終比較 GPU_COMPUTE:

direct CUDA          4.51ms
optimized CUDA NTT  11.95ms

directが約2.65倍速い。

これで公式制約内では、

Icarus     direct勝利
CPU        direct勝利
GPU        direct勝利

NTT、3連敗です。

「いやー。NTTさん、今日の結果は残念でしたね」

「はい、残念です。僕にはちょっとN数が足りませんでしたね。」

じゃあ、Nを増やしてみよう

今回の公式最大Nは700万。

NTT側は、N個の入力を前処理した後は固定長のconvolutionへ持っていきます。

だったらNをもっと大きくすれば、どこかでdirectと逆転するはず。

ここから先はABC471Gの公式制約外です。

まず、

N = 100,000,000

1億。

結果発表:

scope	direct	optimized NTT
GPU_COMPUTE	62.142 ms	11.911 ms
GPU_PIPELINE	85.572 ms	18.426 ms
EXTERNAL	0.437 s	1.128 s

GPU内ではNTTが勝ちました。

ついに名誉挽回。

ただしNTTはHOST_PREPROCESSだけで、約757msかかっています。

HOST_PREPROCESSの中身は、CPU側で1億個のA要素を生成して、隣接ペアを2300 x 2300ヒストグラムへ集計する作業です。

結局end-to-endではまだdirectの勝ち。

勝者が計測範囲で分かれました。

CUDA起動などの固定費は、仕事量が増えるほど相対的に小さくなります。一方、NTTにはNに比例して増えるHOST_PREPROCESSが残っています。

それにしてもdirect、速すぎない？

N=1億なのに、EXTERNAL ≈ 0.437sです。

……。

Megaでこれなら、Giga行ってみるか。

N = 1,000,000,000

10億です。

メモリ量、grid、index overflowを事前確認すると、RTX 3060 Laptopの6GB VRAMでも実行可能でした。

では走らせます。

N=1G

結果発表:

scope	direct	optimized NTT
GPU_COMPUTE	618.652 ms	136.693 ms
GPU_PIPELINE	853.991 ms	185.453 ms
EXTERNAL	3.223 s	10.835 s

またもや、GPU内ではNTTが勝ち、全体ではdirectの勝ちです。

NTTのHOST_PREPROCESSは、約8.06sまで増えました。

一方directは、外から見ても、

10億要素を3.22秒。

スーパー愚直、すごい。

K=2300なので、direct解法が相手にしている論理的な (i, k) 空間は、

1,000,000,000 × 2,300
= 2,300,000,000,000

2兆3000億。

もちろん32bit packingなどの工夫で、2兆3000億回のscalar演算をそのまま実行しているわけではありません。

それでも、兆オーダーの問題空間を個人向けラップトップで本当に最後まで走らせました。

GPU、高いだけのことはあるじゃん。

※ N=1GはNTTに採用しているmod 998244353を越えています。任意入力に対する一般的な正しさは主張できませんが、今回のall-one / fixed-randomではdirectと全2300出力が一致することを確認しました。

ところでNTTの時間、なんか変じゃない？

ここで1GのNTT時間測定結果の生データをよく見ると、GPU_COMPUTEの3 runが、

138.699 ms
136.693 ms
 12.004 ms

でした。

最後だけ急に速い。

同じ構成でもう10 run測ると、

133〜187 ms
median ≈ 154 ms

で、今度は12ms級が一度も出ません。

何かマシン側の癖に当たっているように見えます。

でも原因はまだ分かりません。

せっかくなので、もう少しだけ掘りすすめます。

GPUだけ10回連続で走らせる

HOST_PREPROCESSとH2Dを1回だけ行い、同じdevice入力を毎回D2D restoreして、NTTのGPU部分だけ10回連続で実行しました。

結果:

run 1    122.887 ms
run 2    110.626 ms
run 3-10  11.515〜12.436 ms

min / max / medianは、

11.515 / 122.887 / 11.681 ms

でした。

12ms級は幻ではありませんでした。

同時に、高レイテンシ状態も先頭2回で再現しています。

ただし、

clock？
power state？
WDDM？
cache？
DRAM？
scheduler？

どれが原因なのかは調べていません。

profilerも取っていません。

詳しい人、誰か調べてください😂

ここまで来ると、アルゴリズム比較というよりGPUの生態観察です。

愚直を馬鹿にするな

今回のdirect法は、アルゴリズムの骨格だけ見れば愚直です。

全kについて
全Aを見て
riseを数える

最後までこれです。

ただし実装は、

2300 lane
↓
wide vector
↓
bit-slice
↓
rise fusion
↓
CSA / hierarchy
↓
time chunk
↓
32 k / thread
↓
alignment bank
↓
geometry tuning
↓
chunk retuning

と、いじくり倒しました。

NTTは、

仕事量そのものを減らす

解法。

direct最適化版は、

仕事は残したまま、労働環境を徹底的に効率化する

解法でした。

そしてABC471Gの公式制約では後者が勝ちました。

公式制約外までNを伸ばすと、100M / 1GではGPU_COMPUTE / GPU_PIPELINEともNTTが逆転しました。

ただし現在のNTT実装はCPU側の前処理が重く、end-to-endでは1Gでもdirectが勝っています。

GPUはCPUの上位互換ではない

今回の7M direct最終版は、GPU計算約4.5ms、GPUへ送って結果を受け取るまででも約6.9msでした。

ところがC++のmain()全体では約86.4ms、OS側から見たプロセス全体では約123.3ms。AVX2は全体約68.5msです。

GPUは大量並列処理そのものには猛烈に強い。でもCPU側で仕事を準備し、GPUへ渡し、結果を受け取り、CUDAプログラムを起動・終了する費用があります。

GPUは大量の単純労働を一気に渡すと強い。仕事が少ないと、渡す手続きの方が高くつく。

ここで気になるのがApple Siliconです。CPUとGPUがユニファイドメモリを共有する環境では、この境界がどこまで変わるのでしょうか。

Macユーザーの方、ぜひ試してみてください😁

仮想理想FPGAはどこへ行った？

最初は、

2300並列？仮想なんだから2300個置けばいいじゃん。

でした。

探検しているうちに、

Icarus
↓
native C++
↓
AVX2
↓
CUDA
↓
CUDA NTT
↓
100M
↓
1G
↓
GPU生態観察

まで来ました。

タイトルの仮想理想FPGAを完全に置き去りにしています。

でも最初にFPGA的に、

どこを並列化できる？
何がstate？
どこがボトルネック？
何をbitでまとめられる？

と考えたことは、その後の最適化にもそのまま使えました。

そして何より、

仮想だからできると思っていた大量並列を、家のラップトップGPUがかなり現実に実行できた。

これは予想外でした。

シリーズのまとめ

今回の探検で分かったこと。

マシンの特性に合わせた解法・実装が一番強い。

そしてABC471Gの公式制約 N=7Mでは、

IcarusでもCPUでもGPUでも、並列direct改善版がNTTより速かった。

でも公式制約を外してNを増やすと、

7M    GPU内も全体も direct
100M  GPU内はNTT / 全体はdirect
1G    GPU内はNTT / 全体はdirect

と景色が変わりました。

算法単体に「速い」「遅い」はもちろんありますが、実機では

問題サイズと計算機の特性に合う形が強い。

ということなのでしょう。

GPUについては、計算時間だけでなく、そこへ仕事を持っていく費用まで含めて速さを考える、ということもよく見えました。

そしてもう一つ。

N = 1,000,000,000
K = 2300
論理空間 = 2兆3000億
direct external ≈ 3.22 s

自宅のラップトップ、思っていたよりずっとすごい計算機でした。

理想FPGAを探しに行ったら、途中でGPUという別の怪物を見つけました。

そのGPUの妙な初動レイテンシまで眺めたところで探検は終わりにして、待ちくたびれているIcarus君のもとへ帰ります。

長々とお付き合いいただき、ありがとうございました。

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

次回：
未定

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