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.88s
• 方法2:~0.52s

提前致谢,

phineliner

编辑:

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

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

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

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

使用此方法,每个线程都运行内部循环的所有n-1迭代,i但只运行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类似,每个线程都会遍历所有n-1迭代i.但是,此方法在内部循环之后具有隐式屏障,导致每个线程暂停,直到所有线程完成一行,使得此方法对于每一行都是顺序的,如方法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,则可能会产生更大的差异.

以下是n=3000我的四核IVB系统GCC 4.9.2的秒数:

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

这个测试可能是内存带宽限制所以我可以选择更好的情况使用更多的计算,但不过差异非常大.为了消除由于创建线程池而产生的偏差,我运行了一种方法而没有先计时.

从时序中可以清楚地知道un-cache friendly方法1是如何进行的.同样清楚的是,方法3比方法2更快,nowait并且在这种情况下几乎没有效果.

由于方法2和方法3都并行处理一行中的列,但是顺序地处理行,因此可能期望它们的时序相同.那他们为什么不同呢？让我提一些意见:

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

2. 方法3和方法2之间的唯一区别是在方法2中只有主线程处理,i而在方法3中,每个线程处理私有i.但这对于我来说解释方法之间的显着差异似乎太过于平凡,因为方法3中的隐式障碍导致它们无论如何都要同步,处理i是增量和条件测试的问题.

3. 方法3并不慢于并行处理整个色谱柱的方法4这一事实表明,方法2中的额外开销全部都在离开并进入每个迭代的并行区域. i

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