prefixSum（又名扫描）

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

循环可以轻松并行执行。

但是，如果您想坚持使用并行算法，这是我的建议来实现它：

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 的下一个幂，或者应用递归调用或手动调整迭代边界。