前回はこんな記事を書きました。
前回記事では役に立たないアルゴリズムとしてスターリンソートを例に挙げ、GPUで爆速化しようというチャレンジの結果、数万要素規模の入力配列でCPUよりも最大で8倍ほど高速な粛清を達成しました。
しかしながら、前回のコードはNVIDIA公式のCUDAのヘッダーライブラリCUBに頼り切っていたため、いまいち真の最適化にたどり着いた感が個人的にはありません。
というわけで、CUBに頼らずにもっと高速粛清できないかに取り組んでみました。
1. カーネルをなるべく一つにする。
今回は高速化のために、前回のコードに出てきたカーネルを1つのカーネルに束ねました。
GPUプログラミングに触れていない方には、よくわからないと思うので、その理由を簡単にまとめておきます。
前回はCUBをそのまま使うというヌルゲーだったので以下のようなタイムラインになっていました。
- Inclusive scanでmaxオペレータを使い、入力配列のmax値をスキャンする。結果を中間出力として配列に格納する。CUBのDeviceScanを使う。
- 入力配列と中間出力を比べて、入力に対し中間出力のほうがおおきい値なら0、そうでなければ1をフラグ配列に格納する。ここはフラグ立てるだけなのでオリジナルの関数。
- フラグ配列をintと解釈してExclusive Sumをとる。
flag == 1の場合はその入力配列要素をExclusive Sumの値と一致する出力インデックスに格納する。この処理はCUBのDevicePartitionで一発でやってくれる。
CUDAにおいてはグローバルメモリとのやり取りはなるべくしないほうがよいとされています。グローバルメモリとは、CPUとのデータのやり取りに使われ大容量だが、スレッドとの通信が遅いというメモリです。カーネルを分けてしまうと、次のカーネルに何か値を渡すときに、どうしてもグローバルメモリに格納しないといけません。上で言う中間出力とかフラグ配列とかです。
カーネルを半ば無理やりにでも一つにまとめることで、グローバルメモリとの通信量が抑えられ、高速化を図れます。
また、カーネルを分けることには同期の問題もあります。CUDAでは、カーネルを抜けるときに必ず全スレッドの同期がとられます。各スレッドはおしなべて同時に動いてるわけではないので、カーネルの始動直後と終了直前は、どうしてもスレッドの動作密度が下がります。これを回避するためにも、カーネルを一つにすることは重要なのです。
2. コード
今回のコードを見せたい気持ちは山々なのですが、最適化のために読みづらすぎるのと、長大なコードになってしまったので、どういうことをやったかの説明をしておきます。
まずInclusiveScanやExclusiveScanについてはCUBとほぼ同じことをやっています。
1スレッドあたりの値の持ち方は以下の論文を参考にしています。
カーネル内の処理内容は以下の通りです。
- 入力配列のInclusive scanでmax値をスキャンする。
- max値と元の値を比べて、元の値 >= max値 なら
flag = 1とする。 -
flagのExclusive scanをとる。 -
flag == 1なら出力のidx = flagのExclusive scanに入力要素を格納する。
やってることはあまり変わってないですが、1カーネル内にすべてを詰め込んだのでグローバルメモリとのやり取りが減りました。
3. 粛清時間
前回と同じ条件で粛清時間を計測しました。結果は以下の通りです。CPUのコードは変更なしですが、一応今回のも載せておきます。
| 要素数 | CPU粛清時間(前回)[ms] | CPU粛清時間(今回)[ms] | GPU粛清時間(前回)[ms] | GPU粛清時間(今回)[ms] |
|---|---|---|---|---|
| 10 | 0.005 | 0.004 | 16.0113 | 8.11213 |
| 100 | 0.077 | 0.063 | 16.3853 | 8.98253 |
| 1000 | 0.573 | 0.895 | 17.8869 | 9.79082 |
| 10000 | 10.58 | 7.313 | 25.0143 | 10.6441 |
| 100000 | 87.223 | 91.487 | 24.2178 | 13.5576 |
| 1000000 | 893.693 | 886.729 | 121.326 | 25.3233 |
| 10000000 | 6487.83 | 5733.1 | 1046.07 | 169.816 |
なんとカーネルを束ねることをするだけで最大で35倍程度の速度で粛清できるようになりました。まだまだ並列数の最適化や、コード内の冗長性を削減できれば高速化の余地があります。
ただ、小さい配列の時は前回同様CPUのほうが速いという結果ですね。ここばかりはしょうがないところです。
3. まとめ
カーネル関数の工夫だけでかなりの高速化が達成できました。CUBのコードを読むのはかなり大変で僕も完璧に理解できませんでしたが、一度読んでみると勉強になりますね。