[ C 文章收集 ] 簡易的程式平行化－OpenMP（二）語法說明

來源自 這裡 
Preface: 
之前對於多執行緒和 OpenMP 的平行化已經做了些簡單的介紹，有興趣的可以回頭參考《簡易的程式平行化方法－OpenMP（一）》。而由於最近看了些資料，也做了些測試，所以主要可能想來講最近學的一些語法吧. 

OpenMP Syntax: 

* Directives: 提供指示詞中 OpenMP API 所使用的連結。(msdn)
* Clauses: 提供連結 OpenMP API 中所使用的子句 (msdn)
* Functions: 提供用於 OpenMP API 函式的連結. (msdn)

而 function 的部份是獨立呼叫的，其實在一般的情況下，似乎不大會用到。而 directive 和 clause 的用法，大致上應該是: 

#pragma omp directive-name [ clause [[[,] clause] .. ]

的形式。像之前 #pragma omp parallel for，實際上 parallel 和 for 都是 directive；所以語法實際上可以拆開成 #pragma omp parallel 和 #pragma omp for 兩行。也就是: 

view plaincopy to clipboardprint?

1. #pragma omp parallel for  
2. for( int i = 0; i < 10; ++ i )  
3.   Test( i );  

實際上是: 

view plaincopy to clipboardprint?

1. #pragma omp parallel  
2. {  
3.   #pragma omp for  
4.   for( int i = 0; i < 10; ++ i )  
5.    Test( i );  
6. }  

所形成的。而 OpenMP 的 directive 列表如下: 
 

其中，要拿來平行化，是使用 parallel、sections、for 這三項；而要指定使用單一執行緒，則是特過 master、single、crigical 這三項。barrier 則是拿來控制執行緒同步用的；ordered 是用來設定平行化的執行順序。atomic、flush、threadprivate 則應該都是用來控制變數的. 

而 clause 的部份，則有下列 13 個: 
 

而在 clause 的中，copyin、copyprivate、default、shared、private、firstprivate、lastprivate、reduction 這 8 項，都是用來控制變數在平行化時的處理方法的。ordered 和schedule 是控制平行化時的執行順序分配方法；num_threads、if 則比較像是控制執行緒的設定. 

而在 Function 的部份，MSDN 列了二十來個 function；有興趣的可以直接去參考 MSDN 上或是 OpenMP tutorial 上面的說明, 這裡就不一一列出. 雖然一般可能用不到，但是在測試的時候，為了驗正執行的順序、多執行緒的關係，有時候必須要知道線在是由哪個執行緒在跑的～這時候，可以透過 omp_get_thread_num() 這個函式，來取得目前執行緒的編號已進行除錯. 

Supplement: 
* 簡易的程式平行化方法－OpenMP（一）簡介 
* 簡易的程式平行化－OpenMP（二）語法說明 
* 簡易的程式平行化－OpenMP（三）範例 parallel、section 
* 簡易的程式平行化－OpenMP（四） 範例 for 
* 簡易的程式平行化－OpenMP（五） 變數的平行化 
* 簡易的程式平行化－OpenMP clause "private" 使用時機

[ 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

[Linux 文章收集] 將 Tab 轉換成 Space

來源自 這裡 
Preface: 
為了統一 Windows 跟 Linux 底下的編輯器在使用 Tab 功能相同，所以調整了 Vim 及 Pspad (我常用編輯器)的設定，底下是針對 Vim 及 Pspad 的解決方法。 

How: 
首先當大家使用 Vim 編輯器撰寫程式，常常會使用 Tab 來縮排程式碼，我們可以使用 expandtab 來插入空白鍵(Space)取代 Tab: 

# vi 某個檔案時
:set expandtab

控制插入 Tab 時所需要的空白鍵(Tab)字元數，例如用4個空白鍵取代 Tab: 

:set tabstop=4

在我們設定完 expandtab 之後，所有的 Tab 鍵將會被 Space 所取代，但是原本在檔案文件中的 Tab 將不會改變，為了取代原有的 Tab 到新的設定，我們必須鍵入: 

:retab

針對程式縮排所需要的 Space 個數，我們可以使用 shiftwidth 選項: 

:set shiftwidth=4

底下舉個例子: 

* 將文件中 Tab 取代成 Space
* 所有 Tab 用4個 Space 取代

對應的設定為: 

:set tabstop=4
:set shiftwidth=4
:set expandtab

如果你希望設定是永久的, 可以考慮將上述設定寫到 ~/.vimrc 中. (此時 ":" 不需要 ^^")