【文章內(nèi)容簡介】 全局共享存儲器 控制器 2 控制器 n 長春工業(yè)大學計算機科學與工程學院 ://.edu. MIMD異步計算模型 —— APRAM模型 ? APRAM模型特點 : ? 每個處理器都有其本地存儲器、局部時鐘和局部程序 ? 處理器間的通信經(jīng)過共享全局存儲器 ? 無全局時鐘，各處理器異步地獨立執(zhí)行各自的指令 ? 處理器任何時間依賴關系需明確地在各處理器的程序中加入同步（路）障（ Synchronization Barrier） ? 一條指令可在非確定但有限的時間內(nèi)完成。 ? APRAM模型中有四類指令 : ? 全局讀，將全局存儲單元中的內(nèi)容讀入本地存儲器單元中 ? 局部操作，對本地存儲器中的數(shù)執(zhí)行操作，其結果存入本地存儲器中 ? 全局寫，將本地存儲器單元中的內(nèi)容寫入全本地存儲器單元中 ? 同步，同步是計算中的一個邏輯點，在該點各處理器均需等待別的處理器到達后才能繼續(xù)執(zhí)行其局部程序 長春工業(yè)大學計算機科學與工程學院 ://.edu. MIMD異步計算模型 —— BSP模型 ? 大同步并行 BSP (Bulk Synchronous Parallel) 模型 作為計算機語言和體系結構之間的橋梁，由以下述三個參數(shù)描述 分布存儲的并行計算機模型 ： ? 處理器 /存儲器模塊（下文簡稱處理器） ? 處理器模塊之間點到點信息傳遞的路由器 ? 執(zhí)行以時間間隔 L為周期的路障同步器 ? 特點 ： ? 將處理器和路由器分開，強調(diào)了計算任務和通信任務的分開，而路由器僅施行點到點的消息傳遞，不提供組合、復制或廣播等功能，這樣做既掩蓋了具體的互聯(lián)網(wǎng)絡拓撲，又簡化了通信協(xié)議 ? 采用路障方式的以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負擔 ? 在分析 BSP模型的性能時，假定局部操作可在一個時間步內(nèi)完成，而在每一超級步中，一個處理器至多發(fā)送或接受 h條消息（ hrelation） 長春工業(yè)大學計算機科學與工程學院 ://.edu. MIMD異步計算模型 —— LogP模型 ? LogP模型是一種分布存儲的、點到點通信的多處理機模型，其中通信網(wǎng)絡由一組參數(shù)來描述，但它并不涉及到具體的網(wǎng)絡結構，也不假定算法一定要用顯式的消息傳遞操作進行描述。 ? L（ Latency） 源處理機與目的處理機進行消息 （ 一個或幾個字 ） 通信所需要的等待或延遲時間的上限 。 ? o（ overhead） 處理機準備發(fā)送或準備接受每個消息的時間開銷 （ 包括操作系統(tǒng)核心開銷和網(wǎng)絡軟件開銷 ） ， 在這段時間里處理機不能執(zhí)行其他操作 。 ? g（ gap） 一臺處理機連續(xù)兩次發(fā)送或連續(xù)兩次接受消息時的最小時間間隔 ， 其倒數(shù)即為處理機的通信帶寬 。 ? P（ Processor） 處理機的個數(shù) 。 長春工業(yè)大學計算機科學與工程學院 ://.edu. MIMD異步計算模型 —— LogP模型 ? 揭示了分布存儲并行計算機的性能瓶頸 ， 用 L、 o、 g三個參數(shù)刻畫了通信網(wǎng)絡的特性 ， ? 但屏蔽了網(wǎng)絡拓撲 、 選路算法和通信協(xié)議等具體細節(jié) ? 參數(shù) g反映了通信帶寬 ? 在任何時刻 ， 最多只能有 [L/g]條消息從一個處理器傳到另一個處理器 ， 這就是網(wǎng)絡容限 ， 當一臺處理機發(fā)送的消息達到這個容限時 ， 在發(fā)送的消息就會被阻塞； ? 在網(wǎng)絡容限范圍內(nèi) ， 點到點傳送一條消息的時間為 (2*o+L)。 ? 設想 LogP模型中的 L、 o、 g都為 0， 那么 LogP模型就等同于PRAM模型 長春工業(yè)大學計算機科學與工程學院 ://.edu. MIMD異步計算模型 —— C3模型 ? C3（ Computation, Communication, Congestion）模型是一個與體系結構無關的粗粒度的并行計算模型，旨在能反映 計算 復雜度， 通信 模式和通信期間潛在的 擁擠 等因素對粗粒度網(wǎng)絡算法的影響。 ? C3模型強調(diào)用共用的通信操作來開發(fā)粗粒度的并行算法 ? BSP、 LogP模型采用點到點的消息傳遞來進行通信，復雜的通信操作由編程實現(xiàn) 長春工業(yè)大學計算機科學與工程學院 ://.edu. 各種計算模型比較 模型屬性 PRAM APRAM BSP LogP C3 體系結構 SIMDSM MIMDSM MIMDDM MIMDDM MIMDDM 計算模式 同步 異步 異步 異步 異步 同步方式 自動同步 路障同步 路障同步 隱式同步 路障同步 模型參數(shù) 單位時間步 d,讀 /寫時間 B,同步時間 p,處理器數(shù) g,帶寬因子 l,同步間隔 L,通信延遲 o,額外開銷 g,帶寬因子 P,處理器數(shù) l,信包長度 s,發(fā)送建立時間 h,通信延遲 計算粒度 細粒度 /中粒度 中粒度 /粗粒度 中粒度 /粗粒度 中粒度 /粗粒度 粗粒度 通信方式 讀 /寫共享變量 讀 /寫共享變量 發(fā)送 /接收消息 發(fā)送 /接收消息 發(fā)送 /接收消息 地址空間 全局地址空間 單地址空間 單 /多地址空間 單 /多地址空間 多地址空間 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行編程方法 ? 編寫正確的串行程序 ? 分析：找出并發(fā)性 ? 找出包含獨立計算的熱點（ Hotspot）位置。熱點是指一段包含了大量操作的代碼 ? 設計與實現(xiàn)：采用線程來實現(xiàn)算法 ? 并行算法是適合在并行機上實現(xiàn)的算法 ? 測試正確性：檢測并修復在線程化時引入的錯誤 ? 性能調(diào)優(yōu)：消除性能瓶頸 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行算法分類 ? 并行算法根據(jù)運算基本對象的不同可分為： ? 數(shù)值并行算法 主要為數(shù)值計算方法而設計的并行算法； ? 非數(shù)值并行算法 主要為符號運算而設計的并行算法，如圖論算法、遺傳算法等。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行算法分類 ? 根據(jù)并行進程間相互執(zhí)行順序關系的不同可分為： ? 同步并行算法 進程間由于運算執(zhí)行順序而必須相互等待的并行算法，如通常的向量算法、 SIMD 算法、 MIMD 并行機上進程間需要相互等待通信結果的算法等； ? 異步并行算法 進程間執(zhí)行相對獨立，不需要相互等待的一種算法，通常針對消息傳遞 MIMD 并行機設計，其主要特征是在計算的整個過程中均不需要等待，而是根據(jù)最新消息決定進程的繼續(xù)或終止； ? 獨立并行算法 進程間執(zhí)行是完全獨立的，計算的整個過程不需要任何通信。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行算法分類 ? 根據(jù)各進程承擔的計算任務粒度的不同，可分為： ? 細粒度并行算法通常指基于向量和循環(huán)級并行的算法； ? 中粒度并行算法通常指基于較大的循環(huán)級并行； ? 大粒度并行算法通常指基于子任務級并行的算法，例如通常的基于區(qū)域分解的并行算法，它們是當前并行算法設計的主流。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行編程環(huán)境 ? 比較流行的并行編程環(huán)境主要有 3類：消息傳遞、共享存儲和數(shù)據(jù)并行： ? 共享存儲并行編程基于線程級細粒度并行，可移植性不如消息傳遞并行編程，但是，由于他們支持數(shù)據(jù)的共享存儲，所以并行編程的難度較小，但一般情況下，當處理機個數(shù)較多時，其并行性能明顯不如消息傳遞編程 ； ? 消息傳遞并行編程基于大粒度的進程級并行，具有最好的可擴展性，幾乎被所有當前流行的各類并行計算機所支持，其具有較好的可擴展性。消息傳遞并行編程只能支持進程間的分布式存儲模式，即各個進程只能支持訪問其局部內(nèi)存空間，而對其他進程的局部內(nèi)存空間的訪問只能通過消息傳遞來實現(xiàn)，因此，學習和使用消息傳遞并行編程的難度均大于共享存儲和數(shù)據(jù)并行這兩種編程模式。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行編程環(huán)境 ? 比較流行的并行編程環(huán)境主要有 3類：消息傳遞、共享存儲和數(shù)據(jù)并行 特征 消息傳遞 共享存儲 數(shù)據(jù)并行 典型代表 MPI, PVM OpenMP HPF 可移植性 所有主流并行計算機 SMP, DSM SMP, DSM, MPP 并行粒度 進程級大粒度 線程級細粒度 進程級細粒度 并行操作方式 異步 異步 松散同步 數(shù)據(jù)存儲模式 分布式存儲 共享存儲 共享存儲 數(shù)據(jù)分配方式 顯式 隱式 半隱式 學習入門難度 較難 容易 偏易 可擴展性 好 較差 一般 長春工業(yè)大學計算機科學與工程學院 ://.edu. 編程語言與編譯器 ? 在科學計算領域對并行編程支持已經(jīng)取得相當成功的三項技術： ? 自動并行化 ? 數(shù)據(jù)并行語言 HPF ? 共享存儲并行編程接口 OpenMP 長春工業(yè)大學計算機科學與工程學院 ://.edu. 編程語言與編譯器 ? 自動并行 ? 始于 20世紀 70年代的自動向量化。 ? 20世紀 80年代中期，基于依賴分析的向量化工具成熟，成為向量機的標準。 ? 自動化并行本身不足以解決并行程序設計問題。 ? 此領域的研究重點逐步轉向基于語言的策略研究，即從用戶那里獲得更多的信息，同時利用自動并行化技術來減輕程序設計的負擔。 依賴分析： 搜索確定對同一數(shù)據(jù)結構的哪些引用是訪問同一存儲單元的 長春工業(yè)大學計算機科學與工程學院 ://.edu. 編程語言與編譯器 ? 數(shù)據(jù)并行編程： HPF ? 高性能 Fortran(HPF)的思想是使數(shù)據(jù)管理的多數(shù)細節(jié)自動并行化 ? HPF提供了一個指令集，通過注釋形式的指令來擴展變量類型的說明，能夠對數(shù)組的數(shù)據(jù)布局進行相當詳細的控制。 ? 對顯式并行機制的說明相當有限，通過系統(tǒng)而非程序員把任務分配給處理機。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 編程語言與編譯器 ? 共享存儲并行編程： OpenMP ? 1997年由 Silicon Graphics領導的工業(yè)協(xié)會推出了 OpenMP ? 是一個與 Fortran77和 C語言綁定的并行編程接口 ? OpenMP指令在單機編譯器上被當作注釋而忽略 ? 通過 parallel section 指令獲得任務并行 pragma omp parallel for … ? 提供了鎖變量用于線程間細粒度同步 ? 是適合于具有一致性訪存的共享存儲計算機的編程接口 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行計算性能評測 ? 并行程序執(zhí)行時間 從并行程序開始執(zhí)行到所有進程執(zhí)行完畢，墻上時鐘走過的時間，也稱為墻上時間 （ wall clock time）。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行計算性能評測 ? 并行程序執(zhí)行時間 對各個進程，墻上時間可進一步分解為計算 CPU時間、通信 CPU時間、同步開銷時間、同步導致的進程空閑時間 ? 計算 CP