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

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

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

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

4、可在t(n)=O(W(n)/p+T(n)時(shí)間內(nèi)執(zhí)行完畢。W(n)和c(n)密切相關(guān)P=O(W(n)/T(n)時(shí)，W(n)和c(n)兩者是漸進(jìn)一致的對(duì)于任意的p，c(n)W(n)第8頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三 并行算法的同步同步概念同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待；可用軟件、硬件和固件的辦法來(lái)實(shí)現(xiàn)。同步語(yǔ)句示例算法4.1 共享存儲(chǔ)多處理器上求和算法 輸入：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頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三 并行算法的通信通信共享存儲(chǔ)多處理器使用：global read(X,Y)和global write(X,Y)分布存儲(chǔ)多計(jì)算機(jī)使用：send(X,i)和receive(Y,j)通信語(yǔ)句示例算法4.2 分布存儲(chǔ)多計(jì)算機(jī)上矩陣向量乘算法 輸入：處理器數(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頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三4.2 并行計(jì)算模型4.2.1 PRAM模型4.2.2 異步APRAM模型4.2.3 BSP模型4.2.4 logP模型第11頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三 PRAM模型基本概念由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個(gè)集中的

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

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

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

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

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

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

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

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

15、W上正確執(zhí)行似乎計(jì)算能力是按CPRAM_CRCW，APRAM_CRCW，PPRAM_CRCW依次增強(qiáng)的。在對(duì)處理器數(shù)目或?qū)蚕泶鎯?chǔ)的容量不加限制時(shí)，三個(gè)模型是等效的。最左俘獲問(wèn)題：p個(gè)處理器，“活躍”或者“非活躍”。每個(gè)活躍的處理器有標(biāo)記，值為0或1。 當(dāng)且僅當(dāng)處理器是編號(hào)最小的活躍處理器，標(biāo)記為1。第27頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三CPRAM-CRCW模擬PPRAM-CRCW定理2 運(yùn)行在p-處理器PPRAM-CRCW上時(shí)間為T(mén)的算法，可在plogp-處理器CPRAM-CRCW上運(yùn)行時(shí)間為O(T)。證明思路：對(duì)于PPRAM-CRCW中每個(gè)參與寫(xiě)操作的處理器，使用l

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

17、化尋找更好的算法設(shè)計(jì)技巧一個(gè)新的算法（上界）可能性說(shuō)明難以得到更好的算法證明技巧對(duì)模型、問(wèn)題的更好認(rèn)識(shí)（下界）第30頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)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頁(yè)

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

19、制理想PRAM模型的下界對(duì)于標(biāo)準(zhǔn)PRAM模型同樣成立第33頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三PRAM模型的下界PRAM-CREW的下界 無(wú)論多少處理器，計(jì)算n變?cè)牟紶柣蛐枰?logn)的時(shí)間PRAM-EREW的下界 p個(gè)處理器，計(jì)算長(zhǎng)度為n的計(jì)數(shù)零問(wèn)題需要(logn-logp)的時(shí)間PRAM-CRCW的下界 計(jì)算n變量奇偶函數(shù)，使用多項(xiàng)式數(shù)目的處理器需要(logn/loglogn)的時(shí)間第34頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三NP完全理論導(dǎo)引計(jì)算復(fù)雜性理論中最重要的理論在工作中，遇到一個(gè)問(wèn)題，找不到好的算法來(lái)解決，怎么辦？第35頁(yè)，共53頁(yè)，202

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

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

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

23、rp歸約 1972)問(wèn)題A的實(shí)例I多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為問(wè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í)間求解第43頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三NP完全問(wèn)題NP完全問(wèn)題是NP問(wèn)題中“最難”的問(wèn)題第44頁(yè)，共53頁(yè)，2022年，5月20日，7點(diǎn)43分，星期三NP完全問(wèn)題第一個(gè)NP完全問(wèn)題（Cook-levin定理 1971）可滿足性問(wèn)題是NP完全問(wèn)題如果一個(gè)NP完全問(wèn)題karp歸約到另一個(gè)NP問(wèn)題，則該問(wèn)題也是NP完全的六個(gè)NP完全問(wèn)題（Karp 1972)3SAT，3DM，VC，團(tuán)，HC，劃分更多的NP完全問(wèn)題1979年：300多個(gè)1998年：2000多個(gè)第45頁(yè)，共53頁(yè)，2022年，5月20