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