嵌套循环、内循环并行化、重用线程

免责声明：以下示例只是一个快速理解问题的虚拟示例。如果您正在考虑现实世界的问题，请考虑任何动态编程。

问题：我们有一个 n*m 矩阵，我们想要复制前一行的元素，如以下代码所示：

for (i = 1; i < n; i++)
    for (j = 0; j < m; j++)
        x[i][j] = x[i-1][j];

方法：外循环迭代必须按顺序执行，它们将按顺序执行。 内循环可以并行化。我们希望最大限度地减少创建和终止线程的开销，因此我们希望只创建一次线程组，但是，这在 OpenMP 中似乎是一项不可能完成的任务。

#pragma omp parallel private(j)
{
   for (i = 1; i < n; i++)
   {   
      #pragma omp for scheduled(dynamic)
      for (j = 0; j < m; j++)
         x[i][j] = x[i-1][j];
   }
}

当我们申请时ordered外循环上的选项，代码将以顺序方式执行，因此不会有性能增益。 我正在寻找上述场景的解决方案，即使我不得不使用一些解决方法。

我正在添加我的实际代码。这实际上比 seq 慢。版本。请查阅：

/* load input */
for (i = 1; i <= n; i++)
    scanf ("%d %d", &in[i][W], &in[i][V]);

/* init */
for (i = 0; i <= wc; i++)
    a[0][i] = 0;

/* compute */
#pragma omp parallel private(i,w)
{
    for(i = 1; i <= n; ++i) // 1 000 000
    {
        j=i%2;
        jn = j == 1 ? 0 : 1;

        #pragma omp for
        for(w = 0; w <= in[i][W]; w++) // 1000
            a[j][w] = a[jn][w];

        #pragma omp for
        for(w = in[i][W]+1; w <= wc; w++) // 350 000
            a[j][w] = max(a[jn][w], in[i][V] + a[jn][w-in[i][W]]);
    }
}

至于测量，我正在使用这样的东西：

double t;
t = omp_get_wtime();
// ...
t = omp_get_wtime() - t;

总结一下 OpenMP 中针对这种特殊情况的并行化：不值得。

Why?内循环的操作很简单。代码编译为-O3, so max()call 可能被函数体的代码替换。 隐式屏障的开销可能足够高，以补偿性能增益，并且总体开销足够高，使得并行代码甚至比顺序代码更慢。 我还发现，这种构造没有真正的性能提升：

#pragma omp parallel private(i,j)
{ 
   for (i = 1; i < n; i++)
   {   
      #pragma omp for
      for (j = 0; j < m; j++)
         x[i][j] = x[i-1][j];
   }
}

因为它的性能和这个类似

for (i = 1; i < n; i++)
{   
   #pragma omp parallel for private(j)
   for (j = 0; j < m; j++)
      x[i][j] = x[i-1][j];
}

感谢 GCC 中的内置线程重用libgomp，根据这篇文章：http://bisqwit.iki.fi/story/howto/openmp/ http://bisqwit.iki.fi/story/howto/openmp/

由于外循环无法并行化（没有ordered选项）看起来没有办法使用 OpenMP 显着提高相关程序的性能。如果有人觉得我做错了什么，而且这是可能的，我会很高兴看到并测试解决方案。