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）。