OpenMP

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 的线程管理是如何工作的。我想防止在每次迭代期间对线程进行不必要的初始化，因此我在外部循环周围放置了一个外部并行块。

第二种方法：

#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;
            }
        }
     }
}

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

现在奇怪的是：第二种方法比第一种方法更快！

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

起初我在想："well yeah, it's probably because of thread management" 但后来我读到 OpenMP 池化了实例化线程，这与我的假设背道而驰。然后我禁用了编译器优化（编译器标志 -O0）以检查它是否与此有关。但这并不影响测量。

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

解决背包问题的测量时间包含 7500 件物品，最大容量为 45000（创建 7500x45000 的矩阵，这超过了代码中使用的 THRESHOLD 变量):

方法 1：~0.88s
方法二：~0.52s

提前致谢，

phineliner

编辑:

更复杂问题的测量：问题增加了2500条（从7500条增加到10000条）（更复杂的问题目前由于内存原因无法处理）

方法一：~1.19s
方法 2：~0.71s

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

Answer 1

我认为原因很简单，因为您将 #pragma omp parallel 置于外部范围级别（第二个版本），调用线程的开销较少。

~~换句话说，在第一个版本中，您在第一个循环中调用线程创建 itemRows 次，而在第二个版本中，您只调用一次创建。~~ 而且我不知道为什么！

我尝试重现一个简单的示例来说明这一点，使用 4 个线程并启用 HT：

#include <iostream>
#include <vector>
#include <algorithm>
#include <omp.h>

int main()
{
    std::vector<double> v(10000);
    std::generate(v.begin(),  v.end(), []() { static double n{0.0}; return n ++;} );

    double start = omp_get_wtime();

    #pragma omp parallel // version 2
    for (auto& el :  v) 
    {
        double t = el - 1.0;
        // #pragma omp parallel // version 1
        #pragma omp for
        for (size_t i = 0; i < v.size(); i ++)
        {
            el += v[i];
            el-= t;
        }
    }
    double end = omp_get_wtime();

    std::cout << "   wall time : " << end - start << std::endl;
    // for (const auto& el :  v) { std::cout << el << ";"; }

}

Comment/uncomment根据你要的版本。如果你编译：-std=c++11 -fopenmp -O2 你应该看到版本 2 更快。

Coliru 演示

Live Version 1 wall time : 0.512144

Live version 2 wall time : 0.333664

Answer 2

让我们首先考虑一下您的代码在做什么。本质上，您的代码是 t运行s 形成一个矩阵（二维数组），其中行的值取决于前一行，但列的值独立于其他列。让我选择一个更简单的例子

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 次迭代，但只有 j 的 n/nthreads 次迭代。这有效地并行处理了列条带。但是，这种方法对缓存非常不友好。

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

方法二：

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 一样，每个线程运行遍历 n-1 次迭代 i。但是，此方法在内部循环之后有一个隐式屏障，这会导致每个线程暂停，直到所有线程都完成一行，使此方法对每一行都是顺序的，就像方法 2 一样。

最好的解决方案是像方法 1 一样并行处理列条带，但仍然对缓存友好。这可以使用 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 都并行处理一行中的列，但按顺序处理行，因此人们可能期望它们的时间相同。那么它们为什么不同呢？让我做一些观察：

由于线程池的原因，方法 2 的外循环的每次迭代都不会创建和销毁线程，所以我不清楚额外的开销是多少。请注意，OpenMP 没有提及线程池。这是每个编译器实现的东西。
方法 3 和方法 2 之间唯一的其他区别是，在方法 2 中，只有主线程处理 i，而在方法 3 中，每个线程处理一个私有线程 i。但这对我来说似乎太微不足道了，无法解释这些方法之间的显着差异，因为方法 3 中的隐式屏障导致它们无论如何都会同步，并且处理 i 是一个增量和条件测试的问题。
事实上，方法 3 并不比方法 4 慢，方法 4 并行处理整个列条带，这表明方法 2 中的额外开销全部在于为 [ 的每次迭代离开和进入并行区域=17=]

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

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

OpenMP - Nested for-loop becomes faster when having parallel before outer loop. Why?

c++

for-loop

nested

knapsack-problem