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)。这肯定会使您的代码比您预期的要慢一些，即您的循环不是“令人尴尬地”（或“令人愉快地”）并行和并行循环迭代需要以某种方式从共享内存访问这些变量。

更糟糕的是，因此，您的代码包含竞争条件。因此，它的行为将是不确定的。换句话说：你的并行矩阵乘法实现现在是不正确的！（继续检查您的计算结果。;））

您要做的是确保外循环的所有迭代都有自己的索引变量j和k. 您可以通过在并行循环的范围内声明这些变量来实现这一点：

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 的并行化）会带来一些开销。只有当您产生足够多的并行工作时，通过并行线程分配工作的收益才会超过产生的开销成本。

为了找出代码和软件/硬件平台需要多少工作量，我建议通过运行不同矩阵大小的代码进行试验。然后，如果您还期望“太”小的矩阵大小作为计算的输入，您可能希望并行处理有条件（例如，通过使用if-clauses装饰您的循环编译指示）：

#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++) {
    ...
  }