CUDAで総和計算をやろう！
配列の要素の総和が知りたいときは多々ある。配列の平均や分散、はたまた最大値などを知りたいときも似たような操作をするだろう。
逐次処理でこういった操作をするのは簡単だが、これを並列にやろうとすると、とたんに難しくなるのだ。案の定手こずったのでここにまとめる。今回はCUDAを用いて解説するが、OpenMPだろうがMPIだろうが、並列処理が関係するなら本質的に同じである。
並列に総和計算をするのが難しいわけ
なぜ難しいのだろうか？
次のコードを見てみよう。これはint型のarrという配列に入っている数の総和を取ろうとしたものだ。sumが総和が入るアドレスを指している。
ただし、getSum()が行われる前の*sum=0とする。それでもこのコードでは正しく動かない。なぜなら上のコードでは異なるスレッドが同時にsumに書き込みを行い、結果としてデータの不整合性が起きてしまうためである。
もちろん、これは一般的な並列コンピューティングでしばしば直面する方法であり、CUDAでも回避する方法がある。それがアトミック関数だ[1]。
上で用いたint atomicAdd(int* address, int a)は排他的にaをaddressに足し込むことを保証する関数で、足し込む前の*addressを返すものだ。
しかし、これでは逐次処理を行っているようなもので、高速化という観点からは推奨されるべきではない。さらにCUDAが用意しているアトミック関数は整数型のみであり、浮動小数点型を扱っていない。
畳み込み計算(reduction)
どうすれば並列かつ競合を起こさず足し算を行えるだろうか。その解決策として畳み込み計算(reduction)というものがある。
配列arrの要素数をjとする。j = remain + reduceとなるようにremainとreduceを決める。この時、reduceはremainを超えないギリギリの整数にするのが良い。
i(<reduce)番目のスレッドが
arr[i]+=arr[i+remain]
とする操作を0番目からreduce-1番目までが並列して1回行うと要素の数が半分となる。これが配列をパタンと畳んでいるように見えるので、畳み込み計算という。それを繰り返していくと最終的にarr[0]の中身が総和になるはずだ。
こうすると計算時間をO(log_2 N)程度に抑えることができる[2]。
共有メモリの活用
上の概念を用いるだけで計算時間は飛躍的に短くなる。しかし、畳み込み操作を行うたびにグローバルメモリにアクセスしていてはもったいない。 更に最適化をするために共有メモリを活用しよう。
指定したスレッド数をNTとおくと、 ブロック内の共有メモリに配列をコピーしてブロック内で先程の畳み込み処理を行えば、全体としては1回の操作で配列の長さは1/2 -> 1/NTとなる。
すると計算時間はO(log_NT N)程度となる[2]。
実際にやってみた
以上を踏まえて総和計算を実際に行ってみよう。コメントも書き加えてみたので順に追ってみてほしい。
課題点
大分処理を速めることは可能になったが問題点はある。それは共有メモリ内での1回目の畳み込み計算ですら1/2のスレッドが休んでおり、仕事を充てることができない点である。これを解決する方法をご存知であればコメントいただけると幸いだ。
References
[2] 畝山多加志 『大規模並列数値計算特論 GPUプログラミング(2)』2019年度講義資料
Follow me!
