multithreading - 通过分离#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 开销。因为线程在外循环的每次迭代中都被 fork 并加入。因此，他提出以下版本:

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

根据作者的说法，第二个版本在外循环开始之前 fork 线程并在每次迭代中重用线程，从而产生更好的性能。

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

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是一个工作共享结构；该指令后面的循环由该区域中的所有线程共享。 IE。它作为单个循环执行，迭代以某种方式跨线程拆分。因此，如果上面的并行区域由 4 个线程执行，循环仍然只会执行一次，而不是 4 次。

回到您问题中的示例:相位循环由每个线程单独执行，但 #pragma omp for在每个阶段迭代指示共享循环的开始。对于n=10，每个线程将进入一个共享循环10次，并执行其中的一部分；所以不会有 40 次内部循环执行，而只有 10 次。

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

还要注意，这种工作共享指令的处理是 OpenMP 特有的。对于其他并行编程框架，您在问题中使用的逻辑可能是正确的。

最后，在并行区域完成后，智能 OpenMP 实现不会加入线程；相反，线程可能会忙等待一段时间，然后休眠直到另一个并行区域启动。这样做正是为了防止并行区域开始和结束时的高开销。因此，虽然书中建议的优化仍然消除了一些开销(也许)，但对于某些算法，它对执行时间的影响可能可以忽略不计。问题中的算法很可能是其中之一；在第一个实现中，并行区域在串行循环中一个接一个地快速跟随，因此 OpenMP 工作线程很可能会在区域的开头处于事件状态并快速启动，从而避免 fork/join 开销。因此，如果在实践中您发现与所描述的优化没有性能差异，请不要感到惊讶。