c - 带有openmp的Adi程序

Question

这是我在这里的第一篇文章，如果我提出了一个简单/愚蠢的问题，我深表歉意。我有一个并行编程类(class)的作业。我需要一些程序来并行化。所以我的问题如下；我无法并行化程序的所有部分。如果我并行化 2 个 for block ，结果与串行结果不同。所以这是程序

#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。我试过了与其他 for 的 openmp 代码大致相同。下面是我遇到问题的两个 for block 。

  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++)

但是这对缓存不友好。

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