c - OpenMP 并行代码较慢

Question

我有两个正在并行化的循环

#pragma omp parallel for
  for (i = 0; i < ni; i++)
    for (j = 0; j < nj; j++) {
      C[i][j] = 0;
      for (k = 0; k < nk; ++k)
        C[i][j] += A[i][k] * B[k][j];
    }
#pragma omp parallel for
  for (i = 0; i < ni; i++)
    for (j = 0; j < nl; j++) {
      E[i][j] = 0;
      for (k = 0; k < nj; ++k)
        E[i][j] += C[i][k] * D[k][j];
    }

奇怪的是，即使使用大量线程，顺序执行也比上面的并行版本快得多。难道我做错了什么？请注意，所有数组都是全局的。这有什么区别吗？

Answer 1

并行外部循环的迭代共享其内部循环的索引变量(j 和 k)。这肯定会使您的代码比您可能预期的要慢一些，即您的循环不是 "embarrassingly" (或“愉快地”)并行和并行循环迭代需要以某种方式从共享内存访问这些变量。

更糟糕的是，正因为如此，您的代码包含 race conditions .因此，它的行为将具有不确定性。换句话说:您的并行矩阵乘法实现现在不正确! (继续检查您的计算结果。;))

您要做的是确保外循环的所有迭代都有索引变量 j 和 k 的私有(private)副本。您可以通过在并行循环的范围内声明这些变量来实现这一点:

int i;

#pragma omp parallel for
  for (i = 0; i < ni; i++) {
    int j1, k1;  /* explicit local copies */
    for (j1 = 0; j1 < nj; j1++) {
      C[i][j1] = 0;
      for (k1 = 0; k1 < nk; ++k1)
        C[i][j1] += A[i][k1] * B[k1][j1];
    }
  }        
#pragma omp parallel for
  for (i = 0; i < ni; i++) {
    int j2, k2;  /* explicit local copies */
    for (j2 = 0; j2 < nl; j2++) {
      E[i][j2] = 0;
      for (k2 = 0; k2 < nj; ++k2)
        E[i][j2] += C[i][k2] * D[k2][j2];
    }
  }

或以其他方式在循环编译指示中将它们声明为 private:

int i, j, k;

#pragma omp parallel for private(j, k)
  for (i = 0; i < ni; i++)
    for (j = 0; j < nj; j++) {
      C[i][j] = 0;
      for (k = 0; k < nk; ++k)
        C[i][j] += A[i][k] * B[k][j];
    }
#pragma omp parallel for private(j, k)
  for (i = 0; i < ni; i++)
    for (j = 0; j < nl; j++) {
      E[i][j] = 0;
      for (k = 0; k < nj; ++k)
        E[i][j] += C[i][k] * D[k][j];
    }

这些变化是否会使您的并行实现比顺序实现更快？很难说。这取决于您的问题大小。并行化(特别是通过 OpenMP 的并行化)会带来一些开销。只有产生足够多的并行工作，通过并行线程分配工作的 yield 才会超过产生的间接费用。

要了解您的代码和您的软件/硬件平台需要多少工作量，我建议通过使用不同的矩阵大小运行您的代码来进行试验。然后，如果您还希望将“太”小的矩阵大小作为计算的输入，您可能希望使并行处理成为条件(例如，通过使用 if 子句修饰循环编译指示):

#pragma omp parallel for private (j, k) if(ni * nj * nk > THRESHOLD)
  for (i = 0; i < ni; i++) {
     ...
  }
#pragma omp parallel for private (j, k) if(ni * nl * nj > THRESHOLD)
  for (i = 0; i < ni; i++) {
    ...
  }