c - OpenMP:前缀和算法

Question

我正在尝试使用 OpenMP 在 C 中实现前缀和算法，但我被卡住了。

#include <stdlib.h>
#include <stdio.h>
#include <omp.h>

int main(int argc, char* argv[])
{
    int p = 5;
    int X[5] = { 1, 5, 4, 2, 3 };
    int* Y = (int*)malloc(p * sizeof(int));

    for (int i = 0; i < p; i++)
        printf("%d ", X[i]);
    printf("\n");

    Y[0] = X[0];

    int i;
    #pragma omp parallel for num_threads(4)
    for (i = 1; i < p; i++)
        Y[i] = X[i - 1] + X[i];

    int k = 2;
    while (k < p)
    {
        int i;
        #pragma omp parallel for
        for (i = k; i < p; i++)
            Y[i] = Y[i - k] + Y[i];
        k += k;
    }

    for (int i = 0; i < p; i++)
        printf("%d ", Y[i]);
    printf("\n");

    system("pause");
    return 0;
}

这段代码应该做什么？

Input numbers are in X,
output numbers are (prefixes) in Y
and the number count is p.

X = 1, 5, 4, 2, 3

第一阶段。

Y[0] = X[0];

Y[0] = 1

第二阶段。

int i;
#pragma omp parallel for num_threads(4)
for (i = 1; i < p; i++)
    Y[i] = X[i - 1] + X[i];

例子:

Y[1] = X[0] + X[1] = 6
Y[2] = X[1] + X[2] = 9
Y[2] = X[2] + X[3] = 6
Y[4] = X[3] + X[4] = 5

第三阶段。 (我被卡住的地方)

int k = 2;
while (k < p)
{
    int i;
    #pragma omp parallel for
    for (i = k; i < p; i++)
        Y[i] = Y[i - k] + Y[i];
    k += k;
}

例子:

k = 2
Y[2] = Y[0] + Y[2] = 1 + 9 = 10
Y[3] = Y[1] + Y[3] = 6 + 6 = 12
Y[4] = Y[2] + Y[4] = 10 + 5 = 15

10 + 5 = 15 上面应该是 9 + 5 = 14，但是 Y[2] 被覆盖了通过另一个线程。我想使用 for 循环开始之前的 Y[2]。

例子:

k = 4
Y[4] = Y[0] + Y[4] = 1 + 15 = 16

结果:1、6、10、12、16。 预期的好结果: 1, 6, 10, 12, 15。

Answer 1

Above the 10 + 5 = 15 should be 9 + 5 = 14, but the Y[2] was overwritten by another thread. I want to use that Y[2] what was before the for-loop started.

使用 OpenMP，您始终必须考虑您的代码是否适用于单线程串行情况，因为

1. 它实际上可能以这种方式运行，并且
2. 如果它在串行上是错误的，那么它作为并行程序几乎肯定也是错误的。

您的代码连续不正确。看起来你可以通过向后运行问题循环来解决这个问题，从 i = p - 1 到 k，但实际上这还不够并行操作。

你最好的选择似乎是将你的部分结果累积到一个不同于保存上一个周期结果的数组中。例如，您可能会在 X 和 Y 之间切换作为数据源和结果，并通过一些指针争论来润滑迭代轮。或者，您可以通过使用二维数组而不是单独的 X 和 Y 来更轻松地做到这一点。