并行程序設計基礎

并行程序設計基礎第1頁，共45頁，2023年，2月20日，星期一并行程序設計基礎12.1并行程序設計概述12.2進程12.3線程12.4同步12.5通信12.6并行程序設計模型2023/4/292第2頁，共45頁，2023年，2月20日，星期一并行程序設計概述并行程序設計難的原因并行語言的構造方法并行性問題交互/通信問題五種并行編程風范計算圓周率的樣本程序2023/4/293第3頁，共45頁，2023年，2月20日，星期一1并行程序設計難的原因技術先行,缺乏理論指導程序的語法/語義復雜,需要用戶自已處理任務/數據的劃分/分配數據交換同步和互斥性能平衡并行語言缺乏代可擴展和異構可擴展,程序移植困難,重寫代碼難度太大環(huán)境和工具缺乏較長的生長期,缺乏代可擴展和異構可擴展2023/4/294第4頁，共45頁，2023年，2月20日，星期一2并行語言的構造方法串行代碼段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)使用庫例程構造并行程序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)擴展串行語言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)加編譯注釋構造并行程序的方法#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/4/295第5頁，共45頁，2023年，2月20日，星期一三種并行語言構造方法比較2并行語言的構造方法2023/4/296第6頁，共45頁，2023年，2月20日，星期一3并行性問題3.1進程的同構性SIMD:所有進程在同一時間執(zhí)行相同的指令MIMD:各個進程在同一時間可以執(zhí)行不同的指令SPMD:各個進程是同構的，多個進程對不同的數據執(zhí)行相同的代碼(一般是數據并行的同義語)常對應并行循環(huán)，數據并行結構，單代碼MPMD:各個進程是異構的，多個進程執(zhí)行不同的代碼（一般是任務并行，或功能并行，或控制并行的同義語）常對應并行塊，多代碼要為有1000個處理器的計算機編寫一個完全異構的并行程序是很困難的2023/4/297第7頁，共45頁，2023年，2月20日，星期一并行塊parbeginS1S2S3…….SnparendS1S2S3…….Sn可以是不同的代碼并行循環(huán):當并行塊中所有進程共享相同代碼時parbeginS1S2S3…….SnparendS1S2S3…….Sn是相同代碼簡化為parfor(i=1;i<=n,i++)S(i)進程的同構性3并行性問題2023/4/298第8頁，共45頁，2023年，2月20日，星期一用單代碼方法說明SPMD要說明以下SPMD程序:parfor(i=0;i<=N,i++)foo(i)用戶需寫一個以下程序:pid=my_process_id();numproc=number_of_processes();parfor(i=pid;i<=N,i=i+numproc)foo(i)此程序經編譯后生成可執(zhí)行程序A,用shell腳本將它加載到N個處理結點上:runA–numnodesNSPMD程序的構造方法用數據并行程序的構造方法要說明以下SPMD程序:parfor(i=0;i<=N,i++){C[i]=A[i]+B[i];}用戶可用一條數據賦值語句:C=A+B或forall(i=1,N)C[i]=A[i]+B[i]進程的同構性3并行性問題2023/4/299第9頁，共45頁，2023年，2月20日，星期一用SPMD偽造MPMD要說明以下MPMD程序:parbeginS1S2S3parend

可以用以下SPMD程序:parfor(i=0;i<3,i++){if(i=0)S1if(i=1)S2if(i=2)S3}因此,對于可擴展并行機來說,只要支持SPMD就足夠了MPMD程序的構造方法用多代碼方法說明MPMD對不提供并行塊或并行循環(huán)的語言要說明以下MPMD程序:parbeginS1S2S3parend用戶需寫3個程序,分別編譯生成3個可執(zhí)行程序S1S2S3,用shell腳本將它們加載到3個處理結點上:runS1onnode1runS2onnode1runS3onnode1S1,S2和S3是順序語言程序加上進行交互的庫調用.進程的同構性3并行性問題2023/4/2910第10頁，共45頁，2023年，2月20日，星期一3.2靜態(tài)和動態(tài)并行性程序的結構:由它的組成部分構成程序的方法靜態(tài)并行性的例子:parbeginP,Q,Rparend其中P,Q,R是靜態(tài)的動態(tài)并行性的例子:while(C>0)beginfork(foo(C));C:=boo(C);end3并行性問題靜態(tài)并行性:程序的結構以及進程的個數在運行之前(如編譯時,連接時或加載時)就可確定,就認為該程序具有靜態(tài)并行性.動態(tài)并行性:否則就認為該程序具有動態(tài)并行性.即意味著進程要在運行時創(chuàng)建和終止2023/4/2911第11頁，共45頁，2023年，2月20日，星期一ProcessA:beginZ:=1fork(B);T:=foo(3);endProcessB:beginfork(C);X:=foo(Z);join(C);output(X+Y);endProcessC:beginY:=foo(Z);end開發(fā)動態(tài)并行性的一般方法:Fork/Join靜態(tài)和動態(tài)并行性3并行性問題Fork:派生一個子進程Join:強制父進程等待子進程2023/4/2912第12頁，共45頁，2023年，2月20日，星期一3.3進程編組目的:支持進程間的交互,常把需要交互的進程調度在同一組中一個進程組成員由：組標識符+成員序號唯一確定.3.4劃分與分配原則:使系統(tǒng)大部分時間忙于計算,而不是閑置或忙于交互;同時不犧牲并行性(度).劃分:切割數據和工作負載分配：將劃分好的數據和工作負載映射到計算結點(處理器)上分配方式顯式分配:由用戶指定數據和負載如何加載隱式分配：由編譯器和運行時支持系統(tǒng)決定就近分配原則：進程所需的數據靠近使用它的進程代碼3并行性問題2023/4/2913第13頁，共45頁，2023年，2月20日，星期一并行度(DegreeofParallelism,DOP):同時執(zhí)行的分進程數.并行粒度(Granularity):兩次并行或交互操作之間所執(zhí)行的計算負載.指令級并行塊級并行進程級并行任務級并行并行度與并行粒度大小?；榈箶?增大粒度會減小并行度.增加并行度會增加系統(tǒng)(同步)開銷3并行性問題2023/4/2914第14頁，共45頁，2023年，2月20日，星期一4交互／通信問題交互：進程間的相互影響4.1交互的類型通信：兩個或多個進程間傳送數的操作通信方式：共享變量父進程傳給子進程(參數傳遞方式)消息傳遞2023/4/2915第15頁，共45頁，2023年，2月20日，星期一同步：導致進程間相互等待或繼續(xù)執(zhí)行的操作同步方式:原子同步控制同步(路障,臨界區(qū))數據同步(鎖,條件臨界區(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}}數據同步(信號量同步)parfor(i:=1;i<n;i++){lock(S);x:=x+1;y:=y-1;unlock(S)}4交互／通信問題2023/4/2916第16頁，共45頁，2023年，2月20日，星期一聚集(aggregation)：用一串超步將各分進程計算所得的部分結果合并為一個完整的結果,每個超步包含一個短的計算和一個簡單的通信或/和同步.聚集方式:歸約掃描交互的類型4交互／通信問題例子:計算兩個向量的內積parfor(i:=1;i<n;i++){X[i]:=A[i]*B[i]inner_product:=aggregate_sum(X[i]);}2023/4/2917第17頁，共45頁，2023年，2月20日，星期一4.2交互的方式4交互／通信問題

交互代碼C

……P1P2Pn相對于交互代碼C,可對進程P定義如下狀態(tài):到達(arrived):P剛到達C,但還未進入在內(in):P在代碼中完成(finished):P剛完成執(zhí)行代碼C,但還未離開在外(out):P不在代碼中(未到達或已離開)同步的交互:所有參與者同時到達并執(zhí)行交互代碼C異步的交互:進程到達C后,不必等待其它進程到達即可執(zhí)行C2023/4/2918第18頁，共45頁，2023年，2月20日，星期一交互方式與入口/出口條件的組合4交互／通信問題鎖定的發(fā)送:消息已發(fā)完,但不一定已收到鎖定的接收:消息已收到非鎖定的發(fā)/收:只是發(fā)出發(fā)/收的請求2023/4/2919第19頁，共45頁，2023年，2月20日，星期一4.3交互的模式按交互模式是否能在編譯時確定分為:靜態(tài)的動態(tài)的按有多少發(fā)送者和接收者參與通信分為一對一:點到點(pointtopoint)一對多:廣播(broadcast),播撒(scatter)多對一:收集(gather),歸約(reduce)多對多:全交換(TatalExchange),掃描(scan),置換/移位(permutation/shift)4交互／通信問題2023/4/2920第20頁，共45頁，2023年，2月20日，星期一135P1P2P3135,1P1P2P3135P1P2P31,13,15,1P1P2P31,3,5

P1P2P31,3,535P1P2P3135P1P2P31,3,535P1P2P3(a)點對點(一對一):P1發(fā)送一個值給P3(b)廣播(一對多):P1發(fā)送一個值給全體(c)播撒(一對多):P1向每個結點發(fā)送一個值(d)收集(多對一):P1從每個結點接收一個值4交互／通信問題2023/4/2921第21頁，共45頁，2023年，2月20日，星期一135P1P2P31,53,15,3P1P2P31,2,34,5,67,8,9P1P2P31,4,72,5,83,6,9P1P2P3135P1P2P31,13,45,9P1P2P3135P1P2P31,935P1P2P3(e)全交換(多對多):每個結點向每個結點發(fā)送一個不同的消息(f)移位(置換,多對多):每個結點向下一個結點發(fā)送一個值并接收來自上一個結點的一個值.(g)歸約(多對一):P1得到和1+3+5=9(h)掃描(多對多):P1得到1,P2得到1+3=4,P3得到1+3+5=94交互／通信問題2023/4/2922第22頁，共45頁，2023年，2月20日，星期一相并行（PhaseParallel）分治并行（DivideandConquerParallel）流水線并行（PipelineParallel）主從并行（Master-SlaveParallel）工作池并行（WorkPoolParallel）5五種并行編程風范2023/4/2923第23頁，共45頁，2023年，2月20日，星期一相并行（PhaseParallel）一組超級步（相）步內各自計算步間通信、同步BSP（4.2.3）方便差錯和性能分析計算和通信不能重疊CCCSynchronousInteraction......CCCSynchronousInteraction......2023/4/2924第24頁，共45頁，2023年，2月20日，星期一主－從并行（Master-SlaveParallel）主進程：串行、協(xié)調任務子進程：計算子任務劃分設計技術（6.1）與相并行結合主進程易成為瓶頸MasterSlaveSlaveSlave2023/4/2925第25頁，共45頁，2023年，2月20日，星期一分治并行（DivideandConquerParallel）父進程把負載分割并指派給子進程遞歸重點在于歸并分治設計技術（6.2）難以負載平衡2023/4/2926第26頁，共45頁，2023年，2月20日，星期一流水線并行（PipelineParallel）一組進程流水線作業(yè)流水線設計技術（6.5）P1P2P32023/4/2927第27頁，共45頁，2023年，2月20日，星期一工作池并行（WorkPoolParallel）初始狀態(tài)：一件工作進程從池中取任務執(zhí)行可產生新任務放回池中直至任務池為空易與負載平衡臨界區(qū)問題（尤其消息傳遞）WorkPoolP1P2P32023/4/2928第28頁，共45頁，2023年，2月20日，星期一8計算圓周率的樣本程序2023/4/2929第29頁，共45頁，2023年，2月20日，星期一計算圓周率的c語言代碼段#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/4/2930第30頁，共45頁，2023年，2月20日，星期一并行程序設計基礎12.1并行程序設計概述12.2進程12.3線程12.4同步12.5通信12.6并行程序設計模型2023/4/2931第31頁，共45頁，2023年，2月20日，星期一進程進程的基本概念進程的并行執(zhí)行進程的相互作用2023/4/2932第32頁，共45頁，2023年，2月20日，星期一并行程序設計基礎12.1并行程序設計概述12.2進程12.3線程12.4同步12.5通信12.6并行程序設計模型2023/4/2933第33頁，共45頁，2023年，2月20日，星期一線程線程的基本概念線程的管理線程的同步2023/4/2934第34頁，共45頁，2023年，2月20日，星期一并行程序設計基礎12.1并行程序設計概述12.2進程12.3線程12.4同步12.5通信12.6并行程序設計模型2023/4/2935第35頁，共45頁，2023年，2月20日，星期一同步原子和互斥高級同步結構低級同步原語2023/4/2936第36頁，共45頁，2023年，2月20日，星期一并行程序設計基礎12.1并行程序設計概述12.2進程12.3線程12.4同步12.5通信12.6并行程序設計模型2023/4/2937第37頁，共45頁，2023年，2月20日，星期一通信影響通信系統(tǒng)性能的因素低級通信支持TCP/IP通信協(xié)議組簡介2023/4/