5

我必须在 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 计算的一般概念在主要框架上并没有真正的不同。

4

1 回答 1

2

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

对于排序,请在此处阅读有关一般策略的信息:

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

于 2012-04-07T03:15:54.617 回答