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

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

问题：我们有一个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; 

Answer 1

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

为什么？ 内循环中的操作很简单。 代码是用-O3编译的，所以max()调用可能用函数体的代码代替。 隐式屏障的开销可能足够高，以补偿性能增益，并且总体开销足够高，使得并行代码甚至比顺序代码更慢。 我也发现，这种结构没有真正的性能提升：

 #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 ： libgomp

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