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

并行計(jì)算 2009年3月10日 第二篇并行算法的設(shè)計(jì) 第四章并行算法的設(shè)計(jì)基礎(chǔ)第五章并行算法的一般設(shè)計(jì)策略第六章并行算法的基本設(shè)計(jì)技術(shù)第七章并行算法的一般設(shè)計(jì)過程 第四章并行算法的設(shè)計(jì)基礎(chǔ) 4 1并行算法的基礎(chǔ)知識4 2并行計(jì)算模型 4 1并行算法的基礎(chǔ)知識 4 1 1并行算法的定義和分類4 1 2并行算法的表達(dá)4 1 3并行算法的復(fù)雜性度量4 1 4并行算法中的同步和通信 并行算法的定義和分類 并行算法的定義算法并行算法 一些可同時(shí)執(zhí)行的諸進(jìn)程的集合 這些進(jìn)程互相作用和協(xié)調(diào)動作從而達(dá)到給定問題的求解 并行算法的分類數(shù)值計(jì)算和非數(shù)值計(jì)算同步算法和異步算法分布算法確定算法和隨機(jī)算法 并行算法的表達(dá) 描述語言可以使用類Algol 類Pascal等 在描述語言中引入并行語句 并行語句示例Par do語句fori 1tonpar do endforforall語句forallPi where0 i k endfor 并行算法的復(fù)雜性度量 串行算法的復(fù)雜性度量最壞情況下的復(fù)雜度 Worst CASEComplexity 期望復(fù)雜度 ExpectedComplexity 并行算法的幾個(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 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)一致的對于任意的p c n W n 并行算法的同步 同步概念同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待 可用軟件 硬件和固件的辦法來實(shí)現(xiàn) 同步語句示例算法4 1共享存儲多處理器上求和算法輸入 A a0 an 1 處理器數(shù)p輸出 S aiBegin 1 S 0 2 3 lock S 2 forallPiwhere0 i p 1doS S L 2 1 L 0 2 4 unlock S 2 2 forj itonsteppdoendforL L ajEndendforendfor 并行算法的通信 通信共享存儲多處理器使用 globalread X Y 和globalwrite X Y 分布存儲多計(jì)算機(jī)使用 send X i 和receive Y j 通信語句示例算法4 2分布存儲多計(jì)算機(jī)上矩陣向量乘算法輸入 處理器數(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 4 2并行計(jì)算模型 4 2 1PRAM模型4 2 2異步APRAM模型4 2 3BSP模型4 2 4logP模型 PRAM模型 基本概念由Fortune和Wyllie1978年提出 又稱SIMD SM模型 有一個(gè)集中的共享存儲器和一個(gè)指令控制器 通過SM的R W交換數(shù)據(jù) 隱式同步計(jì)算 結(jié)構(gòu)圖 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互斥讀互斥寫計(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的競爭 通訊延遲等因素 異步APRAM模型 基本概念又稱分相 Phase PRAM或MIMD SM 每個(gè)處理器有其局部存儲器 局部時(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)系 或令為全局相內(nèi)各處理器執(zhí)行時(shí)間最長者 則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ù) 帶有存儲器 l 同步障時(shí)間 Barriersynchronizationtime g 帶寬因子 timesteps packet 1 bandwidth BSP模型 計(jì)算過程由若干超級步組成 每個(gè)超級步計(jì)算模式為左圖優(yōu)缺點(diǎn)強(qiáng)調(diào)了計(jì)算和通訊的分離 提供了一個(gè)編程環(huán)境 易于程序復(fù)雜性分析 但需要顯式同步機(jī)制 限制至多h條消息的傳遞等 logP模型 基本概念由Culler 1993 年提出的 是一種分布存儲的 點(diǎn)到點(diǎn)通訊的多處理機(jī)模型 其中通訊由一組參數(shù)描述 實(shí)行隱式同步 模型參數(shù)L networklatencyo communicationoverheadg gap 1 bandwidthP processors注 L和g反映了通訊網(wǎng)絡(luò)的容量 logP模型 優(yōu)缺點(diǎn)捕捉了MPC的通訊瓶頸 隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?路由 協(xié)議 可以應(yīng)用到共享存儲 消息傳遞 數(shù)據(jù)并行的編程模型中 但難以進(jìn)行算法描述 設(shè)計(jì)和分析 BSPvs LogPBSP LogP BSP塊同步 BSP子集同步 BSP進(jìn)程對同步 LogPBSP可以常數(shù)因子模擬LogP LogP可以對數(shù)因子模擬BSPBSP LogP Barriers OverheadBSP提供了更方便的程設(shè)環(huán)境 LogP更好地利用了機(jī)器資源BSP似乎更簡單 方便和符合結(jié)構(gòu)化編程 作業(yè) 1 TOP500綜述應(yīng)用舉例 新聞報(bào)道等選擇某個(gè)型號的高性能計(jì)算機(jī) 撰寫調(diào)研報(bào)告顧乃杰等 基于斐波那契序列的多播算法Brent定理的證明和意義BSP編程方法調(diào)研 23 模型與下界 不同的PRAM模型的相互模擬下界NP完全理論P(yáng)完全理論 不同的PRAM模型的相互模擬 不同的PRAM模型PRAM EREWPRAM CREWPRAM CRCWCPRAM CRCWAPRAM CRCWPPRAM CRCW計(jì)算能力是相當(dāng)?shù)?PRAM EREW模擬PPRAM CRCW 定理1 一條p 處理器PPRAM CRCW模型上的指令 可在p 處理器PRAM EREW模型上用O logp 的時(shí)間實(shí)現(xiàn) 證明思路 并發(fā)讀指令和并發(fā)寫指令 PPRAM CRCW 并發(fā)讀指令 處理器Qi讀取Mi單元中的內(nèi)容 PRAM EREW 處理器Pi設(shè)置數(shù)對按照字典序排序 時(shí)間O logp 第一分量相同的數(shù)對組成塊 通過樹播送數(shù)據(jù) 完成數(shù)據(jù)分布 Pi讀取對于的數(shù)據(jù) 時(shí)間O 1 并發(fā)寫指令 使用三元組推論 TEREW O TPCRCWlogp PRAM CRCW之間的模擬 CPRAM CRCW上算法可在APRAM CRCW上正確執(zhí)行APRAM CRCW上算法可在PPRAM CRCW上正確執(zhí)行似乎計(jì)算能力是按CPRAM CRCW APRAM CRCW PPRAM CRCW依次增強(qiáng)的 在對處理器數(shù)目或?qū)蚕泶鎯Φ娜萘坎患酉拗茣r(shí) 三個(gè)模型是等效的 最左俘獲問題 p個(gè)處理器 活躍 或者 非活躍 每個(gè)活躍的處理器有標(biāo)記 值為0或1 當(dāng)且僅當(dāng)處理器是編號最小的活躍處理器 標(biāo)記為1 CPRAM CRCW模擬PPRAM CRCW 定理2運(yùn)行在p 處理器PPRAM CRCW上時(shí)間為T的算法 可在plogp 處理器CPRAM CRCW上運(yùn)行時(shí)間為O T 證明思路 對于PPRAM CRCW中每個(gè)參與寫操作的處理器 使用logp個(gè)輔助處理器 構(gòu)造一個(gè)完全二叉樹來選取標(biāo)號最小的活躍處理器 定理3p 處理器PPRAM CRCW上的一條并發(fā)寫指令 可在p 處理器CPRAM CRCW模型上用O logp loglogp 時(shí)間實(shí)現(xiàn) 證明思路 歸納法 APRAM CRCW模擬PPRAM CRCW 定理4p 處理器PPRAM CRCW上的一條并發(fā)寫指令 可在p 處理器APRAM CRCW模型上用O loglogp 時(shí)間實(shí)現(xiàn) 證明思路 方根劃分技術(shù) 遞歸求解時(shí)間 模擬的意義 算法研究的兩個(gè)方向 優(yōu)化尋找更好的算法設(shè)計(jì)技巧一個(gè)新的算法 上界 可能性說明難以得到更好的算法證明技巧對模型 問題的更好認(rèn)識 下界 Gates WilliamH andChristosH Papadimitriou Boundsforsortingbyprefixreversal DiscreteMathematics27 1979 47 57 HarvardUniversity 1973 Microsoft 1975 PrincetonUniversity MS1974andPhD1976 上界與下界 問題描述 僅通過前綴翻轉(zhuǎn) prefixreversal 操作對n個(gè)大小不同的序列排序 前綴翻轉(zhuǎn) 將包含首個(gè)元素的子序列進(jìn)行翻轉(zhuǎn)結(jié)果 給出算法 證明至多 5n 5 3次操作可以排序完成給出例子 證明17n 16次操作無法完成排序改進(jìn) 1995年 新的下界結(jié)果 PRAM模型的下界 理想的PRAM模型n個(gè)處理器可訪問無限的共享存儲單元每個(gè)處理器有無限的私有存儲單元一步計(jì)算分為三個(gè)階段 讀階段 計(jì)算階段 寫階段每一步計(jì)算允許任意數(shù)量的局部計(jì)算理想PRAM模型反映了通信的限制理想PRAM模型的下界對于標(biāo)準(zhǔn)PRAM模型同樣成立 PRAM模型的下界 PRAM CREW的下界無論多少處理器 計(jì)算n變元的布爾或需要 logn 的時(shí)間PRAM EREW的下界p個(gè)處理器 計(jì)算長度為n的計(jì)數(shù)零問題需要 logn logp 的時(shí)間PRAM CRCW的下界計(jì)算n變量奇偶函數(shù) 使用多項(xiàng)式數(shù)目的處理器需要 logn loglogn 的時(shí)間 NP完全理論導(dǎo)引 計(jì)算復(fù)雜性理論中最重要的理論在工作中 遇到一個(gè)問題 找不到好的算法來解決 怎么辦 算法與好的算法 算法 為實(shí)現(xiàn)某個(gè)任務(wù)而構(gòu)成的簡單指令集有窮的計(jì)算良過程通過有限多次運(yùn)算可以決定的過程圖靈機(jī)好的算法 多項(xiàng)式時(shí)間算法指數(shù)時(shí)間算法往往在實(shí)際中不可接受各種串行計(jì)算模型是多項(xiàng)式時(shí)間等價(jià)的是否所有的問題都有好的算法 SAT問題TSP Travelingsalesmanproblem 猜測TSP沒有多項(xiàng)式時(shí)間算法 J Edmonds1965 圖靈機(jī) 帶子可讀可寫無限長的帶子讀寫頭可左移右移 圖靈機(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è)非確定型算法第一步 猜測一個(gè)變量的真值賦值 第二步 檢查該賦值是否滿足非確定型算法的計(jì)算時(shí)間 各種可能的計(jì)算過程的最短時(shí)間 非確定型圖靈機(jī) NTM 猜想模塊 猜想階段驗(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í)間可解非確定型圖靈機(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 對于A的輸入I的回答與其對應(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問題 則該問題也是NP完全的六個(gè)NP完全問題 Karp1972 3SAT 3DM VC 團(tuán) HC 劃分更多的NP完全問題1979年 300多個(gè)1998年 2000多個(gè) P NP P NP問題 現(xiàn)在的估計(jì) 如果 則NPC問題無有效算法 P NP 如何處理NP完全問題 實(shí)際中的NP完全問題不會消失證明難度并不會使問題得到解決近似算法隨機(jī)算法 并行計(jì)算理想的PRAM模型上可多項(xiàng)式時(shí)間解決NP完全問題 P完全理論導(dǎo)引 計(jì)算模型 PRAMP類NC Nick sClass 類 在PRAM上 使用多項(xiàng)式數(shù)目的處理器 在多對數(shù)時(shí)間內(nèi)可求解的問題 NC類在P類中有些問題難以在使用多項(xiàng)式數(shù)目的處理器 在多對數(shù)時(shí)間