機(jī)群應(yīng)用開發(fā)

并行編程原理及

程序設(shè)計(jì)

ParallelProgramming:

FundamentalsandImplementation戴榮dair@曙光信息產(chǎn)業(yè)有限公司2006.42006年4月1共享存儲編程參考文獻(xiàn)黃鎧,徐志偉著,陸鑫達(dá)等譯.可擴(kuò)展并行計(jì)算技術(shù),結(jié)構(gòu)與編程.北京:機(jī)械工業(yè)出版社,P.33~56,P.227~237,2000.陳國良著.并行計(jì)算—結(jié)構(gòu)、算法、編程.北京:高等教育出版社,1999.BarryWilkinsonandMichaelAllen.ParallelProgramming(TechniquesandApplicationsusingNetworkedWorkstationsandParallelComputers).PrenticeHall,1999.李曉梅,莫則堯等著.可擴(kuò)展并行算法的設(shè)計(jì)與分析.北京:國防工業(yè)出版社,2000.張寶琳,谷同祥等著.數(shù)值并行計(jì)算原理與方法.北京:國防工業(yè)出版社,1999.都志輝著.高性能計(jì)算并行編程技術(shù)—MPI并行程序設(shè)計(jì).北京:清華大學(xué)出版社,2001.

2006年4月2共享存儲編程相關(guān)網(wǎng)址MPI:，

http:///mpiPthreads:http://PVM:http:///pvm/

OpemMP:http://網(wǎng)上搜索:2006年4月3共享存儲編程共享存儲編程

ProgrammingwithSharedMemory2006年4月4共享存儲編程共享存儲并行機(jī)模型體系結(jié)構(gòu)特點(diǎn):多臺處理機(jī)通過互聯(lián)網(wǎng)絡(luò)共享一個統(tǒng)一的內(nèi)存空間,通過單一內(nèi)存地址來實(shí)現(xiàn)處理機(jī)間的協(xié)調(diào).內(nèi)存空間也可由多個存儲器模塊構(gòu)成.每臺處理機(jī)可以執(zhí)行相同或不同的指令流,每臺處理機(jī)可以直接訪問到所有數(shù)據(jù).處理機(jī)間通信是借助于共享主存來實(shí)現(xiàn)的.可擴(kuò)展性差,當(dāng)處理機(jī)需要同時訪問共享全局變量時,產(chǎn)生內(nèi)存競爭現(xiàn)象而嚴(yán)重影響效率,比較適合中小規(guī)模應(yīng)用問題的計(jì)算和事務(wù)處理.2006年4月5共享存儲編程共享存儲編程標(biāo)準(zhǔn)與特點(diǎn)共享存儲器編程標(biāo)準(zhǔn)Pthreads(線程標(biāo)準(zhǔn))

X3H5(線程標(biāo)準(zhǔn))OpenMP(最常用的共享存儲并行編程方式,是我們討論的重點(diǎn).)共享存儲器編程特點(diǎn)顯式多線程庫調(diào)用.(Pthreads).編譯制導(dǎo)語句,OpenMP等.語言C,Fortran77,Fortran90/95,C++…2006年4月6共享存儲編程并行編程標(biāo)準(zhǔn)線程庫標(biāo)準(zhǔn)(ThreadLibrary)–Win32API.–POSIXthreads線程模型.–X3H5:概念性線程模型編譯制導(dǎo)(CompilerDirectives)–OpenMP-portablesharedmemoryparallelism.2006年4月7共享存儲編程為什么流行多線程編程?線程：在進(jìn)程的內(nèi)部執(zhí)行的指令序列.相對于進(jìn)程，線程開銷小:創(chuàng)建一個線程的時間大約是建立一個新進(jìn)程的1/30。如在Sun4/75工作上站上，創(chuàng)建一個非綁定線程約為52微秒，而fork()一次的時間為1700微秒。線程同步時間約是進(jìn)程同步時間的1/3.線程與RPC相結(jié)合，發(fā)揮多處理機(jī)的處理能力;發(fā)揮多處理器的處理能力;開發(fā)程序的并發(fā)性，改善程序的結(jié)構(gòu).容易實(shí)現(xiàn)數(shù)據(jù)共享：由于線程共用內(nèi)存地址，因此可實(shí)現(xiàn)數(shù)據(jù)共享例：一高性能Web服務(wù)器可為每一打開鏈接的瀏覽器分配一個線程，所有線程即可共用同一cache來訪問網(wǎng)站的熱點(diǎn)話題統(tǒng)一的標(biāo)準(zhǔn)：以前各開發(fā)商提供互不兼容的線程庫，結(jié)果導(dǎo)致多線程程序不能很好地移值。自1995年的POSIX線程標(biāo)準(zhǔn)實(shí)施之后，極大地促進(jìn)多線程編程的統(tǒng)一。各系統(tǒng)都支持Pthreads，如Linux、SUN、IBMAIX等。2006年4月8共享存儲編程Pthreads線程模型POSIX1003.4a小組研究多線程編程標(biāo)準(zhǔn).當(dāng)標(biāo)準(zhǔn)完成后,大多數(shù)支持多線程的系統(tǒng)都支持POSIX接口.很好的改善了多線程編程的可移植性.IEEEPortableOperatingSystemInterface,POSIX,1003.1-1995標(biāo)準(zhǔn):POSIX線程模型:pthreads.2006年4月9共享存儲編程線程管理(Pthread為例)創(chuàng)建:pthread_create終止:pthread_exit匯合:pthread_join分離:pthread_detach線程屬性初始化:pthread_attr_init唯一執(zhí)行:pthread_once2006年4月10共享存儲編程同步對象在共享存儲多處理器并行機(jī)上，線程通過全局變量通信，對于全局變量的操作必須進(jìn)行同步。pthread提供兩個線程同步原語:互斥和條件變量.2006年4月11共享存儲編程互斥鎖函數(shù)函數(shù)

操作Mutex_init() 初始化一個互斥鎖Mutext_lock()

阻塞式加鎖操作Mutex_trylock() 非阻塞式加鎖操作Mutex_unlock()

解鎖Mutex_destroy() 解除互斥狀態(tài)2006年4月12共享存儲編程條件變量的函數(shù)

函數(shù)

操作pthread_cond_init() 初始化條件變量pthread_cond_wait()

阻塞直至條件為真pthread_cond_signal()

強(qiáng)制條件為真,解除等待條件的線程的阻塞pthread_cond_timedwait() 阻塞直到指定條件為真或timeoutpthread_cond_broadcast() 解除所有等待條件的線程的阻塞pthread_cond_destroy()

銷毀條件變量2006年4月13共享存儲編程HelloWorld(1)#include<pthread.h>#include"stdio.h"void*worker();main(){pthread_tthread;pthread_create(&thread,NULL,worker,NULL);pthread_join(thread,NULL);}void*worker(){

printf("HelloWorld!\n");}編譯命令gcchello.c–lpthread運(yùn)行結(jié)果HelloWorld!2006年4月14共享存儲編程pthread_t

線程數(shù)據(jù)類型pthread_create(&thread,NULL,worker,NULL);函數(shù)pthread_create()用于創(chuàng)建一新的線程,新線程一旦建立便進(jìn)入運(yùn)行狀態(tài)參數(shù):線程指針或句柄線程屬性變量,屬性參數(shù):默認(rèn)為NULL.屬性對象一旦建立可以用于創(chuàng)建多個具有共同屬性的線程,線程創(chuàng)建后,可刪除屬性對象.線程要執(zhí)行的函數(shù)傳入該執(zhí)行函數(shù)的一個參數(shù),無則NULL.可以是任意類型線程的終止線程函數(shù)正常終止返回;自調(diào)用pthear_exit()函數(shù);線程被取消;線程接收到中止的信號;當(dāng)主進(jìn)程執(zhí)行exit()后,進(jìn)程及其全部線程全部終止.2006年4月15共享存儲編程pthread_join(pthread_twait_for,void**status);

等待直到線程結(jié)束;執(zhí)行該函數(shù)的線程發(fā)生阻塞,直到由wait_for指定的線程終止;等與被等的兩線程必須是同一進(jìn)程內(nèi)部的線程(而且不是分離線程);返回值0 成功返回ESRCH 參數(shù)wait_for指定的線程不存在或是一分離線程;EINVAL 線程參數(shù)無效;EDEADLK 等待自身結(jié)束.不能有兩個線程同時等待同一個線程的結(jié)束,否則其中一個線程正常返回,另外一個返回ESRCH錯誤.2006年4月16共享存儲編程HelloWorld(2)#include<pthread.h>#include"stdio.h"#definenumthrds5pthread_t*tid;void*worker();main(){

inti;

tid=(pthread_t*)calloc(numthrds,sizeof(pthread_t)); for(i=0;i<numthrds;i++)pthread_create(&tid[i],NULL,worker,NULL); for(i=0;i<numthrds;i++)pthread_join(tid[i],NULL);}void*worker(){

int

myid;

myid=pthread_self()-tid[0];

printf("HelloWorldfromthread%d!\n",myid);}HelloWorldfromthread0!HelloWorldfromthread1!HelloWorldfromthread2!HelloWorldfromthread3!HelloWorldfromthread4!2006年4月17共享存儲編程HelloWorld(3)#include<pthread.h>#include"stdio.h"#definenumthrds5pthread_t*tid;pthread_mutex_t

mutex;intsum=0;void*worker();main(){

inti;

tid=(pthread_t*)calloc(numthrds,sizeof(pthread_t));

pthread_mutex_init(&mutex,NULL); for(i=0;i<numthrds;i++)pthread_create(&tid[i],NULL,worker,NULL); for(i=0;i<numthrds;i++)pthread_join(tid[i],NULL);

printf(“Thesumis%d\n",sum); }void*worker(){

intmyid,num;

myid=pthread_self()-tid[0];

printf("%dwasaddedtothesuminthread%d\n",myid*10,myid);

pthread_mutex_lock(&mutex); sum+=myid*10;

pthread_mutex_unlock(&mutex); return;}2006年4月18共享存儲編程運(yùn)行結(jié)果0wasaddedtothesuminthread010wasaddedtothesuminthread120wasaddedtothesuminthread230wasaddedtothesuminthread340wasaddedtothesuminthread4Thesumis1002006年4月19共享存儲編程基于多線程編程的PI求解222006年4月20共享存儲編程#include<pthread.h>#include"stdio.h"pthread_mutex_t

reduction_mutex;pthread_t*tid;doublepi,w;intn;intnum_threads;doublef(a)doublea;{return(4.0/(1.0+a*a));}void*PIworker(void*arg){

inti,myid;doublesum,mypi,x;/*setindividualidtostartat0*/

myid=pthread_self()-tid[0];/*integratefunction*/sum=0.0;for(i=myid+1;i<=n;i+=num_threads){x=w*((double)i-0.5);sum+=f(x);}

mypi=w*sum;/*reducevalue*/

pthread_mutex_lock(&reduction_mutex);pi+=mypi;

pthread_mutex_unlock(&reduction_mutex);return(0);}2006年4月21共享存儲編程voidmain(argc,argv)int

argc;char*argv[];{

inti;

/*checkcommandline*/

if(argc!=3){

printf("Usage:%sNum_intervalsNum_threads\n",argv[0]);exit(0);}

/*getnumintervalsandnumthreadsfromcommandline*/n=atoi(argv[1]);num_threads=atoi(argv[2]);w=1.0/(double)n;pi=0.0;

tid=(pthread_t*)calloc(num_threads,sizeof(pthread_t));/*initilizelock*/if(pthread_mutex_init(&reduction_mutex,NULL)){

fprintf(stderr,"Cannotinitlock\n");

exit(1);}/*createthethreads*/

for(i=0;i<num_threads;i++){

if(pthread_create(&tid[i],NULL,PIworker,NULL)){

fprintf(stderr,"Cannotcreatethread%d\n",i);

exit(1);}}/*jointhreads*/

for(i=0;i<num_threads;i++)

pthread_join(tid[i],NULL);

printf("computedpi=%.16f\n",pi);}gcchello.c–lpthread

a.out10005

computedpi=3.1415927369231271轉(zhuǎn)去Openmp2006年4月22共享存儲編程多線程并行編程特點(diǎn)pthread_create()創(chuàng)建一個新線程比重新啟動一個線程花費(fèi)的時間少:需要時創(chuàng)建+任務(wù)結(jié)束立刻殺掉vs.維護(hù)一大堆的空閑線程并且相互切換.在加鎖的前提下訪問共享資源不支持?jǐn)?shù)據(jù)并行，適合于任務(wù)級并行，即一個線程單獨(dú)執(zhí)行一個任務(wù);不支持增量并行化，對于一個串行程序，很難用Pthreads進(jìn)行并行化Pthreads主要是面向操作系統(tǒng)，而不是為高性能計(jì)算設(shè)計(jì)的，因此不是并行計(jì)算程序設(shè)計(jì)的主流平臺。但是“多線程并發(fā)執(zhí)行”這種思想?yún)s被廣泛地應(yīng)用于高性能計(jì)算。這就是我們即將要講的共享存儲并行編程的另外一種被并行機(jī)制造商和廣用并行計(jì)算用戶廣泛接受的平臺：OpenMP2006年4月23共享存儲編程并行編程標(biāo)準(zhǔn)線程庫標(biāo)準(zhǔn)(ThreadLibrary)–Win32API.–POSIXthreads線程模型.–X3H5:概念性線程模型編譯制導(dǎo)(CompilerDirectives)–

OpenMP-portablesharedmemoryparallelism.2006年4月24共享存儲編程AnIndustryStandardAPIforSharedMemoryProgrammingAnAPIforWritingMultithreadedApplications一系列編譯制導(dǎo)語句和庫函數(shù)使得Fortran,CandC++的多線程編程更加容易2006年4月25共享存儲編程與X3H5的關(guān)系X3H5是ANSI/X3授權(quán)的小組委員會,主要目的是在PCF(theParallelComputingForum)工作的基礎(chǔ)上,發(fā)展并行計(jì)算的一個ANSI標(biāo)準(zhǔn).PCF是一非正式的工業(yè)組織,雖在DO循環(huán)的并行化方法的標(biāo)準(zhǔn)化方面做一些工作,但在起草擬了一個標(biāo)準(zhǔn)后就草草收場.OpenMP專門針對這類并行化問題,并完成了這項(xiàng)工作,同時得到工業(yè)界的廣泛支持.2006年4月26共享存儲編程ANSIX3H5共享編程標(biāo)準(zhǔn)概念性的編程模型(ANSI標(biāo)準(zhǔn)(1993))沒有任何商品化的共享存儲器系統(tǒng)依附于X3H5,但X3H5的基本概念影響以后共享存儲器系統(tǒng)的并行編程.(一些基本概念在OpenMP均出現(xiàn)!)X3H5支持C,Fortran77以及Fortran90語言.X3H5規(guī)定的基本的并行結(jié)構(gòu)用于并行性表述:并行塊(分散任務(wù)WorkSharing)并行循環(huán)單進(jìn)程parallel{…}endparallelpsections{…}endpsectionspdo{…}endpdopsingle{…}endpsingle2006年4月27共享存儲編程X3H5編程實(shí)例programmain !程序以順序模式執(zhí)行A !A只由基本線程執(zhí)行parallel !轉(zhuǎn)換成并行模式B !B為每個組員所復(fù)制psections !并行塊開始section C !一個組員執(zhí)行CsectionD !另一個組員執(zhí)行D endpsections !等待C和D都結(jié)束psingle

暫時轉(zhuǎn)換成順序模式E !E只能被一個組員執(zhí)行endpsingle !轉(zhuǎn)回并行模式pdoI=1,6 !并行do循環(huán)開始F(i) !各線程分擔(dān)循環(huán)任務(wù)endpdo

nowait !無隱式路障同步G !更多的復(fù)制代碼endparallel !結(jié)束并行模式H !根進(jìn)程執(zhí)行H… !更多的并行構(gòu)造end線程PQRBBECF(1:2)F(3:4)F(5:6)GGGH隱式barrier隱式barrier隱式barrier無隱式barrier隱式barrierBD各線程以負(fù)載平衡方式分擔(dān)任務(wù)可能為:F(1:1),F(2:2),F(3:6)…2006年4月28共享存儲編程X3H5例程執(zhí)行過程描述程序以順序方式啟動,此時只有一個初始化線程,稱為基本線程或主線程.當(dāng)程序遇到parallel時,通過派生多個子線程轉(zhuǎn)換為并行執(zhí)行模式(線程數(shù)隱式?jīng)Q定).基本線程與它的子線程形成一個組.所有組員并行處理后繼并行代碼,直至endparallel.然后程序轉(zhuǎn)為順序模式,只有基本線程繼續(xù)執(zhí)行.子線程遇到內(nèi)部并行或任務(wù)分擔(dān)構(gòu)造時,可以繼續(xù)派生其子線程,從而成為一個新組的基本線程.線程間同步,通信與交互隱式路障:parallel,endparallel,endpdo或endpsingle處隱式barrier.如果不需,則加nowait;各處理機(jī)通過全局變量通信,通過私有變量封裝數(shù)據(jù)fork…...barrier…順序執(zhí)行順序執(zhí)行并行執(zhí)行2006年4月29共享存儲編程OpenMP:并行模型Fork-Join并行模式:主線程根據(jù)需要創(chuàng)建一組子線程進(jìn)行工作分擔(dān).可對串行程序進(jìn)行逐步并行化.主線程并行執(zhí)行區(qū)域2006年4月30共享存儲編程如何應(yīng)用OpenMP?OpenMP常用于循環(huán)并行化:–找出最耗時的循環(huán).–將循環(huán)由多線程完成.在串行程序上加上編譯制導(dǎo)語句,完成并行化,因此可先完成串行程序,然后再進(jìn)行OpenMP并行化.voidmain(){doubleRes[1000];for(inti=0;i<1000;i++){do_huge_comp(Res[i]);}}voidmain(){doubleRes[1000];

#pragmaompparallelforfor(inti=0;i<1000;i++){do_huge_comp(Res[i]);}串行程序并行程序用OpenMP將該循環(huán)通過多線程進(jìn)行任務(wù)分割2006年4月31共享存儲編程線程間如何交互?OpenMP

是基于共享內(nèi)存模型.線程通過共享變量通信.訪問共享變量會導(dǎo)致racecondition(競態(tài)狀態(tài))racecondition:是一種狀態(tài)，在這種狀態(tài)下兩個實(shí)體(例如兩個處理過程)對同一資源進(jìn)行競爭，而系統(tǒng)沒有一種機(jī)制來測定首先要執(zhí)行的是哪一個。因此，由于系統(tǒng)不能保證數(shù)據(jù)的正確處理，其結(jié)果是不可預(yù)測的。為了避免線程進(jìn)入競態(tài)狀態(tài):通過同步對象來保護(hù)數(shù)據(jù)沖突.2006年4月32共享存儲編程OpenMP術(shù)語大多OpenMP構(gòu)造是制導(dǎo)語句或pragmas.C和C++的pragmas形式為:#pragma

omp

construct[clause[clause]…]Fortran中,制導(dǎo)語句形式為以下幾種:C$OMPCONSTRUCT[clause[clause]…]!$OMPCONSTRUCT[clause[clause]…](自由書寫格式唯一)*$OMPCONSTRUCT[clause[clause]…]例:以下三種等價(第一行為列數(shù))C23456789!$OMPPARALLELDOSHARED(A,B,C)C$OMPPARALLELDOC$OMP+SHARED(A,B,C)C$OMPPARALLELDOSHARED(A,B,C)由于OpenMP構(gòu)造為注釋性語句,因此一個OpenMP程序在用不支持OpenMP的編譯器編譯后,仍為串行程序.2006年4月33共享存儲編程Structuredblocks(結(jié)構(gòu)化塊)結(jié)構(gòu)化塊性質(zhì):僅在塊頂有一個入口和塊底有一個出口;塊功能可通過構(gòu)造的語法清晰地識別;塊內(nèi)除Fortran中的STOP語句和c/c++中的exit()語句外,不能有其它分支.大多OpenMP構(gòu)造為結(jié)構(gòu)化塊.C$OMP PARALLEL10 … … if(…)goto10C$OMPENDPARALLEL print*,id

C$OMPPARALLEL10 …30 … if(…)goto20 goto10C$OMP ENDPARALLEL if(…)goto3020 print*,id一個結(jié)構(gòu)化塊一個非結(jié)構(gòu)化塊2006年4月34共享存儲編程OpenMP結(jié)構(gòu)化塊類型OpenMP主要有五類結(jié)構(gòu)化塊:并行區(qū)ParallelRegions任務(wù)分割Worksharing數(shù)據(jù)環(huán)境DataEnvironment同步Synchronization運(yùn)行時函數(shù)/環(huán)境變量在Fortran,C/C++中,OpenMP基本上是一樣的.2006年4月35共享存儲編程ParallelRegions(并行區(qū))并行區(qū)是OpenMP的基本構(gòu)造,并行區(qū)內(nèi)的代碼由各線程同時執(zhí)行.當(dāng)一個線程執(zhí)行“ompparallel”后,建立一組線程,該線程成為新建立的線程組的主線程.所有線程構(gòu)成一線程組,各線程以線程ID區(qū)分,主線程ID為0.線程組并行執(zhí)行并行區(qū)內(nèi)代碼.如:建立一個4線程的并行區(qū):doubleA[1000];omp_set_num_threads(4);#pragmaompparallel{

intID=omp_thread_num();worker(ID,A);}每一線程以不同的線程ID和相同的參數(shù)A執(zhí)行并行區(qū)內(nèi)代碼的一拷貝.ID(=0,1,2,3).2006年4月36共享存儲編程并行區(qū)的Lecical/dynamicextent

以及Orphaned制所語句bar.fsubroutinewhoamiexternalomp_get_thread_numintegeriam,omp_get_thread_numiam=omp_get_thread_num()C$OMPCRITICALprint*,’Hellofrom‘,iamC$OMPENDCRITICALreturnendpoo.fC$OMPPARALLELcallwhoamiC$OMPENDPARALLELStatic/lexicalextent:在書寫上直接包含在并行區(qū)內(nèi)的部分.+Dynamicextent:包括并行區(qū)內(nèi)直接和間接(函數(shù)調(diào)用)包含的內(nèi)容,也被稱為region.Orphan制導(dǎo)語句:落在子程序中的制導(dǎo)語句,方便于子程序的并行化,免去傳統(tǒng)的inline處理2006年4月37共享存儲編程并行區(qū)代碼流程doubleA[1000];omp_set_num_threads(4);#pragmaompparallel{

intID=omp_thread_num();worker(ID,A);}opm_set_num_threads(4)worker(2,A)worker(1,A)worker(3,A)DoubleA[1000]worker(0,A)所有線程在此處同步(如,隱式barrier同步)每一線程執(zhí)行相同代碼,不同數(shù)據(jù).所以,并行區(qū)結(jié)構(gòu)也被稱為SPMD結(jié)構(gòu).2006年4月38共享存儲編程HelloWorld(C)#include<omp.h>main(){intmyid,numthreads;

#pragmaompparallel

{

myid=omp_get_thread_num();

numthreads=omp_get_num_threads();

printf("HelloWorldfromthread%dof%d!\n",myid,numthreads);

}}2006年4月39共享存儲編程HelloWorld(Fortran)

PROGRAMHELLO

integermyid,numthreads

integeromp_get_num_threads,omp_get_thread_num!$ompparallelprivate(numthreads,myid)

numthreads=omp_get_num_threads()

myid=omp_get_thread_num()

print*,'HelloWorldfromthread',myid,'of',numthreads!$ompendparallel

stop

end2006年4月40共享存儲編程OpenMP并行程序編譯支持編譯OpenMP的編譯器會提供編譯器命令選項(xiàng),以解釋OpenMP編譯制導(dǎo)語句.IBMAIXxlc編譯器,編譯器命令選項(xiàng)為-qsmpxlcfile.c–qsmpxlf_rfile.f-qsmp

(xlf_r為IBMAIX4.3為支持多線程編程的編譯器)曙光3000：OS:AIX4.3-qsmpAIX4.3支持OpenMP編譯選項(xiàng)IntelC/C++編譯器icc,IntelFortran編譯器選項(xiàng)為-openmpiccfile.c–openmpifcfile.f–openmp曙光4000L：OS:RedhatLinux8.0PGIC/C++編譯器icc,PGIFortran編譯器選項(xiàng)為-mppgccfile.c–mppgf77file.f–mppgf90file.f–mp曙光4000A：OS:SuSELinux8.0/TurboLinux2006年4月41共享存儲編程一些細(xì)節(jié)(可先不關(guān)心)C:#pragma

ompparallel[clause[clause]...]new-linestructured-blockFortran:!$OMPPARALLEL[clause[[,]clause]...]block!$OMPENDPARALLEL子句clause是下列之一:if(expr):根據(jù)expr表達(dá)式執(zhí)行結(jié)果決定是否并行執(zhí)行private(list):變量私有化,默認(rèn)為全部變量firstprivate(list):在并行區(qū)間之外引用變量首次賦值結(jié)果default(shared|none)(C)DEFAULT(PRIVATE|SHARED|NONE)(Fortran)shared(list):并行區(qū)間中的共享變量列表copyin(list):拷貝主線程的threadprivate公共區(qū)數(shù)據(jù)reduction(operator:list):歸約操作2006年4月42共享存儲編程OpenMP結(jié)構(gòu)化塊類型OpenMP主要有五類結(jié)構(gòu)化塊:并行區(qū)ParallelRegions任務(wù)分割WorksharingDO(Fortran)/for(C)結(jié)構(gòu):針對循環(huán)的并行化結(jié)構(gòu)Sections:代碼段間的并行Single:強(qiáng)制并行區(qū)中某些代碼以串行方式執(zhí)行(如:I/O)數(shù)據(jù)環(huán)境DataEnvironment同步Synchronization運(yùn)行時函數(shù)/環(huán)境變量OpenMP最重要部分2006年4月43共享存儲編程循環(huán)分割:DO(Fortran)/for(C)結(jié)構(gòu)Fortran!$OMPDO[clause[[,]clause]...]do_loop[!$OMPENDDO[NOWAIT]](可選)C/C++#pragma

ompfor[clause[clause]...]new-linefor-loopC$OMPPARALLELC$OMPDODOi=0,n…}#pragmaompparallel#pragmaompforfor(i=0;i<n;i++){…}在DO/for結(jié)構(gòu)之后有一隱式barrier同步操作,用NOWAIT/nowait可以禁止.2006年4月44共享存儲編程比較parrallel構(gòu)造與for構(gòu)造for(i=0;I<N;i++){a[i]=a[i]+b[i];}#pragmaompparallel{

intid,i,Nthrds,istart,iend;id=omp_get_thread_num();

Nthrds=omp_get_num_threads();

istart=id*N/Nthrds;

iend=(id+1)*N/Nthrds;for(i=istart;I<iend;i++){a[i]=a[i]+b[i];}}#pragmaompparallel#pragmaompforschedule(static)for(i=0;I<N;i++){a[i]=a[i]+b[i];}串行代碼用并行區(qū)實(shí)現(xiàn)并行化用任務(wù)分割構(gòu)造實(shí)現(xiàn)并行化對于DO結(jié)構(gòu)與PARALLEL結(jié)構(gòu)的比較同理,且以后討論若無特別說明均基于C描述.2006年4月45共享存儲編程并行區(qū)與任務(wù)分割間的關(guān)系并行區(qū)和任務(wù)分割是OpenMP兩類基本的并行性構(gòu)造;并行區(qū)中的代碼對組內(nèi)的各線程是可見的,也即并行區(qū)內(nèi)的代碼由各線程同時執(zhí)行;任務(wù)分割與并行區(qū)不同,它是將一個整體任務(wù)按負(fù)載平衡的方式分配給各線程來互相配合完成.并行區(qū)是并行的先決條件,任務(wù)分割必須要與并行區(qū)一起使用才能生效;并行區(qū)構(gòu)造為!ompparallel;任務(wù)分割構(gòu)造有:do/for,section,和single三種.根進(jìn)程并行區(qū)2006年4月46共享存儲編程更詳細(xì)的for語法#pragma

ompfor[clause[clause]...]new-linefor-loopClause可是下列說明:private(list)firstprivate(list)lastprivate(list)reduction(operator:list)orderedschedule(kind[,chunk_size])nowait后面將詳細(xì)說明2006年4月47共享存儲編程更詳細(xì)的DO語法!$OMPDO[clause[[,]clause]...]do_loop[!$OMPENDDO[NOWAIT]]PRIVATE(list)FIRSTPRIVATE(list)LASTPRIVATE(list)REDUCTION({operator|intrinsic_procedure_name}:list)SCHEDULE(type[,chunk])ORDERED2006年4月48共享存儲編程DO/for使用注意事項(xiàng)循環(huán)體必須緊接在DO或for之后.For循環(huán)必須為一結(jié)構(gòu)化塊,且其執(zhí)行不被break語句中斷.在Fortran中,如果寫上ENDDO制導(dǎo)語句,其必須要緊跟在DO循環(huán)的結(jié)束之后.循環(huán)變量必須為整形.Schedule,

ordered,nowait子句只能出現(xiàn)一次.2006年4月49共享存儲編程scheduleSchedule子名決定循環(huán)如何在各線程中進(jìn)行分配:schedule(dynamic[,chunk])各線程每次得到chunk_size大小的任務(wù),執(zhí)行完后繼續(xù)取得任務(wù),以此反復(fù),直至任務(wù)完成(最后一任務(wù)可能會小于chunk_size).(任務(wù)池)當(dāng)chunk_size未被指定時,默認(rèn)為1.schedule(static[,chunk])如果chunk_size被指定,

則各線程按線程號順序每人每得chunk次的循環(huán)任務(wù),如果任務(wù)不能一次平分掉,則分配循環(huán)進(jìn)行.如果chunk_size未被指定,則各線程任務(wù)數(shù)即為循環(huán)數(shù)除以所用線程數(shù)的結(jié)果.schedule(guided[,chunk])開始以一大的單位進(jìn)行分配憶,逐漸減小到chunk指定的值.schedule(runtime)分配方式與chunk值大小取決于環(huán)境變量OMP_SCHEDULE的設(shè)置.chunk以循環(huán)次數(shù)為單位.示意圖見下頁.2006年4月50共享存儲編程Schedule示意圖WorkpoolWork........Dynamic方式Static方式執(zhí)行時間Guided方式Work........2006年4月51共享存儲編程適用條件靜態(tài):適用于大部分情形.特點(diǎn):各線程任務(wù)明確,在任務(wù)分配時無需同步操作.運(yùn)行快的線程需等慢的線程為:動態(tài):適用于任務(wù)數(shù)量可變或不確定的情形(如條件收斂循環(huán)).特點(diǎn):各線程將要執(zhí)行的任務(wù)不可預(yù)見,任務(wù)分配需同步操作.Guided:線程異步到達(dá)for結(jié)構(gòu)特點(diǎn):首先到達(dá)的線程總是分得q=ceiling(n/p)次循環(huán),然后n=max(n-q,p*k),循環(huán)分配,直到n=p*k為止.環(huán)境變量:無需重新編譯程序,可根據(jù)原始輸入數(shù)據(jù)的情況改變?nèi)蝿?wù)分配策略.2006年4月52共享存儲編程N(yùn)OWAIT子句(Fortran)C$OMPPARALLELC$OMPDOdoi=1,na(i)=cos(a(i))

enddoC$OMPENDDOC$OMPDOdoi=1,nb(i)=a(i)+b(i)

enddoC$OMPENDDOC$OMPENDPARALLELC$OMPPARALLELC$OMPDOdoi=1,na(i)=cos(a(i))

enddoC$OMPENDDONOWAITC$OMPDOdoi=1,nb(i)=a(i)+b(i)

enddoC$OMPENDDOC$OMPENDPARALLEL隱式BARRIERNoBARRIER默認(rèn)循環(huán)變量i為私有線程私有類型變量ENDDO必須緊隨enddo,可省略.2006年4月53共享存儲編程nowait子句(C)#pragmaompparallel{#pragma

ompforfor(i=1;i<n;i++)a(i)=cos(a(i));#pragmaompforfor(i=1;i<n;i++)b(i)=a(i)+b(i);}

{…}為并行區(qū).隱式BARRIER#pragmaompparallel{#pragma

ompfornowaitfor(i=1;i<n;i++)a(i)=cos(a(i));#pragmaompfornowaitfor(i=1;i<n;i++)b(i)=a(i)+b(i);}

NoBARRIER2006年4月54共享存儲編程Sections構(gòu)造(非循環(huán)并行)Sections用于程序中大范圍的非迭代執(zhí)行代碼段間的并行化.(如前10行和后10行間代碼間無依賴關(guān)系,可以并行.)缺省時每一個“ompsections”構(gòu)造結(jié)束后有一個barrier同步操作.通過使用“nowait”子句禁止隱式barrier同步(在構(gòu)造語句后直接加即可).與for結(jié)構(gòu)相類似,OpenMP也提供parallelsections.#pragmaomp

sections[nowait]{ x_calculation(); #pragmaomp

section y_calculation(); #pragmaomp

section z_calculation();}x_calculation(),y_calculation()以及z_calculation()代表三部分之間無依賴關(guān)系的非循環(huán)代碼段.實(shí)質(zhì)上它們各代表很多行代碼.2006年4月55共享存儲編程SingleSingle：強(qiáng)制并行區(qū)中某些代碼以串行方式執(zhí)行#pragma

ompsingle[clause[clause]...]new-linestructured-blockClauseisoneofthefollowing:private(list)firstprivate(list)nowait2006年4月56共享存儲編程Worksharing語句匯總FortranDOSECTIONSSINGLEWORKSHARECforsectionssingle2006年4月57共享存儲編程Binding

并行結(jié)構(gòu)的聯(lián)合使用#pragmaomp

parallel

forfor(I=0;I<N;I++){ NEAT_STUFF(I);}#pragmaomp

parallel#pragma

ompforfor(I=0;I<N;I++){ NEAT_STUFF(I);}=for,sections,single,master,andbarrier如果不位于并行區(qū)內(nèi)或不與并行區(qū)聯(lián)合使用,便不起任何作用.2006年4月58共享存儲編程Fortran!$OMPPARALLELSECTIONS[clause[[,]clause]...][!$OMPSECTION]block[!$OMPSECTIONblock]...!$OMPENDPARALLELSECTIONS!$OMPPARALLELDO[clause[[,]clause]...]do_loop[!$OMPENDPARALLELDO]!$OMPPARALLELWORKSHARE[clause[[,]clause]...]block!$OMPENDPARALLELWORKSHARE2006年4月59共享存儲編程C#pragmaompparallelfor[clause[clause]...]new-linefor-loop#pragmaompparallelsections[clause[clause]...]new-line{[#pragmaompsectionnew-line]structured-block[#pragmaompsectionnew-linestructured-block..]}2006年4月60共享存儲編程OpenMP結(jié)構(gòu)化塊類型OpenMP主要有五類結(jié)構(gòu)化塊:并行區(qū)ParallelRegions任務(wù)分割Worksharing數(shù)據(jù)環(huán)境DataEnvironment同步Synchronization運(yùn)行時函數(shù)/環(huán)境變量2006年4月61共享存儲編程默認(rèn)數(shù)據(jù)類型共享變量編程模型:–大部分變量默認(rèn)為共享類型各線程共享全局變量–Fortran:COMMON塊,SAVE變量,MODULE變量–C:Filescopevariables,static但并不是所有變量全部共享...–在并行區(qū)內(nèi)調(diào)用的子程序中的棧變量是私有–在語句塊中的Auto變量為私有變量.2006年4月62共享存儲編程舉例說明變量類型subroutineworkcommon/input/A(10)realtemp(10)integercountsavecount…………programsortcommon/input/A(10)integerindex(10)callinputC$OMPPARALLELcallwork(index)C$OMPENDPARALLELprint*,index(1)變量A,index和cound為所有線程共享.temp為線程私有變量,各線程間到不可見.2006年4月63共享存儲編程變量類型改變變量類型編譯制導(dǎo):

threadprivate:將某些全局變量或數(shù)據(jù)區(qū)變?yōu)榫€程私有.通過下列類型屬性子句來改變變量類型:–shared(并行區(qū)結(jié)構(gòu))–private–firstprivate–lastprivate:循環(huán)體內(nèi)的私有變量可以轉(zhuǎn)變?yōu)槿肿兞?在循環(huán)結(jié)束后訪問;默認(rèn)數(shù)據(jù)類型狀態(tài)可以改變:–default(private|shared|none)2006年4月64共享存儲編程私有類型變量變量私有化是OpenMP采用的重要的編譯技術(shù).變量私有化;私有變量初始化:CopyinFirstprivate私有變量返回:ReductionLastprivateOpenMP私有類型變量是指并行區(qū)內(nèi)的只能被線程組內(nèi)的某一線程訪問的變量.OpenMP的私有變量包括:并行區(qū)內(nèi)定義的變量;由threadprivate

制導(dǎo)語句指明的變量;由private,firstprivate,lastprivate,orreduction子句指定的變量;循環(huán)控制變量.2006年4月65共享存儲編程Threadprivate:

線程的全局私有變量

parameter(N=1000)realA(N,N)C$OMPTHREADPRIVATE(/buf/)common/buf/lft(N),rht(N)C$OMPPARALLELcallinitcallscalecallorderC$OMPENDPARALLEL

subroutinescaleparameter(N=1000)C$OMPTHREADPRIVATE(/buf/)common/buf/lft(N),rht(N)doi=1,N

lft(i)=const*A(i,iam)enddoreturnend

subroutineorderparameter(N=1000)C$OMPTHREADPRIVATE(/buf/)common/buf/lft(N),rht(N)doi=1,NA(i,iam)=lft(index)enddoreturnendbuf

是線程內(nèi)的公共塊2006年4月66共享存儲編程Privateprivate(list)表明list中所列變量為組內(nèi)線程私有變量.–對變量不進(jìn)行初始化(有構(gòu)造函數(shù)除外)–私有拷貝獨(dú)立存儲,不與原變量一致main(){

inti=10000;#pragmaompparallelprivate(i){i=-10000;}

printf("%d\n",i);}運(yùn)行:10000main(){

inti=10000;#pragmaompparallel{i=-10000;}

printf("%d\n",i);}運(yùn)行:-100002006年4月67共享存儲編程Private變量將在組內(nèi)每一線程中進(jìn)行創(chuàng)建,如果只有如果變量有構(gòu)造函數(shù),則調(diào)用構(gòu)造函數(shù)進(jìn)行初始化,否則該私有變量的值不確定.在進(jìn)入并行結(jié)構(gòu)中,私有變量引用的原變量值是不確定的;也不能在并行構(gòu)造對引用的變量進(jìn)行修改,在結(jié)構(gòu)中對這些對私有變量的修改不影響退出結(jié)構(gòu)后的同名變量值.私有變量應(yīng)在并行性構(gòu)造中進(jìn)行初始化;私有變量不能為引用類型(破壞了數(shù)據(jù)的獨(dú)立性);2006年4月68共享存儲編程?For結(jié)構(gòu)中:main(){

inti,sum=0,myid;#pragmaompparallelfor\

private(i,sum)for(i=0;i<10;i++){

myid=omp_get_thread_num();

printf("%d\n",myid);sum=sum+1;

printf("%d\n",sum);}

printf("sum=%d\n",sum);}3804398705280439870528043987062804398707080439870508043987060804398707180439870518043987061804398707sum=10變量sum未初始化.2006年4月69共享存儲編程FirstprivateFirstprivate是private的特殊情況.–在主線程中初始化每一個線程的私有拷貝變量.main(){

inti,sum=0,myid;#pragmaompparallelforfirstprivate(i,sum)for(i=0;i<10;i++){ sum=sum+1;

printf("%d\n",sum);}

printf("sum=%d\n",sum);}1231123123:2006年4月70共享存儲編程LastprivateLastprivate將位于迭代末的私有變量轉(zhuǎn)化為全局變量.#pragmaompparallel{#pragmaompforlastprivate(i)for(i=0;i<n-1;i++)a[i]=b[i]+b[i+1];}a[i]=b[0];for(i=1;i<n-1;i++) a(i)=b(i+1)a(i)=b(0)順序執(zhí)行i=n-12006年4月71共享存儲編程默認(rèn)情形=default(shared)(因此不顯示使用)改變默認(rèn)default(private):將并行區(qū)內(nèi)變量的默認(rèn)類型改為私有,而不是共享省去在每一并行區(qū)結(jié)構(gòu)后加private(list)default(none):

指事先指定并行區(qū)中變量的默認(rèn)類型Fortran支持default(private).C/C++無default(private),只有default(shared)和default(none).Default2006年4月72共享存儲編程DEFAULT例(Fortran)itotal=1000C$OMPPARALLELDEFAULT(PRIVATE)SHARED(itotal)np=omp_get_num_threads()each=itotal/np………C$OMPENDPARALLELitotal=1000C$OMPPARALLELPRIVATE(np,each)np=omp_get_num_threads()each=itotal/np………C$OMPENDPARALLEL2006年4月73共享存儲編程reduction歸約操作(將各線程中處理結(jié)果經(jīng)某種運(yùn)算后送回到根進(jìn)程)

reduction(op:list).List中所列變量必須為并行區(qū)內(nèi)的共享變量.支持的運(yùn)算操作:OperatorInitialization+ 0* 1&& 1|| 0僅支持標(biāo)量的歸約操作#pragmaompparallelforprivate(i)shared(x,y,n)reduction(+:a,b)for(i=0;i<n;i++){ a=a+x[i]; b=b+y[i];}2006年4月74共享存儲編程實(shí)例:PI求解通過數(shù)值積分的方法串行求解PI很簡單的(具體代碼見下一頁).基于OpenMP將該串行程序并行化.依據(jù)使用制導(dǎo)語句的不同,可有若干種方法(我們只討論基于剛講過的并行區(qū)與for結(jié)構(gòu)):僅用并行區(qū)結(jié)構(gòu)將該程序改為一SPMD并行程序.用任務(wù)分割結(jié)構(gòu)進(jìn)行并行化.歸約.2006年4月75共享存儲編程串行程序#include"stdio.h"main(intargc,char*argv[]){…n=atoi(argv[1]);w=1.0/(double)n;sum=0.0;for(i=0;i<n;i++){x=w*((double)i-0.5);sum=sum+4.0/(1.0+x*x);}pi=w*sum;

printf("Computedpi=%.16f\n",pi);}2006年4月76共享存儲編程僅基于Parallel塊結(jié)構(gòu)的并行程序#include"stdio.h"

main(int

argc,char*argv[]){ …n=atoi(argv[1]);w=1.0/(double)n;sum=0.0;

#pragma

ompparallelprivate(x)shared(w)reduction(+:sum){

myid=omp_get_thread_num();

numthreads=omp_get_num_threads();for(i=myid;i<n;i+=numthreads){x=w*((double)i-0.5);sum=sum+4.0/(1.0+x*x);}

}….

類似于多線程編程2006年4月77共享存儲編程基于for結(jié)構(gòu)的并行化代碼#include"stdio.h"

main(int

argc,char*argv[]){ …n=atoi(argv[1]);w=1.0/(double)n;sum=0.0;

#pragma

ompforreduction(+:sum)for(i=0;i<n;i++){x=w*((double)i-0.5);sum=sum+4.0/(1.0+x*x);}pi=w*sum;

printf("Computedpi=%.16f\n",pi);}與Pthreads比較2006年4月78共享存儲編程OpenMP結(jié)構(gòu)化塊類型OpenMP主要有五類結(jié)構(gòu)化塊:并行區(qū)ParallelRegions任務(wù)分割Worksharing數(shù)據(jù)環(huán)境DataEnvironment同步Synchronization運(yùn)行時函數(shù)/環(huán)境變量2006年4月79共享存儲編程OpenMP同步共享變量讀寫單一文件I/OOpenMP提共下列同步結(jié)構(gòu):–atomic–criticalsection–barrier–flush–ordered–single–master這兩個結(jié)構(gòu)實(shí)質(zhì)上不屬于同步結(jié)構(gòu),是并行區(qū)結(jié)構(gòu)和任務(wù)分割結(jié)構(gòu)中的內(nèi)容.2006年4月80共享存儲編程criticalsection同時至多有一個線程進(jìn)入臨界區(qū).#pragma

ompcritical[(name)]new-linestructured-blockC$OMPPARALLELDOPRIVATE(B)C$OMP&SHARED(RES)DO100I=1,NITERS B=DOIT(I)C$OMP

CRITICAL CALLCONSUME(B,RES)C$OMPENDCRITICAL100CONTINUE2006年4月81共享存儲編程atomicAtomic是臨界區(qū)的特例,主要用于某些簡單的語句.#pragma

ompatomicnew-lineexpression-stmt其中expression-stmt只能為下列情形:xbinop

=expr

(bino只能是+*-/&^|<<>>)x++++xx----x僅用于內(nèi)存變量的更新(在下面的例子中即對X的更新)C$OMPPARALLELPRIVATE(B)B=DOIT(I)C$OMPATOMICX=X+BC$OMPENDPARALLEL2006年4月82共享存儲編程下面兩段代碼區(qū)別是什么?#pragmaompparallelfor\shared(x,y,index,n)for(i=0;i<n;i++){

#pragmaompatomic x[index[i]]+=work1(i); y[i]+=work2(i);}#pragmaompparallelfor\shared(x,y,index,n)for(i=0;i<n;i++){

#pragmaompcritical x[index[i]]+=work1(i); y[i]+=work2(i);}原子操作臨界區(qū)2006年4月83共享存儲編程原子操作和臨界區(qū)比較

原子性是指操作的不可再分性,OpenMP利用原子結(jié)構(gòu)主要是用于防止多線程對內(nèi)存的同一地址的并發(fā)寫.臨界區(qū)可以完成所有的原子操作.原子結(jié)構(gòu)可更好被編譯優(yōu)化:有硬件指令可用于實(shí)現(xiàn)原子操作,而且系統(tǒng)開銷也很小.原子操作與并發(fā)并不