并行計算概述

1、并行計算國家高性能計算中心（合肥）22022-2-14并行計算結(jié)構(gòu)算法編程國家高性能計算中心（合肥）32022-2-14并行計算結(jié)構(gòu)算法編程國家高性能計算中心（合肥）42022-2-14第一章并行計算機系統(tǒng)及結(jié)構(gòu)模型國家高性能計算中心（合肥）52022-2-14并行計算國家高性能計算中心（合肥）62022-2-14國家高性能計算中心（合肥）72022-2-14國家高性能計算中心（合肥）82022-2-14并行計算國家高性能計算中心（合肥）92022-2-14國家高性能計算中心（合肥）102022-2-14國家高性能計算中心（合肥）112022-2-14國家高性能計算中心（合肥）122022-2

2、-14國家高性能計算中心（合肥）132022-2-14國家高性能計算中心（合肥）142022-2-14高性能計算機國家高性能計算中心（合肥）152022-2-14系統(tǒng)互連局 部 總 線I/O總 線SCIHiPPIMyrinet千 兆 位以 太 網(wǎng)光 纖通 道快 速 以 太 網(wǎng)以 太 網(wǎng)10 Base TFDDIATM總 線 或 開 關(guān)SANLANMANWAN100Gb/s10Gb/s1Gb/s100Mb/s10Mb/sIsoEnet網(wǎng)絡(luò)帶寬交 叉 開 關(guān)MIN 或100 Base T國家高性能計算中心（合肥）162022-2-14局部總線、I/O總線、SAN和LANPMI/O橋磁盤SAN(e.

3、g.Myrinet)LAN(e.g.以太網(wǎng),FDDI)系統(tǒng) III/O總線,接口系統(tǒng) I處理器總線局部總線,存儲器總線SCSI節(jié)點 2節(jié)點N系統(tǒng)總線節(jié)點 1國家高性能計算中心（合肥）172022-2-14網(wǎng)絡(luò)性能指標(biāo)國家高性能計算中心（合肥）182022-2-14靜態(tài)互連網(wǎng)絡(luò) 與動態(tài)互連網(wǎng)絡(luò)國家高性能計算中心（合肥）192022-2-14靜態(tài)互連網(wǎng)絡(luò)（1）2/N國家高性能計算中心（合肥）202022-2-14靜態(tài)互連網(wǎng)絡(luò)（2）) 1(2NN1NN22/2NN2NN (a)2-D網(wǎng)孔(b)Illiac網(wǎng)孔(c)2-D環(huán)繞國家高性能計算中心（合肥）212022-2-14靜態(tài)互連網(wǎng)絡(luò)（3）1log2

4、N2/N(a)二叉樹(b)星形連接(c)二叉胖樹國家高性能計算中心（合肥）222022-2-14靜態(tài)互連網(wǎng)絡(luò)（4）nN22/N(b)4-立 方(a)3-立 方(c)頂 點 代 之 以 環(huán)(d)3-立 方 環(huán)國家高性能計算中心（合肥）232022-2-14嵌入國家高性能計算中心（合肥）242022-2-14嵌入10001001101110101100110111111110010001010111011000000001001100100 01 10 01 10 01 10 00 00 00 00 00 00 00 00 01 10 01 11 11 10 01 11 10 00 00 01 1

5、0 00 00 01 11 11 11 10 01 11 11 10 00 01 10 00 00 01 10 00 01 11 11 11 11 11 11 11 10 01 10 01 10 01 10 01 11 1國家高性能計算中心（合肥）252022-2-14NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/(kN1NN)(2NN N2N21N1N2/nN2/3N靜態(tài)互連網(wǎng)絡(luò)特性比較國家高性能計算中心（合肥）262022-2-14動態(tài)互連網(wǎng)絡(luò) (1)L MI O C本 地 總 線高 速 緩 存C P UI

6、 FI FI F存 儲 器 總 線存 儲 器 單 元I FI FC P U 板存 儲 器 板I / O 板通 信 板系 統(tǒng) 總 線( 底 板 上 )數(shù) 據(jù) 總 線緩 沖C CI O P數(shù) 據(jù) 總 線網(wǎng) 絡(luò)( 以 太 網(wǎng) 等 )磁 盤 和 磁 帶部 件打 印 機或 繪 圖 儀本 地 外 圍 設(shè) 備( S C S I 總 線 )M CI F緩 沖國家高性能計算中心（合肥）272022-2-14動態(tài)互連網(wǎng)絡(luò) （2） 國家高性能計算中心（合肥）282022-2-14動態(tài)互聯(lián)網(wǎng)絡(luò) （3）0101010101010101(a)4種可能的開關(guān)連接000001010011100101110111輸入00000

7、1010011100101110111輸出第0級第1級第2級(b)一種8輸入的Omega網(wǎng)絡(luò)國家高性能計算中心（合肥）292022-2-14動態(tài)互連網(wǎng)絡(luò)（4） n2log22國家高性能計算中心（合肥）302022-2-14動態(tài)互連網(wǎng)絡(luò)比較 )(wnO)log(wnnOk)(2wnO)/(nwfO)(wfO)(wfO)(wfO國家高性能計算中心（合肥）312022-2-14標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（1）國家高性能計算中心（合肥）322022-2-14Myrinet連接的LAN/Cluster交換開關(guān)交換開關(guān)交換開關(guān)交換開關(guān)桌面主機機箱內(nèi)多計算機機群多處理機機群網(wǎng)絡(luò)RAM和VME 單板磁盤國家高性能計算中心（

8、合肥）332022-2-14標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（2)國家高性能計算中心（合肥）342022-2-14使用HiPPI通道和開關(guān)構(gòu)筑的LAN主干網(wǎng) HiPPI交 換 開 關(guān)超 級 計 算 機幀 緩 沖 器RGB顯 示 器HiPPI串 行文 件服 務(wù) 器工 作 站小 型 機大 規(guī) 模 并 行處 理 系 統(tǒng)25米300米25米25米HiPPI串 行300米直 至 10千 米300米HiPPI串 行存 儲 器服 務(wù) 器工 作 站光 纖 擴(kuò) 展 器光 纖 擴(kuò) 展 器HiPPI交 換 開 關(guān)國家高性能計算中心（合肥）352022-2-14標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（3） 國家高性能計算中心（合肥）362022-2-14雙向FD

9、DI環(huán)作為主干網(wǎng) 文件服務(wù)器數(shù)據(jù)庫服務(wù)器計算機服務(wù)器雙向 FDDI環(huán)FDDI集中器FDDI 集中器FDDI 集中器桌面計算機以太網(wǎng)集線器路由器國家高性能計算中心（合肥）372022-2-14標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（4）國家高性能計算中心（合肥）382022-2-14香港大學(xué)開發(fā)的Pearl機群 ASX-200BXLAX-20HARNETPower集 線 器 7000IBMSP2城 市 大 學(xué) 的 WS池浸 會 大 學(xué)的 WS池USC的IMSCXL服 務(wù) 器PCFDDIPC和WS去 USA主 干 因 特 網(wǎng)SunE-6000服 務(wù) 器(8 CPU)以 太 網(wǎng)工 作 站 池HP服 務(wù) 器SunE-4000S

10、unUltraSPARC2/1200Sun SPARC20/HS14以 太 網(wǎng)T3T1155Mb/sASX-1000ATM開 關(guān)T1T1155Mb/s155Mb/sSGI PowerChallenge(8CPU)32節(jié) 點 ）(國家高性能計算中心（合肥）392022-2-14標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（5）國家高性能計算中心（合肥）402022-2-14并行計算機結(jié)構(gòu)模型 P/CLMNIC定制網(wǎng)絡(luò)(c)MPPP/CLMNICMBMBVPSM交叉開關(guān)(a)PVPVPVPSMSMP/CSMSMI/O總線或交叉開關(guān)(b)SMPP/CP/CP/CLMNICDIRMB定制網(wǎng)絡(luò)(d)DSMP/CLMNICDIRMBLD

11、P/CMMBIOB(e)COWLDP/CMMBIOB商品網(wǎng)絡(luò)(以太網(wǎng)，ATM，etc.)BridgeNICNICBridge國家高性能計算中心（合肥）412022-2-14并行計算機體系合一結(jié)構(gòu) CPNIC(a)無 共 享NIC互 連 網(wǎng) 絡(luò)MD節(jié) 點N節(jié) 點1Shell共 享 磁 盤CPNIC(b)共 享 磁 盤NICM互 連 網(wǎng) 絡(luò)節(jié) 點N節(jié) 點1ShellCP互 連 網(wǎng) 絡(luò)共 享 存 儲 器共 享 磁 盤(c)共 享 存 儲CPShellShell國家高性能計算中心（合肥）422022-2-14五種結(jié)構(gòu)特性一覽表屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型MIMDMIMDMIMDMIMDM

12、IMD處理器類型專用定制商用商用(可定制)商用商用互連網(wǎng)絡(luò)定制交叉開關(guān)總線、交叉開關(guān)定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)商用網(wǎng)絡(luò)（以太ATM）通信機制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間系統(tǒng)存儲器集中共享集中共享分布非共享分布共享分布非共享訪存模型UMAUMANORMANUMANORMA代表機器Cray C-90，Cray T-90，銀河1號IBM R50，S G I P o w e r Challenge，曙光1號Intel Paragon， IBMSP2，曙光1000/2000Stanford DASH，Cray T 3DBerkeley NOW，

13、Alpha Farm國家高性能計算中心（合肥）432022-2-14并行計算機訪存模型（1)P1P2PnI/OSM1SMm共享存儲器處理器（）系統(tǒng)互連總線 交叉開關(guān)多級,網(wǎng)絡(luò)國家高性能計算中心（合肥）442022-2-14并行計算機訪存模型（2)LM1P1LM2P2LMnPn互連網(wǎng)絡(luò)(a)共享本地存儲模型全局互連網(wǎng)絡(luò)(b)層次式機群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSM國家高性能計算中心（合肥）452022-2-14并行計算機訪存模型（3)互 連 網(wǎng) 絡(luò)DCPDCPDCP國家高性能計算中心（合肥）462022-2-14并行計算機訪存模型（4)

14、I/ONIC,DIR,RC系統(tǒng)互連網(wǎng)路MemP/CP/CI/ONIC,DIR,RCMemP/CP/C節(jié)點N節(jié)點1總線或交叉 開關(guān)總線或交叉 開關(guān)國家高性能計算中心（合肥）472022-2-14并行計算機訪存模型（5)消息傳遞互連網(wǎng)絡(luò)(網(wǎng)絡(luò)，環(huán)網(wǎng)，超立方，立方環(huán)等)PMPMMPMPMPMPMPPMPMPM.國家高性能計算中心（合肥）482022-2-14構(gòu)筑并行機系統(tǒng)的不同存儲結(jié)構(gòu)MIMDMIMD多計算機(多地址空間非共享存儲器)(IBM SP2,DEC TruClusterTandem Hymalaya,HP,Microsoft Wolfpack,etc)NORMANORMAUMAUMANUM

15、ANUMAClusterClusterMPPMPP(Intel TFLOPS)緊耦合PVPPVP(Cray T90)SMPSMP(Intel SHV,SunFire,DEC 8400,SGI PowerChallenge,IBMR60,etc.)COMACOMA(KSR-1,DDM)CC-NUMACC-NUMA(Stanford Dash,SGI Origin 2000,Sequent NUMA-Q,HP/Convex Exemplar)NCC-NUMANCC-NUMA(Cray T3E)DSMDSM(TreadMarks,Wind Tunnel,IVY,Shrimp,etc.)（）松散耦合（

16、）中央存儲器分布存儲器多處理機單地址共享（）空間存儲器國家高性能計算中心（合肥）492022-2-14第二章 當(dāng)代并行機系統(tǒng)國家高性能計算中心（合肥）502022-2-14對稱多處理機SMP(1)P / CS MS MI / O總線或交叉開關(guān)P / CP / C國家高性能計算中心（合肥）512022-2-14對稱多處理機SMP(2)國家高性能計算中心（合肥）522022-2-14大規(guī)模并行機MPPP/CLMNIC定 制 網(wǎng) 絡(luò)P/CLMNICMBMB國家高性能計算中心（合肥）532022-2-14典型MPP系統(tǒng)特性比較MPP模型Intel/Sandia ASCI Option RedIBM S

17、P2SGI/Cray Origin2000一個大型樣機的配置9072個處理器，1.8Tflop/s(NSL)400個處理器，100Gflop/s(MHPCC)128個處理器，51Gflop/s(NCSA)問世日期1996年12月1994年9月1996年10月處理器類型200MHz, 200Mflop/s Pentium Pro67MHz，267Mflop/s POWER2200MHz，400Mflop/s MIPS R10000節(jié)點體系結(jié)構(gòu)和數(shù)據(jù)存儲器2個處理器，32到256MB主存，共享磁盤1個處理器，64MB到2GB本地主存，1GB到14.5GB本地磁盤2個處理器，64MB到256MB分布

18、共享主存和共享磁盤互連網(wǎng)絡(luò)和主存模型分離兩維網(wǎng)孔，NORMA多級網(wǎng)絡(luò)，NORMA胖超立方體網(wǎng)絡(luò)，CC-NUMA節(jié)點操作系統(tǒng)輕量級內(nèi)核（LWK）完全AIX（IBM UNIX）微內(nèi)核Cellular IRIX自然編程機制基于PUMA Portals的MPIMPI和PVMPower C， Power Fortran其他編程模型Nx，PVM，HPFHPF，LindaMPI，PVM國家高性能計算中心（合肥）542022-2-14MPP所用的高性能CPU特性比較屬性Pentium ProPowerPC 602Alpha 21164AUltra SPARC IIMIPS R10000工藝BiCMOSCMOS

19、CMOSCMOSCMOS晶體管數(shù)5.5M/15.5M7M9.6M5.4M6.8M時鐘頻率150MHz133MHz417MHz200MHz200MHz電壓2.9V3.3V2.2V2.5V3.3V功率20W30W20W28W30W字長32位64位64位64位64位I/O高速緩存8KB/8KB32KB/32KB8KB/8KB16KB/16KB32KB/32KB2級高速緩存256KB(多芯片模塊)1128MB(片外)96KB(片上)16MB(片外)16MB(片外)執(zhí)行單元5個單元6個單元4個單元9個單元5個單元超標(biāo)量3路(Way)4路4路4路4路流水線深度14級48級79級9級57級SPECint 9

20、2366225500350300SPECfp 92283300750550600SPECint 958.0922511N/A7.4SPECfp 956.7030017N/A15其它特性CISC/RISC混合短流水線長L1高速緩存最高時鐘頻率最大片上2級高速緩存多媒體和圖形指令MP機群總線可支持4個CPU國家高性能計算中心（合肥）552022-2-14機群型大規(guī)模并行機SP2NICDE 節(jié) 點 1NICDE 節(jié) 點S以 太 網(wǎng)PMCCMCCPPPN高 性 能Omega，網(wǎng) 絡(luò)開 關(guān)I/O總 線I/O總 線國家高性能計算中心（合肥）562022-2-14工作站機群COWP/CMMIOMIOMP/C

21、NICNICDDLAN國家高性能計算中心（合肥）572022-2-14典型的機群系統(tǒng)典型的機群系統(tǒng)特點一覽表名稱系統(tǒng)特點Princeton:SHRIMPPC商用組件，通過專用網(wǎng)絡(luò)接口達(dá)到共享虛擬存儲，支持有效通信Karsruhe:Parastation用于分布并行處理的有效通信網(wǎng)絡(luò)和軟件開發(fā)Rice:TreadMarks軟件實現(xiàn)分布共享存儲的工作站機群Wisconsin:Wind Tunnel在經(jīng)由商用網(wǎng)絡(luò)互連的工作站機群上實現(xiàn)分布共享存儲C h i c a 、 M a r y l 、Penns:NSCP國家可擴(kuò)放機群計劃：在通過因特網(wǎng)互連的3個本地機群系統(tǒng)上進(jìn)行元計算Argonne:Glob

22、us在由ATM連接的北美17個站點的WAN上開發(fā)元計算平臺和軟件Syracuse:WWVM使用因特網(wǎng)和HPCC技術(shù)，在世界范圍的虛擬機上進(jìn)行高性能計算HKU:Pearl Cluster研究機群在分布式多媒體和金融數(shù)字庫方面的應(yīng)用Virgina:Legion在國家虛擬計算機設(shè)施上開發(fā)元計算軟件國家高性能計算中心（合肥）582022-2-14SMPMPP機群比較系統(tǒng)特征SMPMPP機群節(jié)點數(shù)量(N)O(10)O(100)-O(1000)O(100)節(jié)點復(fù)雜度中粒度或細(xì)粒度細(xì)粒度或中粒度中粒度或粗粒度節(jié)點間通信 共享存儲器消息傳遞或共享變量（有DSM時）消息傳遞節(jié)點操作系統(tǒng)1N(微內(nèi)核)和1個主機O

23、S(單一)N (希望為同構(gòu))支持單一系統(tǒng)映像永遠(yuǎn)部分希望地址空間單一多或單一（有DSM時）多個作業(yè)調(diào)度單一運行隊列主機上單一運行隊列協(xié)作多隊列網(wǎng)絡(luò)協(xié)議非標(biāo)準(zhǔn)非標(biāo)準(zhǔn)標(biāo)準(zhǔn)或非標(biāo)準(zhǔn)可用性通常較低低到中高可用或容錯性能/價格比一般一般高互連網(wǎng)絡(luò)總線/交叉開關(guān)定制商用國家高性能計算中心（合肥）592022-2-14第三章 并行計算性能評測國家高性能計算中心（合肥）602022-2-14CPU的某些基本性能指標(biāo)TnTTTnTn11,max國家高性能計算中心（合肥）612022-2-14存儲器性能寄 存 器1級高 速 緩 存2級高 速 緩 存主 存磁 盤遠(yuǎn) 程存 儲 器C2KBL=0周 期B=1-32GB/

24、S4-256KB0-2周 期1-16GB/S64KB-4MB2-10周 期1-4GB/S16MB-16GB10-100周 期 0.4-2GB/S1-100GB100K-1M周 期1-16MB/S1-100GB100-100K周 期1-300MB/S 各層性能參數(shù)各層性能參數(shù)：容量容量C C、延遲延遲L L、帶寬帶寬B B。 相關(guān)參數(shù)：相關(guān)參數(shù)：存儲粒度、一致性粒度、層管理方案等。存儲粒度、一致性粒度、層管理方案等。國家高性能計算中心（合肥）622022-2-14 影響存儲器容量影響存儲器容量C C設(shè)計因素設(shè)計因素： 與主流應(yīng)用的進(jìn)程數(shù)及各進(jìn)程工作集尺寸等有關(guān)。與主流應(yīng)用的進(jìn)程數(shù)及各進(jìn)程工作集尺

25、寸等有關(guān)。 影響存儲器延遲影響存儲器延遲L L設(shè)計因素設(shè)計因素： 與與CPUCPU指令系統(tǒng)指令系統(tǒng)CPICPI及指令所需數(shù)據(jù)量等有關(guān)。及指令所需數(shù)據(jù)量等有關(guān)。 影響存儲器帶寬影響存儲器帶寬B B設(shè)計因素設(shè)計因素： 與應(yīng)用的數(shù)據(jù)通信量、通信頻率和延遲與應(yīng)用的數(shù)據(jù)通信量、通信頻率和延遲L L等有關(guān)。等有關(guān)。國家高性能計算中心（合肥）632022-2-14并行與通信開銷國家高性能計算中心（合肥）642022-2-14Ping-Pong Scheme國家高性能計算中心（合肥）652022-2-14并行開銷的表達(dá)式：點到點通信國家高性能計算中心（合肥）662022-2-14并行開銷的表達(dá)式：整體通信國家

26、高性能計算中心（合肥）672022-2-14機器的成本、價格與性/價比國家高性能計算中心（合肥）682022-2-14算法級性能評測國家高性能計算中心（合肥）692022-2-14Amdahl 定律國家高性能計算中心（合肥）702022-2-14Amdahl定律（contd)pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWfWWWpWWWWSOOOPSPS/) 1(1)1 (國家高性能計算中心（合肥）712022-2-14Amdahls law (contd)程序中順序部分的百分比f(c)0% 1% 2% 3% 4% 100%加速比SS1024=1024/(1+10

27、23f)1024x91x48x31x24x1x WpWp Wp WpWp WpW1W1W1W1W1W1工作負(fù)載W處理器數(shù)P (a)123456T1 T1 Tp Tp Tp Tp Tp Tp T1 T1 T1執(zhí)行時間T處理器數(shù)P (b)T1123456國家高性能計算中心（合肥）722022-2-14Gustafson定律 PSSSSWWpWpWpWppWpWpWS/) p-f (p-p) f ( p -f) p ( f S 111WWfpfWWWpWWSOOPSPS/11國家高性能計算中心（合肥）732022-2-14Gustafson定律（contd)程序中順序部分的百分比f(c)S1024=1024-1023f0%1%2%3%4%1024x1014x 1004x993x983x加速比S 處理器數(shù)P工作負(fù)載W