通过分离#omp parallel和#omp for来减少OpenMP fork/join开销

Question

我正在阅读Peter S. Pacheco 对并行编程的介绍.在5.6.2节中,它提供了一个关于减少fork/join开销的有趣讨论.考虑奇偶换位排序算法:

for(phase=0; phase < n; phase++){
    if(phase is even){
#       pragma omp parallel for default(none) shared(n) private(i)
        for(i=1; i<n; i+=2){//meat}
    }
    else{
#       pragma omp parallel for default(none) shared(n) private(i)
        for(i=1; i<n-1; i+=2){//meat}
    }
}

作者认为上面的代码有一些高的fork/join开销.因为线程在外循环的每次迭代中分叉并连接.因此,他提出以下版本:

# pragma omp parallel default(none) shared(n) private(i, phase)
for(phase=0; phase < n; phase++){
    if(phase is even){
#       pragma omp for
        for(i=1; i<n; i+=2){//meat}
    }
    else{
#       pragma omp for
        for(i=1; i<n-1; i+=2){//meat}
    }
}

根据作者的说法,第二个版本在外部循环开始之前分叉线程,并为每次迭代重用线程,从而产生更好的性能.

但是,我怀疑第二个版本的正确性.在我的理解中,#pragma omp parallel指令启动一组线程并让线程并行执行以下结构化块.在这种情况下,结构化块应该是整个外部for循环for(phase=0 ...).那么,在使用4个线程的情况下,不应该是整个外环执行四次的情况吗？也就是说,如果n=10,那么将在4个线程上执行40次迭代.我的理解有什么问题？那个omp parallel(没有)如何玩上面的跟循环？

Answer 1

第二个版本是正确的.

根据OpenMP规范,#pragma omp parallel for指令只是#pragma omp parallel紧跟其后的快捷方式#pragma omp for,如

#pragma omp parallel
{
    #pragma omp for
    for(int i=0; i<N; ++i) { /*loop body*/ }
}

如果在循环结构之前或之后并行区域中存在某些代码,则它将由区域中的每个线程独立执行(除非受其他OpenMP指令限制).但是,#pragma omp for是一种工作共享结构 ; 该指令后面的循环由该区域中的所有线程共享.即它作为单个循环执行,迭代以某种方式分割在线程上.因此,如果上面的并行区域由4个线程执行,则循环将仅执行一次,而不是4次.

回到你的问题中的例子:相位循环由每个线程单独执行,但#pragma omp for在每个阶段迭代表示共享循环的开始.对于n = 10,每个线程将进入共享循环10次,并执行其中的一部分; 因此内循环不会有40次执行,而只有10次执行.

注意最后有一个隐含的障碍#pragma omp for; 它意味着一个完成其共享循环部分的线程将不会继续,直到所有其他线程也完成它们的部分.因此,执行跨线程同步.这对于确保大多数情况下的正确性是必要的; 例如,在您的示例中,这可以保证线程始终在同一阶段工作.但是,如果区域内的后续共享循环可以安全地同时执行,nowait则可以使用子句来消除隐式屏障,并允许线程立即进入并行区域的其余部分.

另请注意,此类工作共享指令的处理对OpenMP非常具体.对于其他并行编程框架,您在问题中使用的逻辑可能是正确的.

最后,智能OpenMP实现在并行区域完成后不会连接线程; 相反,线程可能忙 - 等待一段时间,然后睡眠直到另一个并行区域启动.这样做完全是为了防止并行区域的开始和结束时的高开销.因此,尽管书中提出的优化仍然消除了一些开销(可能),但对于某些算法,它对执行时间的影响可能微不足道.问题中的算法很可能是其中之一; 在第一个实现中,并行区域在串行循环中一个接一个地快速跟随,因此OpenMP工作线程很可能在区域的开头处处于活动状态并将快速启动,从而避免了fork/join开销.因此,如果在实践中您发现与所描述的优化没有性能差异,请不要感到惊讶.