0

我在 C++ 上使用 OpenMP，我想并行化非常简单的循环。但我不能正确地做到这一点。我一直得到错误的结果。

for(i=2;i<N;i++)
    for(j=2;j<N;j++)
         A[i,j] =A[i-2,j] +A[i,j-2];

代码：

int const N = 10;
int arr[N][N];

#pragma omp parallel for
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        arr[i][j] = 1;

#pragma omp parallel for 
for (int i = 2; i < N; i++)
    for (int j = 2; j < N; j++)
    {
        arr[i][j] = arr[i-2][j] +arr[i][j-2];
    }

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
        printf_s("%d     ",arr[i][j]);
    printf("\n");
}

你有什么建议我该怎么做？谢谢！

4

4 回答 4

3

这个

#pragma omp parallel for 
for (int i = 2; i < N; i++)
    for (int j = 2; j < N; j++)
    {
        arr[i][j] = arr[i-2][j] +arr[i][j-2];
    }

总是会成为悲伤和不可预测的输出的来源。OpenMP 运行时将为每个线程提供一系列值i并留给它处理。线程更新的相对顺序没有确定性arr。例如，当线程 1 使用i = 2,3,4,5,...,100（或其他）更新元素并且线程 2 使用程序更新元素时i = 102,103,104,...,200​​，程序无法确定线程 1 是arr[i,:] = 100在线程 2 想要使用更新的值之前还是之后更新arr。您已经编写了带有经典数据竞赛的代码。

您有多种选择来解决此问题：

您可以将自己打结，以确保线程arr以正确（即顺序）的顺序更新。最终结果将是一个比顺序程序运行得更慢的 OpenMP 程序。不要选择这个选项。

您可以制作 2 个副本arr并始终从一个更新到另一个，然后从另一个更新到另一个。类似的东西（非常伪代码）

for ...
{
    old = 0
    new = 1

    arr[i][j][new] = arr[i-2][j][old] +arr[i][j-2][old];

    old = 1
    new = 0
}

当然，第二种方法是以空间换时间，但这通常是一个合理的权衡。

您可能会发现添加一个额外的平面arr并不会立即加快速度，因为它会破坏拉入缓存的值的空间局部性。对此进行一些实验，可能会创建[old]第一个索引元素而不是最后一个。

由于更新数组中的每个元素取决于在 2 行/列之外的元素中找到的值，因此您可以像棋盘一样有效地将数组拆分为白色和黑色元素。您可以使用 2 个线程，每个“颜色”一个线程，而线程不会竞相访问相同的数据。但是，缓存中空间局部性的破坏可能会对速度产生不良影响。

如果我有任何其他选项，我会编辑它们。

于 2013-09-05T11:02:22.617 回答
3

串行和并行运行会给出不同的。结果是因为在

#pragma omp parallel for 
for (int i = 2; i < N; i++)
    for (int j = 2; j < N; j++)
    {
        arr[i][j] = arr[i-2][j] +arr[i][j-2];
    }
    .....

你更新 arr[i]。所以你改变了另一个线程使用的数据。这将导致读写数据竞争！

于 2013-09-05T10:53:29.280 回答
3

将问题中的循环嵌套并行化很棘手，但可行。Lamport 的论文“DO 循环的并行执行”涵盖了该技术。基本上你必须将你的 (i,j) 坐标旋转 45 度到一个新的坐标系 (k,l) 中，其中 k=i+j 和 l=ij。

尽管要真正获得加速，但可能必须将迭代分组到小块中，这使得代码更加丑陋（四个嵌套循环）。

一种完全不同的方法是使用 OpenMP 任务以递归方式解决问题。递归是：

if( too small to be worth parallelizing ) {
    do serially
} else {
    // Recursively:
    Do upper left quadrant
    Do lower left and upper right quadrants in parallel
    Do lower right quadrant
}

实际上，算术运算与内存访问的比率是如此之低，以至于很难从示例中获得加速。

于 2013-09-05T22:48:22.853 回答
0

如果您一般询问并行性，那么另一个可能的答案是矢量化。您可以在不更改数据结构和代码库的情况下实现一些相对较差的向量并行化（例如 2 倍加速）。这可以使用 OpenMP4.0 或 CilkPlus pragma simd 或类似的（使用 safelen/vectorlength(2)）

好吧，你确实有数据依赖（内部和外部循环），但它属于«WAR»[（读后写）依赖子类别，这是使用«omp parallel for»«as is»的障碍，但不一定«pragma omp simd» 循环的问题。

要使其正常工作，您需要通过 OpenMP4 或 CilkPlus（最新的 gcc 或 Intel 编译器）支持 pragma simd 的 x86 编译器。

于 2013-09-06T19:45:09.430 回答