分段减少与分散的段

Question

我必须在GPU上解决一个非常标准的问题,但我对实际的GPGPU很新,所以我正在寻找解决这个问题的想法.

我在3空间中有很多分配给极少数组(每个点属于一个组),特别是在这种情况下为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用于计算桶大小和每点重定位指数(更好地分类？),原子可能不是最好的主意.之后,他们通过组排序,我可能拿出提出的分段扫描算法的适应这里.

但在这种特殊情况下,我每点得到的数据量非常大(9-10个浮点数,如果需要的话,甚至可以加倍),因此每个线程使用共享内存元素和每点线程的标准算法可能会产生问题将每个多处理器资源视为共享内存或寄存器(好吧,更多关于计算能力1.x而不是2.x,但仍然如此).

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

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

Answer 1

尽管组很少，但我认为您无法避免最初的分组，同时仍然保持缩减步骤的效率。您可能还希望执行完整排序，而不仅仅是对索引进行排序，因为这将有助于在缩减步骤中保持内存访问的效率。

对于排序，请阅读此处的一般策略：

http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html

对于减少（旧但仍然很好）：

http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x86_website/projects/reduction/doc/reduction.pdf

对于并行缩减的示例实现：

http://developer.nvidia.com/cuda-cc-sdk-code-samples#reduction