0

这个问题缺乏细节。所以，我决定创建另一个问题，而不是编辑这个问题。新问题在这里：我可以并行化我的代码还是不值得？

我有一个在 CUDA 中运行的程序，其中一段代码在一个循环中运行（序列化，如下所示）。这段代码是在包含地址和/或 NULL 指针的数组中进行搜索。所有线程都在下面执行此代码。

while (i < n) {
    if (array[i] != NULL) {
        return array[i];
    }
    i++;
}
return NULL;

n数组的大小在哪里array，在共享内存中。我只对不同于 NULL（第一次匹配）的第一个地址感兴趣。

整个代码（我只贴了一段，整个代码很大）运行速度很快，但代码的“心脏”（即重复次数较多的部分）是序列化的，如您所见。我想知道我是否可以用一些优化算法并行化这部分（搜索）。

就像我说的，程序已经在 CUDA 中（以及设备中的数组），所以它不会有从主机到设备的内存传输，反之亦然。

我的问题是：n不大。很难超过 8。

我试图并行化它，但我的“新”代码比上面的代码花费了更多的时间。

我正在研究减少和最小操作，但我已经检查过它在n大时有用。

那么，有什么窍门吗？我可以有效地并行化它，即以低开销吗？

4

2 回答 2

1

为简单起见，GPGPU 代码的主要限制因素之一是内存管理。在大多数计算机中，将内存复制到设备 (GPU) 是一个缓慢的过程。

如http://www.ncsa.illinois.edu/~kindr/papers/ppac09_paper.pdf所示：

“从 GPU 子程序库中获得有效加速的关键要求是最大限度地减少主机和 GPU 之间的 I/O。”

这是因为主机和设备之间的 I/O 操作很慢！

将这与您的问题联系起来，在 GPU 上运行实际上没有意义，因为您提到的数据量非常小。您将花费更多时间运行 memcpy 例程，而不是首先在 CPU 上运行 - 特别是因为您提到您只对第一场比赛感兴趣。

许多人有一个常见的误解是，'如果我在 GPU 上运行它，它有更多的内核，所以运行速度会更快'，但事实并非如此。

在决定是否值得移植到 CUDA 或 OpenCL 时，您必须考虑该过程是否本质上是并行的 - 您是否正在处理大量数据等？

于 2013-07-24T22:37:26.790 回答
1

既然你说的array是共享内存资源，那么这个搜索的结果对于块的每个线程都是一样的。这意味着第一个简单的优化是只让一个线程进行搜索。这将释放除第一个块之外的所有工作（他们仍然需要等待结果，但不必浪费任何计算资源）：

__shared__ void *result = NULL;
if(tid == 0)
{
    for(unsigned int i=0; i<n; ++i)
    {
        if (array[i] != NULL)
        {
            result = array[i];
            break;
        }
    }
}
__syncthreads();
return result;

更进一步的做法是让线程并行执行搜索，作为经典的块内缩减。如果你能保证总是 < = 64，你可以在一个warp中做到这一点，并且在搜索过程中不需要任何同步（当然除了最后的完全同步）。n

for(unsigned int i=n/2; i>32; i>>=1)
{
    if(tid < i && !array[tid])
        array[tid] = array[tid+i];
    __syncthreads();
}

if(tid < 32)
{
    if(n > 32 && !array[tid]) array[tid] = array[tid+32];
    if(n > 16 && !array[tid]) array[tid] = array[tid+16];
    if(n > 8 && !array[tid]) array[tid] = array[tid+8];
    if(n > 4 && !array[tid]) array[tid] = array[tid+4];
    if(n > 2 && !array[tid]) array[tid] = array[tid+2];
    if(n > 1 && !array[tid]) array[tid] = array[tid+1];
}

__syncthreads();    
return array[0];

当然，该示例假定n为 2 的幂（并且s 相应array地用 s 填充NULL），但您可以随意调整它以适应您的需求并进一步优化它。

于 2013-07-25T12:01:22.467 回答