《并行計(jì)算 第二篇 并行算法的設(shè)計(jì)》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算 第二篇 并行算法的設(shè)計(jì)（53頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,,,*,并行計(jì)算,2009,年,3,月,10,日,第二篇 并行算法的設(shè)計(jì),第四章 并行算法的設(shè)計(jì)基礎(chǔ),,第五章 并行算法的一般設(shè)計(jì)策略,,第六章 并行算法的基本設(shè)計(jì)技術(shù),,第七章 并行算法的一般設(shè)計(jì)過程,,第四章 并行算法的設(shè)計(jì)基礎(chǔ),4.1,并行算法的基礎(chǔ)知識(shí),,4.2,并行計(jì)算模型,,4.1,并行算法的基礎(chǔ)知識(shí),4.1.1,并行算法的定義和分類,,4.1.2,并行算法的表達(dá),,4.1.3,并行算法的復(fù)雜性度量,,4.1.4,并行算法中的同步和通信,并行算法的定義和分類,并行算法的定義,,算法,,并

2、行算法：一些可同時(shí)執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程互相作用和協(xié)調(diào)動(dòng)作從而達(dá)到給定問題的求解。,,并行算法的分類,,數(shù)值計(jì)算和非數(shù)值計(jì)算,,同步算法和異步算法,,分布算法,,確定算法和隨機(jī)算法,并行算法的表達(dá),描述語言,,可以使用類,Algol,、類,Pascal,等；,,在描述語言中引入并行語句。,,并行語句示例,,Par-do,語句,,,for i=1 to n par-do,,……,,end for,,for all,語句,,,for all Pi, where 0,≤i≤k,,……,,end for,并行算法的復(fù)雜性度量,串行算法的復(fù)雜性度量,,最壞情況下的復(fù)雜度,(Worst-CASE C

3、omplexity),,期望復(fù)雜度,(Expected Complexity),,并行算法的幾個(gè)復(fù)雜性度量指標(biāo),,運(yùn)行時(shí)間,t(n):,包含計(jì)算時(shí)間和通訊時(shí)間，分別用計(jì)算時(shí)間步和選路時(shí)間步作單位。,n,為問題實(shí)例的輸入規(guī)模。,,處理器數(shù),p(n),,并行算法成本,c(n): c(n)=t(n)p(n),,總運(yùn)算量,W(n):,并行算法求解問題時(shí)所完成的總的操作步數(shù)。,,,并行算法的復(fù)雜性度量,Brent,定理,,令,W(n),是某并行算法,A,在運(yùn)行時(shí)間,T(n),內(nèi)所執(zhí)行的運(yùn)算,,量，則,A,使用,p,臺(tái)處理器可在,t(n)=O(W(n)/p+T(n)),時(shí)間,,內(nèi)執(zhí)行完畢。,,W(n),和

4、,c(n),密切相關(guān),,P=O(W(n)/T(n)),時(shí)，,W(n),和,c(n),兩者是漸進(jìn)一致的,,對(duì)于任意的,p,，,c(n)?W(n),,并行算法的同步,同步概念,,同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待；,,可用軟件、硬件和固件的辦法來實(shí)現(xiàn)。,,同步語句示例,,算法,4.1,共享存儲(chǔ)多處理器上求和算法,,輸入：,A=(a,0,,…,a,n-1,),,處理器數(shù),p,,,輸出：,S=Σa,i,,Begin,,(1)S=0 (2.3) lock(S),,(2)for all P

5、i where 0,≤,i,≤,p-1,,do S=S+L,,(2.1) L=0 (2.4) unlock(S),,(2.2) for j=i to n step p do end for,,L=L+a,j,End,,end for,,end for,并行算法的通信,通信,,共享存儲(chǔ)多處理器使用：,global read(X,Y),和,global write(X,Y),,分布存儲(chǔ)多計(jì)算機(jī)使用：,send(X,i),和,recei

6、ve(Y,j),,通信語句示例,,算法,4.2,分布存儲(chǔ)多計(jì)算機(jī)上矩陣向量乘算法,,,輸入：處理器數(shù),p, A,劃分為,B=A[1..n,(i-1)r+1..ir],,,x,劃分為,w=w[(i-1)r+1;ir],,,輸出：,P,1,保存乘積,AX,,Begin,,(1) Compute z=Bw,,(2) if i=1 then y,i,=0 else receive(y,left) endif,,(3) y=y+z,,(4) send(y,right),,(5) if i=1 then receive(y,left),,End,4.2,并行計(jì)算模型,4.2.1 PRAM,模型,,4.2.

7、2,異步,APRAM,模型,,4.2.3 BSP,模型,,4.2.4 logP,模型,,PRAM,模型,基本概念,,由,Fortune,和,Wyllie1978,年提出，又稱,SIMD-SM,模型。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過,SM,的,R/W,交換數(shù)據(jù)，隱式同步計(jì)算。,,結(jié)構(gòu)圖,Control Unit,Interconnection Network,P,,,LM,,,P,,,LM,,,P,,,LM,,,P,,,LM,,,,Shared Memory,,,PRAM,模型,分類,,PRAM-CRCW,并發(fā)讀并發(fā)寫,,CPRAM-CRCW(Common PRAM-CRCW),：僅

8、允許寫入相同數(shù)據(jù),,PPRAM-CRCW(Priority PRAM-CRCW),：僅允許優(yōu)先級(jí)最高的處理器寫入,,APRAM-CRCW(Arbitrary PRAM-CRCW),：允許任意處理器自由寫入,,PRAM-CREW,并發(fā)讀互斥寫,,PRAM-EREW,互斥讀互斥寫,,計(jì)算能力比較,,PRAM-CRCW,是最強(qiáng)的計(jì)算模型，,PRAM-EREW,可,logp,倍模擬,PRAM-CREW,和,PRAM-CRCW,,,,,,PRAM,模型,優(yōu)點(diǎn),,適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié),。,,缺點(diǎn),,不適合,MIMD,并行機(jī)，忽略了,SM,的競(jìng)爭(zhēng)、通訊延遲等

9、因素,異步,APRAM,模型,基本概念,,又稱分相（,Phase,）,PRAM,或,MIMD-SM,。每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序；無全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過,SM,進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。,,指令類型,,(,1),全局讀,(2),全局寫,,(3),局部操作,(4),同步,異步,APRAM,模型,計(jì)算過程,,由同步障分開的全局相組成,,異步,APRAM,模型,計(jì)算時(shí)間,,,設(shè)局部操作為單位時(shí)間；全局讀,/,寫平均時(shí)間為,d,，,d,隨著處理器數(shù)目的增加而增加；同步路障時(shí)間為,B=B(p),非降函數(shù)。,,滿足關(guān)系

10、 ； 或,,令 為全局相內(nèi)各處理器執(zhí)行時(shí)間最長(zhǎng)者，則,APRAM,上的計(jì)算時(shí)間為,,,優(yōu)缺點(diǎn),,,易編程和分析算法的復(fù)雜度，但與現(xiàn)實(shí)相差較遠(yuǎn)，其上并行算法非常有限，也不適合,MIMD-DM,模型。,,,,,,BSP,模型,基本概念,,由,Valiant(1990),提出的，“塊”同步模型，是一種異步,MIMD-DM,模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。,,,模型參數(shù),,p,：處理器數(shù),(,帶有存儲(chǔ)器,),,l,：同步障時(shí)間,(Barrier synchronization time),,g,：帶

11、寬因子,(time steps/packet)=1/bandwidth,,BSP,模型,計(jì)算過程,,由若干超級(jí)步組成，,,每個(gè)超級(jí)步計(jì)算模式為左圖,,優(yōu)缺點(diǎn),,,強(qiáng)調(diào)了計(jì)算和通訊的分離，,,提供了一個(gè)編程環(huán)境，易于,,程序復(fù)雜性分析。但需要顯,,式同步機(jī)制，限制至多,h,條,,消息的傳遞等。,,logP,模型,基本概念,,由,Culler(1993),年提出的，是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。,,模型參數(shù),,L,：,network latency,,o,：,communication overhead,,g,：,gap=1/bandwidth,

12、,P,：,#processors,,注：,L,和,g,反映了通訊網(wǎng)絡(luò)的容量,,,logP,模型,優(yōu)缺點(diǎn),,,捕捉了,MPC,的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)用到共享存儲(chǔ)、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計(jì)和分析。,,BSP vs. LogP,,BSP,?,LogP,：,BSP,塊同步,?,BSP,子集同步,?,BSP,進(jìn)程對(duì)同步＝,LogP,,BSP,可以常數(shù)因子模擬,LogP,，,LogP,可以對(duì)數(shù)因子模擬,BSP,,BSP,＝,LogP+Barriers,－,Overhead,,BSP,提供了更方便的程設(shè)環(huán)境，,LogP,更好地利用了機(jī)器資源,,

13、BSP,似乎更簡(jiǎn)單、方便和符合結(jié)構(gòu)化編程,,作業(yè)（1）,TOP500,綜述,,應(yīng)用舉例：新聞報(bào)道等,,選擇某個(gè)型號(hào)的高性能計(jì)算機(jī)，撰寫調(diào)研報(bào)告,,顧乃杰等，基于斐波那契序列的多播算法,,Brent,定理的證明和意義,,BSP,編程方法調(diào)研,23,模型與下界,不同的,PRAM,模型的相互模擬,,下界,,NP,完全理論,,P,完全理論,不同的,PRAM,模型的相互模擬,不同的,PRAM,模型,,PRAM-EREW,,PRAM-CREW,,PRAM-CRCW,,CPRAM-CRCW,,APRAM-CRCW,,PPRAM-CRCW,,,計(jì)算能力是相當(dāng)?shù)?PRAM-EREW,模擬,PPRAM-CRCW,

14、定理1：一條,p-,處理器,PPRAM-CRCW,模型上的指令，可在,p-,處理器,PRAM-EREW,模型上用,O(logp),的時(shí)間實(shí)現(xiàn)。,,證明思路：,,并發(fā)讀指令和并發(fā)寫指令,,(PPRAM-CRCW),并發(fā)讀指令 ：處理器,Q,i,讀取,M,i,單元中的內(nèi)容,,(PRAM-EREW),處理器,P,i,設(shè)置數(shù)對(duì),< M,i,, i >,,< M,i,, i >,按照字典序排序：時(shí)間,O(logp),,第一分量相同的數(shù)對(duì)組成塊（通過樹播送數(shù)據(jù)，完成數(shù)據(jù)分布）,,P,i,讀取對(duì)于,< M,i,, i >,的數(shù)據(jù)：時(shí)間,O(1),,并發(fā)寫指令：使用三元組,<,地址，處理器號(hào)，待寫數(shù)據(jù),>,,

15、推論：,T,EREW,=O(T,PCRCW,logp,,),PRAM-CRCW,之間的模擬,CPRAM_CRCW,上算法可在,APRAM_CRCW,上正確執(zhí)行,,APRAM_CRCW,上算法可在,PPRAM_CRCW,上正確執(zhí)行,,,似乎計(jì)算能力是按,CPRAM_CRCW,，,APRAM_CRCW,，,PPRAM_CRCW,依次增強(qiáng)的。在對(duì)處理器數(shù)目或?qū)蚕泶鎯?chǔ)的容量不加限制時(shí)，三個(gè)模型是等效的。,,,最左俘獲問題：,p,個(gè)處理器，“活躍”或者“非活躍”。每個(gè)活躍的處理器有標(biāo)記，值為,0,或,1,。,,當(dāng)且僅當(dāng)處理器是編號(hào)最小的活躍處理器，標(biāo)記為,1,。,CPRAM-CRCW,模擬,PPRAM

16、-CRCW,定理,2,運(yùn)行在,p-,處理器,PPRAM-CRCW,上時(shí)間為,T,的算法，可在,plogp-,處理器,CPRAM-CRCW,上運(yùn)行時(shí)間為,O(T),。,,證明思路：對(duì)于,PPRAM-CRCW,中每個(gè)參與寫操作的處理器，使用,logp,個(gè)輔助處理器，構(gòu)造一個(gè)完全二叉樹來選取標(biāo)號(hào)最小的活躍處理器。,,定理,3 p-,處理器,PPRAM-CRCW,上的一條并發(fā)寫指令，可在,p-,處理器,CPRAM-CRCW,模型上用,O(logp/log logp),時(shí)間實(shí)現(xiàn)。,,證明思路,:,歸納法。,APRAM-CRCW,模擬,PPRAM-CRCW,定理,4 p-,處理器,PPRAM-CRCW,上

17、的一條并發(fā)寫指令，可在,p-,處理器,APRAM-CRCW,模型上用,O(log logp),時(shí)間實(shí)現(xiàn)。,,證明思路：方根劃分技術(shù)，遞歸求解,,,時(shí)間：,模擬的意義？,算法研究的兩個(gè)方向,優(yōu)化,,尋找更好的算法,,設(shè)計(jì)技巧,,一個(gè)新的算法（上界）,,可能性,,說明難以得到更好的算法,,證明技巧,,對(duì)模型、問題的更好認(rèn)識(shí)（下界）,Gates, William H. and Christos H. Papadimitriou.,Bounds for sorting by prefix reversal.,,Discrete Mathematics,27 (1979), 47--57.,,Harva

18、rd University(1973) Microsoft (1975),Princeton University (MS 1974 and PhD 1976),上界與下界,問題描述： 僅通過前綴翻轉(zhuǎn)（,prefix reversal,）操作對(duì),n,個(gè)大小不同的序列排序。,,前綴翻轉(zhuǎn)： 將包含首個(gè)元素的子序列進(jìn)行翻轉(zhuǎn),,,結(jié)果：,,給出算法，證明至多,(5n+5)/3,次操作可以排序完成,,給出例子，證明,17n/16,次操作無法完成排序,,改進(jìn)：,,1995,年，新的下界結(jié)果,PRAM,模型的下界,理想的,PRAM,模型,,n,個(gè)處理器可訪問無限的共享存儲(chǔ)單元,,每個(gè)處理器有無限的私有存儲(chǔ)

19、單元,,一步計(jì)算分為三個(gè)階段：讀階段、計(jì)算階段、寫階段,,每一步計(jì)算允許任意數(shù)量的局部計(jì)算,,理想,PRAM,模型反映了通信的限制,,理想,PRAM,模型的下界對(duì)于標(biāo)準(zhǔn),PRAM,模型同樣成立,PRAM,模型的下界,PRAM-CREW,的下界,,無論多少處理器，計(jì)算,n,變?cè)牟紶柣蛐枰?Ω,(,logn),的時(shí)間,,PRAM-EREW,的下界,,,p,個(gè)處理器，計(jì)算長(zhǎng)度為,n,的計(jì)數(shù)零問題需要,Ω,(,logn-logp),的時(shí)間,,PRAM-CRCW,的下界,,計(jì)算,n,變量奇偶函數(shù)，使用多項(xiàng)式數(shù)目的處理器需要,Ω,(,logn/loglogn),的時(shí)間,NP,完全理論導(dǎo)引,,計(jì)算復(fù)雜性理

20、論中最重要的理論,,,在工作中，遇到一個(gè)問題，找不到好的算法來解決，怎么辦？,算法與好的算法,算法：,,為實(shí)現(xiàn)某個(gè)任務(wù)而構(gòu)成的簡(jiǎn)單指令集,,有窮的計(jì)算良過程,,通過有限多次運(yùn)算可以決定的過程,,圖靈機(jī),,好的算法：多項(xiàng)式時(shí)間算法,,指數(shù)時(shí)間算法往往在實(shí)際中不可接受,,各種串行計(jì)算模型是多項(xiàng)式時(shí)間等價(jià)的,,是否所有的問題都有好的算法？,,SAT,問題,,TSP,（,Traveling salesman problem),,,猜測(cè),TSP,沒有多項(xiàng)式時(shí)間算法（,J.Edmonds 1965,）,圖靈機(jī),有限狀態(tài)控制器,,,,,,,,,,,,,,,,,,,,,,,,1,1,1,1,1,1,0,0,

21、0,0,0,0,0,B,B,B,1,……,……,帶子可讀可寫,,無限長(zhǎng)的帶子,,讀寫頭可左移右移,圖靈機(jī),“實(shí)際的”的圖靈機(jī)模型,,單帶圖靈機(jī)（,1TM,）,,多帶圖靈機(jī)（,kTM,）,,隨機(jī)存取機(jī)（,RAM,）,,“實(shí)際的”,,單位時(shí)間內(nèi)完成的工作量有一個(gè)多項(xiàng)式上界,,所有“實(shí)際的”計(jì)算模型多項(xiàng)式時(shí)間等價(jià),非確定型圖靈機(jī)（,NTM),,不現(xiàn)實(shí)的計(jì)算,,現(xiàn)實(shí)中的計(jì)算方式都是確定的,,解,SAT,問題的一個(gè)非確定型算法,,第一步：猜測(cè)一個(gè)變量的真值賦值；,,第二步：檢查該賦值是否滿足,,非確定型算法的計(jì)算時(shí)間：,,各種可能的計(jì)算過程的最短時(shí)間,非確定型圖靈機(jī)（,NTM),有限狀態(tài)控制器,,,,,

22、,,,,,,,,,,,,,,,,,,,1,1,1,1,1,1,0,0,0,0,0,0,0,B,B,B,1,……,……,猜想模塊,,,,,猜想階段,,驗(yàn)證階段,NTM,計(jì)算樹,,,,,,,,,,,,,,,,,,,,,,計(jì)算過程：從根到葉節(jié)點(diǎn)的路徑,P,類與,NP,類,判定問題：只有肯定和否定兩種答案,,優(yōu)化問題可以化作判定問題處理,,P,類 （,Polynomial),,具有多項(xiàng)式時(shí)間算法的判定問題形成的計(jì)算復(fù)雜性類,,NP,問題：,,在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問題,,在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可驗(yàn)證的問題,,P,類包含于,NP,類中,,NP,類問題在確定圖靈機(jī)上指數(shù)時(shí)間可解,,非確定型

23、圖靈機(jī)和確定型圖靈機(jī)的計(jì)算能力相當(dāng),計(jì)算難度的比較,——,歸約,多項(xiàng)式時(shí)間歸約（,Karp,歸約,1972),,,問題,A,的實(shí)例,I,多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為問題,B,的實(shí)例,f(I),，對(duì)于,A,的輸入,I,的回答與其對(duì)應(yīng)的,B,的輸入,f(I),一致，則稱,A,可多項(xiàng)式歸約于,B,，記為,,,如果,B,可以多項(xiàng)式時(shí)間求解，則,A,也可以多項(xiàng)式時(shí)間求解,NP,完全問題,NP,完全問題是,NP,問題中“最難”的問題,NP,完全問題,第一個(gè),NP,完全問題（,Cook-levin,定理,1971,）,,可滿足性問題是,NP,完全問題,,,如果一個(gè),NP,完全問題,karp,歸約到另一個(gè),NP,問題，

24、則該問題也是,NP,完全的,,,六個(gè),NP,完全問題（,Karp 1972),,3SAT,，,3DM,，,VC,，團(tuán)，,HC,，劃分,,更多的,NP,完全問題,,1979,年：,300,多個(gè),,1998,年：,2000,多個(gè),P=?NP,（,P-NP,問題）,現(xiàn)在的估計(jì),如果 ，則,NPC,問題無有效算法,P=NP,P,NPC,,NP,如何處理,NP,完全問題,實(shí)際中的,NP,完全問題不會(huì)消失,,證明難度并不會(huì)使問題得到解決,,,近似算法,,隨機(jī)算法,,…………,,,并行計(jì)算,,理想的,PRAM,模型上可多項(xiàng)式時(shí)間解決,NP,完全問題,,P,完全理論導(dǎo)引,計(jì)算模型：

25、,PRAM,,P,類,,NC,（,Nick’s Class,）類：在,PRAM,上，使用多項(xiàng)式數(shù)目的處理器，在多對(duì)數(shù)時(shí)間內(nèi)可求解的問題。,,NC,類在,P,類中,,有些問題難以在使用多項(xiàng)式數(shù)目的處理器，在多對(duì)數(shù)時(shí)間內(nèi)求解,,圖的深度優(yōu)先搜索,,最大流問題,,線性規(guī)劃問題,計(jì)算難度的比較,——,歸約,NC-,歸約,,問題,A,的實(shí)例,I,通過,NC,算法轉(zhuǎn)化為問題,B,的實(shí)例,f(I),，對(duì)于,A,的輸入,I,的回答與其對(duì)應(yīng)的,B,的輸入,f(I),一致，則稱,A,可,NC,歸約于,B,，記為,,,如果,B,可以使用多項(xiàng)式數(shù)目的處理器，在多對(duì)數(shù)時(shí)間內(nèi)求解，則,A,也可以,P,完全問題,P,完全問題,CVP,（,Circuit Value Problem,）,,給定一組輸入，確定由非門，二值或門，二值與門構(gòu)成的電路的單個(gè)輸入值,,,以下問題都是,P,完全的（通過,NC,歸約可證）,,圖的深度優(yōu)先搜索,,最大流問題,,線性規(guī)劃問題,P=?NC,（,P-NC,問題）,現(xiàn)在的估計(jì),如果 ，則,PC,問題無好的并行算法,P=NC,NC,PC,,P,,Thanks,