2014年3月7日 星期五

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

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

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...