高性能計(jì)算導(dǎo)論-第五章ppt課件

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

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

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

4、預(yù)處置器指令一樣，pragma的默許長(zhǎng)度是一行，因此假設(shè)有一個(gè)pragma在一行中放不下，那么新行需求被“本義前面加一個(gè)反斜杠“。n#pragma后面要跟什么內(nèi)容，完全取決于正在運(yùn)用哪些擴(kuò)展比如OpenMP。運(yùn)轉(zhuǎn)OpenMP程序n應(yīng)該留意到線程正在競(jìng)爭(zhēng)訪問(wèn)規(guī)范輸出，因此不保證輸出會(huì)按線程編號(hào)的順序出現(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我們來(lái)看一下程序5-1中的源代碼。n除了指令集合外，OpenMP由一個(gè)函數(shù)和宏庫(kù)組成，因此我們通常需求包含一個(gè)有原型和宏定義的頭文件。OpenMP的頭文件是omp.h，程序的第3行包含了它。指定線程數(shù)n在Pth

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

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

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

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

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

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

12、器不支持OpenMP，那么它將只忽略parallel指令。n然而，試圖包含omp.h頭文件以及調(diào)用omp_get_thread_num和omp_get_num_threads將引起錯(cuò)誤。為了處置這些問(wèn)題，可以檢查預(yù)處置器宏_OPENMP能否認(rèn)義。假設(shè)定義了，那么我們可以包含omp.h并調(diào)用OpenMP函數(shù)。我們能夠?qū)Τ绦蜃鲆韵滦拚?。錯(cuò)誤檢查n我們可以在試圖包含omp.h之前先檢查_(kāi)OPENMP的定義# include #ifdef _OPENMP# include #endif錯(cuò)誤檢查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我們來(lái)看一個(gè)更適用也更復(fù)雜的例子：用梯形積分法估計(jì)曲線下方所包圍的面積。串行算法n 再回想一下，假設(shè)每個(gè)子區(qū)間有同樣的寬度h，并且定義h=(b-a)/n，x_i=a+i*h，i=0，1，n，那么近似值將是：Foster的并行程序設(shè)計(jì)方法n(1)識(shí)別兩類義務(wù)：n a. 單

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、滿足上述所列舉規(guī)那么中的任何一條，那么編譯器將簡(jiǎn)單地回絕它。例如，假設(shè)我們?cè)噲D編譯一個(gè)線性查找程序：n編譯器將報(bào)告：隱藏的數(shù)據(jù)依賴性n一個(gè)更隱匿的問(wèn)題發(fā)生在如下的循環(huán)中：在該循環(huán)中，迭代中的計(jì)算依賴于一個(gè)或更多個(gè)先前的迭代結(jié)果。n例如，計(jì)算前n個(gè)斐波那契(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似乎運(yùn)轉(zhuǎn)時(shí)系統(tǒng)將fibo2、fibo3、fibo4和fibo5的計(jì)算分配給了一個(gè)線程，將fibo6、fibo7、fibo8、fibo9分配給了另一個(gè)線程。n在程序的一些運(yùn)轉(zhuǎn)結(jié)果中，結(jié)果之所以正確是由于被分配給fibo2、fibo3、fibo4和fibo5的線程在另一個(gè)線程開(kāi)場(chǎng)前就完成了計(jì)算。n然而，對(duì)于其他運(yùn)轉(zhuǎn)結(jié)

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

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

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

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

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

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

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

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

40、1的任務(wù)量相對(duì)較大。循環(huán)劃分n一個(gè)更好的分配方案是輪番分配線程的任務(wù)循環(huán)劃分。n在循環(huán)劃分中，各次迭代被“輪番地一次一個(gè)地分配給線程：假設(shè)t= thread_count。那么一個(gè)循環(huán)劃分將如下分配各次迭代：測(cè)試程序n為了了解這樣的分配是如何影響性能的，我們編寫(xiě)了如下程序：測(cè)試結(jié)果n每次函數(shù)f(i)調(diào)用i次sin函數(shù)。例如，執(zhí)行f(2i)的時(shí)間幾乎是執(zhí)行f(i)的時(shí)間的兩倍。nn = 10,000none threadnrun-time = 3.67 seconds.測(cè)試結(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我們看到一個(gè)好的迭代分配可以對(duì)性能有很大的影響。在OpenMP中，將循環(huán)分配給線程稱為調(diào)度，schedule子句用于在parallel for或者for指令中進(jìn)展迭代分配。schedule子句n缺省調(diào)度(Default schedule):n循環(huán)調(diào)度(Cyclic schedule):schedule子句的類型n普通而言，schedule子句有如下方式：ntype可以是以

42、下恣意一個(gè)：n 1. static。迭代可以在循環(huán)執(zhí)行前分配給線程。n 2. dynamic或guided。迭代在循環(huán)執(zhí)行時(shí)被分配給線程，因此在一個(gè)線程完成了它的當(dāng)前迭代集合后，它能從運(yùn)轉(zhuǎn)時(shí)系統(tǒng)中懇求更多。n 3. auto。編譯器和運(yùn)轉(zhuǎn)時(shí)系統(tǒng)決議調(diào)度方式。n 4. runtime。調(diào)度在運(yùn)轉(zhuǎn)時(shí)決議。nchunksize是一個(gè)正整數(shù)。在OpenMP中，迭代塊是在順序循環(huán)中延續(xù)執(zhí)行的一塊迭代語(yǔ)句，塊中的迭代次數(shù)是chunksize。static調(diào)度類型n對(duì)于static調(diào)度，系統(tǒng)以輪轉(zhuǎn)的方式分配chunksize塊個(gè)迭代給每個(gè)線程。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個(gè)延續(xù)迭代的塊。n每個(gè)線程執(zhí)行一塊，并且當(dāng)一個(gè)線程完成一塊時(shí)，它將從運(yùn)轉(zhuǎn)時(shí)系統(tǒng)懇求另一塊，直到一切的迭代完成。nChunksize可以被忽略。當(dāng)它被忽略時(shí)，chunksize為1。guided調(diào)度類型n在guided調(diào)度中

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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