带有openmp的Adi程序

Question

这是我第一次 post 在这里，如果我提出 easy/silly 问题，非常抱歉。我有一个并行编程作业 class.I 需要一些程序进行并行化。所以我的问题如下；我无法并行化程序的所有部分。如果我并行化 2 个 for 块，结果与串行结果不一样。所以这是程序

#pragma scop
 for (t = 0; t < _PB_TSTEPS; t++)
    {
#pragma omp parallel for schedule(dynamic) shared(X,B,A)  private(i1,i2) 
      for (i1 = 0; i1 < _PB_N; i1++)
    for (i2 = 1; i2 < _PB_N; i2++)
      {
        X[i1][i2] = X[i1][i2] - X[i1][i2-1] * A[i1][i2] / B[i1][i2-1];
        B[i1][i2] = B[i1][i2] - A[i1][i2] * A[i1][i2] / B[i1][i2-1];
      }
#pragma omp parallel for schedule(dynamic) shared(X,B)  private(i1)
      for (i1 = 0; i1 < _PB_N; i1++)
    X[i1][_PB_N-1] = X[i1][_PB_N-1] / B[i1][_PB_N-1];
#pragma omp parallel for schedule(dynamic) shared(X,B,A)  private(i1,i2) 
      for (i1 = 0; i1 < _PB_N; i1++)
    for (i2 = 0; i2 < _PB_N-2; i2++)
      X[i1][_PB_N-i2-2] = (X[i1][_PB_N-2-i2] - X[i1][_PB_N-2-i2-1] * A[i1][_PB_N-i2-3]) / B[i1][_PB_N-3-i2];

      for (i1 = 1; i1 < _PB_N; i1++)
    for (i2 = 0; i2 < _PB_N; i2++) {
      X[i1][i2] = X[i1][i2] - X[i1-1][i2] * A[i1][i2] / B[i1-1][i2];
      B[i1][i2] = B[i1][i2] - A[i1][i2] * A[i1][i2] / B[i1-1][i2];
    } 
#pragma omp parallel for schedule(dynamic) shared(X,B)  private(i2)
      for (i2 = 0; i2 < _PB_N; i2++)
    X[_PB_N-1][i2] = X[_PB_N-1][i2] / B[_PB_N-1][i2];

      for (i1 = 0; i1 < _PB_N-2; i1++)
    for (i2 = 0; i2 < _PB_N; i2++)
      X[_PB_N-2-i1][i2] = (X[_PB_N-2-i1][i2] - X[_PB_N-i1-3][i2] * A[_PB_N-3-i1][i2]) / B[_PB_N-2-i1][i2];
    }
#pragma endscop

我必须并行化这部分代码，但我不知道如何并行化最后 2 个 for 和另外 2 个 for above.I 已经尝试了大约与其他 for 相同的 openmp 代码。下面是我遇到问题的 for 的两个块。

  for (i1 = 1; i1 < _PB_N; i1++)
    for (i2 = 0; i2 < _PB_N; i2++) {
      X[i1][i2] = X[i1][i2] - X[i1-1][i2] * A[i1][i2] / B[i1-1][i2];
      B[i1][i2] = B[i1][i2] - A[i1][i2] * A[i1][i2] / B[i1-1][i2];
    } 



for (i1 = 0; i1 < _PB_N-2; i1++)
    for (i2 = 0; i2 < _PB_N; i2++)
      X[_PB_N-2-i1][i2] = (X[_PB_N-2-i1][i2] - X[_PB_N-i1-3][i2] * A[_PB_N-3-i1][i2]) / B[_PB_N-2-i1][i2];
    }

提前致谢。

在此处查看所有代码，

https://github.com/fedon99/Stack-Overflow/blob/master/adi.c

Answer 1

行的值取决于其他行，因此您不能轻易并行化。但是，这些列不依赖于其他列，因此您可以像这样并行化内部循环：

for (i1 = 1; i1 < _PB_N; i1++)
    #pragma omp parallel for
    for (i2 = 0; i2 < _PB_N; i2++) {
      X[i1][i2] = X[i1][i2] - X[i1-1][i2] * A[i1][i2] / B[i1-1][i2];
      B[i1][i2] = B[i1][i2] - A[i1][i2] * A[i1][i2] / B[i1-1][i2];
    }
} 

for (i1 = 0; i1 < _PB_N-2; i1++) {
    #pragma omp parallel for
    for (i2 = 0; i2 < _PB_N; i2++) {
        X[_PB_N-2-i1][i2] = (X[_PB_N-2-i1][i2] - X[_PB_N-i1-3][i2] * A[_PB_N3-i1][i2]) / B[_PB_N-2-i1][i2];
    }
}

只要 _PB_N >> nthreads 这应该可以正常工作。

你也可以像这样交换循环的顺序

#pragma omp parallel for private(i1)
for (i2 = 0; i2 < _PB_N; i2++) {
    for (i1 = 1; i1 < _PB_N; i1++)

但是这对缓存不友好。

此外，我看不出有任何理由使用动态调度。静态调度应该更有效。如果您不指定调度（如我上面的代码），则事实上的默认值是静态的。

带有openmp的Adi程序

Adi program with openmp

c

openmp