并行前缀和 CUDAfy

Question

我需要一种算法来计算数组的并行前缀和而不使用共享内存。如果除了使用共享内存别无选择，解决冲突问题的最佳方法是什么？

Answer 1

这篇link包含对并行前缀和的顺序和并行算法的详细分析：

其中还包含一段用于实现并行前缀算法的C代码片段以及避免共享内存冲突的详细解释。

您可以将代码移植到 CUDAfy 或简单地定义 C 区域并将它们用作应用程序中的非托管代码。但是 CUDA C 代码中有几个错误。我正在 Cudafy.NET

中编写代码的更正版本

[Cudafy]
public static void prescan(GThread thread, int[] g_odata, int[] g_idata, int[] n)
{
    int[] temp = thread.AllocateShared<int>("temp", threadsPerBlock);//threadsPerBlock is user defined
    int thid = thread.threadIdx.x;
    int offset = 1;
    if (thid < n[0]/2)
    {
        temp[2 * thid] = g_idata[2 * thid]; // load input into shared memory  
        temp[2 * thid + 1] = g_idata[2 * thid + 1];

        for (int d = n[0] >> 1; d > 0; d >>= 1)                    // build sum in place up the tree  
        {
            thread.SyncThreads();
            if (thid < d)
            {
                int ai = offset * (2 * thid + 1) - 1;
                int bi = offset * (2 * thid + 2) - 1;
                temp[bi] += temp[ai];
            }
            offset *= 2;
        }
        if (thid == 0)
        {
            temp[n[0] - 1] = 0;
        } // clear the last element  


        for (int d = 1; d < n[0]; d *= 2) // traverse down tree & build scan  
        {
            offset >>= 1;
            thread.SyncThreads();
            if (thid < d)
            {
                int ai = offset * (2 * thid + 1) - 1;
                int bi = offset * (2 * thid + 2) - 1;
                int t = temp[ai];
                temp[ai] = temp[bi];
                temp[bi] += t;
            }
        }
        thread.SyncThreads();
        g_odata[2 * thid] = temp[2 * thid]; // write results to device memory  
        g_odata[2 * thid + 1] = temp[2 * thid + 1];
    }
}

您可以使用上面修改过的代码代替link中的代码。

并行前缀和 CUDAfy

Parallel Prefix Sum CUDAfy

algorithm

parallel-processing

shared-memory

cudafy.net