0

OpenCLでgroupbyリダクションを実装したい。たとえば、入力

a1 a2 a3 b1 b2 c3 c4

を生成します

a6 b3 c7

C擬似コードは次のようになります。

int data[n][2], result[n][2], result_count = -1, 
    added = 0, group = data[0][0];
for (int i = 0; i < n; i++) { 
  if (group == data[i][0]) {
    added += data[i][1];
  } else {
    result[++result_count][0] = group;
    result[result_count][1] = added;
    group = data[i][0];
    added = 0;
  }
} 
return result, result_count;

私が知っているこの方向に進む唯一の標準アルゴリズムは、並列削減です。ただし、グループごとの付加価値のバッファではなく、1つの数値に減少します。並列削減が動的結果バッファー（ローカルメモリなど）で機能し、パフォーマンスの点で効率的であるかどうかはわかりません。

4

1 に答える 1

1

ハッシュによる解決策

フェーズ1）ハッシュスキームを使用してグループ値を場所にハッシュし、次にアトミック加算で2番目の値の内容を合計できます。

フェーズ2）プレフィックス合計スキャンアルゴリズムがハッシュテーブルを渡して圧縮します。

フェーズ3）オプションで結果を並べ替えます

ソートによる解決策

フェーズ1）グループ値でデータを並べ替える

フェーズ2）各グループを合計するために削減を使用する

フェーズ3）合計を圧縮するためのプレフィックス合計スキャン

于 2012-08-09T23:47:59.980 に答える