簡易的程式平行化-OpenMP(五) 變數的平行化

本文原發表於:http://heresy.spaces.live.com/blog/cns!E0070FB8ECF9015F!1286.entry


在將程式平行化的時候,其實還可能碰到一些問題。其中一個最大、最有可能碰到的,就是平行化後,每個執行緒裡的變數的獨立與否。下面是一個簡單的兩層迴圈的程式:

#pragma omp parallel for
for( int i = 0; i < 3; i )
for( int j = 0; j < 3; j )
Test2( i, j );

而裡面的函式 Test2 內容如下

void Test2( int n, int m )
{
printf( "<T:%d> - %d, %d
", omp_get_thread_num(), n, m );
}

輸出的形式會是:<T:thread_id> – n, m。這樣的寫法,執行結果是

<T:0> - 0, 0
<T:1> - 2, 0
<T:0> - 0, 1
<T:1> - 2, 1
<T:0> - 0, 2
<T:1> - 2, 2
<T:0> - 1, 0
<T:0> - 1, 1
<T:0> - 1, 2

這樣看起來是是沒問題的。但是如果把程式改成

int	i,	j;
#pragma omp parallel for
for( i = 0; i < 3; i )
for( j = 0; j < 3; j )
Test2( i, j );

的話,執行結果可能就會變成

<T:0> - 0, 0
<T:1> - 2, 0
<T:0> - 0, 1
<T:1> - 2, 2
<T:0> - 1, 0
<T:1> - 2, 1
<T:0> - 1, 2

哪裡有問題呢?最直接的問題,3×3 迴圈應該要跑九次 Test(),但是他只跑了 7 次。原因就是 OpenMP 會把在 parallel 的範圍以外宣告的變數,當成是所有執行緒共用的;所以在執行的時候,兩個執行續可能會同時修改到相同的 j,導致迴圈執行的次數比預期的少。

而解決的方法,就是透過 OpenMP 的 private(詳見 MSDN),來讓每個執行緒對變數 j 有各自的副本;寫法如下:

int	i,	j;
#pragma omp parallel for private( j )
for( i = 0; i < 3; i )
for( j = 0; j < 3; j )
Test2( i, j );

這樣寫的話,就可以得到正確的結果了∼同樣的情形,也會發生在使用 sections 的時候,所以在使用 OpenMP 平行化的時候,要注意有沒有將平行化範圍外的變數拿來在各個不同的執行緒使用。

而相對於 private,OpenMP 有另一個 clause 是 shared,他是用來讓所有執行緒共用變數的語法;不過在一般時候,應該是不需要特別去指定 shared,因為預設值就已經是了∼

而在 privateshare 的設定,OpenMP 還有提供一個 clause 叫做 default(詳見 MSDN)。他的功用,就是指定預設的範圍外變數配置方法;值可以是 sharednone。OpenMP 的預設值就是 shared,在沒有修改或另外指定的情況下,所有的範圍外變數都會以共享的方式來配置。而如果指定成 none 的話,則必需替所有範圍外變數指定配置的方法,否則在編譯的時候就會失敗。例如下面的程式:

int	X;
#pragma omp parallel default(none)
{
#pragma omp for
for( int i = 0; i < 4; i )
for( X = 0; X < 4; X )
Test2( i, X );
}

由於程式中的 X 是在 #pragma omp parallel 的範圍外,而又指定了 default(none),所以在沒有指定變數 X 的情況下,編譯器會出現錯誤訊息。這樣的好處就是可以避免應該指定成 private 卻沒有指定的情形;缺點就是,要額外指定 shared。而修改成下面的形式,就可以編譯、執行了。

int	X;
#pragma omp parallel default(none)
{
#pragma omp for private( X )
for( int i = 0; i < 2; i )
for( X = 0; X < 2; X )
Test2( i, X );
}

而除了 private 外,還有兩個類似的用法,分別是 firstprivatelastprivate。其中,firstprivate (詳見 MSDN)除了有 private 的功能外,還會將各執行緒的 private 變數,設定為執行緒開始前的變數值(透過 copy constructor);而 lastprivate (詳見 MSDN)則是會將變數在執行緒最後的值,寫回主執行緒(透過 assignment constructor)。下面是一個 firstpricate 的例子:

cA	A;
A.counter = 0;
#pragma omp parallel for
for( int i = 0; i < 4; i )
A.Output();
A.Output();

其中,Class cA 的定義是:

class cA
{
public:
int counter;

void Output()
{
counter;
printf( "%d (T:%d)
", counter, omp_get_thread_num() );
}
};

這樣的程式,A 這個變數會是 shared 的,所以結果會是

1 (T:0)
2 (T:1)
3 (T:0)
4 (T:1)
5 (T:0)

而如果將 #pragma omp parallel for 修改為 #pragma omp parallel for private(A),結果則變成:

-858993459 (T:0)
-858993459 (T:1)
-858993458 (T:0)
-858993458 (T:1)
1 (T:0)

這是因為 private(A) 會讓各執行緒擁有一份變數 A 的複本,但是卻不會替他指定起始值所造成的;而在 for 迴圈結束後,所有由 OpenMP 產生的複本將被自動的釋放,而改用回原來開始平行化前的變數 A(姑且稱他為正本好了∼),所以輸出的值依然是 1(因為在平行化過程中,修改的都是複本裡的資料)。

而如果將 #pragma omp parallel for private(A) 修改為 #pragma omp parallel for firstprivate(A),結果則變成:

1 (T:0)
1 (T:1)
2 (T:0)
2 (T:1)
1 (T:0)

在平行化開始、變數 A 開始建立複本的時候,OpenMP 會自動賦予各複本和正本一樣起始值,也就是 A.counter 的值會是 0;而接著各執行緒會各自以自己的複本做運算,所以兩個執行緒都輸出 1, 2。而在迴圈結束後,和使用 private 一樣,所有 A 的複本會被釋放,重新開始使用沒被修改過的正本 A

而如果再將 firstprivate(A) 修改為 lastprivate(A),結果則變成:

-858993459 (T:0)
-858993459 (T:1)
-858993458 (T:0)
-858993458 (T:1)
-858993457 (T:0)

由於 lastprivate(A)private(A) 一樣,不會賦予變數 A 複本起始值,所以在迴圈中的數值會和使用 private(A) 時一樣不如預期;不過不同的是, lastprivate 會把最後的結果寫回正本,所以在迴圈結束後,正本 A 的值也變成最後結束的執行緒中複本 A 的值。

firstprivatelastprivate 似乎也可以同時使用,也就是寫成 #pragma omp parallel for firstprivate(A) lastprivate(A);其結果如下:

1 (T:0)
1 (T:1)
2 (T:0)
2 (T:1)
3 (T:0)

還有一點要注意的,就是在使用 shared 的變數的時候,如果有可能會有「多個執行緒同時修改同一個變數」的情形發生,那可能會讓程式結果有問題!(似乎是叫做「race conditions」?)比如說下面的程式:

int	sum = 0;
#pragma omp parallel
{
#pragma omp for
for( int i = 0; i < 10000; i )
for( int j = 0; j < 50000; j )
sum = x;
}
printf( "%d
",sum );

很直接的想法,結果應該會是 10,000 * 50,000 = 500,000,000 吧?但是 Heresy 實際跑的結果,輸出的值卻不是固定的,而是大約在 300,000,000 左右;這就是因為同時修改變數 sum 所造成的結果。而要避免這種情況,可以使用 atomic 這個 directive(詳見 MSDN);他的用處就是用來防止變數同時被多個執行緒修改。修改後的程式如下:

int	sum = 0;
#pragma omp parallel
{
#pragma omp for
for( int i = 0; i < 10000; i )
for( int j = 0; j < 50000; j )
#pragma omp atomic
sum = x;
}
printf( "%d
",sum );

而這樣執行的結果,就會是正確的值了∼不過相對起來,為了避免同時修改的問題,執行上的速度也慢了不少;本來的程式只要 6000ms 左右就可以執行完成,而加入了 atomic 後,卻需要用到 17000ms 左右的時間。此外,atomic 也不是在所有情形都能用,限制也相當的多;一般來說,只可以用在 、–、 =、-=…這一類的運算元。

而在這個例子中,除了用 atomic 犧牲效率來避免這個問題,也可以使用另一個位這種情形設計的 clause:reduction(詳見 MSDN)。reduction 的使用形式是:

reduction( 運算元 : 變數 )

原則上,它支援的運算元有 , *, -, &, ^, |, &&, ||;而變數則必須要是 shared 的;而他的運作方式,就是讓各個執行緒針對指定的變數擁有一份有起始值的複本(起始值是運算元而定,像 , – 的話就是 0,* 就是 1),然後在平行化的計算時,都以各自的複本做運算,等到最後再以指定的運算元,將各執行緒的複本整合。而以上面的例子,就是把程式改為:

int	sum = 0;
#pragma omp parallel
{
#pragma omp for reduction( :sum)
for( int i = 0; i < 10000; i )
for( int j = 0; j < 50000; j )
sum = x;
}
printf( "%d
",sum );

而這樣的結果不但正確,執行速度也會大幅增加!像上面的例子就只需要 750ms 左右。

不過,atomicreduction 都有一個共同的限制,就是他們只能針對「scalar variable」來做。對於自己設計的 class type,就沒辦法了∼此外,也不能用在 overload 過的 operator。

除了上述的 privatefirstpruvatelastprivate 外,還有專門給 global、namespace 或 static 變數用的 threadprivate(詳見 MSDN);不過 Heresy 研究了好一陣子,還是不清楚他們到底有什麼用處。對於 threadprivate,在 MSDN 裡也有比較簡易的說明;而和前面三種 private 比起來,threadprivate 在使用上則有比較多的限制,詳見 MSDN OpenMP Reference 2.7.1 threadprivate Directive

Heresy 自己在測試的時候,自訂 class 要使用 threadprivate 的話,該 class 似乎不能重新定義 constructor 或 destrcutor;但是 MSDN 的範例程式中的 struct 卻有有重定義 destructor,而該段範例程式在 Heresy 測試時是無法編譯的;或許是編譯器的選項要再做些調整吧? Heresy 本來是想透過定義 constructor 和 destructor 的方法來測試變數建立、結束的時間與次數,但是由於 threadprivate 不支援這種 class,所以也沒辦法測試了。而由於 private 也可以用在 global 或 static 變數,也因此 Heresy 目前還是不大清楚他的確實用處是在哪裡。

不過由下面的程式,可以發現指定為 threadprivate 的變數 X 似乎有著和被同時指定 firstprivatelastprivate 的變數 A 有一樣的效果。

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int x = 1;
#pragma omp threadprivate( x )

int main() {
int a = 1;
#pragma omp parallel for firstprivate( a ) lastprivate(a)
for( int k = 0; k < 4; k )
{
a = 1;
x = 1;
printf( "!a = %d, x = %d
", a, x );
}
printf( "
==========================
" );
printf( "!a = %d, x = %d
", a, x );
system( "pause" );
}

執行結果

!a = 2, x = 2
!a = 2, x = 2
!a = 3, x = 3
!a = 3, x = 3

==========================
!a = 3, x = 3

雖然不清楚到底怎麼用,不過還是提一下:使用 threadprivate 時,還有兩個 clause 可以搭配使用,就是 copyincopyprivate。其中,copyin 是「Allows threads to access the master thread’s value, for a threadprivate variable.」,而 copyprivate 則是「Specifies that one or more variables should be shared among all threads.」(此 clause 只能用於 single)。

怎麼用…等之後研究出來再說了。


目錄:

參考資料:

4 thoughts on “簡易的程式平行化-OpenMP(五) 變數的平行化”

  1. 請教一下,我記得private、firstprivate、lastprivate是僅支援scalar variable而已,strcuture之類的variable是不支援的,您這樣的寫法不會有問題嗎?

  2. 您好,Heresy 沒弄錯的話,threadprivate 的限制應該是不能是 incomplete type 或 reference。structure 不見得一定會是 incomplete type。

  3. 您好,我是大陆的工程师,您是做算法优化的么?

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。