第一章并行編程硬件基礎(chǔ)2

1、并行程序設(shè)計并行程序設(shè)計-2 內(nèi)容提要內(nèi)容提要 一一并行編程硬件基礎(chǔ)并行編程硬件基礎(chǔ) （3學(xué)時）學(xué)時） 二并行編程軟件基礎(chǔ) （3學(xué)時） 三多線程編程基礎(chǔ) （2學(xué)時） 四Linux多線程編程（2學(xué)時） 五Windows多線程編程 （3學(xué)時） 六OpenMP編程 （7學(xué)時） 七M(jìn)PI編程 （4學(xué)時） 八其他編程語言和方法（2學(xué)時） 九并行程序設(shè)計的應(yīng)用實例（2學(xué)時） 1 并行程序設(shè)計引言 2 并行計算機系統(tǒng)互聯(lián)并行計算機系統(tǒng)互聯(lián) 3 并行計算機系統(tǒng)模型并行計算機系統(tǒng)模型 （本節(jié)課內(nèi)容）（本節(jié)課內(nèi)容） 4 多核技術(shù) 一、一、 并行編程硬件基礎(chǔ)并行編程硬件基礎(chǔ) 2并行計算機系統(tǒng)互連網(wǎng)絡(luò)并行計算機系統(tǒng)互

2、連網(wǎng)絡(luò) v互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)是將集中式系統(tǒng)或分布式系統(tǒng)中的節(jié)點連 接起來所構(gòu)成的網(wǎng)絡(luò)。 v 在拓?fù)渖?，互連網(wǎng)絡(luò)為輸入和輸出兩組節(jié)點之間 提供一組互連或映象。 2.1 系統(tǒng)互連網(wǎng)絡(luò)（續(xù)系統(tǒng)互連網(wǎng)絡(luò)（續(xù)1） v不同帶寬與距離的互連技術(shù): 總線、SAN、LAN、MAN、WAN 局 部 總 線 I/O 總 線 SCI HiPPI Myrinet 千 兆 位以 太 網(wǎng) 光 纖 通 道 快 速 以 太 網(wǎng) 以 太 網(wǎng) 10 Base T FDDI ATM 總 線 或 開 關(guān)SANLANMANWAN 100 Gb/s 10 Gb/s 1 Gb/s 100 Mb/s 10 Mb/sIsoEnet 網(wǎng)絡(luò)帶寬 交

3、叉 開 關(guān) MIN 或 100 Base T 2.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)系統(tǒng)互連網(wǎng)絡(luò)（續(xù)2） v 通信網(wǎng)絡(luò)通信網(wǎng)絡(luò)是多處理機性能發(fā)揮的瓶頸 主要方式：總線、交叉開關(guān)、多端口存貯器、開關(guān)樞紐 v 網(wǎng)絡(luò)參數(shù) 節(jié)點度（Node Degree）：射入或射出一個節(jié)點的邊數(shù)。在單向網(wǎng) 絡(luò)中，入射和出射邊之和稱為節(jié)點度。 網(wǎng)絡(luò)直徑（Network Diameter）： 網(wǎng)絡(luò)中任何兩個節(jié)點之間的最長 距離，即最大路徑數(shù)。 對剖寬度（Bisection Width） ：對分網(wǎng)絡(luò)各半所必須移去的最少邊 數(shù) 對剖帶寬（ Bisection Bandwidth）:每秒鐘內(nèi)，在最小的對剖平面上 通過所有連線的最大信息位（或

4、字節(jié)）數(shù) 如果從任一節(jié)點觀看網(wǎng)絡(luò)都一樣，則稱為對稱的（Symmetry） 2.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)系統(tǒng)互連網(wǎng)絡(luò)（續(xù)3） v靜態(tài)互連網(wǎng)絡(luò) 處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間， 這種點到點的鏈接保持不變；典型的靜態(tài)網(wǎng)絡(luò)有一維線 性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡(luò)、立方環(huán)、洗 牌交換網(wǎng)、蝶形網(wǎng)絡(luò)等 v動態(tài)網(wǎng)絡(luò) 用交換開關(guān)構(gòu)成的，可按應(yīng)用程序的要求動態(tài)地改變連 接組態(tài)；典型的動態(tài)網(wǎng)絡(luò)包括總線、交叉開關(guān)和多級互 連網(wǎng)絡(luò)等。 2.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)系統(tǒng)互連網(wǎng)絡(luò)（續(xù)4） v 例子：靜態(tài)互聯(lián)網(wǎng)絡(luò)中的二叉 樹 除了根、葉節(jié)點，每個內(nèi)節(jié)點只 與其父節(jié)點和兩個子節(jié)點相連。 節(jié)點度為3，對剖寬度為1.

5、如果盡量增大節(jié)點度，則直徑縮 小為2，此時就變成了星形網(wǎng)絡(luò). 傳統(tǒng)二叉樹的主要問題是根易成 為通信瓶頸。胖樹節(jié)點間的通路 自葉向根逐漸變寬。 網(wǎng)絡(luò)名稱網(wǎng)絡(luò)名稱網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)規(guī)模節(jié)點度節(jié)點度網(wǎng)絡(luò)直徑網(wǎng)絡(luò)直徑對剖寬對剖寬 度度 對稱對稱鏈路數(shù)鏈路數(shù) 線性陣列線性陣列21非非 環(huán)形環(huán)形2 （雙向）（雙向）2是是 2-D網(wǎng)孔網(wǎng)孔 4非非 Illiac網(wǎng)孔網(wǎng)孔 4非非 2-D環(huán)繞環(huán)繞4是是 二叉樹二叉樹31非非 星形星形2非非 超立方超立方 n n是是 立方環(huán)立方環(huán)3是是 N N N N NN NN NN n N2 k kN2 1N 1N 2/N ) 1(2N 1N 2/2N 1log2N 2/12kk

6、N N2 N2 2/N 2/N 1N N )(2NN N2 N2 1N 1N 2/nN 2/3N 2.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)系統(tǒng)互連網(wǎng)絡(luò)（續(xù)5） /(2 )Nk 靜態(tài)互連網(wǎng)絡(luò)特性比較靜態(tài)互連網(wǎng)絡(luò)特性比較 2.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)系統(tǒng)互連網(wǎng)絡(luò)（續(xù)6） v n,節(jié)點規(guī)模 w，數(shù)據(jù)寬度 動態(tài)互連網(wǎng)絡(luò)的復(fù)雜度和帶寬性能一覽表動態(tài)互連網(wǎng)絡(luò)的復(fù)雜度和帶寬性能一覽表 網(wǎng)絡(luò)特性網(wǎng)絡(luò)特性總線系統(tǒng)總線系統(tǒng)多級互連網(wǎng)絡(luò)多級互連網(wǎng)絡(luò)交叉開關(guān)交叉開關(guān) 硬件復(fù)雜度硬件復(fù)雜度 每個處理器帶寬每個處理器帶寬 )(wnO)log(wnnO k)( 2w nO )/(nwfO)(wfO )(wfO)(wfO 3 并行計算機系統(tǒng)模型并行

7、計算機系統(tǒng)模型 v并行計算機系統(tǒng)結(jié)構(gòu)分類 v并行計算機結(jié)構(gòu)模型 v并行計算機訪存模型 3.1 并行計算機系統(tǒng)結(jié)構(gòu)分類并行計算機系統(tǒng)結(jié)構(gòu)分類 vFlynn分類： SISD, SIMD, MIMD, MISD v結(jié)構(gòu)模型（MIMD） PVP, SMP, MPP, DSM, COW v訪存模型: UMA, NUMA, COMA, CC-NUMA, NORMA 3.1 并行計算機系統(tǒng)結(jié)構(gòu)分類（續(xù)并行計算機系統(tǒng)結(jié)構(gòu)分類（續(xù)1） 1966年年M.J.Flynn根據(jù)指令流根據(jù)指令流(Instruction Stream機器執(zhí)機器執(zhí) 行指令序列）、數(shù)據(jù)流行指令序列）、數(shù)據(jù)流(Data Stream指令流調(diào)用的

8、數(shù)據(jù)序列）、指令流調(diào)用的數(shù)據(jù)序列）、 多倍性多倍性(Multiplicity：在系統(tǒng)結(jié)構(gòu)的流程瓶頸上同時執(zhí)行的指：在系統(tǒng)結(jié)構(gòu)的流程瓶頸上同時執(zhí)行的指 令令or數(shù)據(jù)可能最大個數(shù)）將系統(tǒng)結(jié)構(gòu)分成：數(shù)據(jù)可能最大個數(shù)）將系統(tǒng)結(jié)構(gòu)分成： SISD (single instruction stream over a single data stream) SIMD (single instruction stream over multiple data stream) MIMD (multiple instruction streams over multiple data streams) MISD

9、(multiple instruction streams and a single data streams) 3.1 并行計算機系統(tǒng)結(jié)構(gòu)分類（續(xù)并行計算機系統(tǒng)結(jié)構(gòu)分類（續(xù)2） v 以以處理單元處理單元的作用為主的分類方法：的作用為主的分類方法： PVP 處理器是向量(Vector)處理器 SMP 任意處理器可直接訪問任意內(nèi)存地址（對稱） MPP 處理器與其他部件形成節(jié)點后再組成并行計算機 DSM 加上虛擬層，近似擁有SMP和MPP的優(yōu)點 CLUSTER 處理器與其他部件形成完整節(jié)點完整節(jié)點后再組成并行計算機 以上都是MIMD機器，此外還有專用的SIMD機器。 v 以以存儲單元存儲單元的作用

10、為主的分類方法：的作用為主的分類方法： UMA 存儲器均勻共享 NUMA 存儲器非均勻共享 COMA 只有緩存存儲器 CC-NUMA 通過緩存達(dá)到存儲器非均勻共享 NORMA 存儲器不共享 3.2 并行計算機結(jié)構(gòu)模型并行計算機結(jié)構(gòu)模型 v共享存儲對稱多處理機系統(tǒng)(SMP) 對稱式共享存儲對稱式共享存儲:任意處理器可直接 訪問任意內(nèi)存地址,且訪問延遲、帶 寬、幾率都是等價的; 系統(tǒng)是對稱的。 微處理器微處理器: 一般少于64個; 處理器不能太多, 總線和交叉 開關(guān)的一旦作成難于擴展； 例子例子: IBM R50, SGI Power Challenge, SUN Enterprise, 曙光一

11、號; 3.2 并行計算機結(jié)構(gòu)模型（續(xù)并行計算機結(jié)構(gòu)模型（續(xù)1） v 大規(guī)模并行計算機系統(tǒng)(MPP) 物理和邏輯上均是分布內(nèi)存 能擴展至成百上千個處理器(微處理 器或向量處理器) 采用高通信帶寬和低延遲的互聯(lián)網(wǎng) 絡(luò)(專門設(shè)計和定制的) 一種異步的一種異步的MIMD機器機器；程序系由 多個進(jìn)程組成，每個都有其私有地 址空間，進(jìn)程間采用傳遞消息相互 作用； 代表: CRAY T3E(2048), ASCI Red(3072), IBM SP2, 曙光1000 3.2 并行計算機結(jié)構(gòu)模型（續(xù)并行計算機結(jié)構(gòu)模型（續(xù)2） v分布共享存儲多處理機系統(tǒng)分布共享存儲多處理機系統(tǒng) (DSM) : 內(nèi)存模塊物理上局

12、部于各個處 理器內(nèi)部,但邏輯上(用戶)是共 享存儲的; 這種結(jié)構(gòu)也稱為基于Cache目 錄的非一致內(nèi)存訪問 (CCNUMA)結(jié)構(gòu); 局部與遠(yuǎn)程內(nèi)存訪問的延遲和 帶寬不一致,相差3-10倍 高性能并行程序設(shè)計注意; 3.2 并行計算機結(jié)構(gòu)模型（續(xù)并行計算機結(jié)構(gòu)模型（續(xù)3） v機群系統(tǒng)(Cluster) 每個節(jié)點都是一個完整的計 算機 各個節(jié)點通過高性能網(wǎng)絡(luò)相 互連接 網(wǎng)絡(luò)接口和I/O總線松耦合連 接 每個節(jié)點有完整的操作系統(tǒng) 曙光2000, 3000, ASCI Blue Mountain(48臺128-way DSM Origin 2000,6144個處 理器) 3.2 并行計算機結(jié)構(gòu)模型（續(xù)

13、并行計算機結(jié)構(gòu)模型（續(xù)4） 3.3 并行計算機訪存模型并行計算機訪存模型 v考慮存儲器層次：考慮存儲器層次： 高速緩存高速緩存 本地內(nèi)存本地內(nèi)存 v以以存儲單元存儲單元的作用為主的分類方法：的作用為主的分類方法： UMA 存儲器均勻共享 NUMA 存儲器非均勻共享 COMA 只有緩存存儲器 CC-NUMA 通過緩存達(dá)到存儲器非均勻共享 NORMA 存儲器不共享 3.3 并行計算機訪存模型（續(xù)并行計算機訪存模型（續(xù)1） vUMA（Uniform Memory Access）模型是均勻存儲訪問 模型的簡稱。其特點是： 物理存儲器被所有處理器均勻共享； 所有處理器訪問任何存儲字取相同的時間； 每臺處

14、理器可帶私有高速緩存； 外圍設(shè)備也可以一定形式共享。 由于對資源的高度共享,常稱緊耦合系統(tǒng)(tightly coupled system) 3.3 并行計算機訪存模型（續(xù)并行計算機訪存模型（續(xù)2） v對稱多處理機系統(tǒng)(SMP: symmetric multi- processor) 所有處理機都能同樣訪問所有外圍設(shè)備；所有處理機都 能同樣運行執(zhí)行程序，如操作系統(tǒng)的內(nèi)核、I/O服務(wù)程序 v不對稱處理機系統(tǒng)(asymmtric multi-processor) 只有一臺或一組處理機（MP主處理機）執(zhí)行操作系統(tǒng)并 操縱I/O，其余處理機（AP附屬處理機）沒有I/O能力 3.3 并行計算機訪存模型（續(xù)

15、并行計算機訪存模型（續(xù)3） v NUMA (Nonuniform Memory Access)模型是非均勻存儲訪問非均勻存儲訪問模 型的簡稱。 LM 1 P1 LM 2 P2 LM n Pn 互 連 網(wǎng) 絡(luò) (a)共享本地存儲模型 全局互連網(wǎng)絡(luò) (b)層次式機群模型 GSMGSMGSM P C I N CSM P P CSM CSM 群1 P C I N CSM 群N P P CSM CSM 3.3 并行計算機訪存模型（續(xù)并行計算機訪存模型（續(xù)4） vCOMA(Cache-Only Memory Access)模型是全高速緩存存儲訪全高速緩存存儲訪 問問的簡稱。其特點是： 各處理器節(jié)點中沒有存

16、儲層次結(jié)構(gòu)， 全部高速緩存組成了全局地址空間； 利用分布的高速緩存目錄分布的高速緩存目錄D進(jìn)行遠(yuǎn)程 高速緩存的訪問; COMA中的高速緩存容量一般都大于 2 級高速緩存容量； 使用COMA時，數(shù)據(jù)開始時可任意分 配，因為在運行時它最終會被遷移到 要用到它們的地方。 3.3 并行計算機訪存模型（續(xù)并行計算機訪存模型（續(xù)5） v CC-NUMA（Coherent-Cache Nonuniform Memory Access） 模型是高速緩存一致性非均勻存儲訪問高速緩存一致性非均勻存儲訪問模型的簡稱。其 特點是： 大多數(shù)使用基于目錄的高速緩存一致性協(xié)議基于目錄的高速緩存一致性協(xié)議； 保留SMP結(jié)構(gòu)易于編程的優(yōu)點，也改善常規(guī)SMP的可擴放性； CC-NUMA實際上是一個分布共享存儲分布共享存儲的DSM多處理機系統(tǒng)； 它最顯著的優(yōu)點是程序員無需明確地在節(jié)點上分配數(shù)據(jù)，系統(tǒng)的 硬件和軟件開始時自動在各節(jié)點分配數(shù)據(jù)，在運行期間，高速緩 存一致性硬件會自動地將數(shù)據(jù)遷移至要用到它的地方。 3.3 并行計算機訪存模型（續(xù)并行計算機訪存模型（續(xù)6） I/ONIC,DIR,RC 系統(tǒng)互連網(wǎng)路 MemP/CP/C I/ONIC,DIR,RC MemP/C