CUDA并行化数组工作

Question

我是CUDA的新手，我刚读过一些关于CUDA的NVIDIA导师，我需要一些帮助。有以下代码：

//some includes
#define NUM_OF_ACCOMS 3360
#define SIZE_RING 16
#define NUM_OF_BIGRAMMS 256

//...some code...
    for (i = 1; i <= SIZE_RING; i++) {
        for (j = 1; j <= SIZE_RING; j++) {
            if (j == i) continue;
            for (k = 1; k <= SIZE_RING; k++) {
                if (k == j || k == i) continue;
                accoms_theta[indOfAccoms][0] = i - 1; accoms_theta[indOfAccoms][1] = j - 1; accoms_theta[indOfAccoms][2] = k - 1;
                accoms_thetaFix[indOfAccoms][0] = i - 1; accoms_thetaFix[indOfAccoms][1] = j - 1; accoms_thetaFix[indOfAccoms][2] = k - 1;
                results[indOfAccoms][0] = results[indOfAccoms][1] = results[indOfAccoms][2] = 0;
                indOfAccoms++;
            }
        }
    }   

    for (i = 0; i < SIZE_RING; i++)
        for (j = 0; j < SIZE_RING; j++) {
            bigramms[indOfBigramms][0] = i; bigramms[indOfBigramms][1] = j;
            indOfBigramms++;
        }
        for (i = 0; i < NUM_OF_ACCOMS; i++) {
            thetaArr[0] = accoms_theta[i][0]; thetaArr[1] = accoms_theta[i][1]; thetaArr[2] = accoms_theta[i][2];
            d0 = thetaArr[2] - thetaArr[1]; d1 = thetaArr[2] - thetaArr[0];
            if (d0 < 0)
                d0 += SIZE_RING;
            if (d1 < 0)
                d1 += SIZE_RING;
            for (j = 0; j < NUM_OF_ACCOMS; j++) {
                theta_fixArr[0] = accoms_thetaFix[j][0]; theta_fixArr[1] = accoms_thetaFix[j][1]; theta_fixArr[2] = accoms_thetaFix[j][2];
                d0_fix = theta_fixArr[2] - theta_fixArr[1]; d1_fix = theta_fixArr[2] - theta_fixArr[0];
                count = 0;
                if (d0_fix < 0)
                    d0_fix += SIZE_RING;
                if (d1_fix < 0)
                    d1_fix += SIZE_RING;
                for (k = 0; k < NUM_OF_BIGRAMMS; k++) {
                    diff0 = subst[(d0 + bigramms[k][0]) % SIZE_RING] - subst[bigramms[k][0]];
                    diff1 = subst[(d1 + bigramms[k][1]) % SIZE_RING] - subst[bigramms[k][1]];

                    if (diff0 < 0)
                        diff0 += SIZE_RING;
                    if (diff1 < 0)
                        diff1 += SIZE_RING;
                    if (diff0 == d0_fix && diff1 == d1_fix)
                        count++;
                }
                if (max < count) {
                    max = count;
                    results[indResults][0] = max; results[indResults][1] = i; results[indResults][2] = j;
                    count = 0;
                    indResults++;
                }
            }
        }

如您所见，i和j变量有两个主要循环。我需要来自accoms_theta的foreach数组检查来自accoms_thetaFix的每个数组的条件。 （subst是带有SIZE_RING元素的int数组）。那么你需要关于2^30操作来检查所有数组。因为我是CUDA的新手我需要一些帮助来并行化我的算法。

这是关于我的设备的一些信息

GeForce GT730M
Compute Capability 3.5
Global Memory 2 GB
Shared Memory Per Block 48 KB
Max Threads Per Block 1024
Number of multiprocessors 2
Max Threads Dim 1024 : 1024 : 64
Max Grid Dim 2*(10 ^ 9) : 65535 : 65535

Answer 1

我不会详细介绍你想要计算的任何内容，但我会就你可能做的事情提出建议。

在CUDA（或OpenCL，或OpenMP）中并行化串行算法的直接方法是“并行化for循环”。在CUDA的上下文中，这意味着不是让单个线程迭代某些索引i的值，而是有不同的GPU线程处理i的不同值（或者 - i的每个值的一个线程）。

这可以通过嵌套循环来完成，例如两个索引i和j对应于内核启动网格的两个维度。

然而 - 只有embarrassingly parallel问题才能做到“天真地”这样做 - 其中每个线程要计算/写入的数据之间没有依赖关系（例如，对于i和j的每个组合）。此外，如果为不同的i和j读取的数据重叠或交错，则需要额外注意以防止重复读取相同的数据，从而降低性能。

试试这种方法。如果它失败了，或者你得出结论它不能适用，请提出另一个问题 - 但在那个问题中我们需要一个Minimal, Complete, Verifiable Example - 你没有提供这个问题。