在 OpenCL 中按减少分组

Question

我想在OpenCL中实现分组减少。例如，输入

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;

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

Answer 1

哈希的解决方案

阶段 1） 哈希方案可用于将组值哈希到某个位置，然后原子添加可以将第二个值的内容相加。

阶段 2）前缀总和扫描算法通过哈希表以压缩它。

阶段 3） （可选）对结果进行排序

通过排序的解决方案

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

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

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