現(xiàn)代密碼學(xué)理論與實(shí)踐之五――并行計(jì)算

1、并行計(jì)算國(guó)家高性能計(jì)算中心（合肥）22022-2-13并行計(jì)算結(jié)構(gòu)算法編程國(guó)家高性能計(jì)算中心（合肥）32022-2-13并行計(jì)算結(jié)構(gòu)算法編程國(guó)家高性能計(jì)算中心（合肥）42022-2-13第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型國(guó)家高性能計(jì)算中心（合肥）52022-2-13并行計(jì)算國(guó)家高性能計(jì)算中心（合肥）62022-2-13高性能計(jì)算機(jī)國(guó)家高性能計(jì)算中心（合肥）72022-2-13系統(tǒng)互連局 部 總 線I/O總 線SCIHiPPIMyrinet千 兆 位以 太 網(wǎng)光 纖通 道快 速 以 太 網(wǎng)以 太 網(wǎng)10 Base TFDDIATM總 線 或 開(kāi) 關(guān)SANLANMANWAN100Gb/s10Gb/s1

2、Gb/s100Mb/s10Mb/sIsoEnet網(wǎng)絡(luò)帶寬交 叉 開(kāi) 關(guān)MIN 或100 Base T國(guó)家高性能計(jì)算中心（合肥）82022-2-13局部總線、I/O總線、SAN和LANPMI/O橋磁盤(pán)SAN(e.g.Myrinet)LAN(e.g.以太網(wǎng),FDDI)系統(tǒng) III/O總線,接口系統(tǒng) I處理器總線局部總線,存儲(chǔ)器總線SCSI節(jié)點(diǎn) 2節(jié)點(diǎn)N系統(tǒng)總線節(jié)點(diǎn) 1國(guó)家高性能計(jì)算中心（合肥）92022-2-13網(wǎng)絡(luò)性能指標(biāo)國(guó)家高性能計(jì)算中心（合肥）102022-2-13靜態(tài)互連網(wǎng)絡(luò) 與動(dòng)態(tài)互連網(wǎng)絡(luò)國(guó)家高性能計(jì)算中心（合肥）112022-2-13靜態(tài)互連網(wǎng)絡(luò)（1）2/N國(guó)家高性能計(jì)算中心（合肥）1

3、22022-2-13靜態(tài)互連網(wǎng)絡(luò)（2）) 1(2NN1NN22/2NN2NN 國(guó)家高性能計(jì)算中心（合肥）132022-2-13靜態(tài)互連網(wǎng)絡(luò)（3）1log2N2/N(a)二叉樹(shù)(b)星形連接(c)二叉胖樹(shù)國(guó)家高性能計(jì)算中心（合肥）142022-2-13靜態(tài)互連網(wǎng)絡(luò)（4）nN22/N(b)4-立 方(a)3-立 方(c)頂 點(diǎn) 代 之 以 環(huán)(d)3-立 方 環(huán)國(guó)家高性能計(jì)算中心（合肥）152022-2-13嵌入國(guó)家高性能計(jì)算中心（合肥）162022-2-13嵌入0 01 10 01 10 01 10 00 00 00 00 00 00 00 00 01 10 01 11 11 10 01 11

4、10 00 00 01 10 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 11000100110111010110011011111111001000101011101100000000100110010國(guó)家高性能計(jì)算中心（合肥）172022-2-13NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/(kN1NN)(2NN N2N21N1N2/n

5、N2/3N靜態(tài)互連網(wǎng)絡(luò)特性比較國(guó)家高性能計(jì)算中心（合肥）182022-2-13動(dòng)態(tài)互連網(wǎng)絡(luò) (1)L MI O C本 地 總 線高 速 緩 存C P UI FI FI F存 儲(chǔ) 器 總 線存 儲(chǔ) 器 單 元I FI FC P U 板存 儲(chǔ) 器 板I / O 板通 信 板系 統(tǒng) 總 線( 底 板 上 )數(shù) 據(jù) 總 線緩 沖C CI O P數(shù) 據(jù) 總 線網(wǎng) 絡(luò)( 以 太 網(wǎng) 等 )磁 盤(pán) 和 磁 帶部 件打 印 機(jī)或 繪 圖 儀本 地 外 圍 設(shè) 備( S C S I 總 線 )M CI F緩 沖國(guó)家高性能計(jì)算中心（合肥）192022-2-13動(dòng)態(tài)互連網(wǎng)絡(luò) （2） 國(guó)家高性能計(jì)算中心（合肥）202

6、022-2-13動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò) （3）0101010101010101(a)4種可能的開(kāi)關(guān)連接000001010011100101110111輸入000001010011100101110111輸出第0級(jí)第1級(jí)第2級(jí)(b)一種8輸入的Omega網(wǎng)絡(luò)國(guó)家高性能計(jì)算中心（合肥）212022-2-13動(dòng)態(tài)互連網(wǎng)絡(luò)（4） n2log22國(guó)家高性能計(jì)算中心（合肥）222022-2-13動(dòng)態(tài)互連網(wǎng)絡(luò)比較 )(wnO)log(wnnOk)(2wnO)/(nwfO)(wfO)(wfO)(wfO國(guó)家高性能計(jì)算中心（合肥）232022-2-13標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（1）國(guó)家高性能計(jì)算中心（合肥）242022-2-13Myr

7、inet連接的LAN/Cluster交換開(kāi)關(guān)交換開(kāi)關(guān)交換開(kāi)關(guān)交換開(kāi)關(guān)桌面主機(jī)機(jī)箱內(nèi)多計(jì)算機(jī)機(jī)群多處理機(jī)機(jī)群網(wǎng)絡(luò)RAM和VME 單板磁盤(pán)國(guó)家高性能計(jì)算中心（合肥）252022-2-13標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（2)國(guó)家高性能計(jì)算中心（合肥）262022-2-13使用HiPPI通道和開(kāi)關(guān)構(gòu)筑的LAN主干網(wǎng) HiPPI交 換 開(kāi) 關(guān)超 級(jí) 計(jì) 算 機(jī)幀 緩 沖 器RGB顯 示 器HiPPI串 行文 件服 務(wù) 器工 作 站小 型 機(jī)大 規(guī) 模 并 行處 理 系 統(tǒng)25米300米25米25米HiPPI串 行300米直 至 10千 米300米HiPPI串 行存 儲(chǔ) 器服 務(wù) 器工 作 站光 纖 擴(kuò) 展 器光 纖 擴(kuò)

8、展 器HiPPI交 換 開(kāi) 關(guān)國(guó)家高性能計(jì)算中心（合肥）272022-2-13標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（3） 國(guó)家高性能計(jì)算中心（合肥）282022-2-13雙向FDDI環(huán)作為主干網(wǎng) 文件服務(wù)器數(shù)據(jù)庫(kù)服務(wù)器計(jì)算機(jī)服務(wù)器雙向 FDDI環(huán)FDDI集中器FDDI 集中器FDDI 集中器桌面計(jì)算機(jī)以太網(wǎng)集線器路由器國(guó)家高性能計(jì)算中心（合肥）292022-2-13標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（4）國(guó)家高性能計(jì)算中心（合肥）302022-2-13香港大學(xué)開(kāi)發(fā)的Pearl機(jī)群 ASX-200BXLAX-20HARNETPower集 線 器 7000IBMSP2城 市 大 學(xué) 的 WS池浸 會(huì) 大 學(xué)的 WS池USC的IMSCXL服 務(wù)

9、 器PCFDDIPC和WS去 USA主 干 因 特 網(wǎng)SunE-6000服 務(wù) 器(8 CPU)以 太 網(wǎng)工 作 站 池HP服 務(wù) 器SunE-4000SunUltraSPARC2/1200Sun SPARC20/HS14以 太 網(wǎng)T3T1155Mb/sASX-1000ATM開(kāi) 關(guān)T1T1155Mb/s155Mb/sSGI PowerChallenge(8CPU)32節(jié) 點(diǎn) ）(國(guó)家高性能計(jì)算中心（合肥）312022-2-13標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（5）國(guó)家高性能計(jì)算中心（合肥）322022-2-13并行計(jì)算機(jī)結(jié)構(gòu)模型 P/CLMNIC定制網(wǎng)絡(luò)(c)MPPP/CLMNICMBMBVPSM交叉開(kāi)關(guān)(a)P

10、VPVPVPSMSMP/CSMSMI/O總線或交叉開(kāi)關(guān)(b)SMPP/CP/CP/CLMNICDIRMB定制網(wǎng)絡(luò)(d)DSMP/CLMNICDIRMBLDP/CMMBIOB(e)COWLDP/CMMBIOB商品網(wǎng)絡(luò)(以太網(wǎng)，ATM，etc.)BridgeNICNICBridge國(guó)家高性能計(jì)算中心（合肥）332022-2-13并行計(jì)算機(jī)體系合一結(jié)構(gòu) CPNIC(a)無(wú) 共 享NIC互 連 網(wǎng) 絡(luò)MD節(jié) 點(diǎn)N節(jié) 點(diǎn)1Shell共 享 磁 盤(pán)CPNIC(b)共 享 磁 盤(pán)NICM互 連 網(wǎng) 絡(luò)節(jié) 點(diǎn)N節(jié) 點(diǎn)1ShellCP互 連 網(wǎng) 絡(luò)共 享 存 儲(chǔ) 器共 享 磁 盤(pán)(c)共 享 存 儲(chǔ)CPShel

11、lShell國(guó)家高性能計(jì)算中心（合肥）342022-2-13五種結(jié)構(gòu)特性一覽表屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型MIMDMIMDMIMDMIMDMIMD處理器類型專用定制商用商用商用商用互連網(wǎng)絡(luò)定制交叉開(kāi)關(guān)總線、交叉開(kāi)關(guān)定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)商用網(wǎng)絡(luò)（以太ATM）通信機(jī)制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間系統(tǒng)存儲(chǔ)器集中共享集中共享分布非共享分布共享分布非共享訪存模型UMAUMANORMANUMANORMA代表機(jī)器Cray C-90，Cray T-90，銀河1號(hào)IBM R50，S G I P o w e r Challenge，曙

12、光1號(hào)Intel Paragon， IBMSP2，曙光1000/2000Stanford DASH，Cray T 3DBerkeley NOW，Alpha Farm國(guó)家高性能計(jì)算中心（合肥）352022-2-13并行計(jì)算機(jī)訪存模型（1)P1P2PnI/OSM1SMm共享存儲(chǔ)器處理器（）系統(tǒng)互連總線 交叉開(kāi)關(guān)多級(jí),網(wǎng)絡(luò)國(guó)家高性能計(jì)算中心（合肥）362022-2-13并行計(jì)算機(jī)訪存模型（2)LM1P1LM2P2LMnPn互連網(wǎng)絡(luò)(a)共享本地存儲(chǔ)模型全局互連網(wǎng)絡(luò)(b)層次式機(jī)群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSM國(guó)家高性能計(jì)算中心（合肥）372

13、022-2-13并行計(jì)算機(jī)訪存模型（3)互 連 網(wǎng) 絡(luò)DCPDCPDCP國(guó)家高性能計(jì)算中心（合肥）382022-2-13并行計(jì)算機(jī)訪存模型（4)I/ONIC,DIR,RC系統(tǒng)互連網(wǎng)路MemP/CP/CI/ONIC,DIR,RCMemP/CP/C節(jié)點(diǎn)N節(jié)點(diǎn)1總線或交叉 開(kāi)關(guān)總線或交叉 開(kāi)關(guān)國(guó)家高性能計(jì)算中心（合肥）392022-2-13并行計(jì)算機(jī)訪存模型（5)消息傳遞互連網(wǎng)絡(luò)(網(wǎng)絡(luò)，環(huán)網(wǎng)，超立方，立方環(huán)等)PMPMMPMPMPMPMPPMPMPM.國(guó)家高性能計(jì)算中心（合肥）402022-2-13構(gòu)筑并行機(jī)系統(tǒng)的不同存儲(chǔ)結(jié)構(gòu)MIMDMIMD多計(jì)算機(jī)(多地址空間非共享存儲(chǔ)器)(IBM SP2,DEC

14、 TruClusterTandem Hymalaya,HP,Microsoft Wolfpack,etc)NORMANORMAUMAUMANUMANUMAClusterClusterMPPMPP(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-NUM

15、ANCC-NUMA(Cray T3E)DSMDSM(TreadMarks,Wind Tunnel,IVY,Shrimp,etc.)（）松散耦合（）中央存儲(chǔ)器分布存儲(chǔ)器多處理機(jī)單地址共享（）空間存儲(chǔ)器國(guó)家高性能計(jì)算中心（合肥）412022-2-13第二章 當(dāng)代并行機(jī)系統(tǒng)國(guó)家高性能計(jì)算中心（合肥）422022-2-13對(duì)稱多處理機(jī)SMP(1)P / CS MS MI / O總線或交叉開(kāi)關(guān)P / CP / C國(guó)家高性能計(jì)算中心（合肥）432022-2-13對(duì)稱多處理機(jī)SMP(2)國(guó)家高性能計(jì)算中心（合肥）442022-2-13大規(guī)模并行機(jī)MPPP/CLMNIC定 制 網(wǎng) 絡(luò)P/CLMNICMBMB國(guó)

16、家高性能計(jì)算中心（合肥）452022-2-13典型MPP系統(tǒng)特性比較MPP模型Intel/Sandia ASCI Option RedIBM SP2SGI/Cray Origin2000一個(gè)大型樣機(jī)的配置9072個(gè)處理器，1.8Tflop/s(NSL)400個(gè)處理器，100Gflop/s(MHPCC)128個(gè)處理器，51Gflop/s(NCSA)問(wèn)世日期1996年12月1994年9月1996年10月處理器類型200MHz, 200Mflop/s Pentium Pro67MHz，267Mflop/s POWER2200MHz，400Mflop/s MIPS R10000節(jié)點(diǎn)體系結(jié)構(gòu)和數(shù)據(jù)存儲(chǔ)器

17、2個(gè)處理器，32到256MB主存，共享磁盤(pán)1個(gè)處理器，64MB到2GB本地主存，1GB到14.5GB本地磁盤(pán)2個(gè)處理器，64MB到256MB分布共享主存和共享磁盤(pán)互連網(wǎng)絡(luò)和主存模型分離兩維網(wǎng)孔，NORMA多級(jí)網(wǎng)絡(luò)，NORMA胖超立方體網(wǎng)絡(luò)，CC-NUMA節(jié)點(diǎn)操作系統(tǒng)輕量級(jí)內(nèi)核（LWK）完全AIX（IBM UNIX）微內(nèi)核Cellular IRIX自然編程機(jī)制基于PUMA Portals的MPIMPI和PVMPower C， Power Fortran其他編程模型Nx，PVM，HPFHPF，LindaMPI，PVM國(guó)家高性能計(jì)算中心（合肥）462022-2-13MPP所用的高性能CPU特性比較屬

18、性Pentium ProPowerPC 602Alpha 21164AUltra SPARC IIMIPS R10000工藝BiCMOSCMOSCMOSCMOSCMOS晶體管數(shù)5.5M/15.5M7M9.6M5.4M6.8M時(shí)鐘頻率150MHz133MHz417MHz200MHz200MHz電壓2.9V3.3V2.2V2.5V3.3V功率20W30W20W28W30W字長(zhǎng)32位64位64位64位64位I/O高速緩存8KB/8KB32KB/32KB8KB/8KB16KB/16KB32KB/32KB2級(jí)高速緩存256KB(多芯片模塊)1128MB(片外)96KB(片上)16MB(片外)16MB(片

19、外)執(zhí)行單元5個(gè)單元6個(gè)單元4個(gè)單元9個(gè)單元5個(gè)單元超標(biāo)量3路(Way)4路4路4路4路流水線深度14級(jí)48級(jí)79級(jí)9級(jí)57級(jí)SPECint 92366225500350300SPECfp 92283300750550600SPECint 958.0922511N/A7.4SPECfp 956.7030017N/A15其它特性CISC/RISC混合短流水線長(zhǎng)L1高速緩存最高時(shí)鐘頻率最大片上2級(jí)高速緩存多媒體和圖形指令MP機(jī)群總線可支持4個(gè)CPU國(guó)家高性能計(jì)算中心（合肥）472022-2-13機(jī)群型大規(guī)模并行機(jī)SP2NICDE 節(jié) 點(diǎn) 1NICDE 節(jié) 點(diǎn)S以 太 網(wǎng)PMCCMCCPPPN高 性

20、 能Omega，網(wǎng) 絡(luò)開(kāi) 關(guān)I/O總 線I/O總 線國(guó)家高性能計(jì)算中心（合肥）482022-2-13工作站機(jī)群COWP/CMMIOMIOMP/CNICNICDDLAN國(guó)家高性能計(jì)算中心（合肥）492022-2-13典型的機(jī)群系統(tǒng)典型的機(jī)群系統(tǒng)特點(diǎn)一覽表名稱系統(tǒng)特點(diǎn)Princeton:SHRIMPPC商用組件，通過(guò)專用網(wǎng)絡(luò)接口達(dá)到共享虛擬存儲(chǔ)，支持有效通信Karsruhe:Parastation用于分布并行處理的有效通信網(wǎng)絡(luò)和軟件開(kāi)發(fā)Rice:TreadMarks軟件實(shí)現(xiàn)分布共享存儲(chǔ)的工作站機(jī)群Wisconsin:Wind Tunnel在經(jīng)由商用網(wǎng)絡(luò)互連的工作站機(jī)群上實(shí)現(xiàn)分布共享存儲(chǔ)C h i

21、c a 、 M a r y l 、Penns:NSCP國(guó)家可擴(kuò)放機(jī)群計(jì)劃：在通過(guò)因特網(wǎng)互連的3個(gè)本地機(jī)群系統(tǒng)上進(jìn)行元計(jì)算Argonne:Globus在由ATM連接的北美17個(gè)站點(diǎn)的WAN上開(kāi)發(fā)元計(jì)算平臺(tái)和軟件Syracuse:WWVM使用因特網(wǎng)和HPCC技術(shù)，在世界范圍的虛擬機(jī)上進(jìn)行高性能計(jì)算HKU:Pearl Cluster研究機(jī)群在分布式多媒體和金融數(shù)字庫(kù)方面的應(yīng)用Virgina:Legion在國(guó)家虛擬計(jì)算機(jī)設(shè)施上開(kāi)發(fā)元計(jì)算軟件國(guó)家高性能計(jì)算中心（合肥）502022-2-13SMPMPP機(jī)群比較系統(tǒng)特征SMPMPP機(jī)群節(jié)點(diǎn)數(shù)量(N)O(10)O(100)-O(1000)O(100)節(jié)點(diǎn)復(fù)雜

22、度中粒度或細(xì)粒度細(xì)粒度或中粒度中粒度或粗粒度節(jié)點(diǎn)間通信 共享存儲(chǔ)器消息傳遞或共享變量（有DSM時(shí)）消息傳遞節(jié)點(diǎn)操作系統(tǒng)1N(微內(nèi)核)和1個(gè)主機(jī)OS(單一)N (希望為同構(gòu))支持單一系統(tǒng)映像永遠(yuǎn)部分希望地址空間單一多或單一（有DSM時(shí)）多個(gè)作業(yè)調(diào)度單一運(yùn)行隊(duì)列主機(jī)上單一運(yùn)行隊(duì)列協(xié)作多隊(duì)列網(wǎng)絡(luò)協(xié)議非標(biāo)準(zhǔn)非標(biāo)準(zhǔn)標(biāo)準(zhǔn)或非標(biāo)準(zhǔn)可用性通常較低低到中高可用或容錯(cuò)性能/價(jià)格比一般一般高互連網(wǎng)絡(luò)總線/交叉開(kāi)關(guān)定制商用國(guó)家高性能計(jì)算中心（合肥）512022-2-13第三章 并行計(jì)算性能評(píng)測(cè)國(guó)家高性能計(jì)算中心（合肥）522022-2-13CPU的某些基本性能指標(biāo)TnTTTnTn11,max國(guó)家高性能計(jì)算中心（合肥）

23、532022-2-13存儲(chǔ)器性能寄 存 器1級(jí)高 速 緩 存2級(jí)高 速 緩 存主 存磁 盤(pán)遠(yuǎn) 程存 儲(chǔ) 器C2KBL=0周 期B=1-32GB/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國(guó)家高性能計(jì)算中心（合肥）542022-2-13并行與通信開(kāi)銷國(guó)家高性能計(jì)算中心（合肥）552022-2-13Ping-Pong Scheme國(guó)家高性能計(jì)算中心（合肥）562022-2-13并行開(kāi)銷的表達(dá)式：

24、點(diǎn)到點(diǎn)通信國(guó)家高性能計(jì)算中心（合肥）572022-2-13并行開(kāi)銷的表達(dá)式：整體通信國(guó)家高性能計(jì)算中心（合肥）582022-2-13機(jī)器的成本、價(jià)格與性/價(jià)比國(guó)家高性能計(jì)算中心（合肥）592022-2-13算法級(jí)性能評(píng)測(cè)國(guó)家高性能計(jì)算中心（合肥）602022-2-13Amdahl 定律國(guó)家高性能計(jì)算中心（合肥）612022-2-13Amdahl定律（contd)pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWfWWWpWWWWSOOOPSPS/) 1(1)1 (國(guó)家高性能計(jì)算中心（合肥）622022-2-13Amdahls law (contd)程序中順序部分的百分

25、比f(wàn)(c)0% 1% 2% 3% 4% 100%加速比SS1024=1024/(1+1023f)1024x91x48x31x24x1x WpWp Wp WpWp WpW1W1W1W1W1W1工作負(fù)載W處理器數(shù)P (a)123456T1 T1 Tp Tp Tp Tp Tp Tp T1 T1 T1執(zhí)行時(shí)間T處理器數(shù)P (b)T1123456國(guó)家高性能計(jì)算中心（合肥）632022-2-13Gustafson定律 PSSSSWWpWpWpWppWpWpWS/) p-f (p-p) f ( p -f) p ( f S 111WWfpfWWWpWWSOOPSPS/11國(guó)家高性能計(jì)算中心（合肥）642022-2-13Gustafson定律（contd)程序中順序部分的百分比f(wàn)(c)S1024=1024-1023f0%1%2%3%4%1024x1014x 1004x993x983x加速比S 處理器數(shù)P工作負(fù)載W (a)W1W1W1W1W1W1WpWpWpWpWpWp123456 TpT1T1T1T1T1T1執(zhí)行時(shí)間T處理