高性能計算導論-第五章ppt課件

1、用OpenMP進展共享內(nèi)存編程分布式內(nèi)存系統(tǒng)OpenMPn與Pthreads 一樣，OpenMP是一個針對共享內(nèi)存并行編程的API。nOpenMP中的“MP代表“多處置。nOpenMP是為共享內(nèi)存系統(tǒng)而設(shè)計的：在系統(tǒng)中每個線程都有能夠訪問一切可訪問的內(nèi)存區(qū)域。共享內(nèi)存系統(tǒng)n當運用OpenMP編程時，我們將系統(tǒng)看做一組核或CPU的集合，它們都能訪問主存，如圖5-1所示。OpenMP與Pthreadsn雖然OpenMP和Pthreads都是針對共享內(nèi)存編程的API，但它們有許多本質(zhì)的不同。nPthreads要求程序員顯式地明確每個線程的行為。n相反，OpenMP有時允許程序員只需求簡單地聲明一塊代

2、碼應(yīng)該并行執(zhí)行，而由編譯器和運轉(zhuǎn)時系統(tǒng)來決議哪個線程詳細執(zhí)行哪個義務(wù)。OpenMP與PthreadsnPthreads與MPI一樣是一個可以被鏈接到C程序的函數(shù)庫，因此只需系統(tǒng)有Pthreads庫，Pthreads程序就可以被恣意C編譯器運用。n相反，OpenMP要求編譯器支持某些操作，所以完全有能夠他運用的編譯器無法把OpenMP程序編譯成并行程序。OpenMP與PthreadsnPthreads更底層，并且提供了虛擬地編寫任何可知線程行為的才干。然而，這個功能有一定的代價：每個線程行為的每一個細節(jié)都得由我們本人來定義。n相反，OpenMP允許編譯器和運轉(zhuǎn)時系統(tǒng)來決議線程行為的一些細節(jié)，因此

3、運用OpenMP來編寫一些并行行為更容易。但代價是很難對一些底層的線程交互進展編程。預備知識nOpenMP提供“基于指令的共享內(nèi)存API。這意味著：在C和C+中，有一些特殊的預處置器指令pragman在系統(tǒng)中參與預處置器指令普通是用來允許不是根本C言語規(guī)范部分的行為。n不支持pragma的編譯器就會忽略pragma指令提示的那些語句，這樣就允許運用pragma的程序在不支持它們的平臺上運轉(zhuǎn)。n因此，在實際上，假設(shè)他仔細編寫一個OpenMP程序，它就可以在任何有C編譯器的系統(tǒng)上被編譯和運轉(zhuǎn)，而無論編譯器能否支持OpenMP。Pragman在C和C+中，預處置器指令以#pragma開頭。n與一切的

4、預處置器指令一樣，pragma的默許長度是一行，因此假設(shè)有一個pragma在一行中放不下，那么新行需求被“本義前面加一個反斜杠“。n#pragma后面要跟什么內(nèi)容，完全取決于正在運用哪些擴展比如OpenMP。運轉(zhuǎn)OpenMP程序n應(yīng)該留意到線程正在競爭訪問規(guī)范輸出，因此不保證輸出會按線程編號的順序出現(xiàn). / omp_hello 4running with 4 threadsHello from thread 0 of 4Hello from thread 1 of 4Hello from thread 2 of 4Hello from thread 3 of 4Hello from threa

5、d 1 of 4Hello from thread 2 of 4Hello from thread 0 of 4Hello from thread 3 of 4Hello from thread 3 of 4Hello from thread 1 of 4Hello from thread 2 of 4Hello from thread 0 of 4possibleoutcomes程序n我們來看一下程序5-1中的源代碼。n除了指令集合外，OpenMP由一個函數(shù)和宏庫組成，因此我們通常需求包含一個有原型和宏定義的頭文件。OpenMP的頭文件是omp.h，程序的第3行包含了它。指定線程數(shù)n在Pth

6、reads程序中，我們在命令行里指定線程數(shù)，OpenMP程序也經(jīng)常這么做。n在第9行，運用stdlib.h中的strtol函數(shù)來獲得線程數(shù)。這個函數(shù)的語法是：n第一個參數(shù)是一個字符串在我們的例子中，它是命令行參數(shù)，最后的參數(shù)是字符串所表示的數(shù)的基數(shù)在我們的例予中是10十進制。我們不運用第二個參數(shù)，因此只是傳人一個NULL空指針。OpenMP pragmasn程序的第11行是第一條OpenMP指令，運用它來提示程序應(yīng)該啟用一些線程。n每個被啟動的線程都執(zhí)行Hello函數(shù)，并且當線程從Hello調(diào)用前往時，它們應(yīng)該被終止，即在執(zhí)行return語句時線程應(yīng)該被終止。與Pthreads比較n程序的代碼

7、上有許多艱苦的改動。n在Pthreads中，我們必需寫許多代碼來派生(folk)和合并(join)多個線程：需求為每個線程的特殊構(gòu)造分配存儲空間，需求運用一個for循環(huán)來啟動每個線程，并運用另一個for循環(huán)來終止這些線程。n因此，很明顯OpenMP比Pthreads層次更高。OpenMP pragmasnOpenMP的pragma總是以n # pragma ompn 開頭n在pragma后面的第一條指令是一條parallel指令。n運用parallel是用來闡明之后的構(gòu)造化代碼塊也可以稱為根本塊應(yīng)該被多個線程并行執(zhí)行。構(gòu)造化代碼塊n一個構(gòu)造化代碼塊是一條c語句或者只需一個入口和一個出口的一組復

8、合c語句，但在這個代碼塊中允許調(diào)用exit函數(shù)。n這個定義簡單地制止分支語句進入或分開構(gòu)造化代碼塊。parallel指令n最根本的parallel指令可以以如下簡單的方式表示：n運轉(zhuǎn)構(gòu)造化代碼塊的線程數(shù)將由運轉(zhuǎn)時系統(tǒng)決議。但如前面提到的那樣，通常會在命令行里指定線程數(shù)，因此為parallel指令添加了num_threads子句。子句n在OpenMP中，子句只是一些用來修正指令的文本。nnum_threads子句被添加到parallel指令中，這樣就允許程序員指定執(zhí)行代碼塊的線程數(shù)：留意n要留意的是，程序可以啟動的線程數(shù)能夠會受系統(tǒng)定義的限制。nOpenMP規(guī)范并不保證明際情況下可以啟threa

9、d_count個線程。n然而，目前大部分的系統(tǒng)可以啟動數(shù)百甚至數(shù)千個線程，因此除非他試圖啟動許多線程，否那么普通情況下我們幾乎總可以得到需求數(shù)目的線程。一些術(shù)語n在parallel指令之前，程序只運用一個線程。而當程序開場執(zhí)行時，線程開場啟動。當程序到達parallel指令時，原來的線程繼續(xù)執(zhí)行，另外thread_count -1個線程被啟動。n在OpenMP語法中，執(zhí)行并行塊的線程集合原始的線程和新的線程稱為線程組(team)，原始的線程稱為主線程(master)，額外的線程稱為從線程(slave)。一些術(shù)語n每個線程組中的線程都執(zhí)行parallel指令后的代碼塊，因此在我們的例子中，每個線

10、程都調(diào)用Hello函數(shù)。n當代碼塊執(zhí)行完時，即在我們的例子中，當線程從Hello調(diào)用中前往時，有一個隱式路障。隱式路障n隱式路障意味著完成代碼塊的線程將等待線程組中的一切其他線程完成代碼塊.n在我們的例子中，一個曾經(jīng)完成Hello調(diào)用的線程將等待線程組中一切其他線程前往。當一切線程都完戍了代碼塊，從線程將終止，主線程將繼續(xù)執(zhí)行之后的代碼。n在我們的例子中，主線程將執(zhí)行第14行的return語句，程序?qū)⒔K止。私有部分變量n由于每個線程有它本人的棧，所以一個執(zhí)行Hello函數(shù)的線程將在函數(shù)中創(chuàng)建它本人的私有部分變量。n在我們的例子中，當函數(shù)被調(diào)用時，經(jīng)過調(diào)用OpenMP函數(shù)omp_get_thre

11、ad_num和omp_get_num_threads，每個線程將分別得到它的編號或id，以及線程組中的線程數(shù)。n線程的編號是一個整數(shù)，范圍是0、1、thread_count-1。這些函數(shù)的語法是：錯誤檢查n為了使代碼更為緊湊、可讀性更強，我們的程序不做任何錯誤檢查。當然，這是危險的，而且實踐上，試圖預測錯誤并對它們進展檢查是一個非常好的主意，甚至可以說是必需的。n在這個例子中，首先一定要檢查命令行參數(shù)的存在，假設(shè)存在的話，在調(diào)用strtol后應(yīng)該檢查值能否是正的。還要檢查被parallel指令實踐創(chuàng)建的線程數(shù)與thread_count能否一樣。錯誤檢查n 第二個潛在問題的來源是編譯器。假設(shè)編譯

12、器不支持OpenMP，那么它將只忽略parallel指令。n然而，試圖包含omp.h頭文件以及調(diào)用omp_get_thread_num和omp_get_num_threads將引起錯誤。為了處置這些問題，可以檢查預處置器宏_OPENMP能否認義。假設(shè)定義了，那么我們可以包含omp.h并調(diào)用OpenMP函數(shù)。我們能夠?qū)Τ绦蜃鲆韵滦拚?。錯誤檢查n我們可以在試圖包含omp.h之前先檢查_OPENMP的定義# include #ifdef _OPENMP# include #endif錯誤檢查n還有，我們可以首先檢查能否_OPENMP定義，從而取代只調(diào)用OpenMP函數(shù)：# ifdef _OPENMP

13、 int my_rank = omp_get_thread_num ( ); int thread_count = omp_get_num_threads ( );# else int my_rank = 0; int thread_count = 1;# endif梯形積分法The Trapezoidal Rule梯形積分法n我們來看一個更適用也更復雜的例子：用梯形積分法估計曲線下方所包圍的面積。串行算法n 再回想一下，假設(shè)每個子區(qū)間有同樣的寬度h，并且定義h=(b-a)/n，x_i=a+i*h，i=0，1，n，那么近似值將是：Foster的并行程序設(shè)計方法n(1)識別兩類義務(wù)：n a. 單

14、個梯形面積的計算。n b梯形面積的求和。n(2)在1(a)的義務(wù)中，沒有義務(wù)間的通訊，但這一組義務(wù)中的每一個義務(wù)都與1(b)中的義務(wù)通訊。Foster的并行程序設(shè)計方法n(3)假設(shè)梯形的數(shù)量遠大于核的數(shù)量，于是經(jīng)過給每個線程分配延續(xù)的梯形塊和每個核一個線程來聚集義務(wù)。n這能有效地將區(qū)間a，b劃分成更大的子區(qū)間，每個線程對它的子區(qū)間簡單地運用串行梯形積分法。Foster的并行程序設(shè)計方法n(4)累加線程的結(jié)果。n很明顯，其中一個處理方案是運用一個共享變量作為一切線程的和，每個線程可以將它計算的部分結(jié)果累加到共享變量中。讓每個線程執(zhí)行類似下面的語句：n global_result += my_re

15、sult ;n但是，這能夠會導致一個錯誤的global_result值假設(shè)兩個或更多線程試圖同時執(zhí)行這條語句，那么結(jié)果將是不可估計的。例子n假設(shè)global_result曾經(jīng)被初始化為0，線程0曾經(jīng)計算出my_result =1，線程1曾經(jīng)計算出my_result =2。而且，假設(shè)線程根據(jù)以下時間表執(zhí)行語句n global_result+=my_ result;臨界區(qū)n實踐運轉(zhuǎn)時，事件的序列能夠會不同，但除非一個線程在其他線程開場時完成了計算，否那么結(jié)果都將是不正確的。n這其實是一個競爭條件(race condition)的例子：多個線程試圖訪問一個共享資源，并且至少其中一個訪問是更新該共享資

16、源，這能夠會導致錯誤。n引起競爭條件的代碼global_result+=my_result，稱為臨界區(qū)。臨界區(qū)是一個被多個更新共享資源的線程執(zhí)行的代碼，并且共享資源一次只能被一個線程更新。互斥訪問n顯然需求一些機制來確保一次只需一個線程執(zhí)行g(shù)lobal_result+=my_result，并且第一個線程完成操作前，沒有其他的線程能開場執(zhí)行這段代碼。n在Pthreads中，運用互斥量或信號量。在OpenMP中，運用critical指令：n這條指令通知編譯器需求安排線程對以下的代碼塊進展互斥訪問，即一次只需一個線程可以執(zhí)行下面的構(gòu)造化代碼。第一個OpenMP梯形積分法程序主函數(shù)闡明n在main函數(shù)

17、中，第16行之前的代碼是單線程的，它簡單地獲取線程數(shù)和輸入(a、b和n).n第16行里，parallel指令明確Trap函數(shù)應(yīng)該被thread_count個線程執(zhí)行。n在從Trap調(diào)用前往后，任何被parallel指令啟動的新線程將終止，程序只用一個線程恢復執(zhí)行。這個線程打印結(jié)果并終止。Trap函數(shù)n在Trap函數(shù)中，每個線程獲取它的編號，以及在線程組中被parallel指令啟動的線程總數(shù)。然后，每個線程確定以下值：n (1)梯形底的長度第32行。n (2)給每個線程分配的梯形數(shù)第33行。n (3)區(qū)間的左、右端點第34行和第35行。n (4)對globa l_result奉獻的部分和第364

18、1行。n在第43行和第44行，線程經(jīng)過將它們的部分和結(jié)果添加到global_result來完成操作。關(guān)于整除n除非能被thread_count整除，否那么我們將運用小于n個的梯形來信算global_result。n例如，假設(shè)n=14，thread_count=4，那么每個線程將計算n local_n=n /thread_count =14/4 =3n因此每個線程將只運用3個梯形， global_result將由4x3 =12個梯形計算出，而不是14個。n所以在錯誤檢查在程序中沒有顯示時，我們用如下操作來檢查n能否被thread_count整除：變量的作用域SCOPE OF VARIABLES回

19、想n在串行編程中，變量的作用域由程序中的變量可以被運用的那些部分組成。n例如，在C函數(shù)開場處被聲明的變量有“函數(shù)范圍的作用域，即它只可以在函數(shù)體中被訪問。n另一方面，一個在.C文件開場處被聲明的變量有“文件范圍的作用域，表示任何在文件中聲明該變量的函數(shù)都可以訪問這個變量。在OpenMP中，變量的作用域n在OpenMP中，變量的作用域涉及在parallel塊中可以訪問該變量的線程集合。n一個可以被線程組中的一切線程訪問的變量擁有共享作用域，而一個只能被單個線程訪問的變量擁有私有作用域。n在“hello，world程序中，被每個線程運用的變量my_rank和thread_count在Hello函數(shù)

20、中被聲明，這個函數(shù)在parallel塊中被調(diào)用。結(jié)果，被每個線程運用的變量在線程的私有棧中分配，因此一切的變量都有私有作用域。共享作用域n在main函數(shù)中聲明的變量a、b、n、global_result和thread_count對于一切線程組中被parallel指令啟動的線程都是可訪問的。n在parallel塊之前被聲明的變量的缺省作用域是共享的n在Trap函數(shù)中，雖然global_result_p是私有變量，但它援用了global_result變量，這個變量是在main函數(shù)中并且在parallel指令之前聲明的變量。n對于*global_result_p，擁有共享作用域是很重要的。變量的作用

21、域總結(jié)n在parallel指令前曾經(jīng)被聲明的變量，擁有在線程組中一切線程間的共享作用域，而在塊中聲明的變量例如，函數(shù)中的部分變量中有私有作用域。n另外，在parallel塊開場處的共享變量的值，與該變量在parallel塊之前的值一樣。在parallel塊完成后，該變量的值是塊終了時的值。歸約子句THE REDUCTION CLAUSE另一個想法n假設(shè)開發(fā)實現(xiàn)梯形積分法的串行程序，我們能夠會運用一個有些許不同的函數(shù)原型，而不是n我們能夠會定義：n對函數(shù)的調(diào)用將會是n這更容易了解，對于除了指針的忠實擁護者之外的人，這種方法能夠更有吸引力。另一個想法2n保管指針版本是由于我們需求將每個線程的部分計

22、算結(jié)果加到global_result。然而，我們能夠更傾向予以下的函數(shù)原型：n除了沒有臨界區(qū)外，Local_trap的函數(shù)體與程序5-2中Trap的函數(shù)體是一樣的。nPragma omp parallel 指令修正為：問題？處理方法？n！對Local_trap的調(diào)用一次只可以被一個線程執(zhí)行，所以這就相當于強迫各個線程順序執(zhí)行梯形積分法。n可以經(jīng)過在parallel塊中聲明一個私有變量和將臨界區(qū)移到函數(shù)調(diào)用之后來防止這個問題：I dont like it.Neither do I.I think we can do better.歸約操作符nOpenMP提供了一個更為明晰的方法來防止Local_

23、trap的串行執(zhí)行：將global_result定義為一個歸約( reduction)變量。n歸約操作符(reduction operator)是一個二元操作例如：加法和減法，歸約就是將一樣的歸約操作符反復地運用到操作數(shù)序列來得到一個結(jié)果的計算。n另外，一切操作的中間結(jié)果存儲在同一個變量里：歸約變量(reduction variable)。歸約例子n例如，假設(shè)A是一個有n個int型整數(shù)的數(shù)組，計算：n是一個歸約，歸約操作符是加法。歸約子句語法nreduction子句的語法是：n在C言語中，operator能夠是操作符n中的恣意一個+, *, -, &, |, , &, |留意問

24、題n減法不滿足交換律和結(jié)合律。n例如：串行代碼n在result中存儲的結(jié)果是-10。然而，假設(shè)我們將迭代劃分到兩個線程中去執(zhí)行，線程0將減1和2，線程1將減3和4，那么線程0將算出-3，線程1將算出-7。n顯然，-3 -7=4。留意問題2n假設(shè)一個歸約變量是一個float或double型數(shù)據(jù)，那么當運用不同數(shù)量的線程時，結(jié)果能夠會有些許不同。這是由于浮點數(shù)運算不滿足結(jié)合律。n例如，假設(shè)a、b和c是浮點數(shù)，那么a+b+c能夠不會準確地等于a+(b+c)。reduction子句中變量的作用域n當一個變量被包含在一個reduction子句中時，變量本身是共享的。n然而，線程組中的每個線程都創(chuàng)建本人的

25、私有變量。n在parallel塊里，每當一個線程執(zhí)行涉及這個變量的語句時，它運用的其實是私有變量。當parallel塊終了后，私有變量中的值被整合到一個共享變量中。最新版本代碼n代碼明確了global_result是一個歸約變量，加號(“+)指示歸約操作符是加法。nOpenMP為每個線程有效地創(chuàng)建了一個私有變量，運轉(zhuǎn)時系統(tǒng)在這個私有變量中存儲每個線程的結(jié)果。OpenMP也創(chuàng)建了一個臨界區(qū)，并且在這個臨界區(qū)中，將存儲在私有變量中的值進展相加。因此，對Local _trap的調(diào)用可以并行執(zhí)行。parallel for指令The “Parallel For DirectiveParallel for

26、n作為梯形積分法顯式并行化的替代方案，OpenMP提供了parallel for指令。運用該指令，我們可以并行化串行梯形積分法：Parallel forn與parallel指令一樣，parallel for指令生成一組線程來執(zhí)行后面的構(gòu)造化代碼塊。n在parallel for指令之后的構(gòu)造化塊必需是for循環(huán)。n另外，運用parallel for指令，系統(tǒng)經(jīng)過在線程間劃分循環(huán)迭代來并行化for循環(huán)。因此，parallel for指令與parallel指令非常不同，由于在parallel指令之前的塊，普通來說其任務(wù)必需由線程本身在線程之間劃分。線程間的缺省劃分方式n在一個曾經(jīng)被parallel

27、for指令并行化的for循環(huán)中，線程間的缺省劃分方式是由系統(tǒng)決議的。n大部分系統(tǒng)會粗略地運用塊劃分，即假設(shè)有m次迭代，那么大約m/thread_count歡迭代被分配到線程0，接下來的m/thread_count次被分配到線程1，以此類推。Parallel for中變量的作用域n在parallel指令中，一切變量的缺省作用域是共享的。n但在parallel for中，假設(shè)循環(huán)變量i是共享的，那么變量更新i+也會是一個無維護的臨界區(qū)。n因此，在一個被parallel for指令并行化的循環(huán)中，循環(huán)變量的缺省作用域是私有的，在我們的代碼中，每個線程組中的線程擁有它本人的i的副本。遐想n這是一個非常

28、愉快的遐想：經(jīng)過添加一條簡單的parallel for指令，就能夠并行化由大量的for循環(huán)所組成的串行程序。n也能夠經(jīng)過不斷地在每個循環(huán)前放置parallel for指令，來增量地并行化一個串行程序。警告n首先，OpenMP只會并行化for循環(huán)，它不會并行化while或do - while循環(huán)。這似乎不是一個很大的限制，由于任何運用while或do - while循環(huán)的代碼都可以被轉(zhuǎn)化為等效的運用for循環(huán)的代碼。n另外， OpenMP只能并行化確定迭代次數(shù)的for循環(huán)，包括：n由for語句本身來確定；n在循環(huán)執(zhí)行之前確定。不能被并行化的例子n例如，“無限循環(huán)：n類似地，循環(huán)n也不能被并行化，

29、由于迭代的次數(shù)不能只從for語句中來決議。這個for循環(huán)也不是一個構(gòu)造化塊，由于break添加了另一個從循環(huán)退出的出口。典型構(gòu)造的for循環(huán)n現(xiàn)實上，OpenMP只可以并行化具有典型構(gòu)造的for循環(huán)。限制n典型構(gòu)造的for循環(huán)符合一些十清楚顯的限制：n變量index必需是整型或指針類型例如，它不能是float型浮點數(shù)。n表達式start、end和incr必需有一個兼容的類型。例如，假設(shè)index是一個指針，那么incr必需是整型。n表達式start、end和incr不可以在循環(huán)執(zhí)行期間改動。n 在循環(huán)執(zhí)行期間，變量index只可以被for語句中的“增量表達式修正。數(shù)據(jù)依賴性n假設(shè)for循環(huán)不能

30、滿足上述所列舉規(guī)那么中的任何一條，那么編譯器將簡單地回絕它。例如，假設(shè)我們試圖編譯一個線性查找程序：n編譯器將報告：隱藏的數(shù)據(jù)依賴性n一個更隱匿的問題發(fā)生在如下的循環(huán)中：在該循環(huán)中，迭代中的計算依賴于一個或更多個先前的迭代結(jié)果。n例如，計算前n個斐波那契(Fibonacci)數(shù)Fibonacci數(shù)列的并行化1 1 2 3 5 8 13 21 34 551 1 2 3 5 8 0 0 0 0this is correctbut sometimeswe get thisfibo 0 = fibo 1 = 1;for (i = 2; i n; i+) fibo i = fibo i 1 + fibo

31、 i 2 ; fibo 0 = fibo 1 = 1;# pragma omp parallel for num_threads(2) for (i = 2; i n; i+) fibo i = fibo i 1 + fibo i 2 ; note 2 threads終究發(fā)生了什么？n似乎運轉(zhuǎn)時系統(tǒng)將fibo2、fibo3、fibo4和fibo5的計算分配給了一個線程，將fibo6、fibo7、fibo8、fibo9分配給了另一個線程。n在程序的一些運轉(zhuǎn)結(jié)果中，結(jié)果之所以正確是由于被分配給fibo2、fibo3、fibo4和fibo5的線程在另一個線程開場前就完成了計算。n然而，對于其他運轉(zhuǎn)結(jié)

32、果，當?shù)诙€線程計算fibo6時，第一個線程還沒有計算出fibo4和fibo5。系統(tǒng)將fibo的入口初始化為0，第二個線程運用值fibo4 =0和fibo5 =0來計算fibo6。然后它繼續(xù)運用fibo5 =0和fibo6 =0來計算fibo7，以此類推。兩個要點n(1) OpenMP編譯器不檢查被parallel for指令并行化的循環(huán)所包含的迭代間的依賴關(guān)系，而是由程序員來識別這些依賴關(guān)系。n(2) 一個或更多個迭代結(jié)果依賴于其他迭代的循環(huán)，普通不能被OpenMP正確地并行化。尋覓循環(huán)依賴n當我們試圖運用一個parallel for指令時，首先應(yīng)該留意的是：要小心發(fā)現(xiàn)循環(huán)依賴。n我們不需求

33、擔憂普通的數(shù)據(jù)依賴。例如，在以下循環(huán)中：值估計值估計OpenMP solution #1n可以清楚地看到，在第k次迭代中對第7行的factor的更新和接下來的第k+1次迭代中對第6行的sum的累加是一個循環(huán)依賴。n假設(shè)第k次迭代被分配給一個線裎，而第k+1次迭代被分配給另一個線程，那么我們不能保證第6行中factor的值是正確的。solution #1的修復？還有錯誤？n在一個曾經(jīng)被parallel for指令并行化的塊中，缺省情況下任何在循環(huán)前聲明的變量獨一的例外是循環(huán)變量在線程間都是共享的。因此factor被共享。n例如，線程0能夠會給它賦值1，但在它能用這個值更新sum前，線程1能夠給它

34、賦值-1了。OpenMP solution #2n除了消除計算factor時的循環(huán)依賴外，我們還需求保證每個線程有它本人的factor副本。n就是說，為了使代碼正確，我們需求保證factor有私有作用域。經(jīng)過添加一個private子句到parallel指令中來實現(xiàn)這一目的。留意的地方n一個有私有作用域的變量的值在parallel塊或者parallel for塊的開場處是未指定的。它的值在parallel或parallel for塊完成之后也是未指定的。子句defaultn與其讓OpenMP決議每個變量的作用域，還不如讓程序員明確塊中每個變量的作用域。假設(shè)我們添加子句n到parallel或par

35、allel for指令中，那么編譯器將要求我們明確在這個塊中運用的每個變量和曾經(jīng)在塊之外聲明的變量的作用域。在一個塊中聲明的變量時私有的，由于它們會被分配給線程的棧子句defaultn在這個例子中，我們在for循環(huán)中運用4個變量。由于default子句，我們需求明確每個變量的作用域。更多關(guān)于OpenMP的循環(huán)：排序More About Loops in OpenMP: Sorting冒泡排序冒泡排序中的循環(huán)依賴n在外部循環(huán)中有一個循環(huán)依賴，在外部循環(huán)的任何一次迭代中，當前列表的內(nèi)容依賴于外部循環(huán)的前一次迭代。n例如，假設(shè)在算法開場時，a =3，4，1，2，那么外部循環(huán)的第二次迭代將對列表3，1

36、，2進展操作，由于4在第一次迭代中應(yīng)該曾經(jīng)被挪動到列表的最后了。但假設(shè)前兩次迭代同時執(zhí)行，那么有能夠第二次迭代的有效列表包含4。n內(nèi)部循環(huán)的循環(huán)依賴也很容易發(fā)現(xiàn)。奇偶變換排序n奇偶變換排序是一個與冒泡排序類似的算法，但它相對來說更容易并行化。奇偶變換排序的例子奇偶變換排序的循環(huán)依賴n外部循環(huán)有一個循環(huán)依賴。我們尚不清楚如何消除這個循環(huán)依賴，因此并行化外部for循環(huán)不是一個好的選擇。n 但是，內(nèi)部for循環(huán)并沒有任何循環(huán)依賴。例如，在偶階段循環(huán)中，假設(shè)變量i是奇數(shù)，所以對于兩個不同的i值，例如，i =j和i=k，j-1，j和k-1，k將是不同的。并行化奇偶變換排序潛在的問題n首先，雖然任何一個偶

37、階段迭代并不依賴任何這個階段的其他迭代，但是還需求留意，對p階段和p+1階段卻不是這樣的。n我們需求確定在任何一個線程開場p+1階段之前，一切的線程必需先完成p階段。然而，像parallel指令那樣，parallel for指令在循環(huán)終了處有一個隱式的路障，因此，在一切的線程完成當前階段即階段p之前，沒有線程可以進入下一個階段，即p+1階段。潛在的問題2n創(chuàng)建和合并線程的開銷。OpenMP實現(xiàn)能夠會在每一遍外部循環(huán)都創(chuàng)建和合并thread_count個線程。n下表顯示了當輸入列表包含20 000個元素時，在我們系統(tǒng)上運轉(zhuǎn)1、2、3、4個線程的運轉(zhuǎn)時間。能否能做得更好？n每次執(zhí)行內(nèi)部循環(huán)時，運用

38、同樣數(shù)量的線程。因此只創(chuàng)建一次線程，并在每次內(nèi)部循環(huán)的執(zhí)行中重用它們，這樣做能夠更好。nOpenMP提供了允許這樣做的指令。用parallel指令在外部循環(huán)前創(chuàng)建thread_count個線程的集合。然后，我們不在每次內(nèi)部循環(huán)執(zhí)行時創(chuàng)建一組新的線程，而是運用一個for指令，通知OpenMP用已有的線程組來并行化for循環(huán)。并行化奇偶變換排序的第二個版本性能的提升n與parallel for指令不同的是，for 指令并不創(chuàng)建任何線程。它運用曾經(jīng)在parallel塊中創(chuàng)建的線程。在循環(huán)的末尾有一個隱式的路障。代碼的結(jié)果最終列表將因此與原有的并行化代碼所得到的結(jié)果一樣?？?7%練習n用OpenMP編

39、寫完好的奇偶變換并行排序程序n提示：循環(huán)調(diào)度Scheduling Loops回想n 當?shù)谝淮斡龅絧arallel for指令時，我們看到將各次循環(huán)分配給線程的操作是由系統(tǒng)完成的。n然而，大部分的OpenMP實現(xiàn)只是粗略地運用塊分割：假設(shè)在串行循環(huán)中有n次迭代，那么在并行循環(huán)中，前n/thread_count個迭代分配給線程0，接下來的n/thread_count個迭代分配給線程1，以此類推。n不難想到，這種分配方式一定不是最優(yōu)的。一個例子n例如，假設(shè)我們想要并行化循環(huán)：n同時，假設(shè)對f函數(shù)調(diào)用所需求的時間與參數(shù)i的大小成正比，那么與分配給線程0的任務(wù)相比，分配給線程thread_count -

40、1的任務(wù)量相對較大。循環(huán)劃分n一個更好的分配方案是輪番分配線程的任務(wù)循環(huán)劃分。n在循環(huán)劃分中，各次迭代被“輪番地一次一個地分配給線程：假設(shè)t= thread_count。那么一個循環(huán)劃分將如下分配各次迭代：測試程序n為了了解這樣的分配是如何影響性能的，我們編寫了如下程序：測試結(jié)果n每次函數(shù)f(i)調(diào)用i次sin函數(shù)。例如，執(zhí)行f(2i)的時間幾乎是執(zhí)行f(i)的時間的兩倍。nn = 10,000none threadnrun-time = 3.67 seconds.測試結(jié)果nn = 10,000ntwo threadsndefault assignment nrun-time = 2.76 s

41、econdsnspeedup = 1.33nn = 10,000ntwo threadsncyclic assignment nrun-time = 1.84 secondsnspeedup = 1.99schedule子句n我們看到一個好的迭代分配可以對性能有很大的影響。在OpenMP中，將循環(huán)分配給線程稱為調(diào)度，schedule子句用于在parallel for或者for指令中進展迭代分配。schedule子句n缺省調(diào)度(Default schedule):n循環(huán)調(diào)度(Cyclic schedule):schedule子句的類型n普通而言，schedule子句有如下方式：ntype可以是以

42、下恣意一個：n 1. static。迭代可以在循環(huán)執(zhí)行前分配給線程。n 2. dynamic或guided。迭代在循環(huán)執(zhí)行時被分配給線程，因此在一個線程完成了它的當前迭代集合后，它能從運轉(zhuǎn)時系統(tǒng)中懇求更多。n 3. auto。編譯器和運轉(zhuǎn)時系統(tǒng)決議調(diào)度方式。n 4. runtime。調(diào)度在運轉(zhuǎn)時決議。nchunksize是一個正整數(shù)。在OpenMP中，迭代塊是在順序循環(huán)中延續(xù)執(zhí)行的一塊迭代語句，塊中的迭代次數(shù)是chunksize。static調(diào)度類型n對于static調(diào)度，系統(tǒng)以輪轉(zhuǎn)的方式分配chunksize塊個迭代給每個線程。twelve iterations, 0, 1, . . . ,

43、 11, and three threadsstatic調(diào)度類型twelve iterations, 0, 1, . . . , 11, and three threadsstatic調(diào)度類型twelve iterations, 0, 1, . . . , 11, and three threadsdynamic調(diào)度類型n在dynamic調(diào)度中，迭代也被分成chunksize個延續(xù)迭代的塊。n每個線程執(zhí)行一塊，并且當一個線程完成一塊時，它將從運轉(zhuǎn)時系統(tǒng)懇求另一塊，直到一切的迭代完成。nChunksize可以被忽略。當它被忽略時，chunksize為1。guided調(diào)度類型n在guided調(diào)度中

44、，每個線程也執(zhí)行一塊，并且當一個線程完成一塊時，將懇求另一塊。n然而，在guided調(diào)度中，當塊完成后，新塊的大小會變小。n在guided調(diào)度中，假設(shè)沒有指定chunksize，那么塊的大小為1；假設(shè)指定了chunksize，那么塊的大小就是chunksize，除了最后一塊的大小可以比chunksize小。例子n例如，在我們的系統(tǒng)上，假設(shè)用parallel for指令和schedule(guided)子句來運轉(zhuǎn)梯形積分法程序那么當n=10 000并且thread_count =2時，迭代將如表5-3那樣分配。n塊的大小近似等于剩下的迭代數(shù)除以線程數(shù)。第一塊的大小為9999/25000，由于有9

45、999個未被分配的迭代。第二塊的大小為4999/22500，以此類推。runtime調(diào)度類型n當schedule(runtime)指定時，系統(tǒng)運用環(huán)境變量OMP_SCHEDULE在運轉(zhuǎn)時來決議如何調(diào)度循環(huán)。nOMP_SCHEDULE環(huán)境變量會呈現(xiàn)任何能被static、dynamic或guided調(diào)度所運用的值。n例如，假設(shè)在程序中有一條parallel for指令，并且它曾經(jīng)被schedule(runtime)修正了，那么假設(shè)運用bash shell，就能經(jīng)過執(zhí)行以下命令將一個循環(huán)分配所得到的迭代分配給線程：n如今，當開場執(zhí)行程序時，系統(tǒng)將調(diào)度for循環(huán)的迭代，就好像運用子句schedule(

46、static，1)修正了parallel for指令那樣。 調(diào)度選擇n假設(shè)需求并行化一個for循環(huán)，那么我們?nèi)绾螞Q議運用哪一種調(diào)度和chuncksize的大??？n實踐上，每一種schedule子句有不同的系統(tǒng)開銷。ndynamic調(diào)度的系統(tǒng)開銷要大于static調(diào)度，而guided調(diào)度的系統(tǒng)開銷是三種方式中最大的。因此，假設(shè)不運用schedule子句就曾經(jīng)到達了令人稱心的性能，就不需求再進展多余的任務(wù)。調(diào)度選擇n在本節(jié)開場提供的例子中，在程序運用兩個線程的情況下，運用schedule(static，1)替代默許調(diào)度時，加速比從1. 33添加到1.99。n由于在兩個線程的條件下，加速比幾乎不能夠

47、比1.99更好，所以我們可以不用再嘗試其他的調(diào)庋方式，至少在只用兩個線程并且迭代數(shù)為10 000的情況下是這樣。調(diào)度選擇的一些準那么n假設(shè)循環(huán)的每次迭代需求幾乎一樣的計算量，那么能夠默許的調(diào)度方式能提供最好的性能。n假設(shè)隨著循環(huán)的進展，迭代的計算量線性遞增或者遞減，那么采用比較小的chuncksize的static調(diào)度能夠會提供最好的性能。n假設(shè)每次迭代的開銷事先不能確定，那么就能夠需求嘗試運用多種不同的調(diào)度戰(zhàn)略。在這種情況下，該當運用schedule( runtime)子句，經(jīng)過賦予環(huán)境變量OMP_SCHEDULE不同的值來比較不同調(diào)度戰(zhàn)略下程序的性能。消費者和消費者問題Producers

48、and Consumers消費者和消費者問題n本節(jié)將討論一個不適宜用parallel for指令或者for指令來并行化的問題。隊列n隊列是一種籠統(tǒng)的數(shù)據(jù)構(gòu)造，插入元素時將元素插入到隊列的“尾部，而讀取元素時，隊列“頭部的元素被前往并從隊列中被移除。n隊列可以看做是在超市中等待付款的消費者的籠統(tǒng)，隊列中的元素是消費者。新的消費者到達時排在等待隊列的尾部，下一個付款分開等待隊列的是排在隊列頭部的消費者。n當一個新的元素插入到隊列的尾部時，通常稱這個新的元素“入隊了；當一個元素從隊列 的頭部被移除時，通常稱這個元素“出隊了。隊列n隊列也是在多線程運用程序中經(jīng)常運用到的數(shù)據(jù)構(gòu)造。n例如，我們有幾個“消

49、費者線程和幾個“消費者線程。n消費者線程“產(chǎn)生對效力器數(shù)據(jù)的懇求例如當前股票的價錢，而消費者線程經(jīng)過發(fā)現(xiàn)和生成數(shù)據(jù)例如，當前股票的價錢來“消費懇求。消費者線程將懇求入隊，而消費者線程將懇求從隊列中移出。n在這個例子中，只需當消費者線程將懇求的數(shù)據(jù)發(fā)送給消費者線程時，進程才會終了。音訊傳送n消費者和消費者問題模型的另外一個運用是在共享內(nèi)存系統(tǒng)上實現(xiàn)音訊傳送。n每一個線程有一個共享音訊隊列，當一個線程要向另外一個線程“發(fā)送音訊時，它將音訊放入目的線程的音訊隊列中。一個線程接納音訊時只需從它的音訊隊列的頭部取出音訊。n這里我們將實現(xiàn)一個簡單的音訊傳送程序，在這個程序中，每個線程隨機產(chǎn)生整數(shù)“音訊和音

50、訊的目的線程。音訊傳送n當創(chuàng)建一條音訊后，線程將音訊參與到適宜的音訊隊列中。當發(fā)送音訊之后，該線程查看它本人的音訊隊列以獲知它能否收到了音訊，假設(shè)它收到了音訊，它將隊首的音訊出隊并打印該音訊。n每個線程交替發(fā)送和接納音訊，用戶需求指定每個線程發(fā)送音訊的數(shù)目。n當一個線程發(fā)送完一切的音訊后，該線程不斷接納音訊直到其他一切的線程都已完成，此時一切的線程都終了了。音訊傳送發(fā)送音訊Send_msg()n需求留意的是，訪問音訊隊列并將音訊人隊，能夠是一個臨界區(qū)。n雖然我們還沒有深化地研討如何實現(xiàn)音訊隊列，但我們很有能夠需求用一個變量來跟蹤隊列的尾部。n例如，運用一個單鏈表來實現(xiàn)音訊隊列，鏈表的尾部對應(yīng)著

51、隊列的尾部。然后，為了有效地進展人隊操作，需求存儲指向鏈表尾部的指針。n當一條新音訊入隊時，需求檢查和更新這個隊尾指針。假設(shè)兩個線程試圖同時進展這些操作，那么能夠會喪失一條曾經(jīng)由其中一個線程入隊的音訊。發(fā)送音訊Send_msg()nSend_msg()函數(shù)的偽代碼如下：接納音訊Try_receive()n接納音訊的同步問題與發(fā)送音訊有些不同。只需音訊隊列的擁有者即目的線程可以從給定的音訊隊列中獲取音訊。n假設(shè)音訊隊列中至少有兩條音訊，那么只需每次只出隊一條音訊，那么出隊操作和入隊操作就不能夠沖突。因此假設(shè)隊列中至少有兩條音訊，經(jīng)過跟蹤隊列的大小就可以防止任何同步例如critical指令。接納音

52、訊Try_receive()n如今的問題是如何存儲隊列大小。n假設(shè)只運用一個變量來存儲隊列的大小，那么對該變量的操作會構(gòu)成臨界區(qū)。然而可以運用兩個變量：enqueued和dequeued，那么隊列中音訊的個數(shù)隊列的大小就為n獨一可以更新dequeued的線程是音訊隊列的擁有者?？梢钥吹皆谝粋€線程運用enqueued計算隊列大小queue_size的同時，另外一個線程可以更新enqueued。接納音訊Try_receive()終止檢測Done()n接下來，我們討論如何實現(xiàn)Done函數(shù)。首先，我們給出一個“直接的實現(xiàn)，但這個實現(xiàn)隱藏著問題：n假設(shè)線程u執(zhí)行這段代碼，那么很有能夠有些線程，如線程v，

53、在線程u計算出queue_size=0后向線程u發(fā)送一條音訊。當然，線程u在得出queue_size=0后將終止，那么線程v發(fā)送給它的音訊就永遠不會被接納到。終止檢測Done()n在我們的程序中，每個線程在執(zhí)行完for循環(huán)后將不再發(fā)送任何音訊。因此可以添加一個計數(shù)器done_sending，每個線程在for循環(huán)終了后將該計數(shù)器加1，Done的實現(xiàn)如下：啟動n當程序開場執(zhí)行時，主線程將得到命令行參數(shù)并且分配一個數(shù)組空間給音訊隊列，每個線程對應(yīng)著一個音訊隊列。n由于每個線程可以向其他恣意的線程發(fā)送音訊，所以這個數(shù)組應(yīng)該被一切的線程共享，而且每個線程可以向任何一個音訊隊列插入一條音訊。啟動n音訊隊列

54、至少可以存儲：n 音訊列表n 隊尾指針或索引n 隊首指針或索引n 入隊音訊的數(shù)目n 出隊音訊的數(shù)目啟動同步n這里一個重要的問題是：一個或者多個線程能夠在其他線程之前完成它的隊列分配。n假設(shè)這種情況出現(xiàn)了，那么完成分配的線程酉能會試圖開場向那些還沒有完成隊列分配的線程發(fā)送音訊，這將導致程序解體。n因此，我們必需確保任何一個線程都必需在一切的線程都完成了隊列分配后才開場發(fā)送音訊。atomic指令n發(fā)送完一切的音訊后，每個線程在執(zhí)行最后的循環(huán)以便接納音訊之前，需求對done_sendng加1。n顯然，對done_sending的增量操作是臨界區(qū)，可以經(jīng)過critical指令來維護它。nOpenMP提

55、供了另外一種能夠更加高效的指令：atomic指令：atomic指令n與critical指令不同，它只能維護由一條C言語賦值語句所構(gòu)成的臨界區(qū)。n此外，語句必需是以下幾種方式之一：n可以是以下恣意的二元操作符：atomic指令n需求留意的是，只需x的裝載和存儲可以確保是受維護的，例如在下面的代碼中：n其他線程對x的更新必需等到該線程對x的更新終了之后。但是對y的更新不受維護，因此程序的結(jié)果是不可預測的。natomic指令的思想是許多處置器提供專門的裝載-修正-存儲(load - modify - store)指令。運用這種專門的指令而不運用維護臨界區(qū)的通用構(gòu)造，可以更高效地維護臨界區(qū)。臨界區(qū)n在

56、前面的例子里面，我們看到三個臨界區(qū)：n然而，我們不需求強迫對3個代碼塊都進展互斥訪問，甚至不需求強迫對第2個和第3個代碼塊進展完全的互斥訪問。n例如，線程0在向線程1的音訊隊列寫音訊的同時，線程1可以向線程2的音訊隊列寫音訊。臨界區(qū)n根據(jù)OpenMP的規(guī)定，第2個和第3個代碼塊是被critical指令維護的代碼塊。n在OpenMP看來，我們的程序有兩個不同的臨界區(qū)：被atomic指令維護的done_sending+和“復合臨界區(qū)。在“復合臨界區(qū)中，程序讀取和發(fā)送音訊。n 強迫線程間的互斥會使程序的執(zhí)行串行化。OpenMP默許的做法是將一切的臨界區(qū)代碼塊作為復合臨界區(qū)的一部分，這能夠非常不利于程

57、序的性能。臨界區(qū)nOpenMP提供了向critical指令添加名字的選項：n采取這種方式，兩個用不同名字的critical指令維護的代碼塊就可以同時執(zhí)行。n但！臨界區(qū)的名字是在程序編譯過程中設(shè)置的。當我們想讓訪問不同隊列的線程可以同時訪問一樣的代碼塊時，被命名的critical指令就不能滿足我們的要求了。鎖n鎖由一個數(shù)據(jù)構(gòu)造和定義在這個數(shù)據(jù)構(gòu)造上的函數(shù)組成，這些函數(shù)使得程序員可以顯式地強迫對臨界區(qū)進展互斥訪問。鎖的運用n鎖的運用可以大約用下面的偽代碼n鎖的數(shù)據(jù)構(gòu)造被執(zhí)行臨界區(qū)的線程所共享，這些線程中的某個線程如主線程會初始化鎖。而當一切的線程都運用完鎖后，某個線程該當擔任銷毀鎖。鎖的運用n在一

58、個線程進入臨界區(qū)前，它嘗試經(jīng)過調(diào)用鎖函數(shù)來上鎖(set)。假設(shè)沒有其他的線程正在執(zhí)行臨界區(qū)的代碼，那么它將獲得鎖并進入臨界區(qū)。當該線程執(zhí)行完臨界區(qū)的代碼后，它調(diào)用解鎖函數(shù)釋放relinquish或者unset鎖，以便其他線程可以獲得鎖。n當一個線程擁有鎖時，其他的線程都不能進入該臨界區(qū)。其他線程嘗試經(jīng)過調(diào)用鎖函數(shù)進入該臨界區(qū)時會被阻塞。假設(shè)有多個線程被鎖函數(shù)阻塞，那么當臨界區(qū)的線程釋放鎖時，這些線程中的某個線程會獲得鎖，而其他線程仍被阻塞。簡單鎖nOpenMP簡單鎖的類型是omp_lock_t，定義簡單鎖的函數(shù)包括：在音訊傳送程序中運用鎖n在前面對critical指令缺乏之處的討論中，我們看到

59、，在音訊傳送程序中，我們想要確保的是對每個音訊隊列進展互斥訪問，而不是對于一個特定的代碼塊。n鎖可以協(xié)助我們實現(xiàn)這個目的。將omp_lock_t類型的數(shù)據(jù)成員包含在隊列構(gòu)造中，可以經(jīng)過簡單地調(diào)用omp_set_lock函數(shù)來確保對音訊隊列的互斥訪問。在音訊傳送程序中運用鎖在音訊傳送程序中運用鎖critical指令、atomic指令、鎖的比較n到目前為止，有三種機制可以實現(xiàn)對臨界區(qū)的訪問，很自然地我們想知道在不同的情況下該當采取哪一種方法。n普通而言，atomic指令是實現(xiàn)互斥訪問最快的方法。因此，假設(shè)臨界區(qū)由特定方式的賦值語句組成，那么運用atomic指令至少不會比運用其他方法慢。critic

60、al指令、atomic指令、鎖的比較nOpenMP規(guī)范允許atomic指令對程序中圻有atomic指令標志的臨界區(qū)進展強迫互斥訪問這是未命名的critical指令的任務(wù)方式。n假設(shè)這種行為不能滿足要求例如，程序中有多個不同的由atomic指令維護的臨界區(qū)那么該當運用命名的critical指令或者鎖。critical指令、atomic指令、鎖的比較n不論是未命名的critical指令還是命名的critical指令都非常易于運用。n此外，在我們所運用到的OpenMP的實現(xiàn)中，運用critical指令維護臨界區(qū)與運用鎖維護臨界區(qū)在性能上沒有太大的差別。n所以，假設(shè)我們在無法運用atomic指令，卻可以運用criti