バイトニックソートのコンピュートシェーダー移植版。 indexとkeyを一緒にソートします。
Bitonic Sort implemented in ComputeShader. Sort index and key together.
高速化は http://www.bealto.com/gpu-sorting_parallel-bitonic-1.html を参考にしました。
自分のブログにもまとめています。(http://blog.livedoor.jp/toropippi/archives/54817221.html)
1threadあたり2箇所Load,Storeを行います。
一番標準的な実装です。実行時間(ms)の表です。
| 要素数/カーネル名 | B2 |
|---|---|
| 65536 | 1 |
| 131072 | 1 |
| 262144 | 2 |
| 524288 | 4 |
| 1048576 | 10 |
| 2097152 | 19 |
| 4194304 | 39 |
| 8388608 | 83 |
| 16777216 | 179 |
| 33554432 | 382 |
| 67108864 | 818 |
| 134217728 | 1744 |
Shared Memoryを使った高速化版です。
青の部分はグローバルメモリへ書き込みをしないでShared memoryに書き込み使いまわしている部分です。 グローバルメモリのアクセスを抑えたことにより高速化できます。
| 要素数/カーネル名 | B2 | B2C2 |
|---|---|---|
| 65536 | 1 | 0 |
| 131072 | 1 | 1 |
| 262144 | 2 | 1 |
| 524288 | 4 | 3 |
| 1048576 | 10 | 8 |
| 2097152 | 19 | 11 |
| 4194304 | 39 | 24 |
| 8388608 | 83 | 51 |
| 16777216 | 179 | 109 |
| 33554432 | 382 | 236 |
| 67108864 | 818 | 508 |
| 134217728 | 1744 | 1095 |
1threadあたり4箇所Load,Storeを行うことでグローバルメモリのアクセス回数を減らします。
これを8,16と増やすことでさらなる高速化ができます。 Shared memory内も1threadあたり4箇所Load,Storeを行うことでShared memoryへのアクセス回数を減らします。
| 要素数/カーネル名 | B2 | B2C2 | B2B4B8B16C2C4 |
|---|---|---|---|
| 65536 | 1 | 0 | 0 |
| 131072 | 1 | 1 | 0 |
| 262144 | 2 | 1 | 1 |
| 524288 | 4 | 3 | 2 |
| 1048576 | 10 | 8 | 5 |
| 2097152 | 19 | 11 | 7 |
| 4194304 | 39 | 24 | 14 |
| 8388608 | 83 | 51 | 29 |
| 16777216 | 179 | 109 | 60 |
| 33554432 | 382 | 236 | 127 |
| 67108864 | 818 | 508 | 264 |
| 134217728 | 1744 | 1095 | 552 |
最終進化形だとここまで速くなります。最初と比べ3倍以上高速化できました！！わーい