c - C 中的 prefixSum(A.K.A 扫描)

Question

这是一项学校作业，要求我编写一个前缀和方法；该方法需要“就地”和“算法的每次迭代，一个或多个加法并行执行”。我还没有实现它的并行运行部分，但是我已经完成了 up_sweep 和 down_sweep

我担心的是它似乎没有给我正确的输出例如，对于 (1,2,3,4,5,6,7,8) 的数组正确的输出应该是 (1, 3, 6, 10, 15, 21, 28, 36) 但我得到(0, 1, 3, 6, 10, 15, 21, 28) 代替。这就是我所拥有的，请帮忙***感谢 chux 指出这一点将在原始数组上调用 up_sweep，并将结果放入 down_sweep，后者将输出最终结果。

void up_sweep(int A[], int size) {
    int d;
    for (d = 0; d <= (log2(size) - 1); d++) {
        int by = pow(2, (d + 1));
        int partition_size = (size - 1) % by + 1;
        int k = 0;
        while (k < size - 1) {
            //temp = (int) k + ((int) pow(2, (d + 1)) - 1);
            A[(int) k + ((int) pow(2, (d + 1)) - 1)] += A[(int) k + (int) pow(2, d) - 1];
            k += partition_size;
        }
    }
}

void down_sweep(int A[], int size) {
    A[size -1] = 0;
    int depth;
    for (depth = (log2(size)-1); depth >= 0; depth--) {
        int by = pow(2, depth + 1);
        int partition_size = (size - 1) % by + 1;
        int k = 0;
        while (k < size - 1) {
            int temp = A[k + (int) pow(2, depth) - 1];
            A[k + (int) pow(2, depth) - 1] = A[k + (int) pow(2, (depth + 1)) - 1];
            A[k + (int) pow(2, (depth + 1)) - 1] += temp;
            k += partition_size;
        }
    }
}

Answer 1

如果要使用的算法不固定，这将是实现目标的更简单的“直接”方法:

void prefixSum(int A[], int size) {
    for (int i = size-2; i > 0; --i) {
        for (int j = i+1; j < size-1; ++j) {
            A[j] += A[i];
        }
    }
}

内部的 j 循环可以很容易地并行执行。

但是，如果您想坚持 parallel algorithm ，这将是我的实现建议:

void prefixSum(int A[], int size)
{
    // up-sweep
    for (int stepSize = 1; stepSize < size; stepSize *= 2) {
        for (int i = stepSize - 1; i < size - stepSize; i += 2*stepSize) {
            A[i+stepSize] += A[i];
        }
    }

    // down-sweep
    for (int stepSize = size / 4; stepSize > 0; stepSize /= 2) {
        for (int i = 2 * stepSize - 1; i < size - stepSize; i += 2*stepSize) {
            A[i+stepSize] += A[i];
        }
    }           
}

我直接使用 stride 变量而不是“level”变量来控制迭代，这使我不必使用 log 和 pow 函数调用。您可以再次轻松地并行化内部 i 循环，如果您愿意，还可以将函数拆分为单独的向上和向下扫描步骤。

请注意，此函数假定数组的大小是 2 的幂。如果要使其适用于任意长度的数组，则必须用零填充数组直到下一个 2 的幂，或者递归地应用调用或手动调整迭代边界。