體系結(jié)構(gòu)與并行基礎(chǔ)

1、體系結(jié)構(gòu)與并行基礎(chǔ)趙永華中科院計(jì)算機(jī)網(wǎng)絡(luò)信息中心超級(jí)計(jì)算中心11:052 并行機(jī)體系結(jié)構(gòu)并行機(jī)體系結(jié)構(gòu)并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)分類11:053n Flynn分類：（instruction/data stream ）SISD（單指令單數(shù)據(jù)）,SIMD（單指令多數(shù)據(jù)）, MIMD, MISDn 結(jié)構(gòu)模型分類：PVP（并行向量機(jī)）, SMP（共享內(nèi)存）,MPP（大規(guī)模并行計(jì)算機(jī)）,DSM（分布共享內(nèi)存）,COW（集群）n 訪存模型分類：UMA(Uniform Memory-access，均勻存儲(chǔ)訪問模型) NUMA(non-UMA）COMA（Cache-Only Memory Architecture，全

2、高速緩存內(nèi)存體系結(jié)構(gòu)） CC-NUMA(Cache-Coherent0一致性高速緩存非均勻存儲(chǔ)訪問模型), NORMA（No-Romate Memory Access 非遠(yuǎn)程存儲(chǔ)訪問模型）結(jié)構(gòu)模型共享內(nèi)存/對(duì)稱多處理機(jī)系統(tǒng)(SMP)n PVPPVP：并行向量機(jī)：并行向量機(jī) 單地址空間單地址空間 共享存儲(chǔ)共享存儲(chǔ) UMA(UMA( Uniform Memory AccessUniform Memory Access) )n SMPSMP：共享內(nèi)存并行機(jī)（：共享內(nèi)存并行機(jī)（ Shared Memory Shared Memory Processors Processors ）。多個(gè)處理器通過交叉開

3、關(guān)）。多個(gè)處理器通過交叉開關(guān)（CrossbarCrossbar）或總線與共享內(nèi)存互連。）或總線與共享內(nèi)存互連。任意處理器可直接訪問任意內(nèi)存地址任意處理器可直接訪問任意內(nèi)存地址, ,且訪問且訪問延遲、帶寬、幾率都是等價(jià)的延遲、帶寬、幾率都是等價(jià)的; ; 系統(tǒng)是對(duì)稱的；系統(tǒng)是對(duì)稱的；單地址空間單地址空間 、共享存儲(chǔ)、共享存儲(chǔ)、UMAUMA；并行編程方式并行編程方式: : 通常采用通常采用OpenMP, OpenMP, 也可使用消也可使用消息傳遞息傳遞(MPI/PVM) (MPI/PVM) 及及HPFHPF。SGISGI Power Challenge , Dawning 1 Power Chall

4、enge , Dawning 1 11:055MPP：大規(guī)模并行計(jì)算機(jī)系統(tǒng)n MPP:MPP:大規(guī)模并行計(jì)算機(jī)系統(tǒng)大規(guī)模并行計(jì)算機(jī)系統(tǒng)(Massively (Massively Parallel Processors)Parallel Processors)。由大量具有局部內(nèi)由大量具有局部內(nèi)存的計(jì)算結(jié)點(diǎn)通過高速系統(tǒng)網(wǎng)絡(luò)聯(lián)接而存的計(jì)算結(jié)點(diǎn)通過高速系統(tǒng)網(wǎng)絡(luò)聯(lián)接而構(gòu)成的并行處理系統(tǒng)構(gòu)成的并行處理系統(tǒng). . MPP MPP 系統(tǒng)的系統(tǒng)網(wǎng)絡(luò)通常具有某種拓?fù)湎到y(tǒng)的系統(tǒng)網(wǎng)絡(luò)通常具有某種拓?fù)浣Y(jié)構(gòu)結(jié)構(gòu)( (如如tree, mesh, torus, hypercube).tree, mesh, torus, hy

5、percube).物理和邏輯上均是分布內(nèi)存物理和邏輯上均是分布內(nèi)存采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(luò)采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(luò) ( (專專門設(shè)計(jì)和定制的門設(shè)計(jì)和定制的) )NORMANORMA或或CC-NUMACC-NUMA代表代表:CRAY T3E(2048), ASCI Red(3072), :CRAY T3E(2048), ASCI Red(3072), IBM SP2, IBM SP2, 曙光曙光1000100011:056DSM：分布共享存儲(chǔ)多處理機(jī)系統(tǒng)n DSMDSM： 分布共享存貯并行機(jī)（分布共享存貯并行機(jī)（Distributed Distributed Shared Mem

6、oryShared Memory），由結(jié)點(diǎn)（一般是），由結(jié)點(diǎn)（一般是SMPSMP系系統(tǒng)）通過高速消息傳遞網(wǎng)絡(luò)互連而成。存貯統(tǒng)）通過高速消息傳遞網(wǎng)絡(luò)互連而成。存貯系統(tǒng)在物理上分布、邏輯上共享。各結(jié)點(diǎn)有系統(tǒng)在物理上分布、邏輯上共享。各結(jié)點(diǎn)有自己獨(dú)立的尋址空間。自己獨(dú)立的尋址空間。單地址空間單地址空間 、分布共享、分布共享NUMANUMA（ NonuniformNonuniform Memory Access Memory Access ）與與SMPSMP的主要區(qū)別：的主要區(qū)別：DSMDSM在物理上有分布在各在物理上有分布在各個(gè)節(jié)點(diǎn)的局部內(nèi)存從而形成一個(gè)共享的存儲(chǔ)個(gè)節(jié)點(diǎn)的局部內(nèi)存從而形成一個(gè)共享的存

7、儲(chǔ)器；器；代表代表: SGI Origin 2000, Cray T3D: SGI Origin 2000, Cray T3D 11:057Cluster：機(jī)群系統(tǒng)nCluster(Now,Cow)Cluster(Now,Cow)： 群集系統(tǒng)。將單個(gè)節(jié)點(diǎn)，用商業(yè)網(wǎng)群集系統(tǒng)。將單個(gè)節(jié)點(diǎn)，用商業(yè)網(wǎng)絡(luò)絡(luò) ：EthernetEthernet，MyrinetMyrinet，QuadricsQuadrics，InfinibandInfiniband，SwitchSwitch等連結(jié)起來形成群等連結(jié)起來形成群集系統(tǒng)。集系統(tǒng)。 每個(gè)節(jié)點(diǎn)都是一個(gè)完整的計(jì)算機(jī)每個(gè)節(jié)點(diǎn)都是一個(gè)完整的計(jì)算機(jī)（SMPSMP或或DSMDS

8、M），有自己磁盤和操），有自己磁盤和操作系統(tǒng)作系統(tǒng)各個(gè)節(jié)點(diǎn)通過高性能網(wǎng)絡(luò)相互連接各個(gè)節(jié)點(diǎn)通過高性能網(wǎng)絡(luò)相互連接網(wǎng)絡(luò)接口和網(wǎng)絡(luò)接口和I/OI/O總線松耦合連接總線松耦合連接每個(gè)節(jié)點(diǎn)有完整的操作系統(tǒng)每個(gè)節(jié)點(diǎn)有完整的操作系統(tǒng)多地址空間、分布非共享、多地址空間、分布非共享、NORMANORMA通用性、可擴(kuò)展性好，性價(jià)比高通用性、可擴(kuò)展性好，性價(jià)比高11:058訪存模型 11:059UMANORMANUMA:多處理機(jī)（單地址空間共享存儲(chǔ)器）多處理機(jī)（單地址空間共享存儲(chǔ)器） UMA: Uniform Memory Access NUMA: Nonuniform Memory Access多計(jì)算機(jī)（多地址空

9、間非共享存儲(chǔ)器）多計(jì)算機(jī)（多地址空間非共享存儲(chǔ)器） NORMA:No-Remote Memory Access最新的TOP500計(jì)算機(jī)11:051011:0511最新的TOP500計(jì)算機(jī) 來自Cray的美洲豹“Jaguar”，憑借1.75 PFlop/s(每秒1750萬億次)的計(jì)算能力傲視群雄。“Jaguar”采用了224162個(gè)處理器核心來自中國的曙光“星云”系統(tǒng)以1271萬億次/s的峰值速度名列第二采用了自主設(shè)計(jì)的HPP體系結(jié)構(gòu)、高效異構(gòu)協(xié)同計(jì)算技術(shù)處理器是32nm工藝的六核至強(qiáng)X5650，并且采用了Nvidia Tesla C2050 GPU做協(xié)處理的用戶編程環(huán)境；異構(gòu)體系結(jié)構(gòu) 專用 通

10、用 TOP500中85%的系統(tǒng)采用了四核處理器，而有5%的系統(tǒng)已經(jīng)使用了六核或者更多核的處理器。 11:0512并行編程基礎(chǔ)11:0513并行計(jì)算軟件環(huán)境n操作系統(tǒng)：UNIX、LINUX等 n通信庫：MPI 、PVMn數(shù)學(xué)庫：如MKL，ScaLAPACK等n編譯器：GNU Compiler自由軟件，持C/C+、Fortran77等語言高性能計(jì)算中常用的：C/C+：GCC (GNU C/C+ Compiler)Fortran ：gfortran;Intel Compiler由Intel公司針對(duì)Intel處理器開發(fā),支持Linux、Windows支持C/C+（icc，mpicc：Intel C/C

11、+ Compiler）、Fortran77/90/95（ifc： Intel Fortran Compiler)支持多線程和OpenMP14并行程序設(shè)計(jì)方法n隱式并行程序設(shè)計(jì)：隱式并行程序設(shè)計(jì)：常用傳統(tǒng)的語言編程成順序源編碼，把“并行”交給編譯器實(shí)現(xiàn)自動(dòng)并行程序的自動(dòng)并行化是一個(gè)理想目標(biāo)，存在難以克服的困難語言容易，編譯器難n顯式并行程序設(shè)計(jì)：顯式并行程序設(shè)計(jì)：在用戶程序中出現(xiàn)“并行”的調(diào)度語句顯式并行是目前有效的并行程序設(shè)計(jì)方法。例如通過消息傳遞方式或多線程等語言難，編譯器容易11:0515并行程序編程模型n隱式并行（Implicit Parallel）n數(shù)據(jù)并行（Data Parallel

12、）n共享變量（Shared Variable）n消息傳遞（Message Passing）11:0516隱式并行(Implicit Parallel)n概況：概況：程序員用熟悉的串行語言編寫相應(yīng)的串行程序通過編譯器和運(yùn)行支持系統(tǒng)將串行程序自動(dòng)轉(zhuǎn)化為并行代碼n特點(diǎn)：特點(diǎn)：語義簡單可移植性好單線程，易于調(diào)試和驗(yàn)證正確性細(xì)粒度并行效率很低11:0517數(shù)據(jù)并行（Data Parallel）n概況：概況：SIMD的自然模型局部計(jì)算和數(shù)據(jù)選路操作例：HPFn特點(diǎn)：特點(diǎn)：單線程并行操作于聚合數(shù)據(jù)結(jié)構(gòu)（數(shù)組）松散同步單一地址空間隱式交互作用顯式數(shù)據(jù)分布n優(yōu)點(diǎn)優(yōu)點(diǎn):編程相對(duì)簡單,串并行程序一致.n缺點(diǎn)缺點(diǎn):程

13、序的性能在很大程度上依賴于所用的編譯系統(tǒng)及用戶對(duì)編譯系統(tǒng)的了解. 并行粒度局限于數(shù)據(jù)級(jí)并行,粒度較小.18共享變量(Shared Variable)概況：PVP, SMP, DSM的自然模型特點(diǎn)：多線程：SPMD, MPMD異步單一地址空間顯式同步隱式數(shù)據(jù)分布隱式通信典型代表：OpenMP19消息傳遞(Message Passing）概況：MPP、COW的自然模型特點(diǎn)：多進(jìn)程異步并行多地址空間顯式同步顯式數(shù)據(jù)映射和負(fù)載分配顯式通信典型代表MPI、PVM20并行編程模型標(biāo)準(zhǔn)n所有并行編程模型標(biāo)準(zhǔn)可分為以下三類所有并行編程模型標(biāo)準(zhǔn)可分為以下三類:u數(shù)據(jù)并行HPF, Fortran90用于SMP,

14、DSMu共享編程OpenMP用于SMP, DSMu消息傳遞MPI, PVM用于所有并行計(jì)算機(jī)n三者可混合使用三者可混合使用:u如對(duì)以SMP為節(jié)點(diǎn)的Cluster來說, 可以在節(jié)點(diǎn)間進(jìn)行消息傳遞,在節(jié)點(diǎn)內(nèi)進(jìn)行共享變量編程.21基本并行化方法n相并行（相并行（Phase ParallelPhase Parallel）n流水線并行（流水線并行（Pipeline ParallelPipeline Parallel）n主從并行（主從并行（Master-Slave ParallelMaster-Slave Parallel）n分治并行（分治并行（Divide and Conquer ParallelDiv

15、ide and Conquer Parallel）n工作池并行（工作池并行（Work Pool ParallelWork Pool Parallel）11:0522加速比性能定律 并行系統(tǒng)的加速比簡單的說就是指對(duì)于一個(gè)給定的應(yīng)用，并行算法或并行程序的執(zhí)行速度相對(duì)于串行算法或串行程序的執(zhí)行速度加快了多少倍（既Sp=T1/Tp）三種加速比性能定律：Amdahl定律：適用固定計(jì)算負(fù)載 S=（Ws+Wp）/（Ws+Wp/p）Gustafson定律：適用于可擴(kuò)放問題 S=（Ws+pWp）/（Ws+Wp）Sun和Ni定律：受限于存儲(chǔ)器 其中： P ： 處理器數(shù) W ：問題規(guī)模 Ws：問題中的串行分量 Wp

16、：并行分量 WWsWp S ：加速比 S=穿行并行時(shí)間 f：串行分量的比率 fWs/W11:0523可擴(kuò)展性與評(píng)測(cè)標(biāo)準(zhǔn)（一）n可擴(kuò)展性(Scalability): 確定的應(yīng)用背景下，計(jì)算系統(tǒng)(算法或程序等)的性能隨著處理器的數(shù)目的增加而按比例提高的能力n總是將并行算法和體系結(jié)構(gòu)一并考慮算法的可擴(kuò)放性: 該算法針對(duì)某一特定機(jī)器的可擴(kuò)放性體系結(jié)構(gòu)的可擴(kuò)放性: 該體系結(jié)構(gòu)的機(jī)器的某一并行算法的可擴(kuò)放性n一般情況下，增加處理器數(shù)，會(huì)增加額外開銷和降低處理器利用率；所以對(duì)于一個(gè)特定的并行系統(tǒng)、并行算法或并行程序，它們能否有效的利用不斷增加的處理器的能力應(yīng)是受限的n目的：確定某類問題用哪種并行算法與哪種并行體系結(jié)構(gòu)結(jié)合。根據(jù)在小規(guī)模機(jī)器上的運(yùn)行性能，預(yù)測(cè)在大規(guī)模機(jī)器上的性能對(duì)固定的問題規(guī)模，確定最有效的處理機(jī)數(shù)和加速比指導(dǎo)改進(jìn)算法、體系結(jié)構(gòu)，以利用可擴(kuò)充的大量處理器11:0524可擴(kuò)展性與評(píng)測(cè)標(biāo)準(zhǔn)（二）等效率度量標(biāo)準(zhǔn): 若問題規(guī)模w不變，隨著處理器數(shù)P的增加會(huì)導(dǎo)致開銷To隨之增加，效率E下降。為了保持E不變，則在增加p的同時(shí)相應(yīng)的增加問題規(guī)模W，以抵消由于p增加而導(dǎo)致的T