c++ - OpenMP - 嵌套 for 循环在外部循环之前并行时变得更快。为什么？

Question

我目前正在实现一种解决背包问题的动态规划算法。因此我的代码有两个 for 循环，一个外循环和一个内循环。

从逻辑的角度来看，我可以并行化内部 for 循环，因为那里的计算彼此独立。由于依赖关系，外部 for 循环无法并行化。

所以这是我的第一种方法:

for(int i=1; i < itemRows; i++){
        int itemsIndex = i-1;
        int itemWeight = integerItems[itemsIndex].weight;
        int itemWorth = integerItems[itemsIndex].worth;

        #pragma omp parallel for if(weightColumns > THRESHOLD)
        for(int c=1; c < weightColumns; c++){
            if(c < itemWeight){
                table[i][c] = table[i-1][c];
            }else{
                int worthOfNotUsingItem = table[i-1][c];
                int worthOfUsingItem = itemWorth + table[i-1][c-itemWeight];
                table[i][c] = worthOfNotUsingItem < worthOfUsingItem ? worthOfUsingItem : worthOfNotUsingItem;
            }
        }
}

代码运行良好，算法正确解决了问题。 然后我在考虑优化它，因为我不确定 OpenMP 的线程管理是如何工作的。我想防止在每次迭代期间对线程进行不必要的初始化，因此我在外部循环周围放置了一个外部并行 block 。

第二种方法:

#pragma omp parallel if(weightColumns > THRESHOLD)
{
    for(int i=1; i < itemRows; i++){
        int itemsIndex = i-1;
        int itemWeight = integerItems[itemsIndex].weight;
        int itemWorth = integerItems[itemsIndex].worth;

        #pragma omp for
        for(int c=1; c < weightColumns; c++){
            if(c < itemWeight){
                table[i][c] = table[i-1][c];
            }else{
                int worthOfNotUsingItem = table[i-1][c];
                int worthOfUsingItem = itemWorth + table[i-1][c-itemWeight];
                table[i][c] = worthOfNotUsingItem < worthOfUsingItem ? worthOfUsingItem : worthOfNotUsingItem;
            }
        }
     }
}

这有一个不需要的副作用:并行 block 内的所有内容现在都将执行 n 次，其中 n 是可用内核的数量。我已经尝试使用 pragmas single 和 critical 来强制在一个线程中执行外部 for 循环，但是我无法通过多个线程计算内部循环除非我打开一个新的并行 block (但那样不会提高速度)。不过没关系，因为好处是:这不会影响结果。问题依然正确解决。

现在奇怪的是:第二种方法比第一种方法更快!

这怎么可能？我的意思是，尽管外部 for 循环计算了 n 次(并行)并且内部 for 循环在 n 个核心之间分布了 n 次，但它比第一种方法更快，后者只计算一次外部循环并将工作量分配给内部 for 循环均匀。

起初我在想:“嗯，是的，这可能是因为线程管理”，但后来我读到 OpenMP 池化了实例化线程，这与我的假设背道而驰。然后我禁用了编译器优化(编译器标志 -O0)以检查它是否与此有关。但这并不影响测量。

你们中的任何人都可以对此有更多的了解吗？

解决包含 7500 个元素且最大容量为 45000 的背包问题的测量时间(创建一个 7500x45000 的矩阵，这远远超过了代码中使用的 THRESHOLD 变量):

• 方法 1:~0.88s
• 方法 2:~0.52s

提前致谢

花花公子

编辑:

更复杂问题的度量: 向问题添加了 2500 个项目(从 7500 到 10000)(由于内存原因，目前无法处理更复杂的问题)。

• 方法 1:~1.19s
• 方法 2:~0.71s

编辑 2: 我误会了编译器优化。这不影响测量。至少我无法重现我之前测量的差异。我根据这个编辑了问题文本。

Answer 1

让我们首先考虑一下您的代码在做什么。本质上，您的代码正在转换一个矩阵(二维数组)，其中行的值取决于前一行，但列的值独立于其他列。让我选择一个更简单的例子

for(int i=1; i<n; i++) {
    for(int j=0; j<n; j++) {
        a[i*n+j] += a[(i-1)*n+j];
    }
}

并行化的一种方法是像这样交换循环

方法一:

#pragma omp parallel for
for(int j=0; j<n; j++) {
    for(int i=1; i<n; i++) {
        a[i*n+j] += a[(i-1)*n+j];
    }
}

使用此方法，每个线程运行内循环的 i 的所有 n-1 次迭代，但仅运行 的 n/nthreads 次迭代>j。这有效地并行处理了列 strip 。但是，这种方法对缓存非常不友好。

另一种可能性是只并行化内部循环。

方法二:

for(int i=1; i<n; i++) {
    #pragma omp parallel for 
    for(int j=0; j<n; j++) {
        a[i*n+j] += a[(i-1)*n+j];
    }
}

这实质上是并行处理单行中的列，但每一行都是按顺序处理的。 i 的值仅由主线程运行。

另一种并行处理列但按顺序处理每一行的方法是:

方法三:

#pragma omp parallel
for(int i=1; i<n; i++) {
    #pragma omp for
    for(int j=0; j<n; j++) {
        a[i*n+j] += a[(i-1)*n+j];
    }
}

在这种方法中，与方法 1 一样，每个线程在 i 上运行所有 n-1 迭代。但是，此方法在内部循环之后有一个隐式屏障，这会导致每个线程暂停，直到所有线程都完成一行，从而使此方法对每一行都是顺序的，就像方法 2 一样。

最好的解决方案是像方法 1 一样并行处理列 strip ，但仍然对缓存友好。这可以使用 nowait 子句来实现。

方法四:

#pragma omp parallel
for(int i=1; i<n; i++) {
    #pragma omp for nowait
    for(int j=0; j<n; j++) {
        a[i*n+j] += a[(i-1)*n+j];
    }
}

在我的测试中，nowait 子句没有太大区别。这可能是因为负载是均匀的(这就是为什么在这种情况下静态调度是理想的)。如果负载更少，甚至 nowait 可能会产生更大的不同。

以下是我的四核 IVB 系统 GCC 4.9.2 上 n=3000 的时间(以秒为单位):

method 1: 3.00
method 2: 0.26 
method 3: 0.21
method 4: 0.21

此测试可能受内存带宽限制，因此我本可以使用更多计算选择更好的情况，但差异仍然足够大。为了消除由于创建线程池而造成的偏差，我运行了其中一种方法，但没有先对其进行计时。

从时间上可以清楚地看出方法 1 是多么不缓存友好。很明显，方法 3 比方法 2 更快，而且 nowait 在这种情况下几乎没有影响。

由于方法 2 和方法 3 都并行处理一行中的列，但按顺序处理行，因此人们可能期望它们的时间相同。那么它们为什么不同呢？让我做一些观察:

1. 由于线程池的存在，不会为方法 2 的外循环的每次迭代创建和销毁线程，因此我不清楚额外的开销是多少。请注意，OpenMP 没有提及线程池。这是每个编译器实现的东西。

2. 方法 3 和方法 2 之间唯一的其他区别是在方法 2 中只有主线程处理 i 而在方法 3 中每个线程处理一个私有(private)的 i。但这对我来说似乎太微不足道了，无法解释这些方法之间的显着差异，因为方法 3 中的隐式屏障导致它们无论如何都会同步，并且处理 i 是一个增量和条件测试的问题。

3. 事实上，方法 3 并不比方法 4 慢，方法 4 并行处理整个列 strip ，这说明方法 2 中的额外开销全部在于 i< 的每次迭代离开和进入并行区域

所以我的结论是，要解释为什么方法 2 比方法 3 慢得多，需要查看线程池的实现。对于使用 pthreads 的 GCC，这可能可以通过创建线程池的玩具模型来解释，但我还没有足够的经验。