并行计算ppt课件

1、并行计算1;.;.22021-11-17并行计算结构算法编程;.32021-11-17并行计算结构算法编程;.42021-11-17第一章并行计算机系统及结构模型;.52021-11-17并行计算;.62021-11-17高性能计算机;.72021-11-17系统互连局 部 总 线I/O总 线SCIHiPPIMyrinet千 兆 位以 太 网光 纤通 道快 速 以 太 网以 太 网10 Base TFDDIATM总 线 或 开 关SANLANMANWAN100Gb/s10Gb/s1Gb/s100Mb/s10Mb/sIsoEnet网络带宽交 叉 开 关MIN 或100 Base T;.82021

2、-11-17局部总线、I/O总线、SAN和LANPMI/O桥磁盘SAN(e.g.Myrinet)LAN(e.g.以太网,FDDI)系统 III/O总线,接口系统 I处理器总线局部总线,存储器总线SCSI节点 2节点N系统总线节点 1;.92021-11-17网络性能指标;.102021-11-17静态互连网络 与动态互连网络;.112021-11-17静态互连网络（1）2/N;.122021-11-17静态互连网络（2）) 1(2NN1NN22/2NN2NN (a)2-D网孔(b)Illiac网孔(c)2-D环绕;.132021-11-17静态互连网络（3）1log2N2/N(a)二叉树(b)

3、星形连接(c)二叉胖树;.142021-11-17静态互连网络（4）nN22/N(b)4-立 方(a)3-立 方(c)顶 点 代 之 以 环(d)3-立 方 环;.152021-11-17嵌入;.162021-11-17嵌入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 00 00 01 11 11 11 10 01 11 11 10 00 01 10

4、 00 00 01 10 00 01 11 11 11 11 11 11 11 10 01 10 01 10 01 10 01 11 1;.172021-11-17NNNNNN NN NN nN2kkN21N1N2/N) 1(2N1N2/2N1log2N2/12kkNN2N22/N2/N)2/(kN1NN)(2NN N2N21N1N2/nN2/3N静态互连网络特性比较;.182021-11-17动态互连网络 (1)L MI O C本 地 总 线高 速 缓 存C P UI FI FI F存 储 器 总 线存 储 器 单 元I FI FC P U 板存 储 器 板I / O 板通 信 板系 统 总

5、 线( 底 板 上 )数 据 总 线缓 冲C CI O P数 据 总 线网 络( 以 太 网 等 )磁 盘 和 磁 带部 件打 印 机或 绘 图 仪本 地 外 围 设 备( S C S I 总 线 )M CI F缓 冲;.192021-11-17动态互连网络 （2） ;.202021-11-17动态互联网络 （3）0101010101010101(a)4种可能的开关连接000001010011100101110111输入000001010011100101110111输出第0级第1级第2级(b)一种8输入的Omega网络;.212021-11-17动态互连网络（4） n2log22;.2220

6、21-11-17动态互连网络比较 )(wnO)log(wnnOk)(2wnO)/(nwfO)(wfO)(wfO)(wfO;.232021-11-17标准互联网络（1）;.242021-11-17Myrinet连接的LAN/Cluster交换开关交换开关交换开关交换开关桌面主机机箱内多计算机机群多处理机机群网络RAM和VME 单板磁盘;.252021-11-17标准互连网络（2);.262021-11-17使用HiPPI通道和开关构筑的LAN主干网 HiPPI交 换 开 关超 级 计 算 机帧 缓 冲 器RGB显 示 器HiPPI串 行文 件服 务 器工 作 站小 型 机大 规 模 并 行处 理

7、 系 统25米300米25米25米HiPPI串 行300米直 至 10千 米300米HiPPI串 行存 储 器服 务 器工 作 站光 纤 扩 展 器光 纤 扩 展 器HiPPI交 换 开 关;.272021-11-17标准互连网络（3） ;.282021-11-17双向FDDI环作为主干网 文件服务器数据库服务器计算机服务器双向 FDDI环FDDI集中器FDDI 集中器FDDI 集中器桌面计算机以太网集线器路由器;.292021-11-17标准互联网络（4）;.302021-11-17香港大学开发的Pearl机群 ASX-200BXLAX-20HARNETPower集 线 器 7000IBMS

8、P2城 市 大 学 的 WS池浸 会 大 学的 WS池USC的IMSCXL服 务 器PCFDDIPC和WS去 USA主 干 因 特 网SunE-6000服 务 器(8 CPU)以 太 网工 作 站 池HP服 务 器SunE-4000SunUltraSPARC2/1200Sun SPARC20/HS14以 太 网T3T1155Mb/sASX-1000ATM开 关T1T1155Mb/s155Mb/sSGI PowerChallenge(8CPU)32节 点 ）(;.312021-11-17标准互连网络（5）;.322021-11-17并行计算机结构模型 P/CLMNIC定制网络(c)MPPP/CL

9、MNICMBMBVPSM交叉开关(a)PVPVPVPSMSMP/CSMSMI/O总线或交叉开关(b)SMPP/CP/CP/CLMNICDIRMB定制网络(d)DSMP/CLMNICDIRMBLDP/CMMBIOB(e)COWLDP/CMMBIOB商品网络(以太网，ATM，etc.)BridgeNICNICBridge;.332021-11-17并行计算机体系合一结构 CPNIC(a)无 共 享NIC互 连 网 络MD节 点N节 点1Shell共 享 磁 盘CPNIC(b)共 享 磁 盘NICM互 连 网 络节 点N节 点1ShellCP互 连 网 络共 享 存 储 器共 享 磁 盘(c)共 享

10、 存 储CPShellShell;.342021-11-17五种结构特性一览表属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD处理器类型专用定制商用商用商用商用互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（ 以 太ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单 地 址 空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器Cray C-90，Cray T-90，银 河 1号I B M R50，SGI P o w e r Chal

11、lenge，曙 光 1号Intel Paragon， IBMSP2，曙光1000/2000Stanford D A S H ，Cray T 3DBerkeley N O W ，A l p h a Farm;.352021-11-17并行计算机访存模型（1)P1P2PnI/OSM1SMm共享存储器处理器（）系统互连总线 交叉开关多级,网络;.362021-11-17并行计算机访存模型（2)LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSM;.372021-11-17并行

12、计算机访存模型（3)互 连 网 络DCPDCPDCP;.382021-11-17并行计算机访存模型（4)I/ONIC,DIR,RC系统互连网路MemP/CP/CI/ONIC,DIR,RCMemP/CP/C节点N节点1总线或交叉开关总线或交叉 开关;.392021-11-17并行计算机访存模型（5)消息传递互连网络(网络，环网，超立方，立方环等)PMPMMPMPMPMPMPPMPMPM.;.402021-11-17构筑并行机系统的不同存储结构MIMDMIMD多计算机(多地址空间非共享存储器)(IBM SP2,DEC TruClusterTandem Hymalaya,HP,Microsoft W

13、olfpack,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-NUMANCC-NUMA(Cray T3E)DSMDSM(TreadMarks,Wind

14、 Tunnel,IVY,Shrimp,etc.)（）松散耦合（）中央存储器分布存储器多处理机单地址共享（）空间存储器;.412021-11-17第二章 当代并行机系统;.422021-11-17对称多处理机SMP(1)P / CS MS MI / O总线或交叉开关P / CP / C;.432021-11-17对称多处理机SMP(2);.442021-11-17大规模并行机MPPP/CLMNIC定 制 网 络P/CLMNICMBMB;.452021-11-17典型MPP系统特性比较MPP模型Intel/Sandia ASCI Option RedIBM SP2SGI/Cray Origin20

15、00一个大型样机的配置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节点体系结构和数据存储器2个处理器，32到256MB主存，共享磁盘1个处理器，64MB到2GB本地主存，1GB到14.5GB本地磁盘2个处理器，64MB到256MB分布共享主存和共享磁盘互连网络和主存模型分

16、离两维网孔，NORMA多级网络，NORMA胖超立方体网络，CC-NUMA节点操作系统轻量级内核（LWK）完全AIX（IBM UNIX）微内核Cellular IRIX自然编程机制基于PUMA Portals的MPIMPI和PVMPower C， Power Fortran其他编程模型Nx，PVM，HPFHPF，LindaMPI，PVM;.462021-11-17MPP所用的高性能CPU特性比较属性Pentium ProPowerPC 602Alpha 21164AUltra SPARC IIMIPS R10000工艺BiCMOSCMOSCMOSCMOSCMOS晶体管数5.5M/15.5M7M9

17、.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(片外)执行单元5个单元6个单元4个单元9个单元5个单元超标量3路(Way)4路4路4路4路流水线深度14级48级79级9级57级SPECint 92366225500350300SPECfp 922833

18、00750550600SPECint 958.0922511N/A7.4SPECfp 956.7030017N/A15其它特性CISC/RISC混合短流水线长L1高速缓存最高时钟频率最大片上2级高速缓存多媒体和图形指令MP机群总线可支持4个CPU;.472021-11-17机群型大规模并行机SP2NICDE 节 点 1NICDE 节 点S以 太 网PMCCMCCPPPN高 性 能Omega，网 络开 关I/O总 线I/O总 线;.482021-11-17工作站机群COWP/CMMIOMIOMP/CNICNICDDLAN;.492021-11-17典型的机群系统典型的机群系统特点一览表名称系统特

19、点Princeton:SHRIMPPC商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信Karsruhe:Parastation用于分布并行处理的有效通信网络和软件开发Rice:TreadMarks软件实现分布共享存储的工作站机群Wisconsin:Wind Tunnel在经由商用网络互连的工作站机群上实现分布共享存储C h i c a 、 M a r y l 、Penns:NSCP国家可扩放机群计划：在通过因特网互连的3个本地机群系统上进行元计算Argonne:Globus在由ATM连接的北美17个站点的WAN上开发元计算平台和软件Syracuse:WWVM使用因特网和HPCC技术，在

20、世界范围的虚拟机上进行高性能计算HKU:Pearl Cluster研究机群在分布式多媒体和金融数字库方面的应用Virgina:Legion在国家虚拟计算机设施上开发元计算软件;.502021-11-17SMPMPP机群比较系统特征SMPMPP机群节点数量(N)O(10)O(100)-O(1000)O(100)节点复杂度中粒度或细粒度细粒度或中粒度中粒度或粗粒度节点间通信 共享存储器消息传递或共享变量（有DSM时）消息传递节点操作系统1N(微内核)和1个主机OS(单一)N (希望为同构)支持单一系统映像永远部分希望地址空间单一多或单一（有DSM时）多个作业调度单一运行队列主机上单一运行队列协作多

21、队列网络协议非标准非标准标准或非标准可用性通常较低低到中高可用或容错性能/价格比一般一般高互连网络总线/交叉开关定制商用;.512021-11-17第三章 并行计算性能评测;.522021-11-17CPU的某些基本性能指标TnTTTnTn11,max;.532021-11-17存储器性能寄 存 器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-

22、100GB100-100K周 期1-300MB/S;.542021-11-17并行与通信开销;.552021-11-17Ping-Pong Scheme;.562021-11-17并行开销的表达式：点到点通信;.572021-11-17并行开销的表达式：整体通信;.582021-11-17机器的成本、价格与性/价比;.592021-11-17算法级性能评测;.602021-11-17Amdahl 定律;.612021-11-17Amdahl定律（contd)pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWfWWWpWWWWSOOOPSPS/) 1(1)1 (;.62

23、2021-11-17Amdahls law (contd)程序中顺序部分的百分比f(c)0% 1% 2% 3% 4% 100%加速比SS1024=1024/(1+1023f)1024x91x48x31x24x1x WpWp Wp WpWp WpW1W1W1W1W1W1工作负载W处理器数P (a)123456T1 T1 Tp Tp Tp Tp Tp Tp T1 T1 T1执行时间T处理器数P (b)T1123456;.632021-11-17Gustafson定律 PSSSSWWpWpWpWppWpWpWS/) p-f (p-p) f ( p -f) p ( f S 111WWfpfWWWpWWSOOPSPS/11;.642021-11-17Gustafson定律（contd)程序中顺序部分的百分比f(c)S1024=1024-1023f0%1%2%3%4%1024x1014x 1004x993x983x加速比S 处理器数P工作负载W (a)W1W1W1W1W1W1