c-更新2d数组时相邻元素的依赖关系(OpenMP)

我有一个2d数组，比如arr[SIZE][SIZE]，它在两个循环中更新，形式为：

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循环才被计算。

我想知道，在以这种方式并行时，我是否遗漏了什么，或者这个问题是算法工作方式固有的吗？如果是前者，任何其他方法都将受到赞赏。

我想知道在以这种方式并行时是否缺少了什么，或者这个问题是算法工作方式固有的吗？

是的，你错过了一些东西，但没有达到你可能希望的程度。假设并行版本应该计算与串行版本相同的结果，即使对于new_value_1()的情况，棋盘方法也不能解决问题。考虑阵列元素的这种布局：

xoxoxo
oxoxox
xoxoxo
oxoxox

在两次棋盘格中的第一次中，"x"元素根据"o"元素的原始值进行更新——到目前为止，效果不错——但在第二次中，根据"x"的新值更新"o"元件。数据依赖性被打破了，是的，但总体计算并不相同。当然，这同样适用于new_value_2()计算。跳棋对你没有什么帮助。

如果是前者，任何其他方法都将不胜感激。

您可以在shell中进行计算。例如，考虑阵列元素的标签：

具有相同标号的所有元素都可以并行计算(对于两个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]缩放允许进行这样的扩展内存分配，即它再次以[PTME]为代价，希望只支付一次)。

相关内容

最新更新

热门标签：