簡易的程式平行化－OpenMP（五） 變數的平行化

2007-05-042007-05-04| HeresyHeresy| 4 Comments| 10:41
Categories:

本文原發表於：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，因為預設值就已經是了∼

而在 private 和 share 的設定，OpenMP 還有提供一個 clause 叫做 default（詳見 MSDN）。他的功用，就是指定預設的範圍外變數配置方法；值可以是 shared 或 none。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 外，還有兩個類似的用法，分別是 firstprivate 和 lastprivate。其中，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 的值。

而 firstprivate 和 lastprivate 似乎也可以同時使用，也就是寫成 #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 左右。

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

除了上述的 private、firstpruvate、lastprivate 外，還有專門給 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 似乎有著和被同時指定 firstprivate、lastprivate 的變數 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 可以搭配使用，就是 copyin 和 copyprivate。其中，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）。

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

目錄：

參考資料：

C++ OpenMP

4 thoughts on “簡易的程式平行化－OpenMP（五） 變數的平行化”

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

    回覆

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

    回覆

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

    回覆

Leave a Reply

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

Related Posts

Boost 的 STL Container 切割工具（上）：split

這一篇最初的目的，是想來整理一下在 C 裡的字串切割的方法。不過寫到一半就發現，其實 Boost 提供的相關工 […] ...

Read MoreRead More

ATI 建立 OpenCL™ Zone

這是前兩天看到的消息，ATI / AMD 在自家網頁的 Technology Zone 的區域，建立了 Ope […] ...

Read MoreRead More

Kinect Fusion Part 2：含色彩資訊的版本

在前一篇《Kinect Fusion Part 1：C API 基本使用》，基本上已經把不包含顏色資訊的 Ki […] ...

Read MoreRead More