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

第二种方法：

#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是可用核心数。我已经尝试使用pragma single和critical来强制外层for循环在一个线程中执行，但这样我就无法通过多个线程计算内部循环，除非我打开一个新的并行块（但那样速度并没有提升）。但不要紧，因为好的消息是：这不影响结果。问题仍然被正确解决。

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

这怎么可能？我的意思是，虽然外部for循环在n次（并行）中计算，内部for循环在n个核心中分别分配n次，但它比第一种方法更快，第一种方法只计算了外部循环一次，并均匀分配内部for循环的工作负载。

起初我想：“嗯，这可能是由于线程管理”，但后来我读到OpenMP池化实例化的线程，这与我的假设相违背。然后我禁用编译器优化（编译器标志-O0）以检查是否与其有关。但是这并没有影响测量。

请问有人能否对此提供更多的见解？

解决包含7500个项目且最大容量为45000的背包问题所需的测量时间（创建一个7500x45000的矩阵，这远远超过了代码中使用的THRESHOLD变量）：

• 方法1：约0.88秒
• 方法2：约0.52秒

预先感谢您的帮助，

phineliner

编辑：

更复杂问题的测量： 将2500个项目添加到问题中（从7500到10000）（目前由于内存原因无法处理更复杂的问题）。

• 方法1：约1.19秒
• 方法2：约0.71秒

编辑2： 我对编译器优化产生了误解。这不会影响测量。至少我不能再次验证我之前测量到的差异。我根据此编辑了问题文本。

- phineliner

---

THRESHOLD 是如何定义的？编译器似乎能够通过优化标志以某种方式简化代码。也许你应该看一下生成的汇编代码？ - coincoin

感谢您的回复。THRESHOLD目前只是一个虚拟设置为5000，但由于问题的最大容量为45000，它在这里并不起作用。THRESHOLD背后的想法是防止对非常小的问题进行并行化，因为实例化线程所需的时间比顺序解决问题的时间更长。是的，您是正确的，查看汇编代码将是下一步，但也许这里有一些OpenMP大师可以提供帮助？ - phineliner

在您的第一种方法中，内部循环中的每个线程都必须等待主线程完成其工作。在第二种方法中，每个线程都自己完成外部工作，不必等待主线程。在第一种方法中，主线程无论如何都必须等待内部循环中最慢的线程才能完成其工作。 - Z boson

如果你使用 #pragma omp for nowait 会发生什么？ - Z boson

@phineliner，“nowait” 只应该在第二次尝试时有所帮助。它不应该减少两次尝试之间的差异，而应该相反。 - Z boson

Answer 1

首先，让我们考虑一下您的代码在做什么。实际上，您的代码正在转换一个矩阵（2D数组），其中行的值取决于前一行的值，但列的值与其他列无关。让我选择一个更简单的例子来说明。

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

将循环交换的一种并行化方法如下：

方法 1：

#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迭代。这有效地并行处理列条带。然而，这种方法在缓存方面非常不友好。

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

方法2：

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的值仅由主线程运行。

另一种按顺序处理行的并行处理列的方法是：

方法3：

#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一样，并且仍然是缓存友好的。这可以通过使用nowait子句来实现。

方法4：

#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. 由于线程池，线程不会在每次外部循环迭代时被创建和销毁，因此我不清楚额外开销是什么。请注意，OpenMP没有提及线程池。这是每个编译器实现的事情。

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

3. 方法3不比并行处理整个列条的方法4慢，这表明方法2中的额外开销全部在离开和进入每次i迭代的并行区域中。

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

- Z boson

---

非常感谢您详细、清晰且易懂的回答。解释2听起来很有道理。然而，您可能是对的，这不可能是方法3比方法2快得多的唯一原因。另一个想法浮现：也许方法3从提前分配均匀负载中获益，而不是在方法2的每次迭代中再次分配负载？这可能吗？ - phineliner

@phineliner，我不确定如何为解释2制作测试。我可以使i共享，并且仅在单个区域中递增它，但是每个线程仍然必须执行检查i<n的测试。这部分类似于方法2。我想我应该检查一下。但是我的猜测是，在每个并行区域之后，线程池必须重新启动（但不是重新创建）空闲线程并向其发送新参数。使用方法3，它不必这样做。它只需要查看每个线程是否完成即可。 - Z boson

非常有趣的回答。为什么OpenMP实现没有提到线程池？编译器应该在某个地方提供这种信息，不是吗？ - coincoin

@coincoin，这个问题让我受益匪浅。OpenMP没有指定线程池的事实已经让我相信，在我的答案中，方法3或方法4是最佳解决方案。最好不要依赖未指定的功能。时间证明了这一点。编译器可能确实有一些文档可以参考。 - Z boson

@Zboson，你能再看一下你的回答吗？假设已经过去了5年，我想你可能有什么要补充的。就个人而言，我并不认为你的回答很有说服力，但我也花了很长时间研究OpenMP，却无法得出一个具体的结论。我想知道在过去的5年里，你是否遇到了新的信息，可以改变你的答案或者能够对其进行更多的补充。 - Ali

Answer 2

我认为简单的原因是，由于您将#pragma omp parallel放置在外部作用域级别（第二个版本），调用线程的开销较小。

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

我尝试使用启用HT的4个线程复制一个简单的示例来说明：

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

}

根据您想要的版本进行注释/取消注释。如果您使用以下编译：-std=c++11 -fopenmp -O2，您应该会发现第二个版本更快。

在Coliru上演示

版本1实时演示 Wall Time : 0.512144

版本2实时演示 Wall Time : 0.333664

- coincoin

---

谢谢您的回复。这正是我最初的想法，也是我实际实现第二种方法的原因。但我在某个地方读到OpenMP在池中管理线程，这意味着在每次迭代中访问它们不应该有任何问题。不幸的是，由于依赖关系，我无法并行化外部for循环。这将使结果失真。 - phineliner

在线程池中访问线程和创建线程之间是有区别的。请查看我编辑过的帖子，其中包含一个简单的示例。您应该会看到差异。 - coincoin

谢谢你的努力。我明白你想告诉我的意思。这就意味着，在每次使用parallel编译指示时，线程会再次创建，而不是从OpenMP内部的线程池中获取？我可以接受这一点。但是有一个负面影响，即在第二个版本中，外层循环将由每个核心计算（整个循环每次都要计算，而不是分布式工作负载！）见实例。我想使用一个线程通过外层循环（就像在第一个版本中一样）。 - phineliner

不，线程不会再次创建。它们在两个版本中都只创建一次。这就是线程池的目的。您可以使用Linux/Windows中的调用转储线程列表，并查看线程列表及其静态信息（除非您在另一个并行区域中显式更改线程数）。 - Z boson

你的答案还可以，因为你成功地使用另一个测试重现了OP的结果。这很有趣。我知道原因，但是我很难解释清楚。基本上，在第一种方法中，内部循环必须在外部循环的每次迭代中等待主线程。而在第二种方法中，每个线程不必等待主线程。 - Z boson