以下の話は、NVIDIAのG8シリーズ固有の話である。ただ、推定実行時間でソートしてGPUに投げるというのは恐らくどのGPUでも通用するテクニックだと思われる。
スレッド群
次のようにテクスチャを用意し、
int bit = atoi(argv[1]);
int mask = 1 << bit;
const int nWidth = 128;
const int nHeight = 128;
const int nData = nWidth * nHeight * 4;
float *data = new float[nData];
for(int i = 0; i < nData / 4; i++) {
data[i*4] = (float)((i & mask) >> bit);
data[i*4+1] = data[i*4] * 10000000;
}
このようなシェーダプログラムにかけたときにかかる時間を計測してみよう。
uniform sampler2DRect texUnit0; // datavoid main(void) {
int nPrimes = 0;
vec4 color = texRECT(texUnit0, gl_FragCoord.xy);
int x = int(color.x);
int nRep = int(color.y);;
for(int n = 0; n < nRep; n++)
x = 1 - x;
gl_FragColor = vec4(x, 0, 0, 0);
}
すなわち、入力が0だとすぐ抜けて、1だと1000万回繰り返し計算する。
処理時間の10回平均は次のようになった。
これはどのように解釈すればよいだろう。
0を黒、1を白で表現すると、入力テクスチャは次のような図になる。
スレッド群の中で、各スレッドは同じ動作を強制される。だから、スレッド群の中に入力が0と1が混在すれば遅くなるし、すべてどちらかになれば速くなる（0ばかりならすぐに終わる。ちなみにbitが14以上だとすべて0になる）。
おそらく、スレッド群は、8×4のピクセルを処理している、あるいは8×8など。だから、bit=6は速いのに、bit=7で急に遅くなる。
データが市松模様になるように並べて入力してみよう。
for(int i = 0; i < nData / 4; i++) {
int r = (i % nWidth) >> bit;
int c = (i / nWidth) >> bit;
data[i*4] = (float)(c % 2);
data[i*4+1] = data[i*4] * 10000000;
}
bitが1なら2×2、bitが2なら4×4が基本単位の市松模様になる。
すると実行時間は、
1 5101.0
2 4141.9
3 3238.9
4 3075.3
いまいちどういう単位でスレッド群にわからないが、4×4では不十分で、16×16で同じような処理を集めればよいらしい。
とはいっても、今回は極端な例で、前の素数の個数のときのように実行時間にばらつきがあったとしても、推定実行時間でソートしておけばおそらく十分だろう。
