并行程序設(shè)計(jì)基礎(chǔ)

并行程序設(shè)計(jì)基礎(chǔ)第一頁(yè)，共四十五頁(yè)，2022年，8月28日并行程序設(shè)計(jì)基礎(chǔ)12.1并行程序設(shè)計(jì)概述12.2進(jìn)程12.3線程12.4同步12.5通信12.6并行程序設(shè)計(jì)模型2023/3/152第二頁(yè)，共四十五頁(yè)，2022年，8月28日并行程序設(shè)計(jì)概述并行程序設(shè)計(jì)難的原因并行語(yǔ)言的構(gòu)造方法并行性問(wèn)題交互/通信問(wèn)題五種并行編程風(fēng)范計(jì)算圓周率的樣本程序2023/3/153第三頁(yè)，共四十五頁(yè)，2022年，8月28日1并行程序設(shè)計(jì)難的原因技術(shù)先行,缺乏理論指導(dǎo)程序的語(yǔ)法/語(yǔ)義復(fù)雜,需要用戶自已處理任務(wù)/數(shù)據(jù)的劃分/分配數(shù)據(jù)交換同步和互斥性能平衡并行語(yǔ)言缺乏代可擴(kuò)展和異構(gòu)可擴(kuò)展,程序移植困難,重寫(xiě)代碼難度太大環(huán)境和工具缺乏較長(zhǎng)的生長(zhǎng)期,缺乏代可擴(kuò)展和異構(gòu)可擴(kuò)展2023/3/154第四頁(yè)，共四十五頁(yè)，2022年，8月28日2并行語(yǔ)言的構(gòu)造方法串行代碼段for(i=0;i<N;i++)A[i]=b[i]*b[i+1];for(i=0;i<N;i++)c[i]=A[i]+A[i+1];(a)使用庫(kù)例程構(gòu)造并行程序id=my_process_id();p=number_of_processes();for(i=id;i<N;i=i+p)A[i]=b[i]*b[i+1];barrier();for(i=id;i<N;i=i+p)c[i]=A[i]+A[i+1];例子:MPI,PVM,Pthreads(b)擴(kuò)展串行語(yǔ)言my_process_id,number_of_processes(),andbarrier()A(0:N-1)=b(0:N-1)*b(1:N)c=A(0:N-1)+A(1:N)例子:Fortran90(c)加編譯注釋構(gòu)造并行程序的方法#pragmaparallel#pragmashared(A,b,c)#pragmalocal(i){#pragmapforiterate(i=0;N;1)for(i=0;i<N;i++)A[i]=b[i]*b[i+1];#pragmasynchronize#pragmapforiterate(i=0;N;1)for(i=0;i<N;i++)c[i]=A[i]+A[i+1];}例子：SGIpowerC2023/3/155第五頁(yè)，共四十五頁(yè)，2022年，8月28日三種并行語(yǔ)言構(gòu)造方法比較2并行語(yǔ)言的構(gòu)造方法2023/3/156第六頁(yè)，共四十五頁(yè)，2022年，8月28日3并行性問(wèn)題3.1進(jìn)程的同構(gòu)性SIMD:所有進(jìn)程在同一時(shí)間執(zhí)行相同的指令MIMD:各個(gè)進(jìn)程在同一時(shí)間可以執(zhí)行不同的指令SPMD:各個(gè)進(jìn)程是同構(gòu)的，多個(gè)進(jìn)程對(duì)不同的數(shù)據(jù)執(zhí)行相同的代碼(一般是數(shù)據(jù)并行的同義語(yǔ))常對(duì)應(yīng)并行循環(huán)，數(shù)據(jù)并行結(jié)構(gòu)，單代碼MPMD:各個(gè)進(jìn)程是異構(gòu)的，多個(gè)進(jìn)程執(zhí)行不同的代碼（一般是任務(wù)并行，或功能并行，或控制并行的同義語(yǔ)）常對(duì)應(yīng)并行塊，多代碼要為有1000個(gè)處理器的計(jì)算機(jī)編寫(xiě)一個(gè)完全異構(gòu)的并行程序是很困難的2023/3/157第七頁(yè)，共四十五頁(yè)，2022年，8月28日并行塊parbeginS1S2S3…….SnparendS1S2S3…….Sn可以是不同的代碼并行循環(huán):當(dāng)并行塊中所有進(jìn)程共享相同代碼時(shí)parbeginS1S2S3…….SnparendS1S2S3…….Sn是相同代碼簡(jiǎn)化為parfor(i=1;i<=n,i++)S(i)進(jìn)程的同構(gòu)性3并行性問(wèn)題2023/3/158第八頁(yè)，共四十五頁(yè)，2022年，8月28日用單代碼方法說(shuō)明SPMD要說(shuō)明以下SPMD程序:parfor(i=0;i<=N,i++)foo(i)用戶需寫(xiě)一個(gè)以下程序:pid=my_process_id();numproc=number_of_processes();parfor(i=pid;i<=N,i=i+numproc)foo(i)此程序經(jīng)編譯后生成可執(zhí)行程序A,用shell腳本將它加載到N個(gè)處理結(jié)點(diǎn)上:runA–numnodesNSPMD程序的構(gòu)造方法用數(shù)據(jù)并行程序的構(gòu)造方法要說(shuō)明以下SPMD程序:parfor(i=0;i<=N,i++){C[i]=A[i]+B[i];}用戶可用一條數(shù)據(jù)賦值語(yǔ)句:C=A+B或forall(i=1,N)C[i]=A[i]+B[i]進(jìn)程的同構(gòu)性3并行性問(wèn)題2023/3/159第九頁(yè)，共四十五頁(yè)，2022年，8月28日用SPMD偽造MPMD要說(shuō)明以下MPMD程序:parbeginS1S2S3parend

可以用以下SPMD程序:parfor(i=0;i<3,i++){if(i=0)S1if(i=1)S2if(i=2)S3}因此,對(duì)于可擴(kuò)展并行機(jī)來(lái)說(shuō),只要支持SPMD就足夠了MPMD程序的構(gòu)造方法用多代碼方法說(shuō)明MPMD對(duì)不提供并行塊或并行循環(huán)的語(yǔ)言要說(shuō)明以下MPMD程序:parbeginS1S2S3parend用戶需寫(xiě)3個(gè)程序,分別編譯生成3個(gè)可執(zhí)行程序S1S2S3,用shell腳本將它們加載到3個(gè)處理結(jié)點(diǎn)上:runS1onnode1runS2onnode1runS3onnode1S1,S2和S3是順序語(yǔ)言程序加上進(jìn)行交互的庫(kù)調(diào)用.進(jìn)程的同構(gòu)性3并行性問(wèn)題2023/3/1510第十頁(yè)，共四十五頁(yè)，2022年，8月28日3.2靜態(tài)和動(dòng)態(tài)并行性程序的結(jié)構(gòu):由它的組成部分構(gòu)成程序的方法靜態(tài)并行性的例子:parbeginP,Q,Rparend其中P,Q,R是靜態(tài)的動(dòng)態(tài)并行性的例子:while(C>0)beginfork(foo(C));C:=boo(C);end3并行性問(wèn)題靜態(tài)并行性:程序的結(jié)構(gòu)以及進(jìn)程的個(gè)數(shù)在運(yùn)行之前(如編譯時(shí),連接時(shí)或加載時(shí))就可確定,就認(rèn)為該程序具有靜態(tài)并行性.動(dòng)態(tài)并行性:否則就認(rèn)為該程序具有動(dòng)態(tài)并行性.即意味著進(jìn)程要在運(yùn)行時(shí)創(chuàng)建和終止2023/3/1511第十一頁(yè)，共四十五頁(yè)，2022年，8月28日ProcessA:beginZ:=1fork(B);T:=foo(3);endProcessB:beginfork(C);X:=foo(Z);join(C);output(X+Y);endProcessC:beginY:=foo(Z);end開(kāi)發(fā)動(dòng)態(tài)并行性的一般方法:Fork/Join靜態(tài)和動(dòng)態(tài)并行性3并行性問(wèn)題Fork:派生一個(gè)子進(jìn)程Join:強(qiáng)制父進(jìn)程等待子進(jìn)程2023/3/1512第十二頁(yè)，共四十五頁(yè)，2022年，8月28日3.3進(jìn)程編組目的:支持進(jìn)程間的交互,常把需要交互的進(jìn)程調(diào)度在同一組中一個(gè)進(jìn)程組成員由：組標(biāo)識(shí)符+成員序號(hào)唯一確定.3.4劃分與分配原則:使系統(tǒng)大部分時(shí)間忙于計(jì)算,而不是閑置或忙于交互;同時(shí)不犧牲并行性(度).劃分:切割數(shù)據(jù)和工作負(fù)載分配：將劃分好的數(shù)據(jù)和工作負(fù)載映射到計(jì)算結(jié)點(diǎn)(處理器)上分配方式顯式分配:由用戶指定數(shù)據(jù)和負(fù)載如何加載隱式分配：由編譯器和運(yùn)行時(shí)支持系統(tǒng)決定就近分配原則：進(jìn)程所需的數(shù)據(jù)靠近使用它的進(jìn)程代碼3并行性問(wèn)題2023/3/1513第十三頁(yè)，共四十五頁(yè)，2022年，8月28日并行度(DegreeofParallelism,DOP):同時(shí)執(zhí)行的分進(jìn)程數(shù).并行粒度(Granularity):兩次并行或交互操作之間所執(zhí)行的計(jì)算負(fù)載.指令級(jí)并行塊級(jí)并行進(jìn)程級(jí)并行任務(wù)級(jí)并行并行度與并行粒度大小?；榈箶?shù):增大粒度會(huì)減小并行度.增加并行度會(huì)增加系統(tǒng)(同步)開(kāi)銷3并行性問(wèn)題2023/3/1514第十四頁(yè)，共四十五頁(yè)，2022年，8月28日4交互／通信問(wèn)題交互：進(jìn)程間的相互影響4.1交互的類型通信：兩個(gè)或多個(gè)進(jìn)程間傳送數(shù)的操作通信方式：共享變量父進(jìn)程傳給子進(jìn)程(參數(shù)傳遞方式)消息傳遞2023/3/1515第十五頁(yè)，共四十五頁(yè)，2022年，8月28日同步：導(dǎo)致進(jìn)程間相互等待或繼續(xù)執(zhí)行的操作同步方式:原子同步控制同步(路障,臨界區(qū))數(shù)據(jù)同步(鎖,條件臨界區(qū),監(jiān)控程序,事件)例子:原子同步parfor(i:=1;i<n;i++){atomic{x:=x+1;y:=y-1}}路障同步parfor(i:=1;i<n;i++){Pi

barrierQi

}臨界區(qū)parfor(i:=1;i<n;i++){critical{x:=x+1;y:=y+1}}數(shù)據(jù)同步(信號(hào)量同步)parfor(i:=1;i<n;i++){lock(S);x:=x+1;y:=y-1;unlock(S)}4交互／通信問(wèn)題2023/3/1516第十六頁(yè)，共四十五頁(yè)，2022年，8月28日聚集(aggregation)：用一串超步將各分進(jìn)程計(jì)算所得的部分結(jié)果合并為一個(gè)完整的結(jié)果,每個(gè)超步包含一個(gè)短的計(jì)算和一個(gè)簡(jiǎn)單的通信或/和同步.聚集方式:歸約掃描交互的類型4交互／通信問(wèn)題例子:計(jì)算兩個(gè)向量的內(nèi)積parfor(i:=1;i<n;i++){X[i]:=A[i]*B[i]inner_product:=aggregate_sum(X[i]);}2023/3/1517第十七頁(yè)，共四十五頁(yè)，2022年，8月28日4.2交互的方式4交互／通信問(wèn)題

交互代碼C

……P1P2Pn相對(duì)于交互代碼C,可對(duì)進(jìn)程P定義如下?tīng)顟B(tài):到達(dá)(arrived):P剛到達(dá)C,但還未進(jìn)入在內(nèi)(in):P在代碼中完成(finished):P剛完成執(zhí)行代碼C,但還未離開(kāi)在外(out):P不在代碼中(未到達(dá)或已離開(kāi))同步的交互:所有參與者同時(shí)到達(dá)并執(zhí)行交互代碼C異步的交互:進(jìn)程到達(dá)C后,不必等待其它進(jìn)程到達(dá)即可執(zhí)行C2023/3/1518第十八頁(yè)，共四十五頁(yè)，2022年，8月28日交互方式與入口/出口條件的組合4交互／通信問(wèn)題鎖定的發(fā)送:消息已發(fā)完,但不一定已收到鎖定的接收:消息已收到非鎖定的發(fā)/收:只是發(fā)出發(fā)/收的請(qǐng)求2023/3/1519第十九頁(yè)，共四十五頁(yè)，2022年，8月28日4.3交互的模式按交互模式是否能在編譯時(shí)確定分為:靜態(tài)的動(dòng)態(tài)的按有多少發(fā)送者和接收者參與通信分為一對(duì)一:點(diǎn)到點(diǎn)(pointtopoint)一對(duì)多:廣播(broadcast),播撒(scatter)多對(duì)一:收集(gather),歸約(reduce)多對(duì)多:全交換(TatalExchange),掃描(scan),置換/移位(permutation/shift)4交互／通信問(wèn)題2023/3/1520第二十頁(yè)，共四十五頁(yè)，2022年，8月28日135P1P2P3135,1P1P2P3135P1P2P31,13,15,1P1P2P31,3,5

P1P2P31,3,535P1P2P3135P1P2P31,3,535P1P2P3(a)點(diǎn)對(duì)點(diǎn)(一對(duì)一):P1發(fā)送一個(gè)值給P3(b)廣播(一對(duì)多):P1發(fā)送一個(gè)值給全體(c)播撒(一對(duì)多):P1向每個(gè)結(jié)點(diǎn)發(fā)送一個(gè)值(d)收集(多對(duì)一):P1從每個(gè)結(jié)點(diǎn)接收一個(gè)值4交互／通信問(wèn)題2023/3/1521第二十一頁(yè)，共四十五頁(yè)，2022年，8月28日135P1P2P31,53,15,3P1P2P31,2,34,5,67,8,9P1P2P31,4,72,5,83,6,9P1P2P3135P1P2P31,13,45,9P1P2P3135P1P2P31,935P1P2P3(e)全交換(多對(duì)多):每個(gè)結(jié)點(diǎn)向每個(gè)結(jié)點(diǎn)發(fā)送一個(gè)不同的消息(f)移位(置換,多對(duì)多):每個(gè)結(jié)點(diǎn)向下一個(gè)結(jié)點(diǎn)發(fā)送一個(gè)值并接收來(lái)自上一個(gè)結(jié)點(diǎn)的一個(gè)值.(g)歸約(多對(duì)一):P1得到和1+3+5=9(h)掃描(多對(duì)多):P1得到1,P2得到1+3=4,P3得到1+3+5=94交互／通信問(wèn)題2023/3/1522第二十二頁(yè)，共四十五頁(yè)，2022年，8月28日相并行（PhaseParallel）分治并行（DivideandConquerParallel）流水線并行（PipelineParallel）主從并行（Master-SlaveParallel）工作池并行（WorkPoolParallel）5五種并行編程風(fēng)范2023/3/1523第二十三頁(yè)，共四十五頁(yè)，2022年，8月28日相并行（PhaseParallel）一組超級(jí)步（相）步內(nèi)各自計(jì)算步間通信、同步BSP（4.2.3）方便差錯(cuò)和性能分析計(jì)算和通信不能重疊CCCSynchronousInteraction......CCCSynchronousInteraction......2023/3/1524第二十四頁(yè)，共四十五頁(yè)，2022年，8月28日主－從并行（Master-SlaveParallel）主進(jìn)程：串行、協(xié)調(diào)任務(wù)子進(jìn)程：計(jì)算子任務(wù)劃分設(shè)計(jì)技術(shù)（6.1）與相并行結(jié)合主進(jìn)程易成為瓶頸MasterSlaveSlaveSlave2023/3/1525第二十五頁(yè)，共四十五頁(yè)，2022年，8月28日分治并行（DivideandConquerParallel）父進(jìn)程把負(fù)載分割并指派給子進(jìn)程遞歸重點(diǎn)在于歸并分治設(shè)計(jì)技術(shù)（6.2）難以負(fù)載平衡2023/3/1526第二十六頁(yè)，共四十五頁(yè)，2022年，8月28日流水線并行（PipelineParallel）一組進(jìn)程流水線作業(yè)流水線設(shè)計(jì)技術(shù)（6.5）P1P2P32023/3/1527第二十七頁(yè)，共四十五頁(yè)，2022年，8月28日工作池并行（WorkPoolParallel）初始狀態(tài)：一件工作進(jìn)程從池中取任務(wù)執(zhí)行可產(chǎn)生新任務(wù)放回池中直至任務(wù)池為空易與負(fù)載平衡臨界區(qū)問(wèn)題（尤其消息傳遞）WorkPoolP1P2P32023/3/1528第二十八頁(yè)，共四十五頁(yè)，2022年，8月28日8計(jì)算圓周率的樣本程序2023/3/1529第二十九頁(yè)，共四十五頁(yè)，2022年，8月28日計(jì)算圓周率的c語(yǔ)言代碼段#defineN1000000main(){

doublelocal,pi=0.0,w;

longi; w=1.0/N;

for(i=0;i<N;i++){ local=(i+0.5)*w; pi=pi+4.0/(1.0+local*local); } printf(“piis%f\n”,pi*w);}2023/3/1530第三十頁(yè)，共四十五頁(yè)，2022年，8月28日并行程序設(shè)計(jì)基礎(chǔ)12.1并行程序設(shè)計(jì)概述12.2進(jìn)程12.3線程12.4同步12.5通信12.6并行程序設(shè)計(jì)模型2023/3/1531第三十一頁(yè)，共四十五頁(yè)，2022年，8月28日進(jìn)程進(jìn)程的基本概念進(jìn)程的并行執(zhí)行進(jìn)程的相互作用2023/3/1532第三十二頁(yè)，共四十五頁(yè)，2022年，8月28日并行程序設(shè)計(jì)基礎(chǔ)12.1并行程序設(shè)計(jì)概述12.2進(jìn)程12.3線程12.4同步12.5通信12.6并行程序設(shè)計(jì)模型2023/3/1533第三十三頁(yè)，共四十五頁(yè)，2022年，8月28日線程線程的基本概念線程的管理線程的同步2023/3/1534第三十四頁(yè)，共四十五頁(yè)，2022年，8月28日并行程序設(shè)計(jì)基礎(chǔ)12.1并行程序設(shè)計(jì)概述12.2進(jìn)程12.3線程12.4同步12.5通信12.6并行程序設(shè)計(jì)模型2023/3/1535第三十五頁(yè)，共四十五頁(yè)，2022年，8月28日同步原子和互斥高級(jí)同步結(jié)構(gòu)低級(jí)同步原語(yǔ)2023/3/1536第三十六頁(yè)，共四十五頁(yè)，2022年，8月28日并行程序設(shè)計(jì)基礎(chǔ)12.1并行程序設(shè)計(jì)概述12.2進(jìn)程12.3線程12.4同步12.5通信12.6并行程序設(shè)計(jì)模型2023/3/1537第三十七頁(yè)，共四十五頁(yè)，2022年，8月28日通信影響通信系統(tǒng)性能的因素低級(jí)通信支持TCP/IP通信協(xié)議組簡(jiǎn)介20