带有openmp的Adi程序

Question

如果我提出一个简单的/愚蠢的问题，这是我在这里的第一篇文章。我有一份并行编程课的作业，我需要一些程序来并行化。所以我的问题是:我不能并行化程序的所有部分。如果我并行两个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。我和其他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++)

然而，这将是不友好的缓存。

而且，我不认为有任何理由使用动态调度。静态调度应该更有效。如果您不指定调度(如我上面的代码)，那么事实上的默认是静态的。