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

體系結(jié)構(gòu)與并行基礎(chǔ)趙永華中科院計算機網(wǎng)絡信息中心超級計算中心yhzhao@體系結(jié)構(gòu)與并行基礎(chǔ)*2并行機體系結(jié)構(gòu)*2并行計算機系統(tǒng)結(jié)構(gòu)分類*3

Flynn分類：（instruction/datastream）SISD（單指令單數(shù)據(jù)）,SIMD（單指令多數(shù)據(jù)）,MIMD,MISD結(jié)構(gòu)模型分類：PVP（并行向量機）,SMP（共享內(nèi)存）,MPP（大規(guī)模并行計算機）,DSM（分布共享內(nèi)存）,COW（集群）訪存模型分類：UMA(UniformMemory-access，均勻存儲訪問模型)NUMA(non-UMA）COMA（Cache-OnlyMemoryArchitecture，全高速緩存內(nèi)存體系結(jié)構(gòu)）

CC-NUMA(Cache-Coherent0一致性高速緩存非均勻存儲訪問模型),NORMA（No-RomateMemoryAccess非遠程存儲訪問模型）并行計算機系統(tǒng)結(jié)構(gòu)分類*3Flynn分類：（instruc結(jié)構(gòu)模型結(jié)構(gòu)模型共享內(nèi)存/對稱多處理機系統(tǒng)(SMP)

PVP：并行向量機

單地址空間共享存儲

UMA(

UniformMemoryAccess)

SMP：共享內(nèi)存并行機（SharedMemoryProcessors）。多個處理器通過交叉開關(guān)（Crossbar）或總線與共享內(nèi)存互連。任意處理器可直接訪問任意內(nèi)存地址,且訪問延遲、帶寬、幾率都是等價的;

系統(tǒng)是對稱的；單地址空間、共享存儲、UMA；并行編程方式:通常采用OpenMP,也可使用消息傳遞(MPI/PVM)及HPF。SGI

PowerChallenge,Dawning1

*5共享內(nèi)存/對稱多處理機系統(tǒng)(SMP)PVP：并行向量機*5MPP：大規(guī)模并行計算機系統(tǒng)

MPP:大規(guī)模并行計算機系統(tǒng)(MassivelyParallelProcessors)。由大量具有局部內(nèi)存的計算結(jié)點通過高速系統(tǒng)網(wǎng)絡聯(lián)接而構(gòu)成的并行處理系統(tǒng).

MPP系統(tǒng)的系統(tǒng)網(wǎng)絡通常具有某種拓撲結(jié)構(gòu)(如tree,mesh,torus,hypercube).物理和邏輯上均是分布內(nèi)存采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(專門設(shè)計和定制的)NORMA或CC-NUMA代表:CRAYT3E(2048),ASCIRed(3072),IBMSP2,曙光1000*6MPP：大規(guī)模并行計算機系統(tǒng)MPP:大規(guī)模并行計算機系統(tǒng)(DSM：分布共享存儲多處理機系統(tǒng)

DSM：分布共享存貯并行機（DistributedSharedMemory），由結(jié)點（一般是SMP系統(tǒng)）通過高速消息傳遞網(wǎng)絡互連而成。存貯系統(tǒng)在物理上分布、邏輯上共享。各結(jié)點有自己獨立的尋址空間。單地址空間、分布共享NUMA（NonuniformMemoryAccess）與SMP的主要區(qū)別：DSM在物理上有分布在各個節(jié)點的局部內(nèi)存從而形成一個共享的存儲器；代表:SGIOrigin2000,CrayT3D

*7DSM：分布共享存儲多處理機系統(tǒng)DSM：*7Cluster：機群系統(tǒng)Cluster(Now,Cow)：群集系統(tǒng)。將單個節(jié)點，用商業(yè)網(wǎng)絡：Ethernet，Myrinet，Quadrics，Infiniband，Switch等連結(jié)起來形成群集系統(tǒng)。每個節(jié)點都是一個完整的計算機（SMP或DSM），有自己磁盤和操作系統(tǒng)各個節(jié)點通過高性能網(wǎng)絡相互連接網(wǎng)絡接口和I/O總線松耦合連接每個節(jié)點有完整的操作系統(tǒng)多地址空間、分布非共享、NORMA通用性、可擴展性好，性價比高*8Cluster：機群系統(tǒng)Cluster(Now,Cow)：*訪存模型

*9UMANORMANUMA:多處理機（單地址空間共享存儲器）

UMA:UniformMemoryAccessNUMA:NonuniformMemoryAccess多計算機（多地址空間非共享存儲器）

NORMA:No-RemoteMemoryAccess訪存模型*9UMANORMANUMA:多處理機（單地址空間最新的TOP500計算機*10最新的TOP500計算機*10*11最新的TOP500計算機*11最新的TOP500計算機來自Cray的美洲豹“Jaguar”，憑借1.75PFlop/s(每秒1750萬億次)的計算能力傲視群雄?！癑aguar”采用了224162個處理器核心來自中國的曙光“星云”系統(tǒng)以1271萬億次/s的峰值速度名列第二采用了自主設(shè)計的HPP體系結(jié)構(gòu)、高效異構(gòu)協(xié)同計算技術(shù)處理器是32nm工藝的六核至強X5650，并且采用了NvidiaTeslaC2050GPU做協(xié)處理的用戶編程環(huán)境；異構(gòu)體系結(jié)構(gòu)專用通用

TOP500中85%的系統(tǒng)采用了四核處理器，而有5%的系統(tǒng)已經(jīng)使用了六核或者更多核的處理器。

*12來自Cray的美洲豹“Jaguar”，憑借1.75PFl并行編程基礎(chǔ)*13*13并行計算軟件環(huán)境操作系統(tǒng)：UNIX、LINUX等通信庫：MPI、PVM數(shù)學庫：如MKL，ScaLAPACK等編譯器：GNUCompiler自由軟件，持C/C++、Fortran77等語言高性能計算中常用的：C/C++：GCC(GNUC/C++Compiler)Fortran：gfortran;IntelCompiler由Intel公司針對Intel處理器開發(fā),支持Linux、Windows支持C/C++（icc，mpicc：IntelC/C++Compiler）、Fortran77/90/95（ifc：IntelFortranCompiler)支持多線程和OpenMP14并行計算軟件環(huán)境操作系統(tǒng)：UNIX、LINUX等14并行程序設(shè)計方法隱式并行程序設(shè)計：常用傳統(tǒng)的語言編程成順序源編碼，把“并行”交給編譯器實現(xiàn)自動并行程序的自動并行化是一個理想目標，存在難以克服的困難語言容易，編譯器難顯式并行程序設(shè)計：在用戶程序中出現(xiàn)“并行”的調(diào)度語句顯式并行是目前有效的并行程序設(shè)計方法。例如通過消息傳遞方式或多線程等語言難，編譯器容易*15并行程序設(shè)計方法隱式并行程序設(shè)計：*15并行程序編程模型隱式并行（ImplicitParallel）數(shù)據(jù)并行（DataParallel）共享變量（SharedVariable）消息傳遞（MessagePassing）*16并行程序編程模型隱式并行（ImplicitParallel隱式并行(ImplicitParallel)概況：程序員用熟悉的串行語言編寫相應的串行程序通過編譯器和運行支持系統(tǒng)將串行程序自動轉(zhuǎn)化為并行代碼特點：語義簡單可移植性好單線程，易于調(diào)試和驗證正確性細粒度并行效率很低*17隱式并行(ImplicitParallel)概況：*17數(shù)據(jù)并行（DataParallel）概況：SIMD的自然模型局部計算和數(shù)據(jù)選路操作例：HPF特點：單線程并行操作于聚合數(shù)據(jù)結(jié)構(gòu)（數(shù)組）松散同步單一地址空間隱式交互作用顯式數(shù)據(jù)分布優(yōu)點:編程相對簡單,串并行程序一致.缺點:程序的性能在很大程度上依賴于所用的編譯系統(tǒng)及用戶對編譯系統(tǒng)的了解.并行粒度局限于數(shù)據(jù)級并行,粒度較小.18數(shù)據(jù)并行（DataParallel）概況：18共享變量(SharedVariable)概況：PVP,SMP,DSM的自然模型特點：多線程：SPMD,MPMD異步單一地址空間顯式同步隱式數(shù)據(jù)分布隱式通信典型代表：OpenMP19共享變量(SharedVariable)概況：19消息傳遞(MessagePassing）概況：MPP、COW的自然模型特點：多進程異步并行多地址空間顯式同步顯式數(shù)據(jù)映射和負載分配顯式通信典型代表MPI、PVM20消息傳遞(MessagePassing）概況：20并行編程模型標準所有并行編程模型標準可分為以下三類:數(shù)據(jù)并行HPF,Fortran90用于SMP,DSM共享編程OpenMP用于SMP,DSM消息傳遞MPI,PVM用于所有并行計算機三者可混合使用:如對以SMP為節(jié)點的Cluster來說,可以在節(jié)點間進行消息傳遞,在節(jié)點內(nèi)進行共享變量編程.21并行編程模型標準所有并行編程模型標準可分為以下三類:21基本并行化方法相并行（PhaseParallel）流水線并行（PipelineParallel）主從并行（Master-SlaveParallel）分治并行（DivideandConquerParallel）工作池并行（WorkPoolParallel）*22基本并行化方法相并行（PhaseParallel）*22加速比性能定律并行系統(tǒ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：問題中的串行分量Wp：并行分量

W＝Ws＋Wp

S：加速比S=穿行并行時間

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

To:額外開銷時間之和*25可擴展性與評測標準（二）等效率度量標準:*25可擴展性與評測標準（三）等速度度量標準系統(tǒng)規(guī)模增加時，若保持平均速度(每個處理器的速度)不變，每個處理器增加浮點操作的量速度常以每秒多少次浮點運算(Flops)來表示等計算時間/通信開銷比率度量標準系統(tǒng)規(guī)模增加時，保持計/通信比不變所需要增加的問題規(guī)模計算時間/通信開銷比率并行計算時間與系統(tǒng)開銷之比*26可擴展性與評測標準（三）等速度度量標準*26謝謝大家！*27*27體系結(jié)構(gòu)與并行基礎(chǔ)趙永華中科院計算機網(wǎng)絡信息中心超級計算中心yhzhao@體系結(jié)構(gòu)與并行基礎(chǔ)*29并行機體系結(jié)構(gòu)*2并行計算機系統(tǒng)結(jié)構(gòu)分類*30

Flynn分類：（instruction/datastream）SISD（單指令單數(shù)據(jù)）,SIMD（單指令多數(shù)據(jù)）,MIMD,MISD結(jié)構(gòu)模型分類：PVP（并行向量機）,SMP（共享內(nèi)存）,MPP（大規(guī)模并行計算機）,DSM（分布共享內(nèi)存）,COW（集群）訪存模型分類：UMA(UniformMemory-access，均勻存儲訪問模型)NUMA(non-UMA）COMA（Cache-OnlyMemoryArchitecture，全高速緩存內(nèi)存體系結(jié)構(gòu)）

CC-NUMA(Cache-Coherent0一致性高速緩存非均勻存儲訪問模型),NORMA（No-RomateMemoryAccess非遠程存儲訪問模型）并行計算機系統(tǒng)結(jié)構(gòu)分類*3Flynn分類：（instruc結(jié)構(gòu)模型結(jié)構(gòu)模型共享內(nèi)存/對稱多處理機系統(tǒng)(SMP)

PVP：并行向量機

單地址空間共享存儲

UMA(

UniformMemoryAccess)

SMP：共享內(nèi)存并行機（SharedMemoryProcessors）。多個處理器通過交叉開關(guān)（Crossbar）或總線與共享內(nèi)存互連。任意處理器可直接訪問任意內(nèi)存地址,且訪問延遲、帶寬、幾率都是等價的;

系統(tǒng)是對稱的；單地址空間、共享存儲、UMA；并行編程方式:通常采用OpenMP,也可使用消息傳遞(MPI/PVM)及HPF。SGI

PowerChallenge,Dawning1

*32共享內(nèi)存/對稱多處理機系統(tǒng)(SMP)PVP：并行向量機*5MPP：大規(guī)模并行計算機系統(tǒng)

MPP:大規(guī)模并行計算機系統(tǒng)(MassivelyParallelProcessors)。由大量具有局部內(nèi)存的計算結(jié)點通過高速系統(tǒng)網(wǎng)絡聯(lián)接而構(gòu)成的并行處理系統(tǒng).

MPP系統(tǒng)的系統(tǒng)網(wǎng)絡通常具有某種拓撲結(jié)構(gòu)(如tree,mesh,torus,hypercube).物理和邏輯上均是分布內(nèi)存采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(專門設(shè)計和定制的)NORMA或CC-NUMA代表:CRAYT3E(2048),ASCIRed(3072),IBMSP2,曙光1000*33MPP：大規(guī)模并行計算機系統(tǒng)MPP:大規(guī)模并行計算機系統(tǒng)(DSM：分布共享存儲多處理機系統(tǒng)

DSM：分布共享存貯并行機（DistributedSharedMemory），由結(jié)點（一般是SMP系統(tǒng)）通過高速消息傳遞網(wǎng)絡互連而成。存貯系統(tǒng)在物理上分布、邏輯上共享。各結(jié)點有自己獨立的尋址空間。單地址空間、分布共享NUMA（NonuniformMemoryAccess）與SMP的主要區(qū)別：DSM在物理上有分布在各個節(jié)點的局部內(nèi)存從而形成一個共享的存儲器；代表:SGIOrigin2000,CrayT3D

*34DSM：分布共享存儲多處理機系統(tǒng)DSM：*7Cluster：機群系統(tǒng)Cluster(Now,Cow)：群集系統(tǒng)。將單個節(jié)點，用商業(yè)網(wǎng)絡：Ethernet，Myrinet，Quadrics，Infiniband，Switch等連結(jié)起來形成群集系統(tǒng)。每個節(jié)點都是一個完整的計算機（SMP或DSM），有自己磁盤和操作系統(tǒng)各個節(jié)點通過高性能網(wǎng)絡相互連接網(wǎng)絡接口和I/O總線松耦合連接每個節(jié)點有完整的操作系統(tǒng)多地址空間、分布非共享、NORMA通用性、可擴展性好，性價比高*35Cluster：機群系統(tǒng)Cluster(Now,Cow)：*訪存模型

*36UMANORMANUMA:多處理機（單地址空間共享存儲器）

UMA:UniformMemoryAccessNUMA:NonuniformMemoryAccess多計算機（多地址空間非共享存儲器）

NORMA:No-RemoteMemoryAccess訪存模型*9UMANORMANUMA:多處理機（單地址空間最新的TOP500計算機*37最新的TOP500計算機*10*38最新的TOP500計算機*11最新的TOP500計算機來自Cray的美洲豹“Jaguar”，憑借1.75PFlop/s(每秒1750萬億次)的計算能力傲視群雄?！癑aguar”采用了224162個處理器核心來自中國的曙光“星云”系統(tǒng)以1271萬億次/s的峰值速度名列第二采用了自主設(shè)計的HPP體系結(jié)構(gòu)、高效異構(gòu)協(xié)同計算技術(shù)處理器是32nm工藝的六核至強X5650，并且采用了NvidiaTeslaC2050GPU做協(xié)處理的用戶編程環(huán)境；異構(gòu)體系結(jié)構(gòu)專用通用

TOP500中85%的系統(tǒng)采用了四核處理器，而有5%的系統(tǒng)已經(jīng)使用了六核或者更多核的處理器。

*39來自Cray的美洲豹“Jaguar”，憑借1.75PFl并行編程基礎(chǔ)*40*13并行計算軟件環(huán)境操作系統(tǒng)：UNIX、LINUX等通信庫：MPI、PVM數(shù)學庫：如MKL，ScaLAPACK等編譯器：GNUCompiler自由軟件，持C/C++、Fortran77等語言高性能計算中常用的：C/C++：GCC(GNUC/C++Compiler)Fortran：gfortran;IntelCompiler由Intel公司針對Intel處理器開發(fā),支持Linux、Windows支持C/C++（icc，mpicc：IntelC/C++Compiler）、Fortran77/90/95（ifc：IntelFortranCompiler)支持多線程和OpenMP41并行計算軟件環(huán)境操作系統(tǒng)：UNIX、LINUX等14并行程序設(shè)計方法隱式并行程序設(shè)計：常用傳統(tǒng)的語言編程成順序源編碼，把“并行”交給編譯器實現(xiàn)自動并行程序的自動并行化是一個理想目標，存在難以克服的困難語言容易，編譯器難顯式并行程序設(shè)計：在用戶程序中出現(xiàn)“并行”的調(diào)度語句顯式并行是目前有效的并行程序設(shè)計方法。例如通過消息傳遞方式或多線程等語言難，編譯器容易*42并行程序設(shè)計方法隱式并行程序設(shè)計：*15并行程序編程模型隱式并行（ImplicitParallel）數(shù)據(jù)并行（DataParallel）共享變量（SharedVariable）消息傳遞（MessagePassing）*43并行程序編程模型隱式并行（ImplicitParallel隱式并行(ImplicitParallel)概況：程序員用熟悉的串行語言編寫相應的串行程序通過編譯器和運行支持系統(tǒng)將串行程序自動轉(zhuǎn)化為并行代碼特點：語義簡單可移植性好單線程，易于調(diào)試和驗證正確性細粒度并行效率很低*44隱式并行(ImplicitParallel)概況：*17數(shù)據(jù)并行（DataParallel）概況：SIMD的自然模型局部計算和數(shù)據(jù)選路操作例：HPF特點：單線程并行操作于聚合數(shù)據(jù)結(jié)構(gòu)（數(shù)組）松散同步單一地址空間隱式交互作用顯式數(shù)據(jù)分布優(yōu)點:編程相對簡單,串并行程序一致.缺點:程序的性能在很大程度上依賴于所用的編譯系統(tǒng)及用戶對編譯系統(tǒng)的了解.并行粒度局限于數(shù)據(jù)級并行,粒度較小.45數(shù)據(jù)并行（DataParallel）概況：18共享變量(SharedVariable)概況：PVP,SMP,DSM的自然模型特點：多線程：SPMD,MPMD異步單一地址空間顯式同步隱式數(shù)據(jù)分布隱式通信典型代表：OpenMP46共享變量(SharedVariable)概況：19消息傳遞(MessagePassing）概況：MPP、COW的自然模型特點：多進程異步并行多地址空間顯式同步顯式數(shù)據(jù)映射和負載分配顯式通信典型代表MPI、PVM47消息傳遞(MessagePassing）概況：20并行編程模型標準所有并行編程模型標準可分為以下三類:數(shù)據(jù)并行HPF,Fortran90用于SMP,DSM共享編程OpenMP用于SMP,DSM消息傳遞MPI,PVM用于所有并行計算機三者可混合使用:如對以SMP為節(jié)點的Cluster來說,可以在節(jié)點間進行消息傳遞,在節(jié)點內(nèi)進行共享變量編程.48并行編程模型標準所有并行編程模型標準可分為以下三類:21基本并行化方法相并行（PhaseParallel）流水線并行（PipelineParallel）主從并行（Master-SlaveParallel）分治并行（DivideandConquerParallel）工作池并行（WorkPoolParallel）*49基本并行化方法相并行（PhaseParallel）*22加速比性能定律并行系統(tǒng)的加速比簡單的說就是指對于一個給定的應用，并行算法或并行程序的執(zhí)行速度相對于串行算法或串行程序的執(zhí)行速度加快了多少倍（既Sp=T1/Tp）三種加速比性能定律：Amdahl定律：適用固定計算負載

S=（Ws+Wp）/（Ws+Wp/p）Gustafson定律：適用于可擴放問題

S=（Ws+pWp）/（Ws+Wp）Sun和Ni定律：受限于存儲器其中