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

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

VjopVk源操作數(shù)之一取自標(biāo)量寄存器組VjopS主存儲(chǔ)與向量寄存器之間數(shù)據(jù)傳送MemopVjVjopmem1.1.1并行向量處理機(jī)（PVP）并行要求無向量沖突V4→V1+V2V1發(fā)生源向量沖突V5→V1*V3無功能部件沖突V4→V1*V3發(fā)生乘部件沖突V5→V2*V61.1.2對(duì)稱多機(jī)系統(tǒng)（SMP）屬于MIMD,UMA,中粒度，高級(jí)別并行多機(jī)系統(tǒng)具有可插拔的Cache芯片的商用多機(jī)系統(tǒng)集中式共享存儲(chǔ)器對(duì)稱性：每個(gè)處理機(jī)關(guān)于I/O操作，OS服務(wù)和SM的權(quán)限是等同的可擴(kuò)展行受到SM和總線的限制機(jī)型：SGI工作站，DEC服務(wù)器8400，Dawning-1等1.1.2對(duì)稱多機(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ī)采用專用的高寬帶低延時(shí)的通信網(wǎng)絡(luò)物理上分布的存儲(chǔ)器進(jìn)程間采用阻塞報(bào)文交互操作（同步）

處理機(jī)級(jí)、任務(wù)級(jí)（異步）機(jī)型：IntelParagon，IBMSPQ，Dawning10001.1.3大規(guī)模并行處理機(jī)（MPP）典型結(jié)構(gòu)：P/CLMNICP/CLMNICCustom-DesignedNetwork…1.1.4分布式共享存儲(chǔ)器多機(jī)系統(tǒng)（DSM）屬于MIMD，NUMA，NORMA，大粒度多機(jī)系統(tǒng)（No-RemoteMemoryAccess）對(duì)用戶來講，是一個(gè)物理上分布的，邏輯上是共享的一個(gè)由硬件支持的單一的存儲(chǔ)器地址空間。采用基于DIR（Cache目錄）的Cache一致性機(jī)制采用專用通信網(wǎng)絡(luò)可使用共享存儲(chǔ)器編程模式1.1.4分布式共享存儲(chǔ)器多機(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)分布式存儲(chǔ)器每個(gè)節(jié)點(diǎn)是一套完整的計(jì)算機(jī)系統(tǒng)（SMP或PC）采用低成本的商品網(wǎng)絡(luò)互連結(jié)構(gòu)每個(gè)節(jié)點(diǎn)擁有本地磁盤和完整的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并行計(jì)算體系結(jié)構(gòu)1.1并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)模型1.2訪存模型1.3并行計(jì)算機(jī)系統(tǒng)互連1.2.1均勻訪存模型（UMA）物理存儲(chǔ)器被所有處理機(jī)均勻共享所有處理機(jī)訪存時(shí)間相同適于通用的或分時(shí)的應(yīng)用程序類型模型：1.2.1均勻訪存模型（UMA）P1P2PnSysteminterconnect(bus,crossbar,multistage,network)SMmSM1I/O1.2.2非均勻訪存模型（NUMA）是所有處理機(jī)的本地存儲(chǔ)器的集合訪問本地LM的訪存時(shí)間較短訪問遠(yuǎn)程LM的訪存時(shí)間較長模型：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）在分布式存儲(chǔ)器多機(jī)系統(tǒng)中，如果所有存儲(chǔ)器都是專用的，而且只能被本地存儲(chǔ)機(jī)訪問，則這種訪問模型稱為NORAM絕大多數(shù)的NUMA支持NORAM在DSM中，NORAM的特性被隱匿的模型：1.2.5非遠(yuǎn)程訪存模型（NORMA）1.2.6小結(jié)并行計(jì)算體系結(jié)構(gòu)1.1并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)模型1.2訪存模型1.3并行計(jì)算機(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ī)總線存儲(chǔ)器總線I/O總線構(gòu)建在母板或背板上，網(wǎng)距在2m之內(nèi)

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

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

Network）1.3.2靜態(tài)互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)1（一維線性陣列）只與左右近鄰節(jié)點(diǎn)相連N個(gè)節(jié)點(diǎn)用N-1條邊節(jié)點(diǎn)度為2網(wǎng)絡(luò)直徑為N-1對(duì)剖度為1首尾連接時(shí)構(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ò)實(shí)例

64個(gè)處理單元的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對(duì)剖寬度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ò)特性對(duì)照表1.3.3動(dòng)態(tài)互連網(wǎng)絡(luò)什么是動(dòng)態(tài)互連網(wǎng)絡(luò)？動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)：用開關(guān)單元構(gòu)成的，可按應(yīng)用程序要求動(dòng)態(tài)地改變連接組態(tài)的網(wǎng)絡(luò)（總線交叉開關(guān)多級(jí)互連）總線：連接處理器存儲(chǔ)模塊I/O設(shè)備的一組導(dǎo)線和插座本地總線，CPU板級(jí)上的總線存儲(chǔ)總線，存儲(chǔ)器板級(jí)的總線數(shù)據(jù)總線，I/O板級(jí)和通信板級(jí)的總線系統(tǒng)總線，底板上的所有插入板間通信提供的通路1.3.3動(dòng)態(tài)互連網(wǎng)絡(luò)總線之間的關(guān)系：1.3.3動(dòng)態(tài)互連網(wǎng)絡(luò)交叉開關(guān)：1.3.3動(dòng)態(tài)互連網(wǎng)絡(luò)交叉開關(guān)特點(diǎn)交叉開關(guān)是一種單級(jí)交互網(wǎng)絡(luò)當(dāng)端口數(shù)為n時(shí)，其開關(guān)量（復(fù)雜度)為n2可在源目對(duì)之間提供動(dòng)態(tài)鏈接，每個(gè)開關(guān)上的狀態(tài)可由程序動(dòng)態(tài)的控制使用交叉開關(guān)的兩個(gè)途徑：交互處理機(jī)通信（COW）、交互處理機(jī)-存儲(chǔ)器訪問（SMP）4*4交叉開關(guān)1.3.3動(dòng)態(tài)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)單級(jí)交叉開關(guān)級(jí)聯(lián)輸入輸出之間可動(dòng)態(tài)切換級(jí)數(shù)logn開關(guān)單元n*logn1.3.3動(dòng)態(tài)互連網(wǎng)絡(luò)多級(jí)互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)：1.3.3動(dòng)態(tài)互連網(wǎng)絡(luò)實(shí)例Ω網(wǎng)絡(luò)1.3.3動(dòng)態(tài)互連網(wǎng)絡(luò)動(dòng)態(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)利用冗余通路實(shí)現(xiàn)可靠性100~200Mbps的傳輸速率網(wǎng)距：100m（使用銅線)2km(使用多模光纖）60km（使用單模光纖）缺陷