第一章并行編程硬件基礎2

并行程序設計-22023/2/42內(nèi)容提要一 并行編程硬件基礎

（3學時）二 并行編程軟件基礎

（3學時）三 多線程編程基礎

（2學時）四 Linux多線程編程

（2學時）五 Windows多線程編程

（3學時）六 OpenMP編程

（7學時）七 MPI編程

（4學時）八 其他編程語言和方法

（2學時）九 并行程序設計的應用實例

（2學時）

1并行程序設計引言2并行計算機系統(tǒng)互聯(lián)3并行計算機系統(tǒng)模型（本節(jié)課內(nèi)容）4多核技術一、 并行編程硬件基礎2023/2/432023/2/442并行計算機系統(tǒng)互連網(wǎng)絡互連網(wǎng)絡是將集中式系統(tǒng)或分布式系統(tǒng)中的節(jié)點連

接起來所構成的網(wǎng)絡。在拓撲上，互連網(wǎng)絡為輸入和輸出兩組節(jié)點之間提供一組互連或映象。2023/2/452.1系統(tǒng)互連網(wǎng)絡（續(xù)1）不同帶寬與距離的互連技術: 總線、SAN、LAN、MAN、WAN2023/2/462.1系統(tǒng)互連網(wǎng)絡（續(xù)2）通信網(wǎng)絡是多處理機性能發(fā)揮的瓶頸主要方式：總線、交叉開關、多端口存貯器、開關樞紐網(wǎng)絡參數(shù)節(jié)點度（NodeDegree）：射入或射出一個節(jié)點的邊數(shù)。在單向網(wǎng)絡中，入射和出射邊之和稱為節(jié)點度。網(wǎng)絡直徑（NetworkDiameter）：網(wǎng)絡中任何兩個節(jié)點之間的最長距離，即最大路徑數(shù)。對剖寬度（BisectionWidth）：對分網(wǎng)絡各半所必須移去的最少邊數(shù)對剖帶寬（BisectionBandwidth）:每秒鐘內(nèi)，在最小的對剖平面上通過所有連線的最大信息位（或字節(jié)）數(shù)如果從任一節(jié)點觀看網(wǎng)絡都一樣，則稱為對稱的（Symmetry）2023/2/472.1系統(tǒng)互連網(wǎng)絡（續(xù)3）靜態(tài)互連網(wǎng)絡處理單元間有著固定連接的一類網(wǎng)絡，在程序執(zhí)行期間，這種點到點的鏈接保持不變；典型的靜態(tài)網(wǎng)絡有一維線性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡、立方環(huán)、洗牌交換網(wǎng)、蝶形網(wǎng)絡等動態(tài)網(wǎng)絡用交換開關構成的，可按應用程序的要求動態(tài)地改變連接組態(tài)；典型的動態(tài)網(wǎng)絡包括總線、交叉開關和多級互連網(wǎng)絡等。2023/2/482.1系統(tǒng)互連網(wǎng)絡（續(xù)4）例子：靜態(tài)互聯(lián)網(wǎng)絡中的二叉樹除了根、葉節(jié)點，每個內(nèi)節(jié)點只與其父節(jié)點和兩個子節(jié)點相連。節(jié)點度為3，對剖寬度為1.如果盡量增大節(jié)點度，則直徑縮小為2，此時就變成了星形網(wǎng)絡.傳統(tǒng)二叉樹的主要問題是根易成為通信瓶頸。胖樹節(jié)點間的通路自葉向根逐漸變寬。2023/2/49網(wǎng)絡名稱網(wǎng)絡規(guī)模節(jié)點度網(wǎng)絡直徑對剖寬度對稱鏈路數(shù)線性陣列21非環(huán)形2（雙向）2是2-D網(wǎng)孔

4非Illiac網(wǎng)孔

4非2-D環(huán)繞4是二叉樹31非星形2非超立方

nn是立方環(huán)3是2.1系統(tǒng)互連網(wǎng)絡（續(xù)5）靜態(tài)互連網(wǎng)絡特性比較2023/2/4102.1系統(tǒng)互連網(wǎng)絡（續(xù)6）n,節(jié)點規(guī)模w，數(shù)據(jù)寬度動態(tài)互連網(wǎng)絡的復雜度和帶寬性能一覽表網(wǎng)絡特性總線系統(tǒng)多級互連網(wǎng)絡交叉開關硬件復雜度每個處理器帶寬～3并行計算機系統(tǒng)模型并行計算機系統(tǒng)結構分類并行計算機結構模型并行計算機訪存模型2023/2/4112023/2/4123.1并行計算機系統(tǒng)結構分類Flynn分類：SISD,SIMD,MIMD,MISD結構模型（MIMD）PVP,SMP,MPP,DSM,COW訪存模型:UMA,NUMA,COMA,CC-NUMA,NORMA2023/2/4133.1并行計算機系統(tǒng)結構分類（續(xù)1）1966年M.J.Flynn根據(jù)指令流(InstructionStream機器執(zhí)行指令序列）、數(shù)據(jù)流(DataStream指令流調用的數(shù)據(jù)序列）、多倍性(Multiplicity：在系統(tǒng)結構的流程瓶頸上同時執(zhí)行的指令or數(shù)據(jù)可能最大個數(shù)）將系統(tǒng)結構分成：SISD(singleinstructionstreamoverasingledatastream)SIMD(singleinstructionstreamovermultipledatastream)MIMD(multipleinstructionstreamsovermultipledatastreams)MISD(multipleinstructionstreamsandasingledatastreams)2023/2/4143.1并行計算機系統(tǒng)結構分類（續(xù)2）以處理單元的作用為主的分類方法：PVP處理器是向量(Vector)處理器SMP任意處理器可直接訪問任意內(nèi)存地址（對稱）MPP處理器與其他部件形成節(jié)點后再組成并行計算機DSM加上虛擬層，近似擁有SMP和MPP的優(yōu)點CLUSTER處理器與其他部件形成完整節(jié)點后再組成并行計算機以上都是MIMD機器，此外還有專用的SIMD機器。以存儲單元的作用為主的分類方法：UMA存儲器均勻共享NUMA存儲器非均勻共享COMA只有緩存存儲器CC-NUMA通過緩存達到存儲器非均勻共享NORMA存儲器不共享2023/2/4153.2并行計算機結構模型共享存儲對稱多處理機系統(tǒng)(SMP)對稱式共享存儲:任意處理器可直接訪問任意內(nèi)存地址,且訪問延遲、帶寬、幾率都是等價的;系統(tǒng)是對稱的。微處理器:

一般少于64個;處理器不能太多,總線和交叉開關的一旦作成難于擴展；例子:IBMR50,SGIPowerChallenge,SUNEnterprise,曙光一號;2023/2/4163.2并行計算機結構模型（續(xù)1）大規(guī)模并行計算機系統(tǒng)(MPP)物理和邏輯上均是分布內(nèi)存能擴展至成百上千個處理器(微處理器或向量處理器)采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(專門設計和定制的)一種異步的MIMD機器；程序系由多個進程組成，每個都有其私有地址空間，進程間采用傳遞消息相互作用；代表:CRAYT3E(2048),ASCIRed(3072),IBMSP2,曙光10002023/2/4173.2并行計算機結構模型（續(xù)2）分布共享存儲多處理機系統(tǒng)(DSM):內(nèi)存模塊物理上局部于各個處理器內(nèi)部,但邏輯上(用戶)是共享存儲的;這種結構也稱為基于Cache目錄的非一致內(nèi)存訪問(CCNUMA)結構;局部與遠程內(nèi)存訪問的延遲和帶寬不一致,相差3-10倍－》高性能并行程序設計注意;2023/2/4183.2并行計算機結構模型（續(xù)3）機群系統(tǒng)(Cluster)每個節(jié)點都是一個完整的計算機各個節(jié)點通過高性能網(wǎng)絡相互連接網(wǎng)絡接口和I/O總線松耦合連接每個節(jié)點有完整的操作系統(tǒng)曙光2000,3000,ASCIBlueMountain(48臺128-wayDSMOrigin2000,6144個處理器)2023/2/4193.2并行計算機結構模型（續(xù)4）2023/2/4203.3并行計算機訪存模型考慮存儲器層次：高速緩存本地內(nèi)存以存儲單元的作用為主的分類方法：UMA存儲器均勻共享NUMA存儲器非均勻共享COMA只有緩存存儲器CC-NUMA通過緩存達到存儲器非均勻共享NORMA存儲器不共享2023/2/4213.3并行計算機訪存模型（續(xù)1）UMA（UniformMemoryAccess）模型是均勻存儲訪問模型的簡稱。其特點是：物理存儲器被所有處理器均勻共享；所有處理器訪問任何存儲字取相同的時間；每臺處理器可帶私有高速緩存；外圍設備也可以一定形式共享。由于對資源的高度共享,常稱緊耦合系統(tǒng)(tightlycoupledsystem)2023/2/4223.3并行計算機訪存模型（續(xù)2）對稱多處理機系統(tǒng)(SMP:symmetricmulti-processor)所有處理機都能同樣訪問所有外圍設備；所有處理機都能同樣運行執(zhí)行程序，如操作系統(tǒng)的內(nèi)核、I/O服務程序不對稱處理機系統(tǒng)(asymmtricmulti-processor)只有一臺或一組處理機（MP主處理機）執(zhí)行操作系統(tǒng)并操縱I/O，其余處理機（AP附屬處理機）沒有I/O能力2023/2/4233.3并行計算機訪存模型（續(xù)3）NUMA(NonuniformMemoryAccess)模型是非均勻存儲訪問模型的簡稱。LM1P1LM2P2LMnPn互連網(wǎng)絡(a)共享本地存儲模型全局互連網(wǎng)絡(b)層次式機群模型GSMGSMGSM…………PCINCSMPPCSMCSM群1……PCINCSM群NPPCSMCSM……2023/2/4243.3并行計算機訪存模型（續(xù)4）COMA(Cache-OnlyMemoryAccess)模型是全高速緩存存儲訪問的簡稱。其特點是：各處理器節(jié)點中沒有存儲層次結構，全部高速緩存組成了全局地址空間；利用分布的高速緩存目錄D進行遠程高速緩存的訪問;COMA中的高速緩存容量一般都大于2級高速緩存容量；使用COMA時，數(shù)據(jù)開始時可任意分配，因為在運行時它最終會被遷移到要用到它們的地方。

2023/2/4253.3并行計算機訪存模型（續(xù)5）CC-NUMA（Coherent-CacheNonuniformMemoryAccess）模型是高速緩存一致性非均勻存儲訪問模型的簡稱。其特點是：大多數(shù)使用基于目錄的高速緩存一致性協(xié)議；保留SMP結構易于編程的優(yōu)點，也改善常規(guī)SMP的可擴放性；CC-NUMA實際上是一個分布共享存儲的DSM多處理機系統(tǒng)；它最顯著的優(yōu)點是程序員無需明確地在節(jié)點上分配數(shù)據(jù)，系統(tǒng)的硬件和軟件開始時