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