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

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

2、A(Cache-Coherent0一致性高速緩存非均勻存儲(chǔ)訪問模型), NORMA（No-Romate Memory Access 非遠(yuǎn)程存儲(chǔ)訪問模型）結(jié)構(gòu)模型共享內(nèi)存/對(duì)稱多處理機(jī)系統(tǒng)(SMP) PVP：并行向量機(jī) 單地址空間 共享存儲(chǔ) UMA( Uniform Memory Access) SMP：共享內(nèi)存并行機(jī)（ Shared Memory Processors ）。多個(gè)處理器通過交叉開關(guān)（Crossbar）或總線與共享內(nèi)存互連。任意處理器可直接訪問任意內(nèi)存地址,且訪問延遲、帶寬、幾率都是等價(jià)的; 系統(tǒng)是對(duì)稱的；單地址空間 、共享存儲(chǔ)、UMA；并行編程方式: 通常采用OpenMP, 也可

3、使用消息傳遞(MPI/PVM) 及HPF。SGI Power Challenge , Dawning 1 *5MPP：大規(guī)模并行計(jì)算機(jī)系統(tǒng) MPP:大規(guī)模并行計(jì)算機(jī)系統(tǒng)(Massively Parallel Processors)。由大量具有局部內(nèi)存的計(jì)算結(jié)點(diǎn)通過高速系統(tǒng)網(wǎng)絡(luò)聯(lián)接而構(gòu)成的并行處理系統(tǒng). MPP 系統(tǒng)的系統(tǒng)網(wǎng)絡(luò)通常具有某種拓?fù)浣Y(jié)構(gòu)(如tree, mesh, torus, hypercube).物理和邏輯上均是分布內(nèi)存采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(luò) (專門設(shè)計(jì)和定制的)NORMA或CC-NUMA代表:CRAY T3E(2048), ASCI Red(3072), IBM SP2,

4、 曙光1000*6DSM：分布共享存儲(chǔ)多處理機(jī)系統(tǒng) DSM： 分布共享存貯并行機(jī)（Distributed Shared Memory），由結(jié)點(diǎn)（一般是SMP系統(tǒng)）通過高速消息傳遞網(wǎng)絡(luò)互連而成。存貯系統(tǒng)在物理上分布、邏輯上共享。各結(jié)點(diǎn)有自己獨(dú)立的尋址空間。單地址空間 、分布共享NUMA（ Nonuniform Memory Access ）與SMP的主要區(qū)別：DSM在物理上有分布在各個(gè)節(jié)點(diǎn)的局部內(nèi)存從而形成一個(gè)共享的存儲(chǔ)器；代表: SGI Origin 2000, Cray T3D *7Cluster：機(jī)群系統(tǒng)Cluster(Now,Cow)： 群集系統(tǒng)。將單個(gè)節(jié)點(diǎn)，用商業(yè)網(wǎng)絡(luò) ：Etherne

5、t，Myrinet，Quadrics，Infiniband，Switch等連結(jié)起來形成群集系統(tǒng)。 每個(gè)節(jié)點(diǎn)都是一個(gè)完整的計(jì)算機(jī)（SMP或DSM），有自己磁盤和操作系統(tǒng)各個(gè)節(jié)點(diǎn)通過高性能網(wǎng)絡(luò)相互連接網(wǎng)絡(luò)接口和I/O總線松耦合連接每個(gè)節(jié)點(diǎn)有完整的操作系統(tǒng)多地址空間、分布非共享、NORMA通用性、可擴(kuò)展性好，性價(jià)比高*8訪存模型 *9UMANORMANUMA:多處理機(jī)（單地址空間共享存儲(chǔ)器） UMA: Uniform Memory Access NUMA: Nonuniform Memory Access多計(jì)算機(jī)（多地址空間非共享存儲(chǔ)器） NORMA:No-Remote Memory Access最

6、新的TOP500計(jì)算機(jī)*10*11最新的TOP500計(jì)算機(jī) 來自Cray的美洲豹“Jaguar”，憑借1.75 PFlop/s(每秒1750萬億次)的計(jì)算能力傲視群雄?！癑aguar”采用了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) 專用 通用 TOP500中85%的系統(tǒng)采用了四核處理器，而有5%的系統(tǒng)已經(jīng)使用了六核或者更多核的處理器。 *12并行編程基礎(chǔ)*13并行計(jì)

7、算軟件環(huán)境操作系統(tǒng)：UNIX、LINUX等 通信庫：MPI 、PVM數(shù)學(xué)庫：如MKL，ScaLAPACK等編譯器：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+ Compiler）、Fortran77/90/95（ifc： Intel Fortran Compiler)支持多線程和OpenMP14并行程序設(shè)計(jì)

8、方法隱式并行程序設(shè)計(jì)：常用傳統(tǒng)的語言編程成順序源編碼，把“并行”交給編譯器實(shí)現(xiàn)自動(dòng)并行程序的自動(dòng)并行化是一個(gè)理想目標(biāo)，存在難以克服的困難語言容易，編譯器難顯式并行程序設(shè)計(jì)：在用戶程序中出現(xiàn)“并行”的調(diào)度語句顯式并行是目前有效的并行程序設(shè)計(jì)方法。例如通過消息傳遞方式或多線程等語言難，編譯器容易*15并行程序編程模型隱式并行（Implicit Parallel）數(shù)據(jù)并行（Data Parallel）共享變量（Shared Variable）消息傳遞（Message Passing）*16隱式并行(Implicit Parallel)概況：程序員用熟悉的串行語言編寫相應(yīng)的串行程序通過編譯器和運(yùn)行支持

9、系統(tǒng)將串行程序自動(dòng)轉(zhuǎn)化為并行代碼特點(diǎn)：語義簡單可移植性好單線程，易于調(diào)試和驗(yàn)證正確性細(xì)粒度并行效率很低*17數(shù)據(jù)并行（Data Parallel）概況：SIMD的自然模型局部計(jì)算和數(shù)據(jù)選路操作例：HPF特點(diǎn)：單線程并行操作于聚合數(shù)據(jù)結(jié)構(gòu)（數(shù)組）松散同步單一地址空間隱式交互作用顯式數(shù)據(jù)分布優(yōu)點(diǎn):編程相對(duì)簡單,串并行程序一致.缺點(diǎn):程序的性能在很大程度上依賴于所用的編譯系統(tǒng)及用戶對(duì)編譯系統(tǒng)的了解. 并行粒度局限于數(shù)據(jù)級(jí)并行,粒度較小.18共享變量(Shared Variable)概況：PVP, SMP, DSM的自然模型特點(diǎn)：多線程：SPMD, MPMD異步單一地址空間顯式同步隱式數(shù)據(jù)分布隱式通信

10、典型代表：OpenMP19消息傳遞(Message Passing）概況：MPP、COW的自然模型特點(diǎn)：多進(jìn)程異步并行多地址空間顯式同步顯式數(shù)據(jù)映射和負(fù)載分配顯式通信典型代表MPI、PVM20并行編程模型標(biāo)準(zhǔn)所有并行編程模型標(biāo)準(zhǔn)可分為以下三類:數(shù)據(jù)并行HPF, Fortran90用于SMP, DSM共享編程OpenMP用于SMP, DSM消息傳遞MPI, PVM用于所有并行計(jì)算機(jī)三者可混合使用:如對(duì)以SMP為節(jié)點(diǎn)的Cluster來說, 可以在節(jié)點(diǎn)間進(jìn)行消息傳遞,在節(jié)點(diǎn)內(nèi)進(jìn)行共享變量編程.21基本并行化方法相并行（Phase Parallel）流水線并行（Pipeline Parallel）主從

11、并行（Master-Slave Parallel）分治并行（Divide and Conquer Parallel）工作池并行（Work Pool Parallel）*22加速比性能定律 并行系統(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：問題中的串行分

12、量 Wp：并行分量 WWsWp S ：加速比 S=穿行并行時(shí)間 f：串行分量的比率 fWs/W*23可擴(kuò)展性與評(píng)測(cè)標(biāo)準(zhǔn)（一）可擴(kuò)展性(Scalability): 確定的應(yīng)用背景下，計(jì)算系統(tǒng)(算法或程序等)的性能隨著處理器的數(shù)目的增加而按比例提高的能力總是將并行算法和體系結(jié)構(gòu)一并考慮算法的可擴(kuò)放性: 該算法針對(duì)某一特定機(jī)器的可擴(kuò)放性體系結(jié)構(gòu)的可擴(kuò)放性: 該體系結(jié)構(gòu)的機(jī)器的某一并行算法的可擴(kuò)放性一般情況下，增加處理器數(shù)，會(huì)增加額外開銷和降低處理器利用率；所以對(duì)于一個(gè)特定的并行系統(tǒng)、并行算法或并行程序，它們能否有效的利用不斷增加的處理器的能力應(yīng)是受限的目的：確定某類問題用哪種并行算法與哪種并行體系結(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ò)充的大量處理器*24可擴(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)致的To的增加，從而保持效率不變隨著系統(tǒng)規(guī)模的增加(處理器數(shù)目的增加) ，測(cè)量增加多少運(yùn)算量會(huì)保持效率不