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

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

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

3、22022-2-13靜態(tài)互連網(wǎng)絡(luò)（2）) 1(2NN1NN22/2NN2NN 國家高性能計算中心（合肥）132022-2-13靜態(tài)互連網(wǎng)絡(luò)（3）1log2N2/N(a)二叉樹(b)星形連接(c)二叉胖樹國家高性能計算中心（合肥）142022-2-13靜態(tài)互連網(wǎng)絡(luò)（4）nN22/N(b)4-立 方(a)3-立 方(c)頂 點 代 之 以 環(huán)(d)3-立 方 環(huán)國家高性能計算中心（合肥）152022-2-13嵌入國家高性能計算中心（合肥）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國家高性能計算中心（合肥）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ò)特性比較國家高性能計算中心（合肥）182022-2-13動態(tài)互連網(wǎng)絡(luò) (1)L MI O C本 地 總 線高 速 緩 存C P UI 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緩 沖國家高性能計算中心（合肥）192022-2-13動態(tài)互連網(wǎng)絡(luò) （2） 國家高性能計算中心（合肥）202

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

7、inet連接的LAN/Cluster交換開關(guān)交換開關(guān)交換開關(guān)交換開關(guān)桌面主機機箱內(nèi)多計算機機群多處理機機群網(wǎng)絡(luò)RAM和VME 單板磁盤國家高性能計算中心（合肥）252022-2-13標準互連網(wǎng)絡(luò)（2)國家高性能計算中心（合肥）262022-2-13使用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ù) 器工 作 站光 纖 擴 展 器光 纖 擴

8、展 器HiPPI交 換 開 關(guān)國家高性能計算中心（合肥）272022-2-13標準互連網(wǎng)絡(luò)（3） 國家高性能計算中心（合肥）282022-2-13雙向FDDI環(huán)作為主干網(wǎng) 文件服務(wù)器數(shù)據(jù)庫服務(wù)器計算機服務(wù)器雙向 FDDI環(huán)FDDI集中器FDDI 集中器FDDI 集中器桌面計算機以太網(wǎng)集線器路由器國家高性能計算中心（合肥）292022-2-13標準互聯(lián)網(wǎng)絡(luò)（4）國家高性能計算中心（合肥）302022-2-13香港大學(xué)開發(fā)的Pearl機群 ASX-200BXLAX-20HARNETPower集 線 器 7000IBMSP2城 市 大 學(xué) 的 WS池浸 會 大 學(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開 關(guān)T1T1155Mb/s155Mb/sSGI PowerChallenge(8CPU)32節(jié) 點 ）(國家高性能計算中心（合肥）312022-2-13標準互連網(wǎng)絡(luò)（5）國家高性能計算中心（合肥）322022-2-13并行計算機結(jié)構(gòu)模型 P/CLMNIC定制網(wǎng)絡(luò)(c)MPPP/CLMNICMBMBVPSM交叉開關(guān)(a)P

10、VPVPVPSMSMP/CSMSMI/O總線或交叉開關(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國家高性能計算中心（合肥）332022-2-13并行計算機體系合一結(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)共 享 存 儲CPShel

11、lShell國家高性能計算中心（合肥）342022-2-13五種結(jié)構(gòu)特性一覽表屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型MIMDMIMDMIMDMIMDMIMD處理器類型專用定制商用商用商用商用互連網(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，曙

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

13、022-2-13并行計算機訪存模型（3)互 連 網(wǎng) 絡(luò)DCPDCPDCP國家高性能計算中心（合肥）382022-2-13并行計算機訪存模型（4)I/ONIC,DIR,RC系統(tǒng)互連網(wǎng)路MemP/CP/CI/ONIC,DIR,RCMemP/CP/C節(jié)點N節(jié)點1總線或交叉 開關(guān)總線或交叉 開關(guān)國家高性能計算中心（合肥）392022-2-13并行計算機訪存模型（5)消息傳遞互連網(wǎng)絡(luò)(網(wǎng)絡(luò)，環(huán)網(wǎng)，超立方，立方環(huán)等)PMPMMPMPMPMPMPPMPMPM.國家高性能計算中心（合肥）402022-2-13構(gòu)筑并行機系統(tǒng)的不同存儲結(jié)構(gòu)MIMDMIMD多計算機(多地址空間非共享存儲器)(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.)（）松散耦合（）中央存儲器分布存儲器多處理機單地址共享（）空間存儲器國家高性能計算中心（合肥）412022-2-13第二章 當(dāng)代并行機系統(tǒng)國家高性能計算中心（合肥）422022-2-13對稱多處理機SMP(1)P / CS MS MI / O總線或交叉開關(guān)P / CP / C國家高性能計算中心（合肥）432022-2-13對稱多處理機SMP(2)國家高性能計算中心（合肥）442022-2-13大規(guī)模并行機MPPP/CLMNIC定 制 網(wǎng) 絡(luò)P/CLMNICMBMB國

16、家高性能計算中心（合肥）452022-2-13典型MPP系統(tǒng)特性比較MPP模型Intel/Sandia ASCI Option RedIBM SP2SGI/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ù)存儲器

17、2個處理器，32到256MB主存，共享磁盤1個處理器，64MB到2GB本地主存，1GB到14.5GB本地磁盤2個處理器，64MB到256MB分布共享主存和共享磁盤互連網(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國家高性能計算中心（合肥）462022-2-13MPP所用的高性能CPU特性比較屬

18、性Pentium ProPowerPC 602Alpha 21164AUltra SPARC IIMIPS R10000工藝BiCMOSCMOSCMOSCMOSCMOS晶體管數(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(片

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

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

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

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

23、532022-2-13存儲器性能寄 存 器1級高 速 緩 存2級高 速 緩 存主 存磁 盤遠 程存 儲 器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國家高性能計算中心（合肥）542022-2-13并行與通信開銷國家高性能計算中心（合肥）552022-2-13Ping-Pong Scheme國家高性能計算中心（合肥）562022-2-13并行開銷的表達式：

24、點到點通信國家高性能計算中心（合肥）572022-2-13并行開銷的表達式：整體通信國家高性能計算中心（合肥）582022-2-13機器的成本、價格與性/價比國家高性能計算中心（合肥）592022-2-13算法級性能評測國家高性能計算中心（合肥）602022-2-13Amdahl 定律國家高性能計算中心（合肥）612022-2-13Amdahl定律（contd)pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWfWWWpWWWWSOOOPSPS/) 1(1)1 (國家高性能計算中心（合肥）622022-2-13Amdahls law (contd)程序中順序部分的百分

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