[ C 文章收集 ] 簡易的程式平行化－OpenMP clause "private" 使用時機

Preface:
在此我們已經都知道可以使用 #pragma parallel for 來對 for 迴圈進行平行化, 接著我們來看一個 2 兩層 for 迴圈的平行化:
- w1.c

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4.   
5. int gc=0;  
6.   
7. void Test(int n, int m)  
8. {  
9.     printf(" - %d, %d\n", omp_get_thread_num(), n, m);  
10.     gc++;  
11. }  
12.   
13. int main()  
14. {  
15.     int i=0, j=0;  
16.     #pragma omp parallel for  
17.     for(i=0; i<8; i++)  
18.     {  
19.         for(j=0; j<3; j++) Test(i, j);  
20.     }  
21.     printf("gc=%d\n", gc);  
22. }  

直覺來猜變數 gc 的值應該是兩層 for 迴圈跑的次數相乘, 所以經該是 3x8=24. 但輸出結果卻不如預期. 一個範例的執行結果如下:

- 0, 0
- 0, 1
- 0, 2
...(中間省略)...
- 6, 1
- 6, 2
gc=18

Clause "private" Usage:
如果大家有修過 計算機結構, 應該知道一行指令如 a+=1, 當細化到組合語言時, 會有如下步驟:

Register < Var_a
Register < Register + 1
Var_a < Register

在只有一個 CPU 執行環境下執行當行時, 每行程式碼都是一行行按照順序執行 (因為程式碼是 sequence 執行, 所以對應的組碼都是以程式碼為單位執行); 但如果考慮到有多顆 CPU 且是以平行運算來執行程式碼時, 則同一行程式碼有可能同時被兩個 CPU 同時執行, 此時兩個 CPU 在執行組碼如果錯開執行, 就會發生恐怖的 Race condition. 首先來一個幸運的 case, 就是當兩個 CPU 執行同一個程式碼時, 其對應的組碼並沒有發生 Overlapping:


因為 a=8 時 a+=1 執行兩次應該是 10, 所以上面的結果是對的, 但是當組碼有 Overlapping 且又運氣不好時, 下面的結果就會造成非預期結果:


上面問題就發生在第二行, 當 CPU1 執行 Register = Register + 1 時, CPU2 緊接著執行 Register = Var_a, 導致 CPU1 的運算結果本來應該是 9, 卻被改成 8! 而事實上 Race condition 的狀況又不是 always 可以 reproduce 的, 因此要 debugging 此類的 bug 通常也是很費力... Orz.

回到我們上面的程式碼, 因為變數 i, j 定義在 #pragma parallel for 的外面, 因此當平行程式在執行時, 變數 i, j 會類似於 global variables. 而問題不是發生在第一層 loop, 而是第二層的 for loop 中的變數 j! 因為變數 j 同時被多個線程 (或 CPU) 讀寫, 導致上面解釋的狀況發生因而執行的整體 loop 次數不如預期. 要解這個問題有兩個發法.

一, 將有 Race condition 疑慮的變數定義到 #pragma parallel for 裡
簡單說就是將 global variable 變成 local variable, 這樣每個線程都有自己的變數 j, 如此便不會發生彼此改寫結果的問題:
- w1_f1.c

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4.   
5. int gc=0;  
6.   
7. void Test(int n, int m)  
8. {  
9.     printf(" - %d, %d\n", omp_get_thread_num(), n, m);  
10.     gc++;  
11. }  
12.   
13. int main()  
14. {  
15.     int i=0;  
16.     #pragma omp parallel for  
17.     for(i=0; i<8; i++)  
18.     {  
19.         int j;    
20.         for(j=0; j<3; j++) Test(i, j);  
21.     }  
22.     printf("gc=%d\n", gc);  
23. }  

二, 使用 OpenMP 的 private clause
第二個方法是使用 OpenMP 的 clause private 來告訴 OpenMP 那些變數應該是每個線程都應該有自己的一個位置儲存:
- w1_f2.c

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4.   
5. int gc=0;  
6.   
7. void Test(int n, int m)  
8. {  
9.     printf(" - %d, %d\n", omp_get_thread_num(), n, m);  
10.     gc++;  
11. }  
12.   
13. int main()  
14. {  
15.     int i=0, j=0;  
16.     #pragma omp parallel for private(j)  
17.     for(i=0; i<8; i++)  
18.     {  
19.         for(j=0; j<3; j++) Test(i, j);  
20.     }  
21.     printf("gc=%d\n", gc);  
22. }  

一個使用 gcc 編譯的 shell script 範例如下:
- w1.sh

view plaincopy to clipboardprint?

1. #!/bin/sh  
2. echo "Clearning..."  
3. test -f w1.out && rm -f w1.out  
4. test -f w1_f1.out && rm -f w1_f1.out  
5. test -f w1_f2.out && rm -f w1_f2.out  
6.   
7. echo "Compiling..."  
8. #gcc -std=c99 a.c -o a.out  
9. gcc -std=c99 -O1 -fopenmp w1.c -o w1.out  
10. gcc -std=c99 -O1 -fopenmp w1_f1.c -o w1_f1.out  
11. gcc -std=c99 -O1 -fopenmp w1_f2.c -o w1_f2.out  
12. echo "Running w1:"  
13. ./w1.out  
14. echo ""  
15. echo "Running w1 fix1:"  
16. ./w1_f1.out  
17. echo ""  
18. echo "Running w2 fix2:"  
19. ./w1_f2.out  

This message was edited 19 times. Last update was at 08/03/2014 12:51:42