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

并行計算第二篇并行算法的設(shè)計第一頁，共五十三頁，編輯于2023年，星期日第二篇并行算法的設(shè)計第四章并行算法的設(shè)計基礎(chǔ)第五章并行算法的一般設(shè)計策略第六章并行算法的基本設(shè)計技術(shù)第七章并行算法的一般設(shè)計過程第二頁，共五十三頁，編輯于2023年，星期日第四章并行算法的設(shè)計基礎(chǔ)4.1并行算法的基礎(chǔ)知識4.2并行計算模型

第三頁，共五十三頁，編輯于2023年，星期日4.1并行算法的基礎(chǔ)知識4.1.1并行算法的定義和分類4.1.2并行算法的表達4.1.3并行算法的復(fù)雜性度量4.1.4并行算法中的同步和通信第四頁，共五十三頁，編輯于2023年，星期日并行算法的定義和分類并行算法的定義算法并行算法：一些可同時執(zhí)行的諸進程的集合，這些進程互相作用和協(xié)調(diào)動作從而達到給定問題的求解。并行算法的分類數(shù)值計算和非數(shù)值計算同步算法和異步算法分布算法確定算法和隨機算法第五頁，共五十三頁，編輯于2023年，星期日并行算法的表達描述語言可以使用類Algol、類Pascal等；在描述語言中引入并行語句。并行語句示例Par-do語句

fori=1tonpar-do……endforforall語句forallPi,where0≤i≤k……endfor第六頁，共五十三頁，編輯于2023年，星期日并行算法的復(fù)雜性度量串行算法的復(fù)雜性度量最壞情況下的復(fù)雜度(Worst-CASEComplexity)期望復(fù)雜度(ExpectedComplexity)并行算法的幾個復(fù)雜性度量指標(biāo)運行時間t(n):包含計算時間和通訊時間，分別用計算時間步和選路時間步作單位。n為問題實例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n):c(n)=t(n)p(n)總運算量W(n):并行算法求解問題時所完成的總的操作步數(shù)。

第七頁，共五十三頁，編輯于2023年，星期日并行算法的復(fù)雜性度量Brent定理令W(n)是某并行算法A在運行時間T(n)內(nèi)所執(zhí)行的運算量，則A使用p臺處理器可在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)第八頁，共五十三頁，編輯于2023年，星期日并行算法的同步同步概念同步是在時間上強使各執(zhí)行進程在某一點必須互相等待；可用軟件、硬件和固件的辦法來實現(xiàn)。同步語句示例算法4.1共享存儲多處理器上求和算法輸入：A=(a0,…,an-1),處理器數(shù)p輸出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1

doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)forj=itonsteppdoendforL=L+ajEndendforendfor第九頁，共五十三頁，編輯于2023年，星期日并行算法的通信通信共享存儲多處理器使用：globalread(X,Y)和globalwrite(X,Y)分布存儲多計算機使用：send(X,i)和receive(Y,j)通信語句示例算法4.2分布存儲多計算機上矩陣向量乘算法

輸入：處理器數(shù)p,A劃分為B=A[1..n,(i-1)r+1..ir],x劃分為w=w[(i-1)r+1;ir]輸出：P1保存乘積AXBegin(1)Computez=Bw(2)ifi=1thenyi=0elsereceive(y,left)endif(3)y=y+z(4)send(y,right)(5)ifi=1thenreceive(y,left)End第十頁，共五十三頁，編輯于2023年，星期日4.2并行計算模型4.2.1PRAM模型4.2.2異步APRAM模型4.2.3BSP模型4.2.4logP模型第十一頁，共五十三頁，編輯于2023年，星期日PRAM模型基本概念由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個集中的共享存儲器和一個指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計算。結(jié)構(gòu)圖ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory第十二頁，共五十三頁，編輯于2023年，星期日PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-CRCW(CommonPRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(PriorityPRAM-CRCW)：僅允許優(yōu)先級最高的處理器寫入APRAM-CRCW(ArbitraryPRAM-CRCW)：允許任意處理器自由寫入PRAM-CREW并發(fā)讀互斥寫PRAM-EREW互斥讀互斥寫計算能力比較PRAM-CRCW是最強的計算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW第十三頁，共五十三頁，編輯于2023年，星期日PRAM模型優(yōu)點適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機的通訊、同步等細節(jié)。缺點不適合MIMD并行機，忽略了SM的競爭、通訊延遲等因素第十四頁，共五十三頁，編輯于2023年，星期日異步APRAM模型基本概念又稱分相（Phase）PRAM或MIMD-SM。每個處理器有其局部存儲器、局部時鐘、局部程序；無全局時鐘，各處理器異步執(zhí)行；處理器通過SM進行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀(2)全局寫(3)局部操作(4)同步第十五頁，共五十三頁，編輯于2023年，星期日異步APRAM模型計算過程由同步障分開的全局相組成第十六頁，共五十三頁，編輯于2023年，星期日異步APRAM模型計算時間

設(shè)局部操作為單位時間；全局讀/寫平均時間為d，d隨著處理器數(shù)目的增加而增加；同步路障時間為B=B(p)非降函數(shù)。滿足關(guān)系；或令為全局相內(nèi)各處理器執(zhí)行時間最長者，則APRAM上的計算時間為優(yōu)缺點

易編程和分析算法的復(fù)雜度，但與現(xiàn)實相差較遠，其上并行算法非常有限，也不適合MIMD-DM模型。

第十七頁，共五十三頁，編輯于2023年，星期日BSP模型基本概念由Valiant(1990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。

模型參數(shù)p：處理器數(shù)(帶有存儲器)l：同步障時間(Barriersynchronizationtime)g：帶寬因子(timesteps/packet)=1/bandwidth第十八頁，共五十三頁，編輯于2023年，星期日BSP模型計算過程由若干超級步組成，每個超級步計算模式為左圖優(yōu)缺點

強調(diào)了計算和通訊的分離，提供了一個編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機制，限制至多h條消息的傳遞等。第十九頁，共五十三頁，編輯于2023年，星期日logP模型基本概念由Culler(1993)年提出的，是一種分布存儲的、點到點通訊的多處理機模型，其中通訊由一組參數(shù)描述，實行隱式同步。模型參數(shù)L：networklatencyo：communicationoverheadg：gap=1/bandwidthP：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量

第二十頁，共五十三頁，編輯于2023年，星期日logP模型優(yōu)缺點

捕捉了MPC的通訊瓶頸，隱藏了并行機的網(wǎng)絡(luò)拓撲、路由、協(xié)議，可以應(yīng)用到共享存儲、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進行算法描述、設(shè)計和分析。BSPvs.LogPBSPLogP：BSP塊同步BSP子集同步BSP進程對同步＝LogPBSP可以常數(shù)因子模擬LogP，LogP可以對數(shù)因子模擬BSPBSP＝LogP+Barriers－OverheadBSP提供了更方便的程設(shè)環(huán)境，LogP更好地利用了機器資源BSP似乎更簡單、方便和符合結(jié)構(gòu)化編程

第二十一頁，共五十三頁，編輯于2023年，星期日作業(yè)（1）TOP500綜述應(yīng)用舉例：新聞報道等選擇某個型號的高性能計算機，撰寫調(diào)研報告顧乃杰等，基于斐波那契序列的多播算法Brent定理的證明和意義BSP編程方法調(diào)研第二十二頁，共五十三頁，編輯于2023年，星期日23第二十三頁，共五十三頁，編輯于2023年，星期日模型與下界不同的PRAM模型的相互模擬下界NP完全理論P完全理論第二十四頁，共五十三頁，編輯于2023年，星期日不同的PRAM模型的相互模擬不同的PRAM模型PRAM-EREWPRAM-CREWPRAM-CRCWCPRAM-CRCWAPRAM-CRCWPPRAM-CRCW計算能力是相當(dāng)?shù)牡诙屙?，共五十三頁，編輯?023年，星期日PRAM-EREW模擬PPRAM-CRCW定理1：一條p-處理器PPRAM-CRCW模型上的指令，可在p-處理器PRAM-EREW模型上用O(logp)的時間實現(xiàn)。證明思路：并發(fā)讀指令和并發(fā)寫指令(PPRAM-CRCW)并發(fā)讀指令：處理器Qi讀取Mi單元中的內(nèi)容(PRAM-EREW)處理器Pi設(shè)置數(shù)對<Mi,i><Mi,i>按照字典序排序：時間O(logp)第一分量相同的數(shù)對組成塊（通過樹播送數(shù)據(jù)，完成數(shù)據(jù)分布）Pi讀取對于<Mi,i>的數(shù)據(jù)：時間O(1)并發(fā)寫指令：使用三元組<地址，處理器號，待寫數(shù)據(jù)>推論：TEREW=O(TPCRCWlogp

)第二十六頁，共五十三頁，編輯于2023年，星期日PRAM-CRCW之間的模擬CPRAM_CRCW上算法可在APRAM_CRCW上正確執(zhí)行APRAM_CRCW上算法可在PPRAM_CRCW上正確執(zhí)行似乎計算能力是按CPRAM_CRCW，APRAM_CRCW，PPRAM_CRCW依次增強的。在對處理器數(shù)目或?qū)蚕泶鎯Φ娜萘坎患酉拗茣r，三個模型是等效的。最左俘獲問題：p個處理器，“活躍”或者“非活躍”。每個活躍的處理器有標(biāo)記，值為0或1。當(dāng)且僅當(dāng)處理器是編號最小的活躍處理器，標(biāo)記為1。第二十七頁，共五十三頁，編輯于2023年，星期日CPRAM-CRCW模擬PPRAM-CRCW定理2運行在p-處理器PPRAM-CRCW上時間為T的算法，可在plogp-處理器CPRAM-CRCW上運行時間為O(T)。證明思路：對于PPRAM-CRCW中每個參與寫操作的處理器，使用logp個輔助處理器，構(gòu)造一個完全二叉樹來選取標(biāo)號最小的活躍處理器。定理3p-處理器PPRAM-CRCW上的一條并發(fā)寫指令，可在p-處理器CPRAM-CRCW模型上用O(logp/loglogp)時間實現(xiàn)。證明思路:歸納法。第二十八頁，共五十三頁，編輯于2023年，星期日APRAM-CRCW模擬PPRAM-CRCW定理4p-處理器PPRAM-CRCW上的一條并發(fā)寫指令，可在p-處理器APRAM-CRCW模型上用O(loglogp)時間實現(xiàn)。證明思路：方根劃分技術(shù)，遞歸求解時間：模擬的意義？第二十九頁，共五十三頁，編輯于2023年，星期日算法研究的兩個方向優(yōu)化尋找更好的算法設(shè)計技巧一個新的算法（上界）可能性說明難以得到更好的算法證明技巧對模型、問題的更好認識（下界）第三十頁，共五十三頁，編輯于2023年，星期日Gates,WilliamH.andChristosH.Papadimitriou.Boundsforsortingbyprefixreversal.

DiscreteMathematics27(1979),47--57.HarvardUniversity(1973)Microsoft(1975)PrincetonUniversity(MS1974andPhD1976)第三十一頁，共五十三頁，編輯于2023年，星期日上界與下界問題描述：僅通過前綴翻轉(zhuǎn)（prefixreversal）操作對n個大小不同的序列排序。前綴翻轉(zhuǎn)：將包含首個元素的子序列進行翻轉(zhuǎn)結(jié)果：給出算法，證明至多(5n+5)/3次操作可以排序完成給出例子，證明17n/16次操作無法完成排序改進：1995年，新的下界結(jié)果第三十二頁，共五十三頁，編輯于2023年，星期日PRAM模型的下界理想的PRAM模型n個處理器可訪問無限的共享存儲單元每個處理器有無限的私有存儲單元一步計算分為三個階段：讀階段、計算階段、寫階段每一步計算允許任意數(shù)量的局部計算理想PRAM模型反映了通信的限制理想PRAM模型的下界對于標(biāo)準(zhǔn)PRAM模型同樣成立第三十三頁，共五十三頁，編輯于2023年，星期日PRAM模型的下界PRAM-CREW的下界無論多少處理器，計算n變元的布爾或需要Ω(logn)的時間PRAM-EREW的下界p個處理器，計算長度為n的計數(shù)零問題需要Ω(logn-logp)的時間PRAM-CRCW的下界計算n變量奇偶函數(shù)，使用多項式數(shù)目的處理器需要Ω(logn/loglogn)的時間第三十四頁，共五十三頁，編輯于2023年，星期日NP完全理論導(dǎo)引計算復(fù)雜性理論中最重要的理論在工作中，遇到一個問題，找不到好的算法來解決，怎么辦？第三十五頁，共五十三頁，編輯于2023年，星期日算法與好的算法算法：為實現(xiàn)某個任務(wù)而構(gòu)成的簡單指令集有窮的計算良過程通過有限多次運算可以決定的過程圖靈機好的算法：多項式時間算法指數(shù)時間算法往往在實際中不可接受各種串行計算模型是多項式時間等價的是否所有的問題都有好的算法？SAT問題TSP（Travelingsalesmanproblem)猜測TSP沒有多項式時間算法（J.Edmonds1965）第三十六頁，共五十三頁，編輯于2023年，星期日圖靈機有限狀態(tài)控制器1111110000000BBB1…………帶子可讀可寫無限長的帶子讀寫頭可左移右移第三十七頁，共五十三頁，編輯于2023年，星期日圖靈機“實際的”的圖靈機模型單帶圖靈機（1TM）多帶圖靈機（kTM）隨機存取機（RAM）“實際的”單位時間內(nèi)完成的工作量有一個多項式上界所有“實際的”計算模型多項式時間等價第三十八頁，共五十三頁，編輯于2023年，星期日非確定型圖靈機（NTM)不現(xiàn)實的計算現(xiàn)實中的計算方式都是確定的解SAT問題的一個非確定型算法第一步：猜測一個變量的真值賦值；第二步：檢查該賦值是否滿足非確定型算法的計算時間：各種可能的計算過程的最短時間第三十九頁，共五十三頁，編輯于2023年，星期日非確定型圖靈機（NTM)有限狀態(tài)控制器1111110000000BBB1…………猜想模塊猜想階段驗證階段第四十頁，共五十三頁，編輯于2023年，星期日NTM計算樹計算過程：從根到葉節(jié)點的路徑第四十一頁，共五十三頁，編輯于2023年，星期日P類與NP類判定問題：只有肯定和否定兩種答案優(yōu)化問題可以化作判定問題處理P類 （Polynomial)具有多項式時間算法的判定問題形成的計算復(fù)雜性類NP問題：在非確定型圖靈機上多項式時間可解的問題在確定型圖靈機上多項式時間可驗證的問題P類包含于NP類中NP類問題在確定圖靈機上指數(shù)時間可解非確定型圖靈機和確定型圖靈機的計算能力相當(dāng)?shù)谒氖?，共五十三頁，編輯?023年，星期日計算難度的比較——歸約多項式時間歸約（Karp歸約1972)問題A的實例I多項式時間內(nèi)轉(zhuǎn)化為問題B的實例f(I)，對于A的輸入I的回答與其對應(yīng)的B的輸入f(I)一致，則稱A可多項式歸約于B，記為如果B可以多項式時間求解，則A也可以多項式時間求解第四十三頁，共五十三頁，編輯于2023年，星期日NP完全問題NP完全問題是NP問題中“最難”的問題第四十四頁，共五十三頁，編輯于2023年，星期日NP完全問題第一個NP完全問題（Cook-levin定理1971）可滿足性問題是NP完全問題如果一個NP完全問題karp歸約到另一個NP問題，則該問題也是NP完全的六個NP完全問題（Karp1972)3