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

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

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

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

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

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

6、新的TOP500計算機*10*11最新的TOP500計算機 來自Cray的美洲豹“Jaguar”，憑借1.75 PFlop/s(每秒1750萬億次)的計算能力傲視群雄?！癑aguar”采用了224162個處理器核心來自中國的曙光“星云”系統(tǒng)以1271萬億次/s的峰值速度名列第二采用了自主設(shè)計的HPP體系結(jié)構(gòu)、高效異構(gòu)協(xié)同計算技術(shù)處理器是32nm工藝的六核至強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并行計

7、算軟件環(huán)境操作系統(tǒng)：UNIX、LINUX等 通信庫：MPI 、PVM數(shù)學(xué)庫：如MKL，ScaLAPACK等編譯器：GNU Compiler自由軟件，持C/C+、Fortran77等語言高性能計算中常用的：C/C+：GCC (GNU C/C+ Compiler)Fortran ：gfortran;Intel Compiler由Intel公司針對Intel處理器開發(fā),支持Linux、Windows支持C/C+（icc，mpicc：Intel C/C+ Compiler）、Fortran77/90/95（ifc： Intel Fortran Compiler)支持多線程和OpenMP14并行程序設(shè)計

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

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

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

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

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