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

1、并行程序設(shè)計(jì)基礎(chǔ)第1頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行程序設(shè)計(jì)基礎(chǔ)12.1 并行程序設(shè)計(jì)概述12.2 進(jìn)程12.3 線程12.4 同步12.5 通信12.6 并行程序設(shè)計(jì)模型2022/9/172第2頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行程序設(shè)計(jì)概述并行程序設(shè)計(jì)難的原因并行語(yǔ)言的構(gòu)造方法并行性問(wèn)題交互/通信問(wèn)題五種并行編程風(fēng)范計(jì)算圓周率的樣本程序2022/9/173第3頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三1 并行程序設(shè)計(jì)難的原因技術(shù)先行,缺乏理論指導(dǎo)程序的語(yǔ)法/語(yǔ)義復(fù)雜, 需要用戶自已處理任務(wù)/數(shù)據(jù)的劃分/分配 數(shù)據(jù)交換同步和互

2、斥 性能平衡并行語(yǔ)言缺乏代可擴(kuò)展和異構(gòu)可擴(kuò)展, 程序移植困難, 重寫(xiě)代碼難度太大環(huán)境和工具缺乏較長(zhǎng)的生長(zhǎng)期, 缺乏代可擴(kuò)展和異構(gòu)可擴(kuò)展2022/9/174第4頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三2 并行語(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;

3、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 sync

4、hronize# pragma pfor iterate (i=0; N; 1)for (i=0;iN;i+)ci=Ai+Ai+1;例子：SGI power C 2022/9/175第5頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三三種并行語(yǔ)言構(gòu)造方法比較2 并行語(yǔ)言的構(gòu)造方法2022/9/176第6頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三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ù)

5、據(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)的并行程序是很困難的2022/9/177第7頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行塊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

6、并行性問(wèn)題2022/9/178第8頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三用單代碼方法說(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)上:run A numnodes NSPMD程序的構(gòu)造方法用數(shù)據(jù)并行程序的構(gòu)造方法要說(shuō)明以下SPMD程序:parfor (i=0;

7、i=N, i+) Ci=Ai+Bi;用戶可用一條數(shù)據(jù)賦值語(yǔ)句:C=A+B或forall (i=1,N) Ci=Ai+Bi進(jìn)程的同構(gòu)性3 并行性問(wèn)題2022/9/179第9頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三用SPMD偽造MPMD要說(shuō)明以下MPMD程序:parbegin S1 S2 S3 parend 可以用以下SPMD程序:parfor (i=0; i0) 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)為

8、該程序具有動(dòng)態(tài)并行性. 即意味著進(jìn)程要在運(yùn)行時(shí)創(chuàng)建和終止2022/9/1711第11頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三Process 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開(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)程2022/9/1712第12頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)4

9、2分，星期三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)題2022/9/1713第13頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行度(Degree of Parallelism

10、, 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)題2022/9/1714第14頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三4 交互通信問(wèn)題交互：進(jìn)程間的相互影響4.1 交互的類型通信：兩個(gè)或多個(gè)進(jìn)程間傳送數(shù)的操作 通信方式：共享變量父進(jìn)程傳給子進(jìn)程(參數(shù)傳遞方式)消息傳遞 2022/9/1715第15頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三同步：導(dǎo)致進(jìn)程間相互等

11、待或繼續(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 交互通信問(wèn)題2022/9/1716第16頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期

12、三聚集(aggregation)：用一串超步將各分進(jìn)程計(jì)算所得的部分結(jié)果合并為一個(gè)完整的結(jié)果, 每個(gè)超步包含一個(gè)短的計(jì)算和一個(gè)簡(jiǎn)單的通信或/和同步.聚集方式:歸約掃描交互的類型4 交互通信問(wèn)題例子: 計(jì)算兩個(gè)向量的內(nèi)積parfor(i:=1; in; i+)Xi:=Ai*Biinner_product:=aggregate_sum(Xi);2022/9/1717第17頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三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在代

13、碼中完成(finished):P剛完成執(zhí)行代碼C,但還未離開(kāi)在外(out): P不在代碼中(未到達(dá)或已離開(kāi))同步的交互: 所有參與者同時(shí)到達(dá)并執(zhí)行交互代碼C異步的交互: 進(jìn)程到達(dá)C后, 不必等待其它進(jìn)程到達(dá)即可執(zhí)行C2022/9/1718第18頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三交互方式與入口/出口條件的組合4 交互通信問(wèn)題鎖定的發(fā)送: 消息已發(fā)完, 但不一定已收到鎖定的接收: 消息已收到非鎖定的發(fā)/收: 只是發(fā)出發(fā)/收的請(qǐng)求2022/9/1719第19頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三4.3 交互的模式按交互模式是否能在編譯時(shí)確定分為:靜態(tài)的動(dòng)態(tài)的按

14、有多少發(fā)送者和接收者參與通信分為一對(duì)一:點(diǎn)到點(diǎn)(point to point)一對(duì)多:廣播(broadcast),播撒(scatter)多對(duì)一:收集(gather), 歸約(reduce)多對(duì)多:全交換(Tatal Exchange), 掃描(scan) , 置換/移位(permutation/shift)4 交互通信問(wèn)題2022/9/1720第20頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三1 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 P1P2P3

15、1,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 交互通信問(wèn)題2022/9/1721第21頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三1 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

16、) 全交換(多對(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)題2022/9/1722第22頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三相并行（Phase Parallel）分治并行（Divide and Conquer Parallel）流水線并行（Pipeline Parallel）主從并行（Master-Slave Parallel）工作池

17、并行（Work Pool Parallel）5 五種并行編程風(fēng)范2022/9/1723第23頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三相并行（Phase Parallel）一組超級(jí)步（相）步內(nèi)各自計(jì)算步間通信、同步BSP（4.2.3）方便差錯(cuò)和性能分析計(jì)算和通信不能重疊CCCSynchronous Interaction.CCCSynchronous Interaction.2022/9/1724第24頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三主從并行（Master-Slave Parallel）主進(jìn)程：串行、協(xié)調(diào)任務(wù)子進(jìn)程：計(jì)算子任務(wù)劃分設(shè)計(jì)技術(shù)（ 6.1）與相并

18、行結(jié)合主進(jìn)程易成為瓶頸MasterSlaveSlaveSlave2022/9/1725第25頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三分治并行（Divide and Conquer Parallel）父進(jìn)程把負(fù)載分割并指派給子進(jìn)程遞歸重點(diǎn)在于歸并分治設(shè)計(jì)技術(shù)（6.2）難以負(fù)載平衡2022/9/1726第26頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三流水線并行（Pipeline Parallel）一組進(jìn)程流水線作業(yè)流水線設(shè)計(jì)技術(shù)（6.5）P1P2P32022/9/1727第27頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三工作池并行（Work Pool Pa

19、rallel）初始狀態(tài)：一件工作進(jìn)程從池中取任務(wù)執(zhí)行可產(chǎn)生新任務(wù)放回池中直至任務(wù)池為空易與負(fù)載平衡臨界區(qū)問(wèn)題（尤其消息傳遞）Work PoolP1P2P32022/9/1728第28頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三8 計(jì)算圓周率的樣本程序2022/9/1729第29頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三計(jì)算圓周率的c語(yǔ)言代碼段#define N 1000000main() double local, pi = 0.0, w;long i;w=1.0/N;for (i = 0; iN; i +) local = (i + 0.5)*w;pi = pi +

20、 4.0/(1.0+local * local);printf(“pi is %f n”, pi *w);2022/9/1730第30頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行程序設(shè)計(jì)基礎(chǔ)12.1 并行程序設(shè)計(jì)概述12.2 進(jìn)程12.3 線程12.4 同步12.5 通信12.6 并行程序設(shè)計(jì)模型2022/9/1731第31頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三進(jìn)程進(jìn)程的基本概念進(jìn)程的并行執(zhí)行進(jìn)程的相互作用2022/9/1732第32頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行程序設(shè)計(jì)基礎(chǔ)12.1 并行程序設(shè)計(jì)概述12.2 進(jìn)程12.3 線程1

21、2.4 同步12.5 通信12.6 并行程序設(shè)計(jì)模型2022/9/1733第33頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三線程線程的基本概念線程的管理線程的同步2022/9/1734第34頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行程序設(shè)計(jì)基礎(chǔ)12.1 并行程序設(shè)計(jì)概述12.2 進(jìn)程12.3 線程12.4 同步12.5 通信12.6 并行程序設(shè)計(jì)模型2022/9/1735第35頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三同步原子和互斥高級(jí)同步結(jié)構(gòu)低級(jí)同步原語(yǔ)2022/9/1736第36頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行程序設(shè)計(jì)基礎(chǔ)12.1 并行程序設(shè)計(jì)概述12.2 進(jìn)程12.3 線程12.4 同步12.5 通信12.6 并行程序設(shè)計(jì)模型2022/9/1737第37頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三通信影響通信系統(tǒng)性能的因素低級(jí)通信支持TCP/IP通信協(xié)議組簡(jiǎn)介2022/9/1738第38頁(yè)，共45頁(yè)，2022年，5月20日，7點(diǎn)42分，星期三并行程序設(shè)計(jì)基礎(chǔ)12.1 并行程序設(shè)計(jì)概述12.2 進(jìn)程12.3 線程12.4 同步12.5 通信12.6 并行程序設(shè)計(jì)模型2022/9/1739第39頁(yè)