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

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

（3學(xué)時(shí)）二 并行編程軟件基礎(chǔ)

（3學(xué)時(shí)）三 多線程編程基礎(chǔ)

（2學(xué)時(shí)）四 Linux多線程編程

（2學(xué)時(shí)）五 Windows多線程編程

（3學(xué)時(shí)）六 OpenMP編程

（7學(xué)時(shí)）七 MPI編程

（4學(xué)時(shí)）八 其他編程語(yǔ)言和方法

（2學(xué)時(shí)）九 并行程序設(shè)計(jì)的應(yīng)用實(shí)例

（2學(xué)時(shí)）

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

接起來(lái)所構(gòu)成的網(wǎng)絡(luò)。在拓?fù)渖?，互連網(wǎng)絡(luò)為輸入和輸出兩組節(jié)點(diǎn)之間提供一組互連或映象。2023/2/452.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)1）不同帶寬與距離的互連技術(shù): 總線、SAN、LAN、MAN、WAN2023/2/462.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)2）通信網(wǎng)絡(luò)是多處理機(jī)性能發(fā)揮的瓶頸主要方式：總線、交叉開關(guān)、多端口存貯器、開關(guān)樞紐網(wǎng)絡(luò)參數(shù)節(jié)點(diǎn)度（NodeDegree）：射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)。在單向網(wǎng)絡(luò)中，入射和出射邊之和稱為節(jié)點(diǎn)度。網(wǎng)絡(luò)直徑（NetworkDiameter）：網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長(zhǎng)距離，即最大路徑數(shù)。對(duì)剖寬度（BisectionWidth）：對(duì)分網(wǎng)絡(luò)各半所必須移去的最少邊數(shù)對(duì)剖帶寬（BisectionBandwidth）:每秒鐘內(nèi)，在最小的對(duì)剖平面上通過(guò)所有連線的最大信息位（或字節(jié)）數(shù)如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱為對(duì)稱的（Symmetry）2023/2/472.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)3）靜態(tài)互連網(wǎng)絡(luò)處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點(diǎn)到點(diǎn)的鏈接保持不變；典型的靜態(tài)網(wǎng)絡(luò)有一維線性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡(luò)、立方環(huán)、洗牌交換網(wǎng)、蝶形網(wǎng)絡(luò)等動(dòng)態(tài)網(wǎng)絡(luò)用交換開關(guān)構(gòu)成的，可按應(yīng)用程序的要求動(dòng)態(tài)地改變連接組態(tài)；典型的動(dòng)態(tài)網(wǎng)絡(luò)包括總線、交叉開關(guān)和多級(jí)互連網(wǎng)絡(luò)等。2023/2/482.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)4）例子：靜態(tài)互聯(lián)網(wǎng)絡(luò)中的二叉樹除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連。節(jié)點(diǎn)度為3，對(duì)剖寬度為1.如果盡量增大節(jié)點(diǎn)度，則直徑縮小為2，此時(shí)就變成了星形網(wǎng)絡(luò).傳統(tǒng)二叉樹的主要問(wèn)題是根易成為通信瓶頸。胖樹節(jié)點(diǎn)間的通路自葉向根逐漸變寬。2023/2/49網(wǎng)絡(luò)名稱網(wǎng)絡(luò)規(guī)模節(jié)點(diǎn)度網(wǎng)絡(luò)直徑對(duì)剖寬度對(duì)稱鏈路數(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)絡(luò)（續(xù)5）靜態(tài)互連網(wǎng)絡(luò)特性比較2023/2/4102.1系統(tǒng)互連網(wǎng)絡(luò)（續(xù)6）n,節(jié)點(diǎn)規(guī)模w，數(shù)據(jù)寬度動(dòng)態(tài)互連網(wǎng)絡(luò)的復(fù)雜度和帶寬性能一覽表網(wǎng)絡(luò)特性總線系統(tǒng)多級(jí)互連網(wǎng)絡(luò)交叉開關(guān)硬件復(fù)雜度每個(gè)處理器帶寬～3并行計(jì)算機(jī)系統(tǒng)模型并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)分類并行計(jì)算機(jī)結(jié)構(gòu)模型并行計(jì)算機(jī)訪存模型2023/2/4112023/2/4123.1并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)分類Flynn分類：SISD,SIMD,MIMD,MISD結(jié)構(gòu)模型（MIMD）PVP,SMP,MPP,DSM,COW訪存模型:UMA,NUMA,COMA,CC-NUMA,NORMA2023/2/4133.1并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)分類（續(xù)1）1966年M.J.Flynn根據(jù)指令流(InstructionStream機(jī)器執(zhí)行指令序列）、數(shù)據(jù)流(DataStream指令流調(diào)用的數(shù)據(jù)序列）、多倍性(Multiplicity：在系統(tǒng)結(jié)構(gòu)的流程瓶頸上同時(shí)執(zhí)行的指令or數(shù)據(jù)可能最大個(gè)數(shù)）將系統(tǒng)結(jié)構(gòu)分成：SISD(singleinstructionstreamoverasingledatastream)SIMD(singleinstructionstreamovermultipledatastream)MIMD(multipleinstructionstreamsovermultipledatastreams)MISD(multipleinstructionstreamsandasingledatastreams)2023/2/4143.1并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)分類（續(xù)2）以處理單元的作用為主的分類方法：PVP處理器是向量(Vector)處理器SMP任意處理器可直接訪問(wèn)任意內(nèi)存地址（對(duì)稱）MPP處理器與其他部件形成節(jié)點(diǎn)后再組成并行計(jì)算機(jī)DSM加上虛擬層，近似擁有SMP和MPP的優(yōu)點(diǎn)CLUSTER處理器與其他部件形成完整節(jié)點(diǎn)后再組成并行計(jì)算機(jī)以上都是MIMD機(jī)器，此外還有專用的SIMD機(jī)器。以存儲(chǔ)單元的作用為主的分類方法：UMA存儲(chǔ)器均勻共享NUMA存儲(chǔ)器非均勻共享COMA只有緩存存儲(chǔ)器CC-NUMA通過(guò)緩存達(dá)到存儲(chǔ)器非均勻共享NORMA存儲(chǔ)器不共享2023/2/4153.2并行計(jì)算機(jī)結(jié)構(gòu)模型共享存儲(chǔ)對(duì)稱多處理機(jī)系統(tǒng)(SMP)對(duì)稱式共享存儲(chǔ):任意處理器可直接訪問(wèn)任意內(nèi)存地址,且訪問(wèn)延遲、帶寬、幾率都是等價(jià)的;系統(tǒng)是對(duì)稱的。微處理器:

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

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