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