问具有散乱片段的分段约简

EN

我在GPU上解决了一个非常标准的问题，但我对实用的GPGPU非常陌生，所以我正在寻找解决这个问题的想法。

我在3-space中有许多点，它们被分配到非常少量的组(每个点属于一个组)，在这种情况下是15个(永远不会改变)。现在我想计算所有组的均值和协方差矩阵。因此，在CPU上，它大致相同：

for each point p
{
    mean[p.group] += p.pos;
    covariance[p.group] += p.pos * p.pos;
    ++count[p.group];
}

for each group g
{
    mean[g] /= count[g];
    covariance[g] = covariance[g]/count[g] - mean[g]*mean[g];
}

由于组的数量非常少，所以最后一步可以在CPU上完成(无论如何，我都需要CPU上的这些值)。第一步实际上只是分段缩减，但分段分散在周围。

因此，我想到的第一个想法是，首先按分组对点进行排序。我想过一个简单的存储桶排序，使用atomic_inc来计算存储桶大小和每个点的重定位索引(对于排序有更好的想法吗?原子可能不是最好的想法)。在此之后，它们按组进行排序，我可能会提出一种适用于here的分段扫描算法。

但是在这个特殊的情况下，我得到了一个非常大的数据量(9-10个浮点数，如果需要的话，甚至可能是两倍)，所以使用每个线程一个共享内存元素和每个线程一个点的标准算法可能会出现关于每个多处理器资源作为共享内存或寄存器的问题(好吧，计算能力1.x比2.x多得多，但仍然)。

由于小组的数量非常少，而且数量不变，我认为可能会有更好的方法。也许已经有了适合这种标准问题的这些特定属性的现有想法。或者，也许我的一般方法并不是那么糟糕，并且您有改进各个步骤的想法，比如适用于非常少的键的好的排序算法，或者一些最小化共享内存/寄存器使用的分段缩减算法。

我正在寻找通用的方法，并不想使用外部库。FWIW我正在使用OpenCL，但这并不重要，因为GPU计算的一般概念在主要框架上并没有真正的不同。