免责声明:以下示例只是一个用于快速理解问题的虚拟示例。如果您正在考虑现实世界的问题,请考虑任何动态规划。
问题: 我们有一个 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 中的并行化:不值得。
为什么?
内循环中的操作很简单。代码是用-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://bisqwit.iki.fi/story/howto/openmp/
由于外部循环无法并行化(没有 ordered
选项),看起来没有办法使用 OpenMP 显着提高相关程序的性能。如果有人觉得我做错了什么,并且有可能,我会很高兴看到并测试解决方案。
关于c - 嵌套循环、内循环并行化、重用线程,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27342408/