在并行計算領(lǐng)域有一個廣為流傳的笑話——并行計算是未來之事并且永遠都是。這個小笑話幾十年來一直都是對的。一種類似的觀點在計算機架構(gòu)社區(qū)中流傳，處理器時鐘速度的極限似乎近在眼前，但時鐘速度卻一直在加快。多核革命是并行社區(qū)的樂觀和架構(gòu)社區(qū)的悲觀的沖突。
現(xiàn)在主流的CPU廠商開始從追求時鐘頻率轉(zhuǎn)移到通過多核處理器來增加并行支持。原因很簡單：把多個CPU內(nèi)核封裝在一個芯片里可以讓雙核單處理器系統(tǒng)就像雙處理器系統(tǒng)一樣、四核單處理器系統(tǒng)像四處理器系統(tǒng)一樣。這一實用方法讓CPU廠商在能夠提供更強大的處理器的同時規(guī)避了加速頻率的諸多障礙。
到此為止這聽起來是一個好消息，但事實上如果你的程序沒有從多核里獲取優(yōu)勢的話，它并不會運行得更快。這就是OpenMP的用武之地了。OpenMP可以幫助C++開發(fā)者更快地開發(fā)出多線程應(yīng)用程序。
在這短小的篇幅里完整講述OpenMP這個大而強的API庫的相關(guān)內(nèi)容是不可能的。因此，本文僅作一些初始介紹，通過示例讓你能夠快速地應(yīng)用OpenMP的諸多特性編寫多線程應(yīng)用程序。如果你希望閱讀更深入的內(nèi)容，我們建議你去
OpenMP的網(wǎng)站看看。
在Visual C++中使用OpenMP
OpenMP標(biāo)準作為一個用以編寫可移植的多線程應(yīng)用程序的API庫，規(guī)劃于1997年。它一開始是一個基于Fortran的標(biāo)準，但很快就支持C和C++了。當(dāng)前的版本是OpenMP 2.0（譯者注：最新版本已經(jīng)是2.5版）， Visual C++ 2005和XBox360平臺都完全支持這一標(biāo)準。
在我們開始編碼之前，你需要知道如何讓編譯器支持OpenMP。Visual C++ 2005提供了一個新的/openmp開關(guān)來使能編譯器支持OpenMP指令。（你也可以通過項目屬性頁來使能OpenMP指令。點擊配置屬性頁，然后[C/C++]，然后[語言]，選中OpenMP支持。）當(dāng)/openmp參數(shù)被設(shè)定，編譯器將定義一個標(biāo)識符_OPENMP，使得可以用#ifndef _OPENMP來檢測OpenMP是否可用。
OpenMP通過導(dǎo)入vcomp.lib來連接應(yīng)用程序，相應(yīng)的運行時庫是vcomp.dll。Debug版本導(dǎo)入的連接庫和運行時庫（分別為vcompd.lib和vcompd.dll）有額外的錯誤消息，當(dāng)發(fā)生異常操作時被發(fā)出以輔助調(diào)試。記住盡管Xbox360平臺支持靜態(tài)連接OpenMP，但Visual C++并不支持。
OpenMP中的并行
OpenMP應(yīng)用程序剛運行時只有一條線程，這個線程我們叫它主線程。當(dāng)程序執(zhí)行時，主線程生成一組線程（包括主線程），隨著應(yīng)用程序執(zhí)行可能會有一些區(qū)域并行執(zhí)行。在并行結(jié)束后，主線程繼續(xù)執(zhí)行，其它線程被掛起。在一個并行區(qū)域內(nèi)能夠嵌套并行區(qū)域，此時原來的線程就成為它所擁有的線程組的主線程。嵌套的并行區(qū)域能夠再嵌套并行區(qū)域。
（圖1）OpenMP并行段
圖1展示了OpenMP如何并行工作。在最左邊黃色的線是主線程，之前這一線程就像單線程程序那樣運行，直到在執(zhí)行到點1——它的第一個并行區(qū)域。在并行區(qū)域主線程生成了一個線程組（參照黃色和桔黃色的線條），并且這組線程同時運行在并行區(qū)域。
在點2，有4條線程運行在并行區(qū)域并且在嵌套并行區(qū)域里生成了新的線程組（粉紅、綠和藍）。黃色和桔黃色進程分別作為他們生成的線程組的主線程。記住每一個線程都可以在不同的時間點生成一個新的線程組，即便它們沒有遇到嵌套并行區(qū)域。
在點3，嵌套的并行區(qū)域結(jié)束，每一個嵌套線程在并行區(qū)域同步，但并非整個區(qū)域的嵌套線程都同步。點4是第一個并行區(qū)域的終點，點5則開始了一個新的并行區(qū)域。在點5開始的新的并行區(qū)域，每一個線程從前一并行區(qū)域繼承利用線程本地數(shù)據(jù)。
現(xiàn)在你基本了解了執(zhí)行模型，可以真正地開始練習(xí)并行應(yīng)用程序開發(fā)了。
OpenMP的構(gòu)成
OpenMP易于使用和組合，它僅有的兩個基本構(gòu)成部分：編譯器指令和運行時例程。OpenMP編譯器指令用以告知編譯器哪一段代碼需要并行，所有的OpenMP編譯器指令都 以#pragma omp開始。就像其它編譯器指令一樣，在編譯器不支持這些特征的時候OpenMP指令將被忽略。
OpenMP運行時例程原本用以設(shè)置和獲取執(zhí)行環(huán)境相關(guān)的信息，它們當(dāng)中也包含一系列用以同步的API。要使用這些例程，必須包含OpenMP頭文件——omp.h。如果應(yīng)用程序僅僅使用編譯器指令，你可以忽略omp.h。
為一個應(yīng)用程序增加OpenMP并行能力只需要增加幾個編譯器指令或者在需要的地方調(diào)用OpenMP函數(shù)。這些編譯器指令的格式如下：
#pragma omp <directive> [clause[ [,] clause]…]
dierctive（指令）包含如下幾種：parallel，for，parallel for，section，sections，single，master，criticle，flush，ordered和atomic。這些指令指定要么是用以工作共享要么是用以同步。本文將討論大部分的編譯器指令。
對于directive（指令）而言clause（子句）是可選的，但子句可以影響到指令的行為。每一個指令有一系列適合它的子句，但有五個指令（master，cirticle，flush，ordered和atomic）不能使用子句。
指定并行
盡管有很多指令，但易于作為初學(xué)用例的只有極少數(shù)的一部分。最常用并且最重要的指令是parallel。這條指令為動態(tài)長度的結(jié)構(gòu)化程序塊創(chuàng)建一個并行區(qū)域。如：
#pragma omp <directive> [clause[ [,] clause]…]
structured-block
這條指令告知編譯器這一程序塊應(yīng)被多線程并行執(zhí)行。每一條指令都執(zhí)行一樣的指令流，但可能不是完全相同的指令集合。這可能依賴于if-else這樣的控制流語句。
這里有一個慣常使用的“Hello, World!”程序：
#pragma omp parallel
{
printf("Hello World\n");
}
在一個雙處理器系統(tǒng)上，你可能認為輸入出下：
Hello World
Hello World
但你可能得到的輸出如下：
HellHell oo WorWlodrl
d
出現(xiàn)這種情況是因為兩條線程同時并行運行并且都在同一時間嘗試輸出。任何時候超過一個線程嘗試讀取或者改變共享資源（在這里共享資源是控制臺窗口），那就可能會發(fā)生紊亂。這是一種非確定性的bug并且難以查出。程序員有責(zé)任讓這種情況不會發(fā)生，一般通過使用線程鎖或者避免使用共享資源來解決。
現(xiàn)在來看一個比較實用的例子——計算一個數(shù)組里兩個值的平均值并將結(jié)果存放到另一個數(shù)組。這里我們引入一個新的OpenMP指令：#pragma omp parallel for。這是一個工作共享指令。工作共享指令并不產(chǎn)生并行，#pragma omp for工作共享指令告訴OpenMP將緊隨的for循環(huán)的迭代工作分給線程組并行處理：
#pragma omp parallel
{
#pragma omp for
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
}
在這個例子中，設(shè)size的值為100并且運行在一個四處理器的計算機上，那么循環(huán)的迭代可能分配給處理器p1迭代1-25，處理器p2迭代26-50，處理器p3迭代51-75，處理器p4迭代76-99。在這里假設(shè)使用靜態(tài)調(diào)度的調(diào)度策略，我們將在下文討論更深層次的調(diào)度策略。
還有一點需要指出的是這一程序在并行區(qū)域的結(jié)束處需要同步，即所有的線程將阻塞在并行區(qū)域結(jié)束處，直到所有線程都完成。
如果前面的代碼沒有使用#pragma omp for指令，那么每一個線程都將完全執(zhí)行這個循環(huán)，造成的后果就是線程冗余計算：
#pragma omp parallel
{
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
}
因為并行循環(huán)是極常見的的可并行工作共享結(jié)構(gòu)，所以O(shè)penMP提供了一個簡短的寫法用以取代在#pragma omp parallel后面緊跟#pragma omp for的形式：
#pragma omp parallel for
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
你必須確保沒有循環(huán)依賴，即循環(huán)中的某一次迭代不依賴于其它迭代的結(jié)果。例如下面兩個循環(huán)就有不同的循環(huán)依賴問題：
for(int i = 1; i <= n; ++i) // Loop (1)
a[i] = a[i-1] + b[i];
for(int i = 0; i < n; ++i) // Loop (2)
x[i] = x[i+1] + b[i];
并行的Loop1的問題是因為當(dāng)執(zhí)行第i層迭代時需要用到i-1次迭代的結(jié)果，這是迭代i到i-1的依賴。并行的Loop2同樣有問題，盡管原因有些不同。在這個循環(huán)中能夠在計算x[i-1]的值之前計算x[i]的值，但在這樣并行的時候不能再計算x[i-1]的值，這是迭代i-1到i的依賴。
當(dāng)并行執(zhí)行循環(huán)的時候必須確保沒有循環(huán)依賴。當(dāng)沒有循環(huán)依賴的時候，編譯器將能夠以任意的次序執(zhí)行迭代，甚至在并行中也一樣。這是一個編譯器并不檢測的重要需求。你應(yīng)該有力地向編譯器斷言將要并行執(zhí)行的循環(huán)中沒有循環(huán)依賴。如果一個循環(huán)存在循環(huán)依賴而你告訴編譯器要并行執(zhí)行它，編譯器仍然會按你說的做，但結(jié)果應(yīng)該是錯誤的。
另外，OpenMP對在#pragma omp for或#pragma omp parallel for里的循環(huán)體有形式上的限制，循環(huán)必須使用下面的形式：
for([integer type] i = loop invariant value;
i {<,>,=,<=,>=} loop invariant value;
i {+,-}= loop invariant value)
這樣OpenMP才能知道在進入循環(huán)時需要執(zhí)行多少次迭代。
OpenMP和Win32線程比較
當(dāng)使用Windows API進行線程化的時候，用#pragma omp parallel為例來比較它們有利于更好地比較異同。從圖2可見為達到同樣的效果Win32線程需要更多的代碼，并且有很多幕后魔術(shù)般的細節(jié)難以了解。例如ThreadData的構(gòu)造函數(shù)必須指定每一個線程被調(diào)用時開始和結(jié)束的值。OpenMP自動地掌管這些細節(jié)，并額外地給予程序員配置并行區(qū)域和代碼的能力。
DWORD ThreadFn(void* passedInData)
{
ThreadData *threadData = (ThreadData *)passedInData;
for(int i = threadData->start; i < threadData->stop; ++i )
x[i] = (y[i-1] + y[i+1]) / 2;
return 0;
}
void ParallelFor()
{
// Start thread teams
for(int i=0; i < nTeams; ++i)
ResumeThread(hTeams[i]);
// ThreadFn implicitly called here on each thread
// Wait for completion
WaitForMultipleObjects(nTeams, hTeams, TRUE, INFINITE);
}
int main(int argc, char* argv[])
{
// Create thread teams
for(int i=0; i < nTeams; ++i)
{
ThreadData *threadData = new ThreadData(i);
hTeams[i] = CreateThread(NULL, 0, ThreadFn, threadData,
CREATE_SUSPENDED, NULL);
}
ParallelFor(); // simulate OpenMP parallel for
// Clean up
for(int i=0; i < nTeams; ++i)
CloseHandle(hTeams[i]);
}
（圖2）Win32多線程編程
共享數(shù)據(jù)與私有數(shù)據(jù)
在編寫并行程序的時候，理解什么數(shù)據(jù)是共享的、什么數(shù)據(jù)是私有的變得非常重要——不僅因為性能，更因為正確的操作。OpenMP讓共享和私有的差別顯而易見，并且你能手動干涉。
共享變量在線程組內(nèi)的所有線程間共享。因此在并行區(qū)域里某一條線程改變的共享變量可能被其它線程訪問。反過來說，在線程組的線程都擁有一份私有變量的拷貝，所以在某一線程中改變私有變量對于其它線程是不可訪問的。
默認地，并行區(qū)域的所有變量都是共享的，除非如下三種特別情況：一、在并行for循環(huán)中，循環(huán)變量是私有的。如圖3里面的例子，變量i是私有的，變量j默認是共享的，但使用了firstprivate子句將其聲明為私有的。
float sum = 10.0f;
MatrixClass myMatrix;
int j = myMatrix.RowStart();
int i;
#pragma omp parallel
{
#pragma omp for firstprivate(j) lastprivate(i) reduction(+: sum)
for(i = 0; i < count; ++i)
{
int doubleI = 2 * i;
for(; j < doubleI; ++j)
{
sum += myMatrix.GetElement(i, j);
}
}
}
（圖3）OpenMP子句與嵌套for循環(huán)
二、并行區(qū)域代碼塊里的本地變量是私有的。在圖３中，變量doubleI是一個私有變量——因為它聲明在并行區(qū)域。任一聲明在myMatrix::GetElement里的非靜態(tài)變量和非成員變量都是私有的。
三、所有通過private，firstprivate，lastprivate和reduction子句聲明的變量為私有變量。在圖３中變量i,j和sum是線程組里每一個線程的私有變量，它們將被拷貝到每一個線程。
這四個子句每個都有一序列的變量，但它們的語義完全不同。private子句說明變量序列里的每一個變量都應(yīng)該為每一條線程作私有拷貝。這些私有拷貝將被初始化為默認值（使用適當(dāng)?shù)臉?gòu)造函數(shù)），例如int型的變量的默認值是０。
firstprivate有著與private一樣的語義外，它使用拷貝構(gòu)造函數(shù)在線程進入并行區(qū)域之前拷貝私有變量。
lastprivate有著與private一樣的語義外，在工作共享結(jié)構(gòu)里的最后一次迭代或者代碼段執(zhí)行之后，lastprivate子句的變量序列里的值將賦值給主線程的同名變量，如果合適，在這里使用拷貝賦值操作符來拷貝對象。
reduction與private的語義相近，但它同時接受變量和操作符(可接受的操作符被限制為圖４列出的這幾種之一)，并且reduction變量必須為標(biāo)量變量（如浮點型、整型、長整型，但不可為std::vector，int[]等）。reduction變量初始化為圖４表中所示的值。在代碼塊的結(jié)束處，為變量的私有拷貝和變量原值一起應(yīng)用reduction操作符。
Reduction operator
Initialized value (canonical value)
+
0
*
1
-
0
&
~0(every bit set)
|
0
^
0
&&
1
||
0
（圖４）Reductoin操作符
在圖３的例子中，sum對應(yīng)于每一個線程的私有拷貝的值在后臺被初始化為0.0f（記住圖４表中的規(guī)范值為０，如果數(shù)據(jù)類型為浮點型就轉(zhuǎn)化為0.0f。）在#pragma omp for代碼塊完成后，線程為所有的私有sum和原值做+操作（sum的原值在例子中是10.0f），再把結(jié)果賦值給原本的共享的sum變量。
非循環(huán)并行
OpenMP經(jīng)常用以循環(huán)層并行，但它同樣支持函數(shù)層并行，這個機制稱為OpenMP sections。sections的結(jié)構(gòu)是簡明易懂的，并且很多例子都證明它相當(dāng)有用。
現(xiàn)在來看一下計算機科學(xué)里一個極其重要的算法——快速排序（QuickSort）。在這里使用的例子是為一序列整型數(shù)進行遞歸的快速排序。為了簡單化，我們不使用泛型模板版本，但其仍然可以表達OpenMP的思想。圖5的代碼展示了如何在快速排序的主要函數(shù)中應(yīng)用sections（為簡單起見我們忽略了劃分函數(shù)）。
void QuickSort (int numList[], int nLower, int nUpper)
{
if (nLower < nUpper)
{
// create partitions
int nSplit = Partition (numList, nLower, nUpper);
#pragma omp parallel sections
{
#pragma omp section
QuickSort (numList, nLower, nSplit - 1);
#pragma omp section
QuickSort (numList, nSplit + 1, nUpper);
}
}
}
（圖5）用OpenMP sections實現(xiàn)Quicksort
在這個例子中，第一個#pragma創(chuàng)建一個sections并行區(qū)域，每一個section用#pragma omp section前綴指令聲明。每一個section都將被分配線程組里的單獨線程執(zhí)行，并且所有的sectoins能夠確保一致并行。每一個并行section都遞歸地調(diào)用QuickSort。
就像在#pragma omp parallel for結(jié)構(gòu)中一樣，你有責(zé)任確保每一個section都不依賴于其它的sectoin，以使得它們能夠并行執(zhí)行。如果sectoins在沒有同步存取資源的情況下改變了共享資源，將導(dǎo)致未定義結(jié)果。
在本例中像使用#pragma omp parallel for一樣使用了簡短的#pragma omp parallel sections。你也可以使用單獨使用#pragma omp sections，后跟一個并行區(qū)域，就像你在#pragma omp for里做的一樣。
在圖5的程序?qū)崿F(xiàn)中我們需要了解一些東西。首先，并行的sections遞歸調(diào)用，并行區(qū)域是支持遞歸調(diào)用的，特別在本例中并行sectoins就只是遞歸調(diào)用。因此如果使能并行嵌套機制，程序遞歸調(diào)用QuickSort時將產(chǎn)生大量新線程。這可能是也可能不是程序員所期望的，因為它導(dǎo)致產(chǎn)生相當(dāng)多的線程。程序能夠不使能并行嵌套機制以限制線程數(shù)量。不使能嵌套機制的時候，應(yīng)用程序?qū)⒃趦蓷l線程上遞歸調(diào)用QuickSort，而絕不會產(chǎn)生多于兩條的線程。
另外，如果沒有打開/openmp開關(guān)，編譯器將生成完美的正確的串行快速排序?qū)崿F(xiàn)。OpenMP的好處之一就是能夠與不支持OpenMP的編譯器中共存。
