c - 更新二维数组时相邻元素的依赖性 (OpenMP)

Question

我有一个二维数组，比如 arr[SIZE][SIZE]，它在两个 for 循环中以以下形式更新:

for(int i = 0; i < SIZE; i++)
    for(int j = 0; j < SIZE; j++)
        arr[i][j] = new_value();

我正在尝试使用 OpenMP 进行并行处理。

有两种情况会发生这种情况，第一种是 new_value_1() 函数，它依赖于 arr[i+1][j] 和 arr [i][j+1](“数组的边缘”问题已经解决)，我可以愉快地使用棋盘技术将其并行化:

for(int l = 0; l < 2; l++)
#pragma omp parallel for private(i, j)
    for(int i = 0; i < SIZE; i++)
        for(int j = (i + l) % 2; j < SIZE; j += 2)
            arr[i][j] = new_value_1();

问题来自第二个实例 new_value_2()，它依赖于:

arr[i+1][j],
arr[i-1][j],
arr[i][j+1],
arr[i][j-1]

即各个方向的相邻元素。

这里，对负相邻元素有依赖，所以arr[0][2] = new_value_2()依赖于arr[0][1已经更新的值] 直到第二个 l 循环才会被计算。

我想知道在以这种方式进行并行化时是否遗漏了什么，或者这个问题是否与算法的工作方式有关？如果是前者，任何其他方法将不胜感激。

Answer 1

I was wondering if there was something I was missing in parallelising this way or if the issue is inherent with the way the algorithm works?

是的，您遗漏了一些东西，但不是您可能希望的那样。假设并行版本应该计算与串行版本相同的结果，棋盘方法即使对于 new_value_1() 情况也不能解决问题。考虑这种数组元素的布局:

xoxoxo
oxoxox
xoxoxo
oxoxox

在两次棋盘传递中的第一次，“x”元素根据“o”元素的原始值进行更新——到目前为止一切顺利——但在第二次传递中，“o”元素根据“x”元素的新值进行更新。数据依赖性被打破了，是的，但是整体计算是不一样的。当然，这同样适用于 new_value_2() 计算。棋盘并不能真正帮助您。

If the former, any other approaches would be appreciated.

您可以在 shell 中进行计算。例如，考虑数组元素的这个标签:

0123
1234
2345
3456

可以并行计算所有具有相同标签的元素(对于两个 new_value() 函数)，前提是首先计算所有具有较小标签的元素。这可能看起来像这样:

for(int l = 0; l < (2 * SIZE - 1); l++) {
    int iterations = (l < SIZE) ? (l + 1) : (2 * SIZE - (l + l));
    int i = (l < SIZE) ? l : (SIZE - 1);
    int j = (l < SIZE) ? 0 : (1 + l - SIZE);

    #pragma omp parallel for private(i, j, m)
    for(int m = 0; m < iterations; m++) {
        arr[i--][j++] = new_value_1();
    }
}

那样的话，您不会从并行化中获得太多好处，但是串行计算工作方式的固有方面，至少对于 new_value_2()案例。

不过，对于 new_value_1() 的情况，逐行进行可能会做得更好:

for(int i = 0; i < SIZE; i++)
    #pragma omp parallel for private(j)
    for(int j = 0; j < SIZE; j++)
        arr[i][j] = new_value_1();

或者，仅对于 new_value_1() 情况，您可以通过将结果存储在单独的数组中来获得良好的加速:

#pragma omp parallel for private(i, j), collapse(2)
for(int i = 0; i < SIZE; i++)
    for(int j = 0; j < SIZE; j++)
        arr2[i][j] = new_value_1();

如果这要求您随后将结果复制回原始数组，那么这可能不值得，但您可以通过在两个数组之间来回翻转来避免这种情况:从第一个数组计算到第二个数组，然后然后下一次，从第二个计算到第一个(如果问题 [PSPACE] 缩放允许有这样一个扩展的内存分配，即它再次出现在[PTIME] 费用，希望只支付一次)。