吉林大學(xué)研究所課程-并行計算課件-第1章-并行計算體系結(jié)構(gòu)

第1章并行計算體系結(jié)構(gòu)1.1并行計算機(jī)系統(tǒng)結(jié)構(gòu)模型1.2訪存模型1.3并行計算機(jī)系統(tǒng)互連1.1.1并行向量處理機(jī)（PVP）屬于MIMD（Multiple-InstructionMultiple-Data）、UMA（UniformMemoryAccess）型的細(xì)粒度并行計算機(jī)少量的高性能向量處理器，處理能力≧1Gflops專用高寬帶交叉開關(guān)實現(xiàn)存儲器之間的互聯(lián)大量的共享存儲器模塊（SM）大量向量寄存器和指令緩沖器,不使用高速緩存。機(jī)型CrayC-90/T-9,NECSX-4,Gralaxy-1,Cray-11.1.1并行向量處理機(jī)（PVP）典型結(jié)構(gòu)VPVPVP交叉開關(guān)SMSMSM…………1.1.1并行向量處理機(jī)（PVP）實例Cray-1,組成如下：中央處理器，含運算控制部件，指令緩沖器，指令控制部件和寄存的功能部件。存儲器（內(nèi)存）交互通道，連接診斷維護(hù)控制機(jī)，磁盤存儲器（SM）前端機(jī)（用戶機(jī)）向量流水部件，含8*64個向量寄存器，但V0-V7配向量加和浮點加部件，標(biāo)量寄存器組S0-S71.1.1并行向量處理機(jī)（PVP）4種向量運算指令源向量取自兩個向量寄存器組

VjopVk源操作數(shù)之一取自標(biāo)量寄存器組VjopS主存儲與向量寄存器之間數(shù)據(jù)傳送MemopVjVjopmem1.1.1并行向量處理機(jī)（PVP）并行要求無向量沖突V4→V1+V2V1發(fā)生源向量沖突V5→V1*V3無功能部件沖突V4→V1*V3發(fā)生乘部件沖突V5→V2*V61.1.2對稱多機(jī)系統(tǒng)（SMP）屬于MIMD,UMA,中粒度，高級別并行多機(jī)系統(tǒng)具有可插拔的Cache芯片的商用多機(jī)系統(tǒng)集中式共享存儲器對稱性：每個處理機(jī)關(guān)于I/O操作，OS服務(wù)和SM的權(quán)限是等同的可擴(kuò)展行受到SM和總線的限制機(jī)型：SGI工作站，DEC服務(wù)器8400，Dawning-1等1.1.2對稱多機(jī)系統(tǒng)（SMP）典型結(jié)構(gòu)：SMp/cp/cSMp/c主機(jī)cacheSM總線和交叉開關(guān)…………

5種商用機(jī)型1.1.3大規(guī)模并行處理機(jī)（MPP）屬于MIMD，NUMA中/大粒度多處理機(jī)采用專用的高寬帶低延時的通信網(wǎng)絡(luò)物理上分布的存儲器進(jìn)程間采用阻塞報文交互操作（同步）

處理機(jī)級、任務(wù)級（異步）機(jī)型：IntelParagon，IBMSPQ，Dawning10001.1.3大規(guī)模并行處理機(jī)（MPP）典型結(jié)構(gòu)：P/CLMNICP/CLMNICCustom-DesignedNetwork…1.1.4分布式共享存儲器多機(jī)系統(tǒng)（DSM）屬于MIMD，NUMA，NORMA，大粒度多機(jī)系統(tǒng)（No-RemoteMemoryAccess）對用戶來講，是一個物理上分布的，邏輯上是共享的一個由硬件支持的單一的存儲器地址空間。采用基于DIR（Cache目錄）的Cache一致性機(jī)制采用專用通信網(wǎng)絡(luò)可使用共享存儲器編程模式1.1.4分布式共享存儲器多機(jī)系統(tǒng)（DSM）機(jī)型StanfordDASH,GrayT30典型結(jié)構(gòu)：P/CLMD/RNICMBP/CLMD/RNICMB……專用網(wǎng)絡(luò)1.1.5工作站機(jī)群（COW）屬于MIMDNUMA粗粒度多機(jī)系統(tǒng)分布式存儲器每個節(jié)點是一套完整的計算機(jī)系統(tǒng)（SMP或PC）采用低成本的商品網(wǎng)絡(luò)互連結(jié)構(gòu)每個節(jié)點擁有本地磁盤和完整的OS（MPP只有內(nèi)核）機(jī)型：BerkeleyNoW，AlphaFarm,FXCOW等1.1.5工作站機(jī)群（COW）典型結(jié)構(gòu)：NICP/CMBridgeMBNICP/CMBridgeMB……商用網(wǎng)絡(luò)LDLD10M10M5種典型系統(tǒng)結(jié)構(gòu)特征1.1.6小結(jié)AttributePVPSMPDSMMPPCOWExampleSystemsCrayC-90CrayT-90CrayCS6400DEC8000DASHCrayT3DIntelparagonIBMSP2BerkeleyNOW,AlphafarmProcessorTypeCustomvectorprocessorCommoditymicro-processorCommoditymicro-processorCommoditymicro-processorCommoditymicro-processorMemoryModelCentralizedsharedCentralizedsharedDistributedsharedDistributedunsharedDistributedunsharedAddressSpaceSingleSingleSingleMultipleMultipleAccessModelUMAUMANUMANORMAorNUMAInter-connectCustomCrossbarBusorCrossbarCustomNetworkCustomNetworkCommodityNetwork1.1.6小結(jié)系統(tǒng)比較SystemCharacteristicsDECAlphaserver84005/440HP9000/T600IBMRS6000/R40SunUltraEnterprise6000SGIPowerChallengeXLNcessors121283036Processortype437MHzAlpha21164180MHzPA8000112MHzPowerPC604167MHzUltraSPARCI195MHzMIPSR10000Off-chipcacheperprocessor4MB8MB1MB512KB4MBMaxmemory28GB16GB2GB30GB16GBInterconnectBandwidthBus2.1GB/sBus960MB/sBus+Xbar1.8GB/sBus+Xbar2.6GB/sBus1.2GB/sInternaldisk192GB168GB38GB63GB114GBI/Ochannels12PCIbuses,each133MB/sN/A2MCA,each160MB/s30Sbus,each200MB/s6PowerChannel-2HIO,each320MB/sI/Oslots144PCIslots112HP-PBslots15MCA45Sbusslots12HIOSlotsI/Obandwidth1.2GB/s1GB/s320MB/s2.6GM/s320MBperHIOslot并行計算體系結(jié)構(gòu)1.1并行計算機(jī)系統(tǒng)結(jié)構(gòu)模型1.2訪存模型1.3并行計算機(jī)系統(tǒng)互連1.2.1均勻訪存模型（UMA）物理存儲器被所有處理機(jī)均勻共享所有處理機(jī)訪存時間相同適于通用的或分時的應(yīng)用程序類型模型：1.2.1均勻訪存模型（UMA）P1P2PnSysteminterconnect(bus,crossbar,multistage,network)SMmSM1I/O1.2.2非均勻訪存模型（NUMA）是所有處理機(jī)的本地存儲器的集合訪問本地LM的訪存時間較短訪問遠(yuǎn)程LM的訪存時間較長模型：1.2.2非均勻訪存模型（NUMA）LM1LM2LMnP1P2PnInter-connectionNetwork……1.2.3Cache一致性非均勻訪存模型（CC-NUMA）DSM結(jié)構(gòu)模型：NIC,DIR,RCP/CMEMI/OP/C總線和交叉開關(guān)Node1NIC,DIR,RCP/CMEMI/OP/C總線和交叉開關(guān)Noden…SystemInterconnectNetwork1.2.4全局Cache訪存模型（COMA）是NUMA的一種特例，是采用各處理機(jī)的Cache組成的全局地址空間遠(yuǎn)程Cache的訪問是由Cache目錄支持的模型：1.2.4全Cache訪存模型（COMA）InterconnectionNetworkDCPDCPDCP1.2.5非遠(yuǎn)程訪存模型（NORMA）在分布式存儲器多機(jī)系統(tǒng)中，如果所有存儲器都是專用的，而且只能被本地存儲機(jī)訪問，則這種訪問模型稱為NORAM絕大多數(shù)的NUMA支持NORAM在DSM中，NORAM的特性被隱匿的模型：1.2.5非遠(yuǎn)程訪存模型（NORMA）1.2.6小結(jié)并行計算體系結(jié)構(gòu)1.1并行計算機(jī)系統(tǒng)結(jié)構(gòu)模型1.2訪存模型1.3并行計算機(jī)系統(tǒng)互連1.3.1系統(tǒng)互連橫向：網(wǎng)距漸增總線或交叉開

SANs

LANs

MANs

WANs縱向：網(wǎng)速漸增10M100M1000M10G100GNetworkBandwidth10Mb/s100Mb/s1Gb/s10Gb/s100Gb/sMINorDrossbarSwitchesLocelBosesSCIHippIMyrinetGigabitEthernetFibercChannelFDDII/OBusesFastEthernet:100BaseTATMIsoEnetEthernet:10BaseTWANsMANsLANsSANsBusesorSwitches網(wǎng)絡(luò)環(huán)境總線SANLANMANWAN總線處理機(jī)總線存儲器總線I/O總線構(gòu)建在母板或背板上，網(wǎng)距在2m之內(nèi)

注意，這里連接的實際口是多機(jī)系統(tǒng)的各個部件，而不是多計算機(jī)系統(tǒng)。SANSystemAreaNetwork把不同的節(jié)點連成一個單一的多計算機(jī)系統(tǒng)網(wǎng)距在3-25m。

注意，這是一個緊密耦合的多處理機(jī)或多計算機(jī)系統(tǒng)。LANLocalAreaNetwork在一個建筑物或一個校園或一個企業(yè)內(nèi)部形成的多計算機(jī)系統(tǒng)網(wǎng)距25-500m。MANMetropolitanAreaNetwork覆蓋整個城市的計算機(jī)網(wǎng)絡(luò)網(wǎng)距<=25km。WANWorldAreaNetwork覆蓋全球的計算機(jī)網(wǎng)絡(luò)，將大量的IntraNet構(gòu)建形成大的全球范圍的Internet，可實現(xiàn)meta(i)計算1.3.2靜態(tài)互連網(wǎng)絡(luò)定義靜態(tài)互連網(wǎng)絡(luò)：處理單元之間有固定的連接，在程序執(zhí)行期間，這種點到點的鏈接保持不變。節(jié)點度：射入或者射出一個節(jié)點的邊數(shù)稱為節(jié)點度（NodeDegree）網(wǎng)絡(luò)直徑：兩個節(jié)點之間的最大距離，即最大徑數(shù)稱為~（NetworkDiametre）1.3.2靜態(tài)互連網(wǎng)絡(luò)對剖寬度：對分網(wǎng)絡(luò)各半所必須移去的最小邊數(shù)稱為對剖寬度（BisectionWidth）對稱網(wǎng)絡(luò)：如果從任意節(jié)點上觀看網(wǎng)絡(luò)都是一樣的，則稱為對稱網(wǎng)絡(luò)（Symmetry

Network）1.3.2靜態(tài)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)1（一維線性陣列）只與左右近鄰節(jié)點相連N個節(jié)點用N-1條邊節(jié)點度為2網(wǎng)絡(luò)直徑為N-1對剖度為1首尾連接時構(gòu)成環(huán)（單向或雙向）1.3.2靜態(tài)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)2（四近鄰連接）1.3.2靜態(tài)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)3（樹形連接）1.3.2靜態(tài)互連網(wǎng)絡(luò)實例

64個處理單元的IlliacIU型處理器PU0PU7PU1PU8PI15PU9PU56PU63PU57PU8PU16PU0PU56PU57PU63PU63PU7PU55PU0PU1PU7…………………………1.3.2靜態(tài)互連網(wǎng)絡(luò)

1.3.2靜態(tài)互連網(wǎng)絡(luò)PU9->PU45：PU9->PU1->PU57->PU56->PU48->PU47->PU46->PU45

或：PU9->PU1->PU57->PU49->

PU48->PU47->PU46->PU45對剖寬度2根下N=16（橫向連接8根，蛇形連接8根）1.3.2靜態(tài)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)4（超立方連接）1.3.2靜態(tài)互連網(wǎng)絡(luò)特性對照表1.3.3動態(tài)互連網(wǎng)絡(luò)什么是動態(tài)互連網(wǎng)絡(luò)？動態(tài)互聯(lián)網(wǎng)絡(luò)：用開關(guān)單元構(gòu)成的，可按應(yīng)用程序要求動態(tài)地改變連接組態(tài)的網(wǎng)絡(luò)（總線交叉開關(guān)多級互連）總線：連接處理器存儲模塊I/O設(shè)備的一組導(dǎo)線和插座本地總線，CPU板級上的總線存儲總線，存儲器板級的總線數(shù)據(jù)總線，I/O板級和通信板級的總線系統(tǒng)總線，底板上的所有插入板間通信提供的通路1.3.3動態(tài)互連網(wǎng)絡(luò)總線之間的關(guān)系：1.3.3動態(tài)互連網(wǎng)絡(luò)交叉開關(guān)：1.3.3動態(tài)互連網(wǎng)絡(luò)交叉開關(guān)特點交叉開關(guān)是一種單級交互網(wǎng)絡(luò)當(dāng)端口數(shù)為n時，其開關(guān)量（復(fù)雜度)為n2可在源目對之間提供動態(tài)鏈接，每個開關(guān)上的狀態(tài)可由程序動態(tài)的控制使用交叉開關(guān)的兩個途徑：交互處理機(jī)通信（COW）、交互處理機(jī)-存儲器訪問（SMP）4*4交叉開關(guān)1.3.3動態(tài)互連網(wǎng)絡(luò)多級互連網(wǎng)絡(luò)單級交叉開關(guān)級聯(lián)輸入輸出之間可動態(tài)切換級數(shù)logn開關(guān)單元n*logn1.3.3動態(tài)互連網(wǎng)絡(luò)多級互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)：1.3.3動態(tài)互連網(wǎng)絡(luò)實例Ω網(wǎng)絡(luò)1.3.3動態(tài)互連網(wǎng)絡(luò)動態(tài)網(wǎng)絡(luò)互連特性1.3.3寬帶互連網(wǎng)絡(luò)協(xié)議標(biāo)準(zhǔn)光纖分布數(shù)據(jù)接口（FDDI）快速以太網(wǎng)MyrinetSAN和LAN高性能并行接口（HiPPI）異步傳輸機(jī)制（ATM）可擴(kuò)充一致接口（SCI）FDDI反向雙向環(huán)利用冗余通路實現(xiàn)可靠性100~200Mbps的傳輸速率網(wǎng)距：100m（使用銅線)2km(使用多模光纖）60km（使用單模光纖）缺陷