并行區(qū)域

1、第四章 OpenMP多線程編程,主要內(nèi)容,OpenMP編程簡(jiǎn)介 OpenMP多線程應(yīng)用程序編程技術(shù),1. OpenMP編程簡(jiǎn)介,,1.1 OpenMP多線程編程發(fā)展概況,OpenMP是一種面向共享內(nèi)存多線程并行編程技術(shù)OpenMP具有良好的可移植性支持多種編程語(yǔ)言 Fortran C/C++支持多種平臺(tái) www.openmp.org,,OpenMP最初是為共享內(nèi)存的多處理器系統(tǒng)設(shè)計(jì)的并行編程方法，這與通過(guò)消息傳遞進(jìn)行并行編程

2、模型有很大的不同。,OpenMP的支持環(huán)境,Intel的C++和Fortran編譯器Microsoft的Visual Studio 2005gcc4.2以上版本,1.2 OpenMP多線程編程基礎(chǔ),OpenMP的編程模型以線程為基礎(chǔ)，通過(guò)編譯制導(dǎo)語(yǔ)句來(lái)顯示地指導(dǎo)并行化 OpenMP的執(zhí)行模型采用Fork-Join的形式，在開(kāi)始時(shí)，只有一個(gè)叫做主線程的運(yùn)行線程存在；在運(yùn)行過(guò)程中，當(dāng)遇到需要進(jìn)行并行計(jì)算的時(shí)候，派生出（Fork）線程來(lái)

3、執(zhí)行并行任務(wù)；在并行代碼結(jié)束執(zhí)行，派生線程退出或掛起，控制流程回到單獨(dú)的主線程中（Join）,Fork-Join模型,并行區(qū)域,OpenMP的實(shí)現(xiàn),編譯制導(dǎo)語(yǔ)句（精髓）運(yùn)行時(shí)庫(kù)函數(shù)環(huán)境變量,編譯制導(dǎo)語(yǔ)句,在編譯器編譯程序的時(shí)候，會(huì)識(shí)別特定的注釋，而這些注釋就包含著OpenMP程序的一些語(yǔ)義 在一個(gè)無(wú)法識(shí)別OpenMP語(yǔ)意的普通編譯器中，這些注釋會(huì)被當(dāng)作普通的注釋而被忽略 在C/C++程序中，OpenMP所有編譯制導(dǎo)語(yǔ)句以#pra

4、gma omp開(kāi)始，后面跟具體功能指令,編譯制導(dǎo)語(yǔ)句,,編譯制導(dǎo)語(yǔ)句,Directiveparallel, for, parallel for, section, sections, single, master, critical, flush, ordered, atomic,運(yùn)行時(shí)庫(kù)函數(shù),OpenMP運(yùn)行時(shí)函數(shù)庫(kù)主要用以設(shè)置和獲取執(zhí)行環(huán)境相關(guān)的信息，它們當(dāng)中也包含一系列用以同步的API 運(yùn)行時(shí)函數(shù)庫(kù) “omp.h”omp

5、_get_thread_num() 返回當(dāng)前線程的號(hào)碼,,通過(guò)編譯制導(dǎo)語(yǔ)句,可以將串行的程序逐步地改造成一個(gè)并行程序,達(dá)到增量更新程序的目的,減少程序編寫(xiě)人員一定的負(fù)擔(dān).串行程序和并行程序保持在同一個(gè)源代碼文件當(dāng)中,減少了維護(hù)負(fù)擔(dān).編譯制導(dǎo)語(yǔ)句,優(yōu)勢(shì)體現(xiàn)在編譯階段運(yùn)行時(shí)庫(kù)函數(shù),支持運(yùn)行時(shí)對(duì)并行環(huán)境的改變和優(yōu)化,1.3 編寫(xiě)OpenMP程序的準(zhǔn)備工作,當(dāng)前的Visual Studio .Net 2005完全支持OpenMP 2.0

6、標(biāo)準(zhǔn) 通過(guò)新的編譯器選項(xiàng) /openmp來(lái)支持OpenMP程序的編譯和鏈接,建立一個(gè)新的項(xiàng)目,配置項(xiàng)目屬性,設(shè)置環(huán)境變量,在OpenMP中，主要通過(guò)對(duì)循環(huán)或一段結(jié)構(gòu)化代碼定義并行區(qū)域的方式來(lái)實(shí)現(xiàn)多線程并行。,#include "omp.h"int _tmain(int argc, _TCHAR* argv[]){printf("Hello from serial.\n");prin

7、tf("Thread number=%d\n",omp_get_thread_num());#pragma omp parallel{printf("Hello from parallel. Thread number=%d\n", omp_get_thread_num());}printf("Hello from serial again.\n");

8、getchar();return 0;},2. OpenMP多線程應(yīng)用程序編程技術(shù),,2.1 循環(huán)并行化,循環(huán)并行化是使用OpenMP來(lái)并行化程序的最重要的部分 在C/C++語(yǔ)言中，循環(huán)并行化語(yǔ)句的編譯制導(dǎo)語(yǔ)句格式如下： #pragma omp parallel for [clause[clause…]]for（ i = first ; i<last ; i++） {body of the loop;},另

9、一種格式： #pragma omp parallel [clause[clause…]]{#pragma omp for [clause[clause…]]for（ i = first ; i<last ; i++） {body of the loop;}}如果并行的線程需要在循環(huán)的開(kāi)始，或結(jié)束時(shí)作些工作的話，就只能用parallel與for子句分離的版本。Parallel 將緊跟的程序塊擴(kuò)展為若干完全等同

10、的并行區(qū)域，每個(gè)線程擁有完全相同的并行區(qū)域；For 將循環(huán)中工作分配到線程組中，線程組中的每一個(gè)線程完成循環(huán)中的一部分。子句用來(lái)控制編譯制導(dǎo)語(yǔ)句的具體行為。,循環(huán)并行化語(yǔ)句的限制,并行化的語(yǔ)句必須是for循環(huán)語(yǔ)句并具有規(guī)范格式 能夠推測(cè)出循環(huán)的次數(shù) for （index = start ; index < end ; increment_expr）在循環(huán)過(guò)程中不能使用break語(yǔ)句 不能使用goto和return語(yǔ)句從

11、循環(huán)中跳出 可以使用continue語(yǔ)句,簡(jiǎn)單循環(huán)并行化,各個(gè)分量之間沒(méi)有數(shù)據(jù)相關(guān)性循環(huán)計(jì)算的過(guò)程也沒(méi)有循環(huán)依賴型,循環(huán)依賴性,循環(huán)迭代相關(guān),循環(huán)迭代相關(guān),,,循環(huán)分塊技術(shù)創(chuàng)建無(wú)循環(huán)迭代相關(guān)的循環(huán)m,,循環(huán)并行化編譯制導(dǎo)語(yǔ)句的子句,循環(huán)并行化子句可以包含一個(gè)或者多個(gè)子句來(lái)控制循環(huán)并行化的實(shí)際執(zhí)行 常見(jiàn)子句有：作用域子句（變量是共享的share還是私有的private）控制線程的調(diào)度（schedule ）子句動(dòng)態(tài)控制是否并行化

12、（if ）子句進(jìn)行同步的子句（ordered ）子句控制變量在串行部分與并行部分傳遞（copyin ）子句,循環(huán)嵌套,可以將嵌套循環(huán)的任意一個(gè)循環(huán)體進(jìn)行并行化 循環(huán)并行化編譯指導(dǎo)語(yǔ)句可以加在任意一個(gè)循環(huán)之前，則對(duì)應(yīng)的最近的循環(huán)語(yǔ)句被并行化，其它部分保持不變,,,,,控制數(shù)據(jù)的共享屬性,OpenMP程序在同一個(gè)共享內(nèi)存空間上執(zhí)行 可以任意使用這個(gè)共享內(nèi)存空間上的變量進(jìn)行線程間的數(shù)據(jù)傳遞 OpenMP還允許線程保留自己的私有變量不

13、能讓其它線程訪問(wèn)到,,分配在棧上的數(shù)據(jù)都是私有的全局變量及代碼是共享的動(dòng)態(tài)分配的堆空間是共享的threadprivate指明某數(shù)據(jù)結(jié)構(gòu)是私有的全局變量,控制數(shù)據(jù)的共享屬性,shared用來(lái)指示一個(gè)變量的作用域是共享的。privare用來(lái)指示一個(gè)變量的作用域是私有的。firstprivate對(duì)私有變量進(jìn)行初始化，把串行變量值拷貝到私有變量中（線程開(kāi)始）lastprivate對(duì)私有變量最后終結(jié)的操作，把私有變量拷貝到同名串行變量

14、中,使用作用域子句的一些規(guī)則,作用域子句中的變量是已經(jīng)聲明的有名變量 作用域子句在作用到類或者結(jié)構(gòu)的時(shí)候，只能作用到類或者結(jié)構(gòu)的整體，而不能只作用域類或者結(jié)構(gòu)的一個(gè)部分 一個(gè)編譯指導(dǎo)語(yǔ)句能夠包含多個(gè)數(shù)據(jù)作用域子句作用域子句只能出現(xiàn)在編譯制導(dǎo)語(yǔ)句起作用的語(yǔ)句變量部分 默認(rèn)情況下，并行區(qū)域中的所有變量是共享的，三種例外：parallel for 循環(huán)中，循環(huán)變量是私有的并行區(qū)域中的局部變量是私有的Private，firstpr

15、ivate，lastprivate，reduction子句列出的變量是私有的,,,規(guī)約操作的并行化,在規(guī)約操作中，會(huì)反復(fù)將一個(gè)二元運(yùn)算符應(yīng)用在一個(gè)變量和另外一個(gè)值上，并把結(jié)果保存在原變量中 在使用規(guī)約操作時(shí)，只需在變量前指明規(guī)約操作的類型以及規(guī)約的變量 # pragma omp parallel for private（arx,ary,n） reduction（+:a,b）for（i=0;i<n;i++）{a=a+arx

16、[i];b=b+ary[i];},規(guī)約操作并行化的限制,能夠在OpenMP的C/C++語(yǔ)言中出現(xiàn)的規(guī)約操作,私有變量的初始化和終結(jié)操作,循環(huán)并行化開(kāi)始的時(shí)候，私有變量具有主線程中的同名變量的值循環(huán)并行化后將私有變量返回給主線程中的同名變量firstprivate lastprivate,,,數(shù)據(jù)相關(guān)性與并行化操作,并不是所有的循環(huán)都能夠使用#pragma omp parallel for來(lái)進(jìn)行并行化 必須要保證數(shù)據(jù)兩次循

17、環(huán)之間不存在數(shù)據(jù)相關(guān)性 數(shù)據(jù)相關(guān)性又被稱為數(shù)據(jù)競(jìng)爭(zhēng)（Data Race） 當(dāng)兩個(gè)線程對(duì)同一個(gè)變量進(jìn)行操作，并且有一個(gè)操作為寫(xiě)操作的時(shí)候，就說(shuō)明這兩個(gè)線程存在數(shù)據(jù)競(jìng)爭(zhēng),,,2.2 并行區(qū)域編程,循環(huán)并行化實(shí)際上是并行區(qū)域編程的一個(gè)特例 并行區(qū)域簡(jiǎn)單的說(shuō)就是通過(guò)編譯制導(dǎo)語(yǔ)句使得一段代碼能夠在多個(gè)線程內(nèi)部同時(shí)執(zhí)行 并行區(qū)域編寫(xiě)的格式如下：#pragma omp parallel [clause[clause]…]block,

18、parallel編譯制導(dǎo)語(yǔ)句的執(zhí)行過(guò)程,當(dāng)程序遇到parallel編譯制導(dǎo)語(yǔ)句的時(shí)候，就會(huì)生成相應(yīng)數(shù)目（根據(jù)環(huán)境變量）的線程組成一個(gè)線程組，并將代碼重復(fù)地在各個(gè)線程內(nèi)部執(zhí)行 parallel的末尾有一個(gè)隱含的同步屏障（barrier），所有線程完成所需的重復(fù)任務(wù)有，在這個(gè)同步屏障出會(huì)和（join）,,,線程私有數(shù)據(jù)threadprivate,copyin,threadprivate指明(全局)變量是線程私有數(shù)據(jù)copyin對(duì)線程私有

19、的全局變量進(jìn)行初始化,線程私有數(shù)據(jù)與threadprivate, copyin子句,,,工作隊(duì)列,工作隊(duì)列的基本工作過(guò)程：為維持一個(gè)工作的隊(duì)列，線程在并行執(zhí)行的時(shí)候，不斷從這個(gè)隊(duì)列中取出相應(yīng)的工作完成，直到隊(duì)列為空為止,,,,,根據(jù)線程號(hào)分配任務(wù),每一個(gè)線程在執(zhí)行的過(guò)程中的線程標(biāo)識(shí)號(hào)是不同的，可以根據(jù)這個(gè)線程標(biāo)識(shí)號(hào)來(lái)分配不同的任務(wù) #pragma omp parallel private（myid）{nthreads=omp_g

20、et_num_threads（）;myid=omp_get_thread_num（）;get_my_work_done（myid,nthreads）;},使用循環(huán)語(yǔ)句分配任務(wù),,工作分區(qū)編碼,,2.3 線程同步,OpenMP支持兩種不同類型的線程同步機(jī)制 ：互斥鎖：可以用來(lái)保護(hù)一塊共享的存儲(chǔ)空間，使得每一次訪問(wèn)這塊共享內(nèi)存空間的線程最多一個(gè)，保證了數(shù)據(jù)的完整性事件通知：這種機(jī)制保證了多個(gè)線程之間的執(zhí)行順序,數(shù)據(jù)競(jìng)爭(zhēng),,互斥鎖機(jī)

21、制,用來(lái)對(duì)一塊內(nèi)存進(jìn)行保護(hù)OpenMP提供了三種不同的互斥鎖機(jī)制 ：臨界區(qū)（critical）原子操作（atomic）由庫(kù)函數(shù)來(lái)提供同步操作（互斥函數(shù)）,臨界區(qū)（critical）,臨界區(qū)通過(guò)編譯指導(dǎo)語(yǔ)句對(duì)產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)的內(nèi)存變量進(jìn)行保護(hù) 在程序需要訪問(wèn)可能產(chǎn)生競(jìng)爭(zhēng)的內(nèi)存數(shù)據(jù)的時(shí)候，都需要插入相應(yīng)的臨界區(qū)代碼 #pragma omp critical [（name）]block在執(zhí)行上述的程序塊block之前，必須首先

22、要獲得臨界區(qū)的控制權(quán),正整數(shù)組最大的元素,,原子操作,現(xiàn)代體系結(jié)構(gòu)的多處理計(jì)算機(jī)提供了原子更新一個(gè)單一內(nèi)存單元的方法，提供了一種更高效率的互斥鎖機(jī)制。通過(guò)編譯制導(dǎo)可以調(diào)用上述方法#pragma omp atomicx ++,,,運(yùn)行時(shí)庫(kù)函數(shù)的互斥鎖支持,,,,,,事件同步機(jī)制,鎖：維護(hù)一塊代碼或者一塊內(nèi)存的一致性；事件：用來(lái)控制代碼的執(zhí)行順序，使得某一部分代碼必須在其它的代碼執(zhí)行完畢之后才能執(zhí)行。OpenMP中的事件同步主

23、要包括：同步屏障（barrier）定序區(qū)段（ordered sections）主線程執(zhí)行（master）,隱含的同步屏障（barrier）,在每一個(gè)并行區(qū)域都會(huì)有一個(gè)隱含的同步屏障一個(gè)同步屏障要求所有的線程執(zhí)行到此屏障，然后才能夠繼續(xù)執(zhí)行下面的代碼 #pragma omp for，#pragma omp single， #pragma omp sections程序塊都包含自己的隱含的同步屏障 為了避免在循環(huán)過(guò)程中不必要的同步

24、屏障，可以增加nowait子句到相應(yīng)的編譯指導(dǎo)語(yǔ)句中,,,明確的同步屏障語(yǔ)句,在有些情況下，隱含的同步屏障并不能提供有效的同步措施 程序員可以在需要的地方插入明確的同步屏障語(yǔ)句#pragma omp barrier 在并行區(qū)域的執(zhí)行過(guò)程中，所有的執(zhí)行線程都會(huì)在同步屏障語(yǔ)句上進(jìn)行同步 #pragma omp parallel{initialization（）;#pragma omp barrierprocess（）;

25、},,,,,循環(huán)并行化中的順序語(yǔ)句（ordered）,對(duì)于循環(huán)并行化中的某些處理需要規(guī)定執(zhí)行的順序 典型的情況：在一次循環(huán)的過(guò)程中一大部分的工作是可以并行執(zhí)行的，而其余的工作需要等到前面的工作全部完成之后才能夠執(zhí)行 在循環(huán)并行化的過(guò)程中，可以使用ordered子句使得順序執(zhí)行的語(yǔ)句直到前面的循環(huán)都執(zhí)行完畢之后再執(zhí)行,,,OpenMP任務(wù)調(diào)度,OpenMP中，任務(wù)調(diào)度主要用于并行的for循環(huán)中，當(dāng)循環(huán)中每次迭代的計(jì)算量不相等時(shí)，如果

26、簡(jiǎn)單地給各個(gè)線程分配相同次數(shù)的迭代的話，會(huì)造成各個(gè)線程計(jì)算負(fù)載不均衡，這會(huì)使得有些線程先執(zhí)行完，有些后執(zhí)行完，造成某些CPU核空閑，影響程序性能。,int i, j;int a[100][100] = {0};for ( i =0; i < 100; i++){for( j = i; j < 100; j++ ){    a[i][j] = i*j;}} 如果將最外層循環(huán)

27、并行化的話，比如使用4個(gè)線程，如果給每個(gè)線程平均分配25次循環(huán)迭代計(jì)算的話，顯然i＝0和i＝99的計(jì)算量相差了100倍，那么各個(gè)線程間可能出現(xiàn)較大的負(fù)載不平衡情況。,for循環(huán)并行化的任務(wù)調(diào)度方案,schedule子句的使用格式為：schedule(type[,size])type參數(shù)表示調(diào)度類型，有四種調(diào)度類型如下：· static· dynamic· guided·&

28、#160;runtime (實(shí)際上是根據(jù)環(huán)境變量來(lái)選擇前三種中的某中類型。)size參數(shù) (可選) size參數(shù)表示循環(huán)迭代次數(shù)，size參數(shù)必須是整數(shù)。,靜態(tài)調(diào)度(static),當(dāng)parallel for編譯制導(dǎo)語(yǔ)句沒(méi)有帶schedule子句時(shí)，大部分系統(tǒng)中默認(rèn)采用static調(diào)度方式，這種調(diào)度方式非常簡(jiǎn)單。假設(shè)有n次循環(huán)迭代，t個(gè)線程，那么給每個(gè)線程靜態(tài)分配大約n/t次迭代計(jì)算。不使用size參數(shù)時(shí)，分配給每個(gè)線程的是n/

29、t次連續(xù)的迭代,#pragma omp parallel for schedule(static)    for(i = 0; i < 10; i++ )    {         printf("i=%d, thread_id=%d\n", i, omp_get_t

30、hread_num());},i=0, thread_id=0i=1, thread_id=0i=2, thread_id=0i=3, thread_id=0i=4, thread_id=0i=5, thread_id=1i=6, thread_id=1i=7, thread_id=1i=8, thread_id=1i=9, thread_id=1可以看出線程0得到了0～4次連續(xù)迭代，線程1得到5～9次連續(xù)迭代。,

31、#pragma omp parallel for schedule(static, 2)    for(i = 0; i < 10; i++ )    {         printf("i=%d, thread_id=%d\n", i, omp_get_thread

32、_num());},i=0, thread_id=0i=1, thread_id=0i=4, thread_id=0i=5, thread_id=0i=8, thread_id=0i=9, thread_id=0i=2, thread_id=1i=3, thread_id=1i=6, thread_id=1i=7, thread_id=10、1次迭代分配給線程0,每個(gè)線程依次分配到2次連續(xù)的迭代計(jì)算。,動(dòng)態(tài)調(diào)度(d

33、ynamic),動(dòng)態(tài)調(diào)度是動(dòng)態(tài)地將迭代分配到各個(gè)線程，動(dòng)態(tài)調(diào)度可以使用size參數(shù)也可以不使用size參數(shù)，不使用size參數(shù)時(shí)是將迭代逐個(gè)地分配到各個(gè)線程，使用size參數(shù)時(shí)，每次分配給線程的迭代次數(shù)為指定的size次。使用一個(gè)內(nèi)部任務(wù)隊(duì)列，采用先來(lái)先服務(wù)的方式進(jìn)行調(diào)度。當(dāng)某個(gè)線程閑下來(lái)，就為其分配一個(gè)循環(huán)塊。由此可見(jiàn)，動(dòng)態(tài)策略可以極大地保證線程組的負(fù)載平衡，但是需要額外的開(kāi)銷，不能達(dá)到最佳性能。,guided調(diào)度（guided）,

34、guided調(diào)度是一種采用指導(dǎo)性的啟發(fā)式自調(diào)度方法。開(kāi)始時(shí)每個(gè)線程會(huì)分配到較大的迭代塊，之后分配到的迭代塊會(huì)逐漸遞減。迭代塊的大小會(huì)按指數(shù)級(jí)下降到指定的size大小，如果沒(méi)有指定size參數(shù)，那么迭代塊大小最小會(huì)降到1。,runtime調(diào)度（rumtime）,runtime調(diào)度并不是和前面三種調(diào)度方式似的真實(shí)調(diào)度方式，它是在運(yùn)行時(shí)根據(jù)環(huán)境變量OMP_SCHEDULE來(lái)確定調(diào)度類型 例如在unix系統(tǒng)中，可以使用setenv命令來(lái)設(shè)置O