OpenMP嵌套for，不等于num。的迭代

Question

我正在使用OpenMP来并行化循环。在正常情况下，应当使用：

#pragma omp for schedule(static, N_CHUNK) 
for(int i = 0; i < N; i++) { 
    // ... 
} 

对于嵌套的循环，我可以把pragma在内部或outter循环

#pragma omp for schedule(static, N_CHUNK) // can be here... 
for(int i = 0; i < N; i++) { 
#pragma omp for schedule(static, N_CHUNK) // or here... 
    for(int k = 0; k < N; k++) { 
    // both loops have consant number of iterations 
    // ... 
    } 
} 

但是！我有两个回路，其中在第二循环迭代的数量取决于第一环：

for(int i = 0; i < N; i++) { 
    for(int k = i; k < N; k++) { 
    // k starts from i, not from 0... 
    } 
} 

什么是平衡的CPU使用这种循环的最佳方式？

Answer 1

一如往常：

• 这取决于
• 轮廓。
• 在这种情况下：又见OMP_NESTED environment variable

是要赚取差价的事情在这里不被显示：

• （非）线性存储器寻址（还看的顺序循环
• 共享变量的使用;

至于你的最后一个场景：

for(int i = 0; i < N; i++) { 
    for(int k = i; k < N; k++) { 
    // k starts from i, not from 0... 
    } 
} 

我建议并行外环有以下原因：

• 所有其他的事情都是平等的粗粒度并行化通常会导致更好的性能，因为

  • 增加缓存局部性
  • 需要锁定的频率降低 （请注意，这取决于假设关于我无法真正做到的循环内容;我使其基于我的/常用的/并行代码的经验）

• 内循环可能变得太短，是低效的并行（IOW：外环的范围内是可预测的，内循环没有那么，或者本身不适合于静态调度以及）

• 嵌套parallellism很少很好地扩展

Answer 2

sehe的点 - 尤其是“看情况”和“配置文件” - 非常的地步。

但是，通常情况下，只要外部循环足够大以保持所有内核忙碌，您就不会想要嵌套并行循环。另一个并行部分内部环路的额外开销可能比额外的小部分工作带来的收益成本更高。

解决此问题的常用方法是动态调度外部循环，以便每个循环迭代采用不同长度类型的事实不会导致负载平衡问题（因为i==N-1迭代几乎立即完成在i==0迭代需要永远）

​​

崩溃编译是实质上摆脱嵌套的非常有用的，是特别有价值的，如果外环小（例如，N < num_threads）：

#pragma omp parallel for default(none) shared(N) collapse(2) 
for(int i = 0; i < N; i++) { 
    for(int k = 0 ; k < N; k++) { 

    } 
} 

通过这种方式，两个循环被合并为一个，并且组块的数量更少，这意味着更少的开销。但在这种情况下，这不起作用，因为循环范围不是固定的;你不能collapse一个循环的边界改变（例如，与i）。