并行區(qū)域

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

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

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

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

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

6、標(biāo)準(zhǔn) 通過新的編譯器選項 /openmp來支持OpenMP程序的編譯和鏈接,建立一個新的項目,配置項目屬性,設(shè)置環(huán)境變量,在OpenMP中，主要通過對循環(huán)或一段結(jié)構(gòu)化代碼定義并行區(qū)域的方式來實現(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來并行化程序的最重要的部分 在C/C++語言中，循環(huán)并行化語句的編譯制導(dǎo)語句格式如下： #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)的開始，或結(jié)束時作些工作的話，就只能用parallel與for子句分離的版本。Parallel 將緊跟的程序塊擴展為若干完全等同

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

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

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

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

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

15、ivate，lastprivate，reduction子句列出的變量是私有的,,,規(guī)約操作的并行化,在規(guī)約操作中，會反復(fù)將一個二元運算符應(yīng)用在一個變量和另外一個值上，并把結(jié)果保存在原變量中 在使用規(guī)約操作時，只需在變量前指明規(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++語言中出現(xiàn)的規(guī)約操作,私有變量的初始化和終結(jié)操作,循環(huán)并行化開始的時候，私有變量具有主線程中的同名變量的值循環(huán)并行化后將私有變量返回給主線程中的同名變量firstprivate lastprivate,,,數(shù)據(jù)相關(guān)性與并行化操作,并不是所有的循環(huán)都能夠使用#pragma omp parallel for來進(jìn)行并行化 必須要保證數(shù)據(jù)兩次循

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

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

19、的全局變量進(jìn)行初始化,線程私有數(shù)據(jù)與threadprivate, copyin子句,,,工作隊列,工作隊列的基本工作過程：為維持一個工作的隊列，線程在并行執(zhí)行的時候，不斷從這個隊列中取出相應(yīng)的工作完成，直到隊列為空為止,,,,,根據(jù)線程號分配任務(wù),每一個線程在執(zhí)行的過程中的線程標(biāo)識號是不同的，可以根據(jù)這個線程標(biāo)識號來分配不同的任務(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)語句分配任務(wù),,工作分區(qū)編碼,,2.3 線程同步,OpenMP支持兩種不同類型的線程同步機制 ：互斥鎖：可以用來保護(hù)一塊共享的存儲空間，使得每一次訪問這塊共享內(nèi)存空間的線程最多一個，保證了數(shù)據(jù)的完整性事件通知：這種機制保證了多個線程之間的執(zhí)行順序,數(shù)據(jù)競爭,,互斥鎖機

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

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

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

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

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

26、簡單地給各個線程分配相同次數(shù)的迭代的話，會造成各個線程計算負(fù)載不均衡，這會使得有些線程先執(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個線程，如果給每個線程平均分配25次循環(huán)迭代計算的話，顯然i＝0和i＝99的計算量相差了100倍，那么各個線程間可能出現(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 (實際上是根據(jù)環(huán)境變量來選擇前三種中的某中類型。)size參數(shù) (可選) size參數(shù)表示循環(huán)迭代次數(shù)，size參數(shù)必須是整數(shù)。,靜態(tài)調(diào)度(static),當(dāng)parallel for編譯制導(dǎo)語句沒有帶schedule子句時，大部分系統(tǒng)中默認(rèn)采用static調(diào)度方式，這種調(diào)度方式非常簡單。假設(shè)有n次循環(huán)迭代，t個線程，那么給每個線程靜態(tài)分配大約n/t次迭代計算。不使用size參數(shù)時，分配給每個線程的是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,每個線程依次分配到2次連續(xù)的迭代計算。,動態(tài)調(diào)度(d

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

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