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


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

#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, %dn", 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 x 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)n", 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( "%dn",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( "%dn",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( "%dn",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 = %dn", a, x ); } printf( "n==========================n" ); printf( "!a = %d, x = %dn", 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)。

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

參考資料:


目錄:

對「簡易的程式平行化-OpenMP(五) 變數的平行化」的想法

  1. to egmkang
    ㄟ~Heresy 最近已經沒什麼在玩 OpenMP 了,建議你把問題直接貼出來,Heresy 會的話就回答?

    • Heresy, 你好。
      我最近 发现一个问题,很多工作站只有8 或12核 处理器, 可是我的LOOP 是24, 直接做OPENMP的话,会不会出现问题? 似乎有点问题: 8个处理器不知道如何分配LOOP里面的24个并行任务。谢谢

      • 不太了解你擔心的問題點是什麼?
        如果你是用 parallel for 來平行化迴圈的話,OpenMP 就是把迴圈不同次的工作,分給不同的核心同時做而已;假設你的例子很單純、可以正確平行化的話,他應該就是讓每個核心去執行迴圈的三項、讓八顆核心合力完成本來要做的 24 項。
        所以只要你的迴圈內要做的是沒有相依性,基本上應該都沒問題。
        當然,效率會增加多少會是另一回事。

  2. 一個可能是你所執行的程式,在平行化後,每個 thread 中執行的程式量太少;相對之下,使用 openMP 來做 thread 的切割、管理所增加的時間,反而比不上平行化減少的時間。
    當然,也有可能是其他各式的原因,這個就要看程式所做的動作才能判斷了。

  3. 我为什么用了omp,反而计算速度下降了,cpu越多,速度越慢。可能会是什么原因?

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.