OS XのOpenCL - その18

来週から会社はお盆休みなんだけど、来週月曜に僕が設計したレンズのファーストショットが上がってくる（レンズを成形する連中は今週頑張って、あとはよろしく〜と休みに突入するつもり）ので、僕はその評価のために設計部の部長とふたりで出社することに決定。ちなみに設計部も僕の研究開発部と同じで、構成員は部長ひとり。

ということで、先日の続き。画像にガウシアンブラーをかけるルーチンを例にとって、そいつのOpenCLでのパフォーマンスを上げる話になる。今日のところは、まずどんなアルゴリズムのガウシアンブラーを使うのがいいか、というOpenCLとは関係ない一般的な話。関係ないとはいうものの、普通はガウシアンブラーぐらいで、ここまで真面目にアルゴリズムが違うときのパフォーマンスを比較することはないので、これだけでも結構面白い。

13.7  例：ガウシアンブラーのパフォーマンスのチューニング

次の例はGPUで画像に対してガウシアンブラーをかけるアプリの最適化プロセスのステップになっている。GPUを使うコードのチューニングに同じようなことが使える。

13.7.1  パフォーマンスがもっともいいとどのくらいかを見積もる

{{decafish : チューニングの上限を知るためである}}

13.7.2  テストコードを作る

おそらく参照バージョンとしてホストでのコードを書いて結果を保存して、そのあと最適化したコードによって出力されたものを比較するコードを書くのが簡単である。

13.7.3  ガウシアンブラーを実装するアルゴリズムを選択する

3つの可能性がある。

• 古典的な2次元コンボリューション。 図-15は31x31カーネルでシグマ=5の場合の2次元コンボリューションを説明している。これは31 ×31、961ピクセルの入力からひとつの出力ピクセルを計算する。それぞれの入力ピクセルに対してひとつの足し算とひとつの掛け算が使われ、1ピクセルあたりトータルとして961+1I/Oか961の2倍の浮動小数点演算が使われる。結果は表-1の2番目である。
  
• 2次元コンボリューションを分割。 この場合はアルゴリズムは分割可能である。 結果は表-1の3列目である。図-16に示すように水平方向と垂直方向のふたつの2次元フィルタに分割できる。次元を分割することでメモリと計算のコストを減らすことができて、1ピクセルに対して64回の読み書きと124回の浮動小数点演算になる。結果は表-1の3番目である。
  
  サイズが31の1次元コンボリューションを使うカーネルはひとつの出力ピクセルに31個の入力を必要とし、それぞれの入力ピクセルに対してひとつの足し算とひとつの掛け算を実行する。それは31+1I/Oと2掛ける31の62浮動小数点となる。2パスあるのでそれを倍にする（シグマ=5の場合）。
• 再帰的ガウシアンフィルタ。 このアルゴリズムは正確なガウシアンブラーではなくて、その良好な近似である。図-17に示すように、横方向2パス縦方向2パスの4パス必要であるが、1ピクセルに対して10回の読み書きと64浮動小数点に減る。
  
  
  結果は表-1の4番目である。
  
  表-1は2Dコンボリューション、分割コンボリューション、再帰的ガウシアン繰り返しのメモリに対する計算の比を比較したものである（一番上は単純なコピーの結果を示してある）。再帰的ガウシアンアルゴリズムが最も良いように見える。 最初の列はピクセルあたりのメモリアクセスの回数である。2番目はピクセルあたりの浮動小数点演算の回数である。3番目はメモリに対する演算の比である。最後はそれぞれのアルゴリズムが1秒間にいくつのピクセルを処理できると期待できるかを百万ピクセル単位で書いてある。この数はコピーカーネルのI/Oに対する比から計算してある。コピーカーネルではピクセルあたり2I/Oの場合に14,200MPixel/秒の処理をしている。64I/Oだとその32倍遅くなるので14200/32=443MPixels/秒となる。

表-1: アルゴリズムの比較

Algorithm	Memory	Compute	C/M	Estimate
	(float R+W)	(flops)	Ratio	(MP/s)
Copy	2	0	0	14,200
2D Convolution	962	1,922	2	30
Separable Convolution	64	124	2	443
Recursive Gaussian	10	64	6	2,840