考虑奇偶换位排序算法：
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指令启动一组线程,让线程并行执行以下结构化块.在这种情况下,结构化块应该是(phase = 0 …)的整个外部for循环.那么,在使用4个线程的情况下,不应该是整个外环执行四次的情况吗？也就是说,如果n = 10,那么将在4个线程上执行40次迭代.我的理解有什么问题？ omp如何与上面的for循环并行(没有for)？
解决方法
根据OpenMP规范,#pragma omp parallel for directive只是#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 each phase iteration指示共享循环的开始.对于n = 10,每个线程将进入共享循环10次,并执行其中的一部分;因此内循环不会有40次执行,而只有10次执行.
注意#pragma omp末尾有一个隐含的障碍;它意味着一个完成其共享循环部分的线程将不会继续,直到所有其他线程也完成它们的部分.因此,执行跨线程同步.这对于确保大多数情况下的正确性是必要的;例如在您的示例中,这可以保证线程始终在同一阶段工作.但是,如果区域内的后续共享循环可以安全地同时执行,则可以使用nowait子句来消除隐式屏障,并允许线程立即进入并行区域的其余部分.
另请注意,此类工作共享指令的处理对OpenMP非常具体.对于其他并行编程框架,您在问题中使用的逻辑可能是正确的.
最后,智能OpenMP实现在并行区域完成后不会连接线程;相反,线程可能忙 – 等待一段时间,然后睡眠直到另一个并行区域启动.这样做完全是为了防止并行区域的开始和结束时的高开销.因此,尽管书中提出的优化仍然消除了一些开销(可能),但对于某些算法,它对执行时间的影响可能微不足道.问题中的算法很可能是其中之一;在第一个实现中,并行区域在串行循环中一个接一个地快速跟随,因此OpenMP工作线程很可能在区域的开头处处于活动状态并将快速启动,从而避免了fork / join开销.因此,如果在实践中您发现与所描述的优化没有性能差异,请不要感到惊讶.
