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;

我知道朝这个方向发展的唯一标准算法是并行归约。但是，它减少到一个数字，而不是按组添加值的缓冲区。我不确定并行减少是否可以与动态结果缓冲区（例如在本地内存中）一起使用，并且在性能方面仍然有效。

4

1 回答 1

1

哈希的解决方案

阶段 1) 可以使用散列方案将组值散列到某个位置，然后原子加法可以将第二个值的内容相加。

阶段 2) 前缀和扫描算法通过哈希表来压缩它。

阶段 3) 可选择对结果进行排序

排序解决方案

阶段 1) 对组值上的数据进行排序

阶段 2) 使用归约法对每个组求和

阶段 3) 前缀和扫描以压缩总和

于 2012-08-09T23:47:59.980 回答