《并行計算 第二篇 并行算法的設計》由會員分享，可在線閱讀，更多相關《并行計算 第二篇 并行算法的設計（53頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,并行計算,2009,年,3,月,10,日,第二篇 并行算法的設計,第四章 并行算法的設計基礎,,第五章 并行算法的一般設計策略,,第六章 并行算法的基本設計技術,,第七章 并行算法的一般設計過程,,第四章 并行算法的設計基礎,4.1,并行算法的基礎知識,,4.2,并行計算模型,,4.1,并行算法的基礎知識,4.1.1,并行算法的定義和分類,,4.1.2,并行算法的表達,,4.1.3,并行算法的復雜性度量,,4.1.4,并行算法中的同步和通信,并行算法的定義和分類,并行算法的定義,,算法,,并
2、行算法：一些可同時執(zhí)行的諸進程的集合，這些進程互相作用和協(xié)調(diào)動作從而達到給定問題的求解。,,并行算法的分類,,數(shù)值計算和非數(shù)值計算,,同步算法和異步算法,,分布算法,,確定算法和隨機算法,并行算法的表達,描述語言,,可以使用類,Algol,、類,Pascal,等；,,在描述語言中引入并行語句。,,并行語句示例,,Par-do,語句,,,for i=1 to n par-do,,……,,end for,,for all,語句,,,for all Pi, where 0,≤i≤k,,……,,end for,并行算法的復雜性度量,串行算法的復雜性度量,,最壞情況下的復雜度,(Worst-CASE C
3、omplexity),,期望復雜度,(Expected Complexity),,并行算法的幾個復雜性度量指標,,運行時間,t(n):,包含計算時間和通訊時間，分別用計算時間步和選路時間步作單位。,n,為問題實例的輸入規(guī)模。,,處理器數(shù),p(n),,并行算法成本,c(n): c(n)=t(n)p(n),,總運算量,W(n):,并行算法求解問題時所完成的總的操作步數(shù)。,,,并行算法的復雜性度量,Brent,定理,,令,W(n),是某并行算法,A,在運行時間,T(n),內(nèi)所執(zhí)行的運算,,量，則,A,使用,p,臺處理器可在,t(n)=O(W(n)/p+T(n)),時間,,內(nèi)執(zhí)行完畢。,,W(n),和
4、,c(n),密切相關,,P=O(W(n)/T(n)),時，,W(n),和,c(n),兩者是漸進一致的,,對于任意的,p,，,c(n)?W(n),,并行算法的同步,同步概念,,同步是在時間上強使各執(zhí)行進程在某一點必須互相等待；,,可用軟件、硬件和固件的辦法來實現(xiàn)。,,同步語句示例,,算法,4.1,共享存儲多處理器上求和算法,,輸入：,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,并行算法的通信,通信,,共享存儲多處理器使用：,global read(X,Y),和,global write(X,Y),,分布存儲多計算機使用：,send(X,i),和,recei
6、ve(Y,j),,通信語句示例,,算法,4.2,分布存儲多計算機上矩陣向量乘算法,,,輸入：處理器數(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,并行計算模型,4.2.1 PRAM,模型,,4.2.
7、2,異步,APRAM,模型,,4.2.3 BSP,模型,,4.2.4 logP,模型,,PRAM,模型,基本概念,,由,Fortune,和,Wyllie1978,年提出，又稱,SIMD-SM,模型。有一個集中的共享存儲器和一個指令控制器，通過,SM,的,R/W,交換數(shù)據(jù)，隱式同步計算。,,結構圖,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)先級最高的處理器寫入,,APRAM-CRCW(Arbitrary PRAM-CRCW),：允許任意處理器自由寫入,,PRAM-CREW,并發(fā)讀互斥寫,,PRAM-EREW,互斥讀互斥寫,,計算能力比較,,PRAM-CRCW,是最強的計算模型，,PRAM-EREW,可,logp,倍模擬,PRAM-CREW,和,PRAM-CRCW,,,,,,PRAM,模型,優(yōu)點,,適合并行算法表示和復雜性分析，易于使用，隱藏了并行機的通訊、同步等細節(jié),。,,缺點,,不適合,MIMD,并行機，忽略了,SM,的競爭、通訊延遲等
9、因素,異步,APRAM,模型,基本概念,,又稱分相（,Phase,）,PRAM,或,MIMD-SM,。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過,SM,進行通訊；處理器間依賴關系，需在并行程序中顯式地加入同步路障。,,指令類型,,(,1),全局讀,(2),全局寫,,(3),局部操作,(4),同步,異步,APRAM,模型,計算過程,,由同步障分開的全局相組成,,異步,APRAM,模型,計算時間,,,設局部操作為單位時間；全局讀,/,寫平均時間為,d,，,d,隨著處理器數(shù)目的增加而增加；同步路障時間為,B=B(p),非降函數(shù)。,,滿足關系
10、 ； 或,,令 為全局相內(nèi)各處理器執(zhí)行時間最長者，則,APRAM,上的計算時間為,,,優(yōu)缺點,,,易編程和分析算法的復雜度，但與現(xiàn)實相差較遠，其上并行算法非常有限，也不適合,MIMD-DM,模型。,,,,,,BSP,模型,基本概念,,由,Valiant(1990),提出的，“塊”同步模型，是一種異步,MIMD-DM,模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。,,,模型參數(shù),,p,：處理器數(shù),(,帶有存儲器,),,l,：同步障時間,(Barrier synchronization time),,g,：帶
11、寬因子,(time steps/packet)=1/bandwidth,,BSP,模型,計算過程,,由若干超級步組成，,,每個超級步計算模式為左圖,,優(yōu)缺點,,,強調(diào)了計算和通訊的分離，,,提供了一個編程環(huán)境，易于,,程序復雜性分析。但需要顯,,式同步機制，限制至多,h,條,,消息的傳遞等。,,logP,模型,基本概念,,由,Culler(1993),年提出的，是一種分布存儲的、點到點通訊的多處理機模型，其中通訊由一組參數(shù)描述，實行隱式同步。,,模型參數(shù),,L,：,network latency,,o,：,communication overhead,,g,：,gap=1/bandwidth,
12、,P,：,#processors,,注：,L,和,g,反映了通訊網(wǎng)絡的容量,,,logP,模型,優(yōu)缺點,,,捕捉了,MPC,的通訊瓶頸，隱藏了并行機的網(wǎng)絡拓撲、路由、協(xié)議，可以應用到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進行算法描述、設計和分析。,,BSP vs. LogP,,BSP,?,LogP,：,BSP,塊同步,?,BSP,子集同步,?,BSP,進程對同步＝,LogP,,BSP,可以常數(shù)因子模擬,LogP,，,LogP,可以對數(shù)因子模擬,BSP,,BSP,＝,LogP+Barriers,－,Overhead,,BSP,提供了更方便的程設環(huán)境，,LogP,更好地利用了機器資源,,
13、BSP,似乎更簡單、方便和符合結構化編程,,作業(yè)（1）,TOP500,綜述,,應用舉例：新聞報道等,,選擇某個型號的高性能計算機，撰寫調(diào)研報告,,顧乃杰等，基于斐波那契序列的多播算法,,Brent,定理的證明和意義,,BSP,編程方法調(diào)研,23,模型與下界,不同的,PRAM,模型的相互模擬,,下界,,NP,完全理論,,P,完全理論,不同的,PRAM,模型的相互模擬,不同的,PRAM,模型,,PRAM-EREW,,PRAM-CREW,,PRAM-CRCW,,CPRAM-CRCW,,APRAM-CRCW,,PPRAM-CRCW,,,計算能力是相當?shù)?PRAM-EREW,模擬,PPRAM-CRCW,
14、定理1：一條,p-,處理器,PPRAM-CRCW,模型上的指令，可在,p-,處理器,PRAM-EREW,模型上用,O(logp),的時間實現(xiàn)。,,證明思路：,,并發(fā)讀指令和并發(fā)寫指令,,(PPRAM-CRCW),并發(fā)讀指令 ：處理器,Q,i,讀取,M,i,單元中的內(nèi)容,,(PRAM-EREW),處理器,P,i,設置數(shù)對,< M,i,, i >,,< M,i,, i >,按照字典序排序：時間,O(logp),,第一分量相同的數(shù)對組成塊（通過樹播送數(shù)據(jù)，完成數(shù)據(jù)分布）,,P,i,讀取對于,< M,i,, i >,的數(shù)據(jù)：時間,O(1),,并發(fā)寫指令：使用三元組,<,地址，處理器號，待寫數(shù)據(jù),>,,
15、推論：,T,EREW,=O(T,PCRCW,logp,,),PRAM-CRCW,之間的模擬,CPRAM_CRCW,上算法可在,APRAM_CRCW,上正確執(zhí)行,,APRAM_CRCW,上算法可在,PPRAM_CRCW,上正確執(zhí)行,,,似乎計算能力是按,CPRAM_CRCW,，,APRAM_CRCW,，,PPRAM_CRCW,依次增強的。在對處理器數(shù)目或對共享存儲的容量不加限制時，三個模型是等效的。,,,最左俘獲問題：,p,個處理器，“活躍”或者“非活躍”。每個活躍的處理器有標記，值為,0,或,1,。,,當且僅當處理器是編號最小的活躍處理器，標記為,1,。,CPRAM-CRCW,模擬,PPRAM
16、-CRCW,定理,2,運行在,p-,處理器,PPRAM-CRCW,上時間為,T,的算法，可在,plogp-,處理器,CPRAM-CRCW,上運行時間為,O(T),。,,證明思路：對于,PPRAM-CRCW,中每個參與寫操作的處理器，使用,logp,個輔助處理器，構造一個完全二叉樹來選取標號最小的活躍處理器。,,定理,3 p-,處理器,PPRAM-CRCW,上的一條并發(fā)寫指令，可在,p-,處理器,CPRAM-CRCW,模型上用,O(logp/log logp),時間實現(xiàn)。,,證明思路,:,歸納法。,APRAM-CRCW,模擬,PPRAM-CRCW,定理,4 p-,處理器,PPRAM-CRCW,上
17、的一條并發(fā)寫指令，可在,p-,處理器,APRAM-CRCW,模型上用,O(log logp),時間實現(xiàn)。,,證明思路：方根劃分技術，遞歸求解,,,時間：,模擬的意義？,算法研究的兩個方向,優(yōu)化,,尋找更好的算法,,設計技巧,,一個新的算法（上界）,,可能性,,說明難以得到更好的算法,,證明技巧,,對模型、問題的更好認識（下界）,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),上界與下界,問題描述： 僅通過前綴翻轉（,prefix reversal,）操作對,n,個大小不同的序列排序。,,前綴翻轉： 將包含首個元素的子序列進行翻轉,,,結果：,,給出算法，證明至多,(5n+5)/3,次操作可以排序完成,,給出例子，證明,17n/16,次操作無法完成排序,,改進：,,1995,年，新的下界結果,PRAM,模型的下界,理想的,PRAM,模型,,n,個處理器可訪問無限的共享存儲單元,,每個處理器有無限的私有存儲
19、單元,,一步計算分為三個階段：讀階段、計算階段、寫階段,,每一步計算允許任意數(shù)量的局部計算,,理想,PRAM,模型反映了通信的限制,,理想,PRAM,模型的下界對于標準,PRAM,模型同樣成立,PRAM,模型的下界,PRAM-CREW,的下界,,無論多少處理器，計算,n,變元的布爾或需要,Ω,(,logn),的時間,,PRAM-EREW,的下界,,,p,個處理器，計算長度為,n,的計數(shù)零問題需要,Ω,(,logn-logp),的時間,,PRAM-CRCW,的下界,,計算,n,變量奇偶函數(shù)，使用多項式數(shù)目的處理器需要,Ω,(,logn/loglogn),的時間,NP,完全理論導引,,計算復雜性理
20、論中最重要的理論,,,在工作中，遇到一個問題，找不到好的算法來解決，怎么辦？,算法與好的算法,算法：,,為實現(xiàn)某個任務而構成的簡單指令集,,有窮的計算良過程,,通過有限多次運算可以決定的過程,,圖靈機,,好的算法：多項式時間算法,,指數(shù)時間算法往往在實際中不可接受,,各種串行計算模型是多項式時間等價的,,是否所有的問題都有好的算法？,,SAT,問題,,TSP,（,Traveling salesman problem),,,猜測,TSP,沒有多項式時間算法（,J.Edmonds 1965,）,圖靈機,有限狀態(tài)控制器,,,,,,,,,,,,,,,,,,,,,,,,1,1,1,1,1,1,0,0,
21、0,0,0,0,0,B,B,B,1,……,……,帶子可讀可寫,,無限長的帶子,,讀寫頭可左移右移,圖靈機,“實際的”的圖靈機模型,,單帶圖靈機（,1TM,）,,多帶圖靈機（,kTM,）,,隨機存取機（,RAM,）,,“實際的”,,單位時間內(nèi)完成的工作量有一個多項式上界,,所有“實際的”計算模型多項式時間等價,非確定型圖靈機（,NTM),,不現(xiàn)實的計算,,現(xiàn)實中的計算方式都是確定的,,解,SAT,問題的一個非確定型算法,,第一步：猜測一個變量的真值賦值；,,第二步：檢查該賦值是否滿足,,非確定型算法的計算時間：,,各種可能的計算過程的最短時間,非確定型圖靈機（,NTM),有限狀態(tài)控制器,,,,,
22、,,,,,,,,,,,,,,,,,,,1,1,1,1,1,1,0,0,0,0,0,0,0,B,B,B,1,……,……,猜想模塊,,,,,猜想階段,,驗證階段,NTM,計算樹,,,,,,,,,,,,,,,,,,,,,,計算過程：從根到葉節(jié)點的路徑,P,類與,NP,類,判定問題：只有肯定和否定兩種答案,,優(yōu)化問題可以化作判定問題處理,,P,類 （,Polynomial),,具有多項式時間算法的判定問題形成的計算復雜性類,,NP,問題：,,在非確定型圖靈機上多項式時間可解的問題,,在確定型圖靈機上多項式時間可驗證的問題,,P,類包含于,NP,類中,,NP,類問題在確定圖靈機上指數(shù)時間可解,,非確定型
23、圖靈機和確定型圖靈機的計算能力相當,計算難度的比較,——,歸約,多項式時間歸約（,Karp,歸約,1972),,,問題,A,的實例,I,多項式時間內(nèi)轉化為問題,B,的實例,f(I),，對于,A,的輸入,I,的回答與其對應的,B,的輸入,f(I),一致，則稱,A,可多項式歸約于,B,，記為,,,如果,B,可以多項式時間求解，則,A,也可以多項式時間求解,NP,完全問題,NP,完全問題是,NP,問題中“最難”的問題,NP,完全問題,第一個,NP,完全問題（,Cook-levin,定理,1971,）,,可滿足性問題是,NP,完全問題,,,如果一個,NP,完全問題,karp,歸約到另一個,NP,問題，
24、則該問題也是,NP,完全的,,,六個,NP,完全問題（,Karp 1972),,3SAT,，,3DM,，,VC,，團，,HC,，劃分,,更多的,NP,完全問題,,1979,年：,300,多個,,1998,年：,2000,多個,P=?NP,（,P-NP,問題）,現(xiàn)在的估計,如果 ，則,NPC,問題無有效算法,P=NP,P,NPC,,NP,如何處理,NP,完全問題,實際中的,NP,完全問題不會消失,,證明難度并不會使問題得到解決,,,近似算法,,隨機算法,,…………,,,并行計算,,理想的,PRAM,模型上可多項式時間解決,NP,完全問題,,P,完全理論導引,計算模型：
25、,PRAM,,P,類,,NC,（,Nick’s Class,）類：在,PRAM,上，使用多項式數(shù)目的處理器，在多對數(shù)時間內(nèi)可求解的問題。,,NC,類在,P,類中,,有些問題難以在使用多項式數(shù)目的處理器，在多對數(shù)時間內(nèi)求解,,圖的深度優(yōu)先搜索,,最大流問題,,線性規(guī)劃問題,計算難度的比較,——,歸約,NC-,歸約,,問題,A,的實例,I,通過,NC,算法轉化為問題,B,的實例,f(I),，對于,A,的輸入,I,的回答與其對應的,B,的輸入,f(I),一致，則稱,A,可,NC,歸約于,B,，記為,,,如果,B,可以使用多項式數(shù)目的處理器，在多對數(shù)時間內(nèi)求解，則,A,也可以,P,完全問題,P,完全問題,CVP,（,Circuit Value Problem,）,,給定一組輸入，確定由非門，二值或門，二值與門構成的電路的單個輸入值,,,以下問題都是,P,完全的（通過,NC,歸約可證）,,圖的深度優(yōu)先搜索,,最大流問題,,線性規(guī)劃問題,P=?NC,（,P-NC,問題）,現(xiàn)在的估計,如果 ，則,PC,問題無好的并行算法,P=NC,NC,PC,,P,,Thanks,
并行計算 第二篇 并行算法的設計
