1、現(xiàn)代密碼學(xué)理論與實踐之五12022-2-23并行計算現(xiàn)代密碼學(xué)理論與實踐之五22022-2-23并行計算結(jié)構(gòu)算法編程現(xiàn)代密碼學(xué)理論與實踐之五32022-2-23并行計算結(jié)構(gòu)算法編程現(xiàn)代密碼學(xué)理論與實踐之五42022-2-23第一章并行計算機系統(tǒng)及結(jié)構(gòu)模型現(xiàn)代密碼學(xué)理論與實踐之五52022-2-23并行計算現(xiàn)代密碼學(xué)理論與實踐之五62022-2-23現(xiàn)代密碼學(xué)理論與實踐之五72022-2-23現(xiàn)代密碼學(xué)理論與實踐之五82022-2-23并行計算現(xiàn)代密碼學(xué)理論與實踐之五92022-2-23現(xiàn)代密碼學(xué)理論與實踐之五102022-2-23現(xiàn)代密碼學(xué)理論與實踐之五112022-2-23現(xiàn)代密碼學(xué)理論與實

2、踐之五122022-2-23現(xiàn)代密碼學(xué)理論與實踐之五132022-2-23現(xiàn)代密碼學(xué)理論與實踐之五142022-2-23高性能計算機現(xiàn)代密碼學(xué)理論與實踐之五152022-2-23系統(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現(xiàn)代密碼學(xué)理論與實踐之五162022-2-23局部總線、I/O總線、SAN和LANPMI/O橋磁

3、盤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現(xiàn)代密碼學(xué)理論與實踐之五172022-2-23網(wǎng)絡(luò)性能指標現(xiàn)代密碼學(xué)理論與實踐之五182022-2-23靜態(tài)互連網(wǎng)絡(luò) 與動態(tài)互連網(wǎng)絡(luò)現(xiàn)代密碼學(xué)理論與實踐之五192022-2-23靜態(tài)互連網(wǎng)絡(luò)（1）2/N現(xiàn)代密碼學(xué)理論與實踐之五202022-2-23靜態(tài)互連網(wǎng)絡(luò)（2）) 1(2NN1NN22/2NN2NN (a)2-D網(wǎng)孔(b)Illiac網(wǎng)孔(c)2-D環(huán)繞現(xiàn)代密碼學(xué)理論與實踐之五212022-2-23靜態(tài)互連網(wǎng)絡(luò)（3）1lo

4、g2N2/N(a)二叉樹(b)星形連接(c)二叉胖樹現(xiàn)代密碼學(xué)理論與實踐之五222022-2-23靜態(tài)互連網(wǎng)絡(luò)（4）nN22/N(b)4-立 方(a)3-立 方(c)頂 點 代 之 以 環(huán)(d)3-立 方 環(huán)現(xiàn)代密碼學(xué)理論與實踐之五232022-2-23嵌入現(xiàn)代密碼學(xué)理論與實踐之五242022-2-23嵌入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 10

5、 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現(xiàn)代密碼學(xué)理論與實踐之五252022-2-23NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/(kN1NN)(2NN N2N21N1N2/nN2/3N靜態(tài)互連網(wǎng)絡(luò)特性比較現(xiàn)代密碼學(xué)理論與實踐之五262022-2-23動態(tài)互連網(wǎng)絡(luò) (1)L MI O C本 地 總 線高 速 緩 存C P UI FI

6、 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緩 沖現(xiàn)代密碼學(xué)理論與實踐之五272022-2-23動態(tài)互連網(wǎng)絡(luò) （2） 現(xiàn)代密碼學(xué)理論與實踐之五282022-2-23動態(tài)互聯(lián)網(wǎng)絡(luò) （3）0101010101010101(a)4種可能的開關(guān)連接000001010011100101110111輸入0000010100

7、11100101110111輸出第0級第1級第2級(b)一種8輸入的Omega網(wǎng)絡(luò)現(xiàn)代密碼學(xué)理論與實踐之五292022-2-23動態(tài)互連網(wǎng)絡(luò)（4） n2log22現(xiàn)代密碼學(xué)理論與實踐之五302022-2-23動態(tài)互連網(wǎng)絡(luò)比較 )(wnO)log(wnnOk)(2wnO)/(nwfO)(wfO)(wfO)(wfO現(xiàn)代密碼學(xué)理論與實踐之五312022-2-23標準互聯(lián)網(wǎng)絡(luò)（1）現(xiàn)代密碼學(xué)理論與實踐之五322022-2-23Myrinet連接的LAN/Cluster交換開關(guān)交換開關(guān)交換開關(guān)交換開關(guān)桌面主機機箱內(nèi)多計算機機群多處理機機群網(wǎng)絡(luò)RAM和VME 單板磁盤現(xiàn)代密碼學(xué)理論與實踐之五332022-

8、2-23標準互連網(wǎng)絡(luò)（2)現(xiàn)代密碼學(xué)理論與實踐之五342022-2-23使用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ù) 器工 作 站光 纖 擴 展 器光 纖 擴 展 器HiPPI交 換 開 關(guān)現(xiàn)代密碼學(xué)理論與實踐之五352022-2-23標準互連網(wǎng)絡(luò)（3） 現(xiàn)代密碼學(xué)理論與實踐之五362022-2-23雙向FDDI環(huán)作為主干網(wǎng) 文件服務(wù)

9、器數(shù)據(jù)庫服務(wù)器計算機服務(wù)器雙向 FDDI環(huán)FDDI集中器FDDI 集中器FDDI 集中器桌面計算機以太網(wǎng)集線器路由器現(xiàn)代密碼學(xué)理論與實踐之五372022-2-23標準互聯(lián)網(wǎng)絡(luò)（4）現(xiàn)代密碼學(xué)理論與實踐之五382022-2-23香港大學(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-4000SunUltraSPARC2/1

10、200Sun SPARC20/HS14以 太 網(wǎng)T3T1155Mb/sASX-1000ATM開 關(guān)T1T1155Mb/s155Mb/sSGI PowerChallenge(8CPU)32節(jié) 點 ）(現(xiàn)代密碼學(xué)理論與實踐之五392022-2-23標準互連網(wǎng)絡(luò)（5）現(xiàn)代密碼學(xué)理論與實踐之五402022-2-23并行計算機結(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/CLMNICDIRMBLDP/CMMBIOB(e)COWLD

11、P/CMMBIOB商品網(wǎng)絡(luò)(以太網(wǎng)，ATM，etc.)BridgeNICNICBridge現(xiàn)代密碼學(xué)理論與實踐之五412022-2-23并行計算機體系合一結(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現(xiàn)代密碼學(xué)理論與實踐之五422022-2-23五種結(jié)構(gòu)特性一覽表屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型MIMDMIMDMIMDMIMDMIMD處理器類型專用定制商用商用(可定

12、制)商用商用互連網(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，Alpha Farm現(xiàn)代密碼學(xué)理論與實

13、踐之五432022-2-23并行計算機訪存模型（1)P1P2PnI/OSM1SMm共享存儲器處理器（）系統(tǒng)互連總線 交叉開關(guān)多級,網(wǎng)絡(luò)現(xiàn)代密碼學(xué)理論與實踐之五442022-2-23并行計算機訪存模型（2)LM1P1LM2P2LMnPn互連網(wǎng)絡(luò)(a)共享本地存儲模型全局互連網(wǎng)絡(luò)(b)層次式機群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSM現(xiàn)代密碼學(xué)理論與實踐之五452022-2-23并行計算機訪存模型（3)互 連 網(wǎng) 絡(luò)DCPDCPDCP現(xiàn)代密碼學(xué)理論與實踐之五462022-2-23并行計算機訪存模型（4)I/ONIC,DIR,RC系統(tǒng)互連網(wǎng)路MemP

14、/CP/CI/ONIC,DIR,RCMemP/CP/C節(jié)點N節(jié)點1總線或交叉 開關(guān)總線或交叉 開關(guān)現(xiàn)代密碼學(xué)理論與實踐之五472022-2-23并行計算機訪存模型（5)消息傳遞互連網(wǎng)絡(luò)(網(wǎng)絡(luò)，環(huán)網(wǎng)，超立方，立方環(huán)等)PMPMMPMPMPMPMPPMPMPM.現(xiàn)代密碼學(xué)理論與實踐之五482022-2-23構(gòu)筑并行機系統(tǒng)的不同存儲結(jié)構(gòu)MIMDMIMD多計算機(多地址空間非共享存儲器)(IBM SP2,DEC TruClusterTandem Hymalaya,HP,Microsoft Wolfpack,etc)NORMANORMAUMAUMANUMANUMAClusterClusterMPPMPP

15、(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、儲器現(xiàn)代密碼學(xué)理論與實踐之五492022-2-23第二章 當代并行機系統(tǒng)現(xiàn)代密碼學(xué)理論與實踐之五502022-2-23對稱多處理機SMP(1)P / CS MS MI / O總線或交叉開關(guān)P / CP / C現(xiàn)代密碼學(xué)理論與實踐之五512022-2-23對稱多處理機SMP(2)現(xiàn)代密碼學(xué)理論與實踐之五522022-2-23大規(guī)模并行機MPPP/CLMNIC定 制 網(wǎng) 絡(luò)P/CLMNICMBMB現(xiàn)代密碼學(xué)理論與實踐之五532022-2-23典型MPP系統(tǒng)特性比較MPP模型Intel/Sandia ASCI Option RedIBM SP2SGI/Cray Origin2000一個大型樣機的配置

17、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分布共享主存和共享磁盤互連網(wǎng)絡(luò)和主存模型分離兩維網(wǎng)孔，NORMA

18、多級網(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現(xiàn)代密碼學(xué)理論與實踐之五542022-2-23MPP所用的高性能CPU特性比較屬性Pentium ProPowerPC 602Alpha 21164AUltra SPARC IIMIPS R10000工藝BiCMOSCMOSCMOSCMOSCMOS晶體管數(shù)5.5M/15.5M7M9.6

19、M5.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個單元超標量3路(Way)4路4路4路4路流水線深度14級48級79級9級57級SPECint 92366225500350300SPECfp 92283300

20、750550600SPECint 958.0922511N/A7.4SPECfp 956.7030017N/A15其它特性CISC/RISC混合短流水線長L1高速緩存最高時鐘頻率最大片上2級高速緩存多媒體和圖形指令MP機群總線可支持4個CPU現(xiàn)代密碼學(xué)理論與實踐之五552022-2-23機群型大規(guī)模并行機SP2NICDE 節(jié) 點 1NICDE 節(jié) 點S以 太 網(wǎng)PMCCMCCPPPN高 性 能Omega，網(wǎng) 絡(luò)開 關(guān)I/O總 線I/O總 線現(xiàn)代密碼學(xué)理論與實踐之五562022-2-23工作站機群COWP/CMMIOMIOMP/CNICNICDDLAN現(xiàn)代密碼學(xué)理論與實踐之五572022-2-2

21、3典型的機群系統(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 c a 、 M a r y l 、Penns:NSCP國家可擴放機群計劃：在通過因特網(wǎng)互連的3個本地機群系統(tǒng)上進行元計算Argonne:Globus在由ATM連接的北美17個站點的WAN上開發(fā)元計算平臺和軟件Sy

22、racuse:WWVM使用因特網(wǎng)和HPCC技術(shù)，在世界范圍的虛擬機上進行高性能計算HKU:Pearl Cluster研究機群在分布式多媒體和金融數(shù)字庫方面的應(yīng)用Virgina:Legion在國家虛擬計算機設(shè)施上開發(fā)元計算軟件現(xiàn)代密碼學(xué)理論與實踐之五582022-2-23SMPMPP機群比較系統(tǒng)特征SMPMPP機群節(jié)點數(shù)量(N)O(10)O(100)-O(1000)O(100)節(jié)點復(fù)雜度中粒度或細粒度細粒度或中粒度中粒度或粗粒度節(jié)點間通信 共享存儲器消息傳遞或共享變量（有DSM時）消息傳遞節(jié)點操作系統(tǒng)1N(微內(nèi)核)和1個主機OS(單一)N (希望為同構(gòu))支持單一系統(tǒng)映像永遠部分希望地址空間單一多

23、或單一（有DSM時）多個作業(yè)調(diào)度單一運行隊列主機上單一運行隊列協(xié)作多隊列網(wǎng)絡(luò)協(xié)議非標準非標準標準或非標準可用性通常較低低到中高可用或容錯性能/價格比一般一般高互連網(wǎng)絡(luò)總線/交叉開關(guān)定制商用現(xiàn)代密碼學(xué)理論與實踐之五592022-2-23第三章 并行計算性能評測現(xiàn)代密碼學(xué)理論與實踐之五602022-2-23CPU的某些基本性能指標TnTTTnTn11,max現(xiàn)代密碼學(xué)理論與實踐之五612022-2-23存儲器性能寄 存 器1級高 速 緩 存2級高 速 緩 存主 存磁 盤遠 程存 儲 器C2KBL=0周 期B=1-32GB/S4-256KB0-2周 期1-16GB/S64KB-4MB2-10周 期1

24、-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ù)：存儲粒度、一致性粒度、層管理方案等。存儲粒度、一致性粒度、層管理方案等。現(xiàn)代密碼學(xué)理論與實踐之五622022-2-23 影響存儲器容量影響存儲器容量C C設(shè)計因素：設(shè)計因素： 與主流應(yīng)用的進程數(shù)及各進程工作集尺寸等有關(guān)。與主流應(yīng)用的進程數(shù)及各進程工作集尺寸等有關(guān)。 影響存儲器延遲影響存儲器延遲L L設(shè)計因素：設(shè)計因素： 與

25、與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)。現(xiàn)代密碼學(xué)理論與實踐之五632022-2-23并行與通信開銷現(xiàn)代密碼學(xué)理論與實踐之五642022-2-23Ping-Pong Scheme現(xiàn)代密碼學(xué)理論與實踐之五652022-2-23并行開銷的表達式：點到點通信現(xiàn)代密碼學(xué)理論與實踐之五662022-2-23并行開銷的表達式：整體通信現(xiàn)代密碼學(xué)理論與實踐之五672022-2-23機器的成本、價格與性/價比現(xiàn)代密

26、碼學(xué)理論與實踐之五682022-2-23算法級性能評測現(xiàn)代密碼學(xué)理論與實踐之五692022-2-23Amdahl 定律現(xiàn)代密碼學(xué)理論與實踐之五702022-2-23Amdahl定律（contd)pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWfWWWpWWWWSOOOPSPS/) 1(1)1 (現(xiàn)代密碼學(xué)理論與實踐之五712022-2-23Amdahls law (contd)程序中順序部分的百分比f(c)0% 1% 2% 3% 4% 100%加速比SS1024=1024/(1+1023f)1024x91x48x31x24x1x WpWp Wp WpWp WpW1W

27、1W1W1W1W1工作負載W處理器數(shù)P (a)123456T1 T1 Tp Tp Tp Tp Tp Tp T1 T1 T1執(zhí)行時間T處理器數(shù)P (b)T1123456現(xiàn)代密碼學(xué)理論與實踐之五722022-2-23Gustafson定律 PSSSSWWpWpWpWppWpWpWS/) p-f (p-p) f ( p -f) p ( f S 111WWfpfWWWpWWSOOPSPS/11現(xiàn)代密碼學(xué)理論與實踐之五732022-2-23Gustafson定律（contd)程序中順序部分的百分比f(c)S1024=1024-1023f0%1%2%3%4%1024x1014x 1004x993x983x加速比S 處理器數(shù)P