并行計算第二篇并行算法的設(shè)計

1、并行計算第二篇并行算法的設(shè)計第1頁，共53頁，2022年，5月20日，7點43分，星期三第二篇 并行算法的設(shè)計第四章 并行算法的設(shè)計基礎(chǔ)第五章 并行算法的一般設(shè)計策略第六章 并行算法的基本設(shè)計技術(shù)第七章 并行算法的一般設(shè)計過程第2頁，共53頁，2022年，5月20日，7點43分，星期三第四章 并行算法的設(shè)計基礎(chǔ)4.1 并行算法的基礎(chǔ)知識4.2 并行計算模型第3頁，共53頁，2022年，5月20日，7點43分，星期三4.1 并行算法的基礎(chǔ)知識4.1.1 并行算法的定義和分類4.1.2 并行算法的表達4.1.3 并行算法的復雜性度量4.1.4 并行算法中的同步和通信第4頁，共53頁，2022年，5

2、月20日，7點43分，星期三 并行算法的定義和分類并行算法的定義算法并行算法：一些可同時執(zhí)行的諸進程的集合，這些進程互相作用和協(xié)調(diào)動作從而達到給定問題的求解。并行算法的分類數(shù)值計算和非數(shù)值計算同步算法和異步算法分布算法確定算法和隨機算法第5頁，共53頁，2022年，5月20日，7點43分，星期三 并行算法的表達描述語言可以使用類Algol、類Pascal等；在描述語言中引入并行語句。并行語句示例Par-do語句 for i=1 to n par-do end forfor all語句 for all Pi, where 0ik end for 第6頁，共53頁，2022年，5月20日，7點43

3、分，星期三 并行算法的復雜性度量串行算法的復雜性度量最壞情況下的復雜度(Worst-CASE Complexity)期望復雜度(Expected Complexity)并行算法的幾個復雜性度量指標運行時間t(n):包含計算時間和通訊時間，分別用計算時間步和選路時間步作單位。n為問題實例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n): c(n)=t(n)p(n)總運算量W(n): 并行算法求解問題時所完成的總的操作步數(shù)。 第7頁，共53頁，2022年，5月20日，7點43分，星期三 并行算法的復雜性度量Brent定理令W(n)是某并行算法A在運行時間T(n)內(nèi)所執(zhí)行的運算量，則A使用p臺處理器

4、可在t(n)=O(W(n)/p+T(n)時間內(nèi)執(zhí)行完畢。W(n)和c(n)密切相關(guān)P=O(W(n)/T(n)時，W(n)和c(n)兩者是漸進一致的對于任意的p，c(n)W(n)第8頁，共53頁，2022年，5月20日，7點43分，星期三 并行算法的同步同步概念同步是在時間上強使各執(zhí)行進程在某一點必須互相等待；可用軟件、硬件和固件的辦法來實現(xiàn)。同步語句示例算法4.1 共享存儲多處理器上求和算法 輸入：A=(a0,an-1),處理器數(shù)p 輸出：S=ai Begin (1)S=0 (2.3) lock(S) (2)for all Pi where 0ip-1 do S=S+L (2.1) L=0 (

5、2.4) unlock(S) (2.2) for j=i to n step p do end for L=L+aj End end for end for 第9頁，共53頁，2022年，5月20日，7點43分，星期三 并行算法的通信通信共享存儲多處理器使用：global read(X,Y)和global write(X,Y)分布存儲多計算機使用：send(X,i)和receive(Y,j)通信語句示例算法4.2 分布存儲多計算機上矩陣向量乘算法 輸入：處理器數(shù)p, A劃分為B=A1.n,(i-1)r+1.ir, x劃分為w=w(i-1)r+1;ir 輸出：P1保存乘積AX Begin (1)

6、 Compute z=Bw (2) if i=1 then yi=0 else receive(y,left) endif (3) y=y+z (4) send(y,right) (5) if i=1 then receive(y,left) End 第10頁，共53頁，2022年，5月20日，7點43分，星期三4.2 并行計算模型4.2.1 PRAM模型4.2.2 異步APRAM模型4.2.3 BSP模型4.2.4 logP模型第11頁，共53頁，2022年，5月20日，7點43分，星期三 PRAM模型基本概念由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個集中的

7、共享存儲器和一個指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計算。結(jié)構(gòu)圖Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory第12頁，共53頁，2022年，5月20日，7點43分，星期三 PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-CRCW(Common PRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(Priority PRAM-CRCW)：僅允許優(yōu)先級最高的處理器寫入APRAM-CRCW(Arbitrary PRAM-CRCW)：允許任意處理器自由寫入 PRAM-CREW并發(fā)讀互斥寫 PRAM-

8、EREW互斥讀互斥寫 計算能力比較PRAM-CRCW是最強的計算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW 第13頁，共53頁，2022年，5月20日，7點43分，星期三 PRAM模型優(yōu)點適合并行算法表示和復雜性分析，易于使用，隱藏了并行機的通訊、同步等細節(jié)。缺點不適合MIMD并行機，忽略了SM的競爭、通訊延遲等因素第14頁，共53頁，2022年，5月20日，7點43分，星期三 異步APRAM模型基本概念又稱分相（Phase）PRAM或MIMD-SM。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過SM進行通訊；處理器間

9、依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀 (2)全局寫 (3)局部操作 (4)同步 第15頁，共53頁，2022年，5月20日，7點43分，星期三 異步APRAM模型計算過程由同步障分開的全局相組成 第16頁，共53頁，2022年，5月20日，7點43分，星期三 異步APRAM模型計算時間 設(shè)局部操作為單位時間；全局讀/寫平均時間為d，d隨著處理器數(shù)目的增加而增加；同步路障時間為B=B(p)非降函數(shù)。 滿足關(guān)系 ； 或 令 為全局相內(nèi)各處理器執(zhí)行時間最長者，則APRAM上的計算時間為 優(yōu)缺點 易編程和分析算法的復雜度，但與現(xiàn)實相差較遠，其上并行算法非常有限，也不適合MI

10、MD-DM模型。 第17頁，共53頁，2022年，5月20日，7點43分，星期三 BSP模型基本概念由Valiant(1990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。 模型參數(shù)p：處理器數(shù)(帶有存儲器)l：同步障時間(Barrier synchronization time)g：帶寬因子(time steps/packet)=1/bandwidth 第18頁，共53頁，2022年，5月20日，7點43分，星期三 BSP模型計算過程由若干超級步組成，每個超級步計算模式為左圖優(yōu)缺點 強調(diào)了計算和通訊的分離， 提供了一個編程環(huán)境，易于 程

11、序復雜性分析。但需要顯 式同步機制，限制至多h條 消息的傳遞等。第19頁，共53頁，2022年，5月20日，7點43分，星期三 logP模型基本概念由Culler(1993)年提出的，是一種分布存儲的、點到點通訊的多處理機模型，其中通訊由一組參數(shù)描述，實行隱式同步。模型參數(shù)L：network latencyo：communication overheadg：gap=1/bandwidthP：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量 第20頁，共53頁，2022年，5月20日，7點43分，星期三 logP模型優(yōu)缺點 捕捉了MPC的通訊瓶頸，隱藏了并行機的網(wǎng)絡(luò)拓撲、路由、協(xié)議，可以應(yīng)用

12、到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進行算法描述、設(shè)計和分析。 BSP vs. LogPBSPLogP：BSP塊同步BSP子集同步BSP進程對同步LogPBSP可以常數(shù)因子模擬LogP，LogP可以對數(shù)因子模擬BSPBSPLogP+BarriersOverheadBSP提供了更方便的程設(shè)環(huán)境，LogP更好地利用了機器資源BSP似乎更簡單、方便和符合結(jié)構(gòu)化編程 第21頁，共53頁，2022年，5月20日，7點43分，星期三作業(yè)（1）TOP500 綜述應(yīng)用舉例：新聞報道等選擇某個型號的高性能計算機，撰寫調(diào)研報告顧乃杰等，基于斐波那契序列的多播算法Brent定理的證明和意義BSP編程方

13、法調(diào)研第22頁，共53頁，2022年，5月20日，7點43分，星期三23第23頁，共53頁，2022年，5月20日，7點43分，星期三模型與下界不同的PRAM模型的相互模擬下界NP完全理論P完全理論第24頁，共53頁，2022年，5月20日，7點43分，星期三不同的PRAM模型的相互模擬不同的PRAM模型PRAM-EREWPRAM-CREWPRAM-CRCWCPRAM-CRCWAPRAM-CRCWPPRAM-CRCW計算能力是相當?shù)牡?5頁，共53頁，2022年，5月20日，7點43分，星期三PRAM-EREW模擬PPRAM-CRCW定理1：一條p-處理器PPRAM-CRCW模型上的指令，可在

14、p-處理器PRAM-EREW模型上用O(logp)的時間實現(xiàn)。證明思路：并發(fā)讀指令和并發(fā)寫指令(PPRAM-CRCW) 并發(fā)讀指令 ：處理器Qi讀取Mi單元中的內(nèi)容(PRAM-EREW)處理器Pi 設(shè)置數(shù)對按照字典序排序：時間O(logp)第一分量相同的數(shù)對組成塊（通過樹播送數(shù)據(jù)，完成數(shù)據(jù)分布）Pi讀取對于的數(shù)據(jù)：時間O(1)并發(fā)寫指令：使用三元組推論： TEREW =O(TPCRCW logp )第26頁，共53頁，2022年，5月20日，7點43分，星期三PRAM-CRCW之間的模擬CPRAM_CRCW上算法可在APRAM_CRCW上正確執(zhí)行APRAM_CRCW上算法可在PPRAM_CRC

15、W上正確執(zhí)行似乎計算能力是按CPRAM_CRCW，APRAM_CRCW，PPRAM_CRCW依次增強的。在對處理器數(shù)目或?qū)蚕泶鎯Φ娜萘坎患酉拗茣r，三個模型是等效的。最左俘獲問題：p個處理器，“活躍”或者“非活躍”。每個活躍的處理器有標記，值為0或1。 當且僅當處理器是編號最小的活躍處理器，標記為1。第27頁，共53頁，2022年，5月20日，7點43分，星期三CPRAM-CRCW模擬PPRAM-CRCW定理2 運行在p-處理器PPRAM-CRCW上時間為T的算法，可在plogp-處理器CPRAM-CRCW上運行時間為O(T)。證明思路：對于PPRAM-CRCW中每個參與寫操作的處理器，使用l

16、ogp個輔助處理器，構(gòu)造一個完全二叉樹來選取標號最小的活躍處理器。定理3 p-處理器PPRAM-CRCW上的一條并發(fā)寫指令，可在p-處理器CPRAM-CRCW模型上用O(logp/log logp)時間實現(xiàn)。證明思路: 歸納法。第28頁，共53頁，2022年，5月20日，7點43分，星期三APRAM-CRCW模擬PPRAM-CRCW定理4 p-處理器PPRAM-CRCW上的一條并發(fā)寫指令，可在p-處理器APRAM-CRCW模型上用O(log logp)時間實現(xiàn)。證明思路：方根劃分技術(shù)，遞歸求解 時間：模擬的意義？第29頁，共53頁，2022年，5月20日，7點43分，星期三算法研究的兩個方向優(yōu)

17、化尋找更好的算法設(shè)計技巧一個新的算法（上界）可能性說明難以得到更好的算法證明技巧對模型、問題的更好認識（下界）第30頁，共53頁，2022年，5月20日，7點43分，星期三Gates, William H. and Christos H. Papadimitriou. Bounds for sorting by prefix reversal. Discrete Mathematics 27 (1979), 47-57.Harvard University(1973) Microsoft (1975)Princeton University (MS 1974 and PhD 1976)第31頁

18、，共53頁，2022年，5月20日，7點43分，星期三上界與下界問題描述： 僅通過前綴翻轉(zhuǎn)（prefix reversal）操作對n個大小不同的序列排序。前綴翻轉(zhuǎn)： 將包含首個元素的子序列進行翻轉(zhuǎn)結(jié)果：給出算法，證明至多(5n+5)/3 次操作可以排序完成給出例子，證明17n/16次操作無法完成排序改進：1995年，新的下界結(jié)果第32頁，共53頁，2022年，5月20日，7點43分，星期三PRAM模型的下界理想的PRAM模型n個處理器可訪問無限的共享存儲單元每個處理器有無限的私有存儲單元一步計算分為三個階段：讀階段、計算階段、寫階段每一步計算允許任意數(shù)量的局部計算理想PRAM模型反映了通信的限

19、制理想PRAM模型的下界對于標準PRAM模型同樣成立第33頁，共53頁，2022年，5月20日，7點43分，星期三PRAM模型的下界PRAM-CREW的下界 無論多少處理器，計算n變元的布爾或需要(logn)的時間PRAM-EREW的下界 p個處理器，計算長度為n的計數(shù)零問題需要(logn-logp)的時間PRAM-CRCW的下界 計算n變量奇偶函數(shù)，使用多項式數(shù)目的處理器需要(logn/loglogn)的時間第34頁，共53頁，2022年，5月20日，7點43分，星期三NP完全理論導引計算復雜性理論中最重要的理論在工作中，遇到一個問題，找不到好的算法來解決，怎么辦？第35頁，共53頁，202

20、2年，5月20日，7點43分，星期三算法與好的算法算法：為實現(xiàn)某個任務(wù)而構(gòu)成的簡單指令集有窮的計算良過程通過有限多次運算可以決定的過程圖靈機好的算法：多項式時間算法指數(shù)時間算法往往在實際中不可接受各種串行計算模型是多項式時間等價的是否所有的問題都有好的算法？SAT問題TSP（Traveling salesman problem) 猜測TSP沒有多項式時間算法（J.Edmonds 1965）第36頁，共53頁，2022年，5月20日，7點43分，星期三圖靈機 有限狀態(tài)控制器1111110000000BBB1帶子可讀可寫無限長的帶子讀寫頭可左移右移第37頁，共53頁，2022年，5月20日，7點4

21、3分，星期三圖靈機“實際的”的圖靈機模型單帶圖靈機（1TM）多帶圖靈機（kTM）隨機存取機（RAM）“實際的”單位時間內(nèi)完成的工作量有一個多項式上界所有“實際的”計算模型多項式時間等價第38頁，共53頁，2022年，5月20日，7點43分，星期三非確定型圖靈機（NTM)不現(xiàn)實的計算現(xiàn)實中的計算方式都是確定的解SAT問題的一個非確定型算法第一步：猜測一個變量的真值賦值；第二步：檢查該賦值是否滿足非確定型算法的計算時間：各種可能的計算過程的最短時間第39頁，共53頁，2022年，5月20日，7點43分，星期三非確定型圖靈機（NTM) 有限狀態(tài)控制器1111110000000BBB1猜想模塊猜想階段

22、驗證階段第40頁，共53頁，2022年，5月20日，7點43分，星期三NTM計算樹計算過程：從根到葉節(jié)點的路徑第41頁，共53頁，2022年，5月20日，7點43分，星期三P類與NP類判定問題：只有肯定和否定兩種答案優(yōu)化問題可以化作判定問題處理P類（Polynomial)具有多項式時間算法的判定問題形成的計算復雜性類NP問題：在非確定型圖靈機上多項式時間可解的問題在確定型圖靈機上多項式時間可驗證的問題P類包含于NP類中NP類問題在確定圖靈機上指數(shù)時間可解非確定型圖靈機和確定型圖靈機的計算能力相當?shù)?2頁，共53頁，2022年，5月20日，7點43分，星期三計算難度的比較歸約多項式時間歸約（Ka

23、rp歸約 1972)問題A的實例I多項式時間內(nèi)轉(zhuǎn)化為問題B的實例f(I) ，對于A的輸入I 的回答與其對應(yīng)的B的輸入 f(I) 一致，則稱A可多項式歸約于B，記為如果B可以多項式時間求解，則A也可以多項式時間求解第43頁，共53頁，2022年，5月20日，7點43分，星期三NP完全問題NP完全問題是NP問題中“最難”的問題第44頁，共53頁，2022年，5月20日，7點43分，星期三NP完全問題第一個NP完全問題（Cook-levin定理 1971）可滿足性問題是NP完全問題如果一個NP完全問題karp歸約到另一個NP問題，則該問題也是NP完全的六個NP完全問題（Karp 1972)3SAT，3DM，VC，團，HC，劃分更多的NP完全問題1979年：300多個1998年：2000多個第45頁，共53頁，2022年，5月20