Embedded Files
Prefix Sumにみるgloballycoherent
Prefix Sumにみるgloballycoherent
25/08/24 up
祝200回！
これからもよろしくお願いします。
更新頻度は昔ほど多くはないですが。
前回、Compute Shaderを使ってGBufferを作成する手法について紹介しましたが、この中でPrefix Sumを実装しています。
ここで、globallycoherent という見慣れない修飾子を使っているので、Prefix Sumのプログラムといっしょに紹介しようと思います。
サンプルプログラムには今回のためにPrefix Sumのテストコードを実行するパスを追加しています。
テストコードのパスはコメントアウトされているので、実行したい場合はコメントアウトを外してビルドしてください。
該当箇所は scene.cpp の767行目です。
Prefix Sumとは
Prefix Sumとは
Prefix Sum（もしくはPrefix Scan）はある数列に対して、自身のインデックスより前の値の和のことで、日本語では累積和と呼ばれます。
例えば、以下のようなものが累積和です。
この結果は何に使えるのかというと、前回利用したのはビニング時のメモリの確保です。
マテリアル単位でGBufferへの変換を行うとすると、同一マテリアルのピクセルは連続したバッファ領域で提供される必要があります。
この時、マテリアル数×ピクセル数のバッファを取得していしまうと、マテリアル数が多くなった場合や画面のピクセル数が高解像度になった場合にアホみたいなサイズのバッファを取得してしまいます。
Prefix Sumを計算できると、バッファはピクセル数分だけ確保すれば良く、Prefix Sumからそのバッファの先頭アドレスを、各マテリアルの総数からバッファサイズを求めることができるというわけです。
そんなPrefix Sumを求めるプログラムは簡単です。
C++で実装するなら以下のようなコードで実現できるでしょう。
しかし、これをGPUで実装するとなるとどうでしょう？
GPUは並列処理を行うのが強いハードウェアであり、上記のようなBrute Forceでループをぶん回す方法では高速化出来ません。
要素数が少ないならGPUの1スレッドを利用して上記のようにループを回す手段もありかもしれませんが、数百、数千のマテリアルが出てきたらそうもいかないでしょう。
そこで並列化を前提としたPrefix Sumの計算手法が求められます。
Single-pass Parallel Prefix Scan with Decoupled Look-back
Single-pass Parallel Prefix Scan with Decoupled Look-back
Prefix Sumには複数パスを利用する方法があり、GPU Gems 3にはいくつかの手法が提案されています。
しかし複数パスを利用するのは少し面倒です。
パス間でバリアを張らなければいけませんし、複数のコード実装も必要になります。
そこで紹介するのが "Single-pass Parallel Prefix Scan with Decoupled Look-back" という手法です。
この手法は2016年にNVIDIAから出された論文のタイトルです。
名前の通り、シングルパスでPrefix Sumを計算する手法について記載されています。
https://research.nvidia.com/publication/2016-03_single-pass-parallel-prefix-scan-decoupled-look-back
考え方自体はさほど難しくはありません。
まず、Prefix Sumを求める数列をブロックに切り分けます。
このブロック1つはスレッドグループ1つで実行するので、ブロック1つのサイズはスレッドグループのスレッド数に依存します。
私の実装ではブロック1つは256個の数列ということにしています。当然、スレッド数も256です。
次にブロックごとにPrefix Sumを求めます。
スレッドグループ内では共有メモリを利用することが出来ます。
これを利用すると複数パスを利用しなくても、シングルパスでブロック単位のPrefix Sumを求めることが出来ます。
以下は私が実装したブロック単位のPrefix Sumのコードです。
この処理はスレッドグループ内の各スレッドで並列に実行されます。
Wave Intrinsicsを利用してWave単位でのPrefix Sumを求め、その後にスレッドグループのPrefix Sumまで拡大していきます。
これによってブロックごとのPrefix Sumを求めることが出来ますが、当然それだけでは全体のPrefix Sumは求められません。
最初の0番ブロックは問題ないですが、次の1番ブロックは0番ブロックの総和が必要になります。2番ブロックは0番と1番の総和が必要で…
という感じで、前のブロックの結果を次々に調べる必要があります。
私の実装ではそれをスピンロックを利用して実装しています。
UAVとしてステータスバッファを作成し、ブロックごとにそのステータスバッファに計算結果を書き込みます。
自分より前のブロックで計算が終了しているかどうかをそのステータスバッファの状態を調べることで確認し、終わっているなら結果を受け取って自身のブロックの処理を進めるという感じです。
対応コードは以下のようになっています。
block_sumには各ブロックの総和が求められています。
0番ブロックは何も気にせずステータスを書き込みます。
ステータスはuint2で、xには自身のブロック含む、ここまでの数列の総和を、yにはステータス値を書き込みます。
今回はステータス値が2の場合にLook-backも終了しているとしています。
0番以外のブロックでは自分よりも前のブロック（prevBlock）のステータスバッファを確認します。
ステータスが2になっていなければループを継続、2になったらループを終了してこれまでの総和と自身のブロックの総和を足してステータスに書き込みます。
結果 その1
結果 その1
さて、これだけ見るとなるほど確かに動きそうだと思うかもしれません。
では、テスト用のデータを用意して実行してみましょう。
テスト用データは1024個の要素を持ち、数列としては index + 1 とします。
つまり、1, 2, 3, 4, …という数列で、最後はもちろん1024です。
このような数列のPrefix Sumは最後のインデックスでは "523776" になります。
PIXで実行結果をキャプチャし、出力バッファの結果を表示すると以下のようになりました。
明らかに結果がおかしいです。
バッファを調べていくと、256の段階でおかしくなっているのがわかります。
Look-backがうまくいっていないようです。
これはなぜかというと、UAVへの書き込みが問題になります。
UAVやRenderTargetなどへの書き込みや読み込みはキャッシュが有効になります。通常であればL1キャッシュでしょう。
このキャッシュがどのように動作するかはハードによると思うのですが、まず間違いなく言えることは、同一Dispatch内でキャッシュが共通することは保証されません。
つまり、0番ブロックが書き込んだ内容がまだキャッシュに残っていて実際のバッファには反映されず、1番ブロックは実際のバッファから値を取得してキャッシュしてしまっているため、0番が書き込んでも無視されてしまっているのではないかと推測できます。
ただ、この場合はGPUクラッシュする可能性もあります。
今回はGPUクラッシュしませんでしたが、別の手法を色々試しているときにクラッシュするパターンはありました。
明らかに無限ループになるようなコードを書いた場合にもクラッシュはしなかったので、ドライバ側がいい感じにコンパイルするとかしているのかもしれません。
この問題は複数パスを利用することで回避は可能です。
つまり、まずブロック単位のPrefix Sumを求め（パス1）、ブロックごとの総和からブロックのPrefix Sumを求め（パス2）、最後に各ブロックにパス2で求めた各ブロックのPrefix Sumを加算する（パス3）という3パス方式です。
ブロック数が更に数千とか言ってる場合はパス2、3を複数回実行する必要があるかもしれませんが、そうでなければ3パスで実行可能です。
ですが、シングルパスで実行したいわけです。
3パス実行なんて面倒ですし、バリアも適時張らなければなりません。
問題がキャッシュにあるのであれば、ステータスバッファだけキャッシュ無効にできないものか…
globallycoherentという修飾子
globallycoherentという修飾子
そう、実は存在しています。それが globallycoherent という修飾子です。
MSのRWBufferのドキュメントに少しだけ説明が記載されています。
https://learn.microsoft.com/ja-jp/windows/win32/direct3dhlsl/sm5-object-rwbuffer
この修飾子を付加している場合、GPU全体でフラッシュされるとあります。
ない場合はスレッドグループ内でのみフラッシュされるようです。
説明的にはキャッシュを無視するというわけではなく、フラッシュされる場合にGPU全体で行うという状態のようです。
しかし動作としては求めるものであり、あるスレッドグループのUAV書き込みを別のスレッドグループで調べることができるというわけです。
結果 その2
結果 その2
それでは、ステータスバッファに globallycoherent を付加して実行してみましょう。
正しい結果になりました！
globallycoherent によってGPU全体で一貫性のある結果を得られるということですね！
しかし、キャッシュ無視、もしくはGPU全体でのフラッシュは決して軽い処理ではありません。
ブロック数が数千、数万になるようですと、馬鹿にならないパフォーマンスの影響があると思われます。
実際にはブロック数がそこまで多くなることはほとんどないと思いますが、大規模なデータを扱っている場合は気をつける必要があると思います。
当然ですが、よくわからんから全部のUAVに globallycoherent を付けておこう！なんてやらないように。
特に大きなバッファに対して使う場合は要注意です。
免責事項
免責事項
globallycoherent についてはHLSLの落とし穴として紹介されてもいます。
https://silvesthu.github.io/posts/2020/05/hlsl-pitfalls/
ここからリンクが辿れる部分も読んでおくとより正しく評価できるのではと思います。
これらを読んでこういうことかな？という感じで記事を書いているので、間違っている部分があるかもしれません。
また、今回作成したプログラムはRTX 4080で動作確認を行っています。
もしかしたら別のGPUでは正常動作しないとか、GPUクラッシュしてしまうとかあるかもしれません。
試す場合は慎重にお試しください。
AMDのGPUはあるので、そのうち試してみたいなとは思ってるのですが、いつになることやら。
Intel？ いや、まあ、その、なんだ…
Page updated
Google Sites
Report abuse