十二、并行程序設(shè)計(jì)基礎(chǔ)Date1H.An Copyright Parallel Programming并行程序設(shè)計(jì)基礎(chǔ) 12.1 并行程序設(shè)計(jì)概述 12.2 進(jìn)程 12.3 線程 12.4 同步 12.5 通信 12.6 并行程序設(shè)計(jì)模型Date2H.An Copyright Parallel Programming并行程序設(shè)計(jì)概述 并行程序設(shè)計(jì)難的原因 并行語(yǔ)言的構(gòu)造方法 并行性問題 交互/通信問題 五種并行編程風(fēng)范 計(jì)算圓周率的樣本程序Date3H.An Copyright Parallel Programming1 并行程序設(shè)計(jì)難的原因v 技術(shù)先行,缺乏理論指導(dǎo)v 程序的語(yǔ)法/語(yǔ)義復(fù)雜, 需要用戶自已處理 任務(wù)/數(shù)據(jù)的劃分/分配 數(shù)據(jù)交換 同步和互斥 性能平衡v 并行語(yǔ)言缺乏代可擴(kuò)展和異構(gòu)可擴(kuò)展, 程序移植困難, 重寫代碼難度太大v 環(huán)境和工具缺乏較長(zhǎng)的生長(zhǎng)期, 缺乏代可擴(kuò)展和異構(gòu)可擴(kuò)展Date4H.An Copyright Parallel Programming2 并行語(yǔ)言的構(gòu)造方法串行代碼段for ( i= 0; iN; i+ ) Ai=bi*bi+1;for (i= 0; iN; i+) ci=Ai+Ai+1;(a) 使用庫(kù)例程構(gòu)造并行程序id=my_process_id();p=number_of_processes();for ( i= id; iN; i=i+p) Ai=bi*bi+1;barrier();for (i= id; iN; i=i+p) ci=Ai+Ai+1;例子: MPI,PVM, Pthreads(b) 擴(kuò)展串行語(yǔ)言my_process_id,number_of_processes(), and barrier()A(0:N-1)=b(0:N-1)*b(1:N)c=A(0:N-1)+A(1:N)例子: Fortran 90(c) 加編譯注釋構(gòu)造并行程序的方法#pragma parallel#pragma shared(A,b,c)#pragma local(i) # pragma pfor iterate(i=0;N;1)for (i=0;iN;i+) Ai=bi*bi+1;# pragma synchronize# pragma pfor iterate (i=0; N; 1)for (i=0;iN;i+)ci=Ai+Ai+1;例子：SGI power C Date5H.An Copyright Parallel Programming三種并行語(yǔ)言構(gòu)造方法比較2 并行語(yǔ)言的構(gòu)造方法Date6H.An Copyright Parallel Programming3 并行性問題3.1 進(jìn)程的同構(gòu)性vSIMD: 所有進(jìn)程在同一時(shí)間執(zhí)行相同的指令vMIMD:各個(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ī)編寫一個(gè)完全異構(gòu)的并行程序是很困難的Date7H.An Copyright Parallel Programming并行塊parbegin S1 S2 S3 .Sn parendS1 S2 S3 .Sn可以是不同的代碼并行循環(huán): 當(dāng)并行塊中所有進(jìn)程共享相同代碼時(shí)parbegin S1 S2 S3 .Sn parend S1 S2 S3 .Sn是相同代碼簡(jiǎn)化為parfor (i=1; i=n, i+) S(i)進(jìn)程的同構(gòu)性3 并行性問題Date8H.An Copyright Parallel Programming用單代碼方法說(shuō)明SPMD要說(shuō)明以下SPMD程序:parfor (i=0; i=N, i+) foo(i)用戶需寫一個(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)上:run A numnodes NSPMD程序的構(gòu)造方法用數(shù)據(jù)并行程序的構(gòu)造方法要說(shuō)明以下SPMD程序:parfor (i=0; i=N, i+) Ci=Ai+Bi;用戶可用一條數(shù)據(jù)賦值語(yǔ)句:C=A+B或forall (i=1,N) Ci=Ai+Bi進(jìn)程的同構(gòu)性3 并行性問題Date9H.An Copyright Parallel Programming用SPMD偽造MPMD要說(shuō)明以下MPMD程序:parbegin S1 S2 S3 parend 可以用以下SPMD程序:parfor (i=0; i0) beginfork (foo(C);C:=boo(C);end3 并行性問題靜態(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)建和終止Date11H.An Copyright Parallel ProgrammingProcess A:begin Z:=1fork(B);T:=foo(3);endProcess B:begin fork(C);X:=foo(Z);join(C);output(X+Y);endProcess C:begin Y:=foo(Z);end開發(fā)動(dòng)態(tài)并行性的一般方法: Fork/Join靜態(tài)和動(dòng)態(tài)并行性3 并行性問題Fork: 派生一個(gè)子進(jìn)程Join: 強(qiáng)制父進(jìn)程等待子進(jìn)程Date12H.An Copyright Parallel Programming3.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 并行性問題Date13H.An Copyright Parallel Programming并行度(Degree of Parallelism, DOP):同時(shí)執(zhí)行的分進(jìn)程數(shù). 并行粒度(Granularity): 兩次并行或交互操作之間所執(zhí)行的計(jì)算負(fù)載. 指令級(jí)并行 塊級(jí)并行 進(jìn)程級(jí)并行 任務(wù)級(jí)并行并行度與并行粒度大小?；榈箶?shù): 增大粒度會(huì)減小并行度. 增加并行度會(huì)增加系統(tǒng)(同步)開銷 3 并行性問題Date14H.An Copyright Parallel Programming4 交互通信問題交互：進(jìn)程間的相互影響4.1 交互的類型v通信：兩個(gè)或多個(gè)進(jìn)程間傳送數(shù)的操作 通信方式： 共享變量 父進(jìn)程傳給子進(jìn)程(參數(shù)傳遞方式) 消息傳遞 Date15H.An Copyright Parallel Programmingv同步：導(dǎo)致進(jìn)程間相互等待或繼續(xù)執(zhí)行的操作 同步方式: 原子同步 控制同步(路障,臨界區(qū)) 數(shù)據(jù)同步(鎖,條件臨界區(qū),監(jiān)控程序,事件)例子:原子同步parfor (i:=1; in; i+) atomicx:=x+1; y:=y-1路障同步parfor(i:=1; in; i+)Pi barrierQi 臨界區(qū)parfor(i:=1; in; i+)criticalx:=x+1; y:=y+1數(shù)據(jù)同步(信號(hào)量同步)parfor(i:=1; in; i+)lock(S); x:=x+1; y:=y-1; unlock(S)4 交互通信問題Date16H.An Copyright Parallel Programmingv聚集(aggregation)：用一串超步將各分進(jìn)程計(jì)算所得的部分結(jié)果合并為一個(gè)完整的結(jié)果, 每個(gè)超步包含一個(gè)短的計(jì)算和一個(gè)簡(jiǎn)單的通信或/和同步.聚集方式: 歸約 掃描交互的類型4 交互通信問題例子: 計(jì)算兩個(gè)向量的內(nèi)積parfor(i:=1; in; i+)Xi:=Ai*Biinner_product:=aggregate_sum(Xi);Date17H.An Copyright Parallel Programming4.2 交互的方式4 交互通信問題 交互代碼 C P1P2Pn相對(duì)于交互代碼C,可對(duì)進(jìn)程P定義如下狀態(tài): 到達(dá)(arrived): P剛到達(dá)C,但還未進(jìn)入 在內(nèi)(in): P在代碼中 完成(finished):P剛完成執(zhí)行代碼C,但還未離開 在外(out): P不在代碼中(未到達(dá)或已離開)同步的交互: 所有參與者同時(shí)到達(dá)并執(zhí)行交互代碼C異步的交互: 進(jìn)程到達(dá)C后, 不必等待其它進(jìn)程到達(dá)即可執(zhí)行CDate18H.An Copyright Parallel Programming交互方式與入口/出口條件的組合4 交互通信問題鎖定的發(fā)送: 消息已發(fā)完, 但不一定已收到鎖定的接收: 消息已收到非鎖定的發(fā)/收: 只是發(fā)出發(fā)/收的請(qǐng)求Date19H.An Copyright Parallel Programming4.3 交互的模式按交互模式是否能在編譯時(shí)確定分為: 靜態(tài)的 動(dòng)態(tài)的按有多少發(fā)送者和接收者參與通信分為 一對(duì)一:點(diǎn)到點(diǎn)(point to point) 一對(duì)多:廣播(broadcast),播撒(scatter) 多對(duì)一:收集(gather), 歸約(reduce) 多對(duì)多:全交換(Tatal Exchange), 掃描(scan) , 置換/移位(permutation/shift)4 交互通信問題Date20H.An Copyright Parallel Programming1 3 5 P1P2P31 3 5,1 P1P2P31 3 5 P1P2P31,1 3,1 5,1 P1P2P31,3,5 P1P2P31,3,5 3 5 P1P2P31 3 5 P1P2P31,3,5 3 5 P1P2P3(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 交互通信問題Date21H.An Copyright Parallel Programming1 3 5 P1P2P31,5 3,1 5,3 P1P2P31,2,3 4,5,6 7,8,9 P1P2P31,4,7 2,5,8 3,6,9 P1P2P31 3 5 P1P2P31,1 3,4 5,9 P1P2P31 3 5 P1P2P31,9 3 5 P1P2P3(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 交互通信問題Date22H.An Copyright Parallel Programming 相并行（Phase Parallel） 分治并行（Divide and Conquer Parallel） 流水線并行（Pipeline Parallel） 主從并行（Master-Slave Parallel） 工作池并行（Work Pool Parallel）5 五種并行編程風(fēng)范Date23H.An Copyright Parallel Programming相并行（Phase Parallel） 一組超級(jí)步（相） 步內(nèi)各自計(jì)算 步間通信、同步 BSP（4.2.3） 方便差錯(cuò)和性能分析 計(jì)算和通信不能重。