18.3. ストライドとメモリアクセス

前の項目で解説したメモリ空間の列を拡張する方式は、以下のように実装することができます。

int offset = local_id % BANK_LINE;
int stride = 16 * offset;
int bank_number = local_id >> 2;
value = データを取得
shared_local_memory[value * local_size + stride + bank_number]++;

このコードでは、ローカルサイズが64、バンクライン(BANK_LINE)が4とします。

Note

256x64となるとメモリのサイズとしてはint型で64KBの計算となるので、一部のAMDのGPUであれば対応できますが、IntelやNVIDIAでは効率が悪くなる可能性が濃厚です。

bank_numberのメモリバンクを4回に分散してアクセスするものとします。

例えばlocal_idが1の場合を考えてみましょう。データの値が135だとすると、

となります。この場合、行135、列16、バンク「0」に加算処理を加えます。

次にlocal_idが6の場合を考えてみましょう。データの値が222だとすると、

となります。行222、列33、バンク「1」に加算処理を加えます。

さらにlocal_idが63の場合を考えてみましょう。データの値が135だとすると、

となります。行135、列63、バンク「15」に加算処理を加えます。

この方式では列がバンクに該当するため、まさにバンクコンフリクトが起きやすいケースとなります。

例えばlocal_idが63の場合で、データの値が136になると、

となり、行136、列63、バンク「15」に加算処理を加えます。つまりローカルIDが同じ場合、バンクコンフリクトがおきてしまいます。

これに対応するために、ローカルメモリの割り当ての際に列を一つ追加します。ホストプログラムないでメモリ空間を定義する場合は以下のようにします。

kernel.set_arg(1, cl.LocalMemory(4*BIN_SIZE*(LOCAL_SIZE+1)))

LOCAL_SIZEはローカルサイズ(ローカルスレッド数)、BIN_SIZEはカテゴリ数を指します。

さらにカーネル関数側でも以下のように列を一つずらします。

int offset = local_id % BANK_LINE;
int stride = 16 * offset;
int bank_number = local_id >> 2;
value = データを取得
shared_local_memory[value * (local_size+1) + stride + bank_number]++;

ローカルIDが0の場合で値が異なる場合を考えてみましょう。例えば値が0の場合です。

行0、列0、バンク0となります。

次に同じくローカルIDが0で、今度は値が1となる場合です。

行1、列0、バンク1となります。

さらに同じ条件で値が2の場合です。

行2、列0、バンク2となります。このようにローカルIDが同じでも値が変わるとバンクがスライドしていき、バンクコンフリクトを回避できます。

このようにメモリアクセスパターンを、値に応じてスライドさせることによって(うまくいけば)バンクコンフリクトを減らすことができます。

バンクコンフリクトへの解決策については、基数整列でも解説しています。

Copyright 2018-2019, by Masaki Komatsu