最初のおわび
前回の最後に今回がABC471G最終回と宣言しました。
しかし今回と次回の全7回になってしまいます。ゴメンナサイ。
前回
Icarusで約393秒だったdirect解法をC++/AVX2へ移し、さらに公式SIMD解法を参考に組み直したところ、700万最大ケース ≈ 68.5 msまで来ました。
AVX2、速い。
並列処理、えらい。
そして最後に、ふと、GPUにも計算させてみるかと思い付きました。
今回は
GPUで本当に2300並列してみる。
から始めます。
※ 今回もコード実装やテストレポート生成にはCodexの全面的なサポートを受けています。
※ 今回のコードや実装資料はGithubに上げてあります。文末のリンクからご参照ください。
※ 本記事のテストや測定は筆者のローカル環境（Win 11, i7-12700H, RTX 3060 Laptop GPU）で行っています。
CUDA WORK1: まずは動作確認
前回の最後に行ったCUDAの基本動作確認が、今回のWORK1です。
確認したのは、
RTX 3060 Laptopをdevice 0として認識
↓
HostからDeviceへデータ転送
↓
小さなテストkernelを起動
↓
同期
↓
DeviceからHostへ結果回収
という最小構成です。
CUDA Eventとhost側wall timeの測定も含めて、すべて正常に動きました。
このPCでCUDAの計算を走らせられる。
そこだけ確認して、いよいよABC471Gの実装へ進みます。
先に、実行時間の見方
CUDAでは「何の時間か」を分けて考える必要があります。
今回は読者から見て境界が分かりやすいように、最終的には次の4段階で見ることにします。
EXTERNAL OS側から見たプロセス起動から終了まで
PROGRAM C++のmain()開始から正常処理完了まで
GPU_PIPELINE CPUからGPUへの入力転送開始から結果回収まで
GPU_COMPUTE GPU上の計算部分
外側から内側へ、
EXTERNAL
└─ PROGRAM
└─ GPU_PIPELINE
└─ GPU_COMPUTE
という関係です。
EXTERNALは今回のローカル環境での全体性能、GPU_COMPUTEはGPUという計算装置そのものの速さを見る数字、と考えることにします。
CUDA WORK2: 本当に2300並列
最初のABC471G CUDA版は、仮想理想FPGAの発想をそのまま持ってきます。
1 threadあたり、kレーンを1本担当
K=2300なら2300 active thread。
各threadが自分のkについて、
A[0]
A[1]
...
A[N-1]
を順番に見て、0→1を数えます。
つまり、完全な愚直解法です。
結果: GPU_COMPUTE ≈ 246 ms
……。AVX2より遅い。
2300並列したのに。
もっとthreadを増やそう
立ち上がりカウントが検出されるかは、入力から算出されたV[A'[i]]が0 → 1になるか、だけで決まります。
つまり、自分とそのひとつ前の入力値だけで決まるので、二つ以上前の要素が何であっても影響されません。
だったら、1番めから10000番目、10001番目から20000番目...、699万1番めから700万番目の要素、のように
time方向も分割すればいいんじゃない？
CUDA WORK3: time方向にも並列化
ひとつのthreadの担当を、(chunk, k)へ変更します。
ここでchunkは連続する要素を入力順で複数に分割したブロックのことです。
各chunkでpartial countを作り、最後にkごとにreduce。
とりあえず、1 chunkあたり8192要素を処理してもらいましょう。
7Mでは855 chunkに分割できるので、CUDAが処理するタスクの概算は
855 × 2300
≈ 1,966,500 tasks
です。
GPUはこの197万タスクを順次並列処理していきます。
実機のRTX 3060 Laptopでは、GPU上に数万thread程度を抱えることができます。
ですから、これで2300 threadしかなかった前の構成より、かなりGPUの計算リソースの稼働率が上がるはずです。
結果: GPU_COMPUTE ≈ 40.1 ms
一気に6倍以上高速化。
GPU、仕事をたくさん渡すと急に元気です。
GPU上の計算部分だけなら、前回の最終AVX2版EXTERNAL ≈ 68.5 msを下回りました。
ただし計測範囲が違うので、全体性能の勝負はあとで確認します。
chunkは細かければ細かいほどいい？
ここでchunk sizeの最適化を試します。
先ほどのコードのchunkサイズを1024～65536まで変えながらパフォーマンスを見てみます。
結果は、一定以上ではほぼ横ばい。
最終的に、
CHUNK_SIZE = 32768
GPU_COMPUTE ≈ 36.72 ms
を採用しました。
並列度は多ければ多いほど良いわけでもないようです。
全部tableにしたらもっと速い？
現在のコードでは毎回currentを計算しています。
だったら、**current_table[A][k]**を全部先に作って保持しておけば？
2300種類のAの値に対して、Kmax=2300なので、約5.29MB。
GPUなら余裕です。試します。
結果：約72%遅くなりました。
ハイ残念。不採用ですね。
前計算すれば何でも速くなるわけではありません。
Aをshared memoryへ置いてみよう
同じchunk内では、たくさんのthreadが同じAを読みます。
でも今の実装では、同じchunkを処理するthreadは、GPUのglobal memory上にある同じAの値を読みに行っています。
何か効率が悪そうです。
GPUにはshared memoryという、thread blockごとに配置されている小さなメモリ空間があります。
CPUのcache memoryみたいなものですね。狭いけど近所にあるから早い。
ただ、CPU cacheと違い、GPUでは自分でデータを置いてから使う、という手順が必要です。
そのような仕組みがあるならAをshared memoryに置いてみれば？
やってみました。単独で約6%改善。
効きました。
あとで最終版にも合体してみましょう。
1 threadで32個のkを処理したら？
さて、愚直解法を愚直実装する、という方針で、かなり処理時間を短縮できました。
しかし、そろそろ限界が見えてきています。
Icarus vvpやCPU SIMDで試したように、計算機に合わせたデータの入出力や処理を検討するタイミングのようです。
ここでAVX2を思い出します。
1 threadが1個のkレーンだけを見る必要はありません。
32bit整数の各bitを1個のkレーンに対応させれば、
1 threadあたり、kレーンを32本担当
にできます。
もちろん、入力をbitsetにすると、立ち上がり回数カウンタも、それに合わせて変更が必要です。
1 thread
→ 32 k
→ uint32_t current
→ 32 lane bit-sliced counter
結果: GPU_COMPUTE ≈ 11.58 ms
約3.5倍高速化。
GPUでもbit並列が強い。
counter更新もまとめる
まだ毎Aごとにbit-sliced counterを更新しています。
IcarusやAVX2で効いた、counter更新の最適化もやってみます。
2-rise fusion
CSA
delayed accumulation
をそれぞれGPUに持ってきて、どれがGPUに向いているのかを測定してみます。
結果:
WORK7 ripple 11.59 ms
2-rise 8.15 ms
2-rise + CSA 9.40 ms
2-rise + CSA hierarchy 6.83 ms
CSA hierarchy (compress16方式) が最速。
ついに10msの壁を破りました。
current取得も軽くする
現在はbit-packed Vから、
2 word load + shift処理 + OR演算
で32個のkに対応するcurrentを作っています。
だったら32通りのalignmentを先に作ってしまうというのは？
先ほど不採用となった、全組み合わせlookup tableは約5.29MBのサイズがありました。
でも32 alignment bankなら約18KB。
やってみましょう。
結果: GPU_COMPUTE ≈ 5.77ms
15%以上改善してます。
大きい表はダメだった。でも小さい表なら勝った。
blockの並べ方も変えてみる
CUDAではthread blockのサイズをGPU kernel初期化時に指定しています。
これまでは最初に指定した 64 thread / block のまま、高速化を試してきました。
しかし、高速化の結果、2300レーンを32bitのbitsetとして読み込んでいますから、k方向には72レーンまで縮んでいます。
64 threads/blockでは、72個のk-wordを1 blockに収められません。少し効率が悪そうです。
そこで、thread blockのサイズを最適化してみます。
32 / 64 / 72 / 96 / 128 / 256のブロックサイズで、それぞれ処理時間を実測してみます。
結果: 72と96がほぼ同着。
GPU_COMPUTE
B=96 4.5189 ms
B=72 4.5245 ms
上位二つの差は0.2%未満。
ただし64よりは明確に速い。
guard threadが0になるB=72を後続baselineに採用します。
ここで、5ms切りました。
前に有効だったshared memoryをここで適用
途中で単独では約6%の高速化を実現したshared memoryにAを置く方法。
最後のB=72へ合体すれば、さらに速いのでは？
shared memory不使用 4.516864 ms
shared memory利用 4.934496 ms
9%以上遅くなりました。
ハイ残念。
昔効いた最適化が、最終形でも効くとは限りません。
shared Aは不採用で確定です。
最後にもう一度chunkサイズを最適化してみる
初期の段階でchunkサイズを一度最適化して、CHUNK_SIZE = 32768を採用しました。
しかし、前回最適化の時点では 2300 x 700万 / 32768 ≈ 49.2万taskへの分割でしたが、現在の実装では32bitのbitsetを処理していますので、タスク数も1/32、約15,400taskまで減少しています。
これはもう一度最適化を試す価値がありそうです。
最終構成はそのまま固定して、chunkサイズだけを1024～65536まで変えて測定します。
CHUNK_SIZE active tasks GPU_COMPUTE
1024 492,192 5.69 ms
2048 246,096 4.62 ms
4096 123,048 4.61 ms
8192 61,560 4.45 ms
16384 30,816 4.50 ms
32768 15,408 4.77 ms
65536 7,704 5.42 ms
最小値は8192でしたが、16384との差は約0.9%しかありません。
今回は2%以内を同着とし、その中ではchunk数、partial memory、reduce処理の少ない大きい方を選ぶルールにしていたので、
CHUNK_SIZE = 16384
を最終形に採用して、再度確定測定した時間を最終結果とします。
結果: GPU_COMPUTE ≈ 4.51 msです。
今回のkernelでは、だいたい3万～6万程度のactive taskを並べるあたりに、性能の良い領域があるようです。
4.51ms。でも全体では123.3ms
ここで最終構成を、同じ測定sessionで4つの範囲に分けて測りました。
| 計測範囲 | 時間 |
|---|---|
| GPU_COMPUTE | 4.515 ms |
| GPU_PIPELINE | 6.902 ms |
| PROGRAM | 86.403 ms |
| EXTERNAL | 123.339 ms |
GPUは計算そのものなら約4.5ms。猛烈に速い。
GPUへデータを送り、計算して、結果を受け取るところまで含めても約6.9msです。
ところがC++のmain()全体では約86ms、OS側からプロセス起動～終了までを見ると約123msになりました。
前回の最終AVX2版はEXTERNAL ≈ 68.520 msなので、プログラム全体ではまだCPUの勝ちです。
main()の外側で何をしている？
ここで少し気になることがあります。
EXTERNAL ≈ 123 ms
PROGRAM ≈ 86 ms
です。
main()の外側だけでも35～40msあります。
OSはいったい何をしているのでしょう？
そこで、ほぼ何もしない最小プログラムを3種類作って測ってみました。
PLAIN 普通のC++プログラム
CUDA_LINK CUDA Runtimeをリンクするだけ。CUDA APIは呼ばない
CUDA_TOUCH CUDA Runtime APIでdevice認識まで行う
結果:
| variant | PROGRAM | main()外側 |
|---|---|---|
| PLAIN | ≈ 0 ms | 5.51 ms |
| CUDA_LINK | ≈ 0 ms | 5.89 ms |
| CUDA_TOUCH | 63.86 ms | 30.08 ms |
CUDA Runtimeをリンクしただけでは、普通のC++との差は約0.4msしかありません。
ところがCUDA APIを実際に使うと、main()の中だけでなく、main()の外側も約30msまで増えました。
さらに同じsessionで最終direct CUDA版を測ると、main()外側は約33.6msでした。
CUDAを使った結果として作られた何かをプロセス終了時に片付けているようにも見えます。
が、今回の測定ではpre-mainとpost-mainを分離していません。Runtime、driver、WDDMなどのどこで時間を使っているのかも調べていません。
詳しい方、ぜひ教えてください😂
結論は、N=700万程度では、
GPUが4.5msで仕事を終えても、巨大な並列計算工場を動かす前後の費用を回収できない。
GPUが本領を発揮するのは、爆発的に大量の仕事があり、大量並列が効く比較的単純な計算を一気に渡せるときのようです。
最初のCUDAから約55倍
最初は、愚直解法を愚直に2300並列実装する方法で、GPU_COMPUTE ≈ 246 msでした。
最終的には、
time方向chunk
bit packing
hierarchy
alignment bank
geometry tuning
chunk retuning
を組み合わせ、GPU_COMPUTE ≈ 4.51 msまで来ました。
同じ、
全kについて全Aを見て、0→1を数える
というdirect解法の骨格は変えていません。
仕事量そのものを消したわけではありません。
労働環境を無茶苦茶効率化しました。
今回のまとめ
今回はdirect解法の実装を、GPU向けに徹底的に整えました。
そして計算部分だけなら猛烈に速くなった一方、EXTERNAL ≈ 123.3 msなので、プログラム全体では前回のAVX2版EXTERNAL ≈ 68.5 msにまだ負けています。
GPUは速い。
でも、GPUへ仕事を持っていくにもそれなりの時間がかかる。
さて。
ここまでdirect解法をいじくり倒しました。
では、仕事量そのものを減らすNTTをGPUで処理するとどうなるのでしょう。
ABC471G編は、次回が最終回です。
今度こそ終わらせます。お楽しみに。
前回：
仮想理想FPGAでAtCoderを解く(5) - ABC471G⑤ - direct解法をAVX2で実装してみる（後編）
次回：
仮想理想FPGAでAtCoderを解く(7) - ABC471G⑦ - CUDA NTTと決戦、そして1Gへ
コード全文と実装資料：(コード実装やドキュメント作成は生成AIの助けを借りています)
第6回コード全文と実装資料