11.1. アルゴリズムのパラメータ

戻る		次へ

ヒストグラムの基本アルゴリズムはシングルスレッドでは、シンプルなのですが、GPGPU等を使用したデータ並列プログラミングモデルに適合させると難易度は大半の人が想像される以上に高くなります。

まずアルゴリズムのパラメータですが、以下の４つを考慮する必要があります。

ワークグループ数

データ数: 入力の配列の要素数です。ヒストグラムでは、カテゴリ数 x スレッド数 x ワークグループ数以上の値にします。
カテゴリ（ビン）数: 8ビットのデータ（0-255）を使います。注意すべき点として、OpenCL-C言語（Intelプロセッサ環境）と連携するためにバイトオーダーはLittle-Endian（リトル・エンディアン）とします。Javaの入出力クラス（ByteBuffer等）ではビッグ・エンディアンを優先するので、明示的に変更する必要があります。
ローカルサイズ: 各ワークグループ内のワークアイテム数です。パフォーマンスをチューニングするために使います。
ワークグループ数: ワークグループ数は、グローバルサイズをローカルサイズで除した数です。

次にマイクロプロセッサ（ここではGPUに限定）のキャッシュサイズと、ベンダーのOpenCL推奨値を調べます。共有ローカルメモリ（SLM）に割り当てるサイズ、ローカルサイズ、ワークグループ数はメモリーの容量によって値をチューニングします。

検証機のIntel iGPUのSLMのサイズは64KBとなりますが、AMDはCompute Unitに対して32KB-64KB、NVIDIAは16-48KBなどと異なります。ここでは、Intel HD Graphics内臓GPUの推奨値を使います。

IntelはSLMに最小でも4KBを割り当てるとしているので、4KBxワークグループ数が64KBとなるようにします。するとワークグループ数は16に固定できます。

最後にローカルサイズ（ワークグループ内のスレッド数）を決定する必要がありますが、これは次の項目で解説します。