《并行计算概述》PPT课件

《《并行计算概述》PPT课件》由会员分享，可在线阅读，更多相关《《并行计算概述》PPT课件（84页珍藏版）》请在装配图网上搜索。

1、并行计算,,第一级,,第二级,,第三级,,第一级,,第二级,,第三级,,国家高性能计算中心（合肥）,*,*,并行计算,——,结构•算法•编程,并行计算——结构,•,算法,•,编程,第一篇 并行计算的基础,,第一章 并行计算机系统及其结构模型,,第二章 当代并行机系统：,SMP、MPP,和,Cluster,,第三章 并行计算性能评测,,,第二篇 并行算法的设计,,第四章 并行算法的设计基础,,第五章 并行算法的一般设计方法,,第六章 并行算法的基本设计技术,,第七章 并行算法的一般设计过程,2024/10/7,2,,国家高性能计算中心（合肥）,并行计算——结构,•,算法,•,编程,第三篇 并行数

2、值算法,,第八章 基本通信操作,,第九章 稠密矩阵运算,,第十章 线性方程组的求解,,第十一章 快速傅里叶变换,,,第四篇 并行程序设计,,第十二章 并行程序设计基础,,第十三章 并行程序设计模型和共享存储系统编程,,第十四章 分布存储系统并行编程,,第十五章 并行程序设计环境与工具,2024/10/7,3,,国家高性能计算中心（合肥）,第一章并行计算机系统及结构模型,,1.1 并行计算,,1.1.1,并行计算与计算科学,,1.1.2 当代科学与工程问题的计算需求,,1.2,并行计算机系统互连,,1.2.1 系统互连,,1.2.2 静态互联网络,,1.2.3 动态互连网络,,1.2.4,标准

3、互联网络,,1.3 并行计算机系统结构,,1.3.1,并行计算机结构模型,,1.3.2 并行计算机访存模型,2024/10/7,4,,国家高性能计算中心（合肥）,并行计算,,并行计算：并行机上所作的计算，又称高性能计算或超级计算。,,三大学科：计算科学，理论科学和实验科学,,所有的学科都转向定量化和精确化。,,计算科学是一个交叉学科，用计算的方法来解决应用问题。,,,适用于理论模型复杂或尚未建立，实验费用昂贵或无法进行,,计算科学：计算物理、计算化学、计算生物学等,,科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。,,需求类型：计算密集、数据密集、网络密集。,

4、2024/10/7,5,,国家高性能计算中心（合肥）,2024/10/7,6,,国家高性能计算中心（合肥）,2024/10/7,7,,国家高性能计算中心（合肥）,并行计算,,,美国,HPCC,计划：高性能计算和通信，重大挑战性课题，3,T,性能,,美国,Petaflops,研究项目：,Pflop/s,。,,美国,ASCI,计划：加速战略计算创新，核武器数值模拟。高性能,2024/10/7,8,,国家高性能计算中心（合肥）,2024/10/7,9,,国家高性能计算中心（合肥）,2024/10/7,10,,国家高性能计算中心（合肥）,2024/10/7,11,,国家高性能计算中心（合肥）,2024

5、/10/7,12,,国家高性能计算中心（合肥）,2024/10/7,13,,国家高性能计算中心（合肥）,高性能计算机,,Intel（Option Red)： 1Tflops,1997,Pentium Pro,,SGI(Option Blue Mountain): 3Tflops,1998,MIPS10000,,IBM(Option White): 7Tflops,Top4,2001,Power3,,日本,Earth Simulator: 35Tflops,Top1,2002,VP,,Hewlett-Packard ASCI Q： 7Tflops ,Top2,3,200

6、2, Alpha Server,,中国联想： 1,Tflops,Top43,2002,,,2024/10/7,14,,国家高性能计算中心（合肥）,系统互连,,不同带宽与距离的互连技术: 总线、,SAN、LAN、MAN、WAN,2024/10/7,15,,国家高性能计算中心（合肥）,局部总线、,I/O,总线、,SAN,和,LAN,,2024/10/7,16,,国家高性能计算中心（合肥）,网络性能指标,,节点度（,Node Degree）：,射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。,,网络直径（,Network Diameter）：,网络中任何两个节点

7、之间的最长距离，即最大路径数。,,对剖宽度（,Bisection Width） ：,对分网络各半所必须移去的最少边数,,对剖带宽（,Bisection Bandwidth）:,每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数,,如果从任一节点观看网络都一样，则称网络为对称的（,Symmetry）,2024/10/7,17,,国家高性能计算中心（合肥）,静态互连网络 与动态互连网络,,静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等,,动态网络：用交

8、换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。,,2024/10/7,18,,国家高性能计算中心（合肥）,静态互连网络（1）,,一维线性阵列（1-,D Linear Array）：,,并行机中最简单、最基本的互连方式，,,每个节点只与其左、右近邻相连，也叫二近邻连接，,,N,个节点用,N-1,条边串接之，内节点度为2，直径为,N-1，,对剖宽度为1,,当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为,,（双向环）或为,N-1（,单向环），对剖宽度为2,2024/10/7,19,,国

9、家高性能计算中心（合肥）,静态互连网络（2）,,二维网孔（2-,D Mesh）：,,每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为 ，对剖宽度为,,在垂直方向上带环绕，水平方向呈蛇状，就变成,Illiac,网孔了，节点度恒为4，网络直径为 ，而对剖宽度为,,垂直和水平方向均带环绕，则变成了2-,D,环绕（2-,D,Torus,），,节点度恒为4，网络直径为 ，对剖宽度为,2024/10/7,20,,国家高性能计算中心（合肥）,静态互连网络（3）,,二叉树：,,除了根、叶节点，每个内节点只与其父节点和两个子节

10、点相连。,,节点度为3，对剖宽度为1，而树的直径为,,如果尽量增大节点度为， 则直径缩小为2，此时就变成了星形网络，其对剖宽度为,,传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。,2024/10/7,21,,国家高性能计算中心（合肥）,静态互连网络（4）,,超立方 ：,,一个,n-,立方由 个顶点组成，3-立方如图(,a),所示；4-立方如图(,b),所示，由两个3-立方的对应顶点连接而成。,,n-,立方的节点度为,n，,网络直径也是,n ，,而对剖宽度为 。,,如果将3-立方的每个顶点代之以一个环就构成了如图(,d),所示的3-立

11、方环，此时每个顶点的度为3，而不像超立方那样节点度为,n。,2024/10/7,22,,国家高性能计算中心（合肥）,嵌入,,将网络中的各节点映射到另一个网络中去,,用,膨胀,（,Dilation,）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数,,如果该系数为,1,，则称为完美嵌入。,,,环网可完美嵌入到,2-D,环绕网中,,超立方网可完美嵌入到,2,－,D,环绕网中,,,2024/10/7,23,,国家高性能计算中心（合肥）,嵌入,,,2024/10/7,24,,国家高性能计算中心（合肥）,网络名称,网络规模,节点度,网络直径,对剖宽度,对称,链路数

12、,线性阵列,,2,,1,非,,环形,,2,（双向）,2,是,,2-,D,网孔,,4,,,非,,Illiac,网孔,,4,,,非,,2-,D,环绕,,4,,,是,,二叉树,,3,,1,非,,星形,,,2,,非,,超立方,,,n,n,,是,,立方环,,3,,,是,,静态互连网络特性比较,,2024/10/7,25,,国家高性能计算中心（合肥）,动态互连网络 (1),,总线：,PCI、VME、Multics、Sbus、MicroChannel,,,多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等,2024/10/7,26,,国家

13、高性能计算中心（合肥）,动态互连网络 （2）,,交叉开关（,Crossbar）：,,单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。,,交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于,SMP,服务器或向量超级计算机中处理器和存储器之间的存取。,2024/10/7,27,,国家高性能计算中心（合肥）,动态互联网络 （3）,,单级交叉开关级联起来形成多级互连网络,MIN（Multistage Interconnection Network

14、）,,,2024/10/7,28,,国家高性能计算中心（合肥）,动态互连网络（4）,,交换开关模块：,,,一个交换开关模块有,n,个输入和,n,个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突,,级间互连（,Interstage,Connection ）：,,均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接,,n,输入的,Ω,网络需要 级 开关，在,Ilinois,大学的,Cedar[2],多处理机系统中采用了,Ω,网络,,Cray Y/MP,多级网络，该网络用来支持8个向量处理器和256个存储器模块之间的

15、数据传输。网络能够避免8个处理器同时进行存储器存取时的冲突。,2024/10/7,29,,国家高性能计算中心（合肥）,动态互连网络比较,,n,,节点规模,w，,数据宽度,动态互连网络的复杂度和带宽性能一览表,,,,网络特性,总线系统,多级互连网络,交叉开关,硬件复杂度,,,,每个处理器带宽,,,～,,,报道的聚集带宽,SunFire,服务器中的,Gigaplane,总线：2.67,GB/s,IBM SP2,中的512节点的,HPS：10.24GB/s,Digital,的千兆开关：3.4,GB/s,2024/10/7,30,,国家高性能计算中心（合肥）,标准互联网络（1）,,Myrinet,:,

16、,Myrinet,是由,Myricom,公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。,,Myrinet,是基于加州理工学院开发的多计算机和,VLSI,技术以及在南加州大学开发的,ATOMIC/LAN,技术。,Myrinet,能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。,,Myrinet,在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，,Myrinet,网使用全双工,SAN,链路，最长可达3米，峰值速率为（1.28＋1.28）,Gbps,（,目前有2.56+2.56),,M

17、yrinet,交换开关 :8,12,16端口,,Myrinet,主机接口 : 32位的称作,LANai,芯片的用户定制的,VLSI,处理器，它带有,Myrinet,接口、包接口、,DMA,引擎和快速静态随机存取存储器,SRAM。,,140,of the November 2002 TOP500 use,Myrinet,, including 15 of the top 100,,2024/10/7,31,,国家高性能计算中心（合肥）,Myrinet,连接的,LAN/Cluster,,,2024/10/7,32,,国家高性能计算中心（合肥）,标准互连网络（2,),,高性能并行接口（,HiPPI,

18、）,,Los Alamos,国家实验室于1987年提出的一个标准，其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口。在大型机和超级计算机工业界，,HiPPI,作为短距离的系统到系统以及系统到外设连接的高速,I/O,通道。,,1993年，,ANSI X3T9.3,委员会认可了,HiPPI,标准，它覆盖了物理和数据链路层，但在这两层之上的任何规定却取决于用户。,,HiPPI,是个单工的点到点的数据传输接口，其速率可达800,Mbps,到1.6,Gbps,。,,开发成功了一种能提供潜在的6.4,Gbps,速率，比,HiPPI,快8倍且有很低时延的超级,HiPPI,技术，,,SGI,公司

19、和,Los Alamos,国家实验室都开发了用来构筑速率高达25.6,Gbps,的,HiPPI,交换开关的,HiPPI,技术。,,HiPPI,通道和,HiPPI,交换开关被用在,SGI Power Challenge,服务器、,IBM 390,主机、,Cray Y/MP、C90,和,T3D/T3E,等系统,,2024/10/7,33,,国家高性能计算中心（合肥）,使用,HiPPI,通道和开关构筑的,LAN,主干网,,2024/10/7,34,,国家高性能计算中心（合肥）,标准互连网络（3）,,光纤通道,FC（Fiber Channel） :,,通道和网络标准的集成,,光纤通道既可以是共享介质，

20、也可以是一种交换技术,,光纤通道操作速度范围可从100到133、200、400和800,Mbps。FCSI,厂商也正在推出未来具有更高速度（1、2或4,Gbps,）,的光纤通道,,光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术的,,连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、仲裁环及交换光纤连接,,FDDI :,,光纤分布式数据接口,FDDI（Fiber Distributed Data Interface）,,FDDI,采用双向光纤令牌环可提供100-200,Mbps,数据传输速率,,FDDI,具有互连大量设备的能力,,传统的,FDDI,仅以异步方

21、式操作,2024/10/7,35,,国家高性能计算中心（合肥）,双向,FDDI,环作为主干网,,2024/10/7,36,,国家高性能计算中心（合肥）,标准互联网络（4）,,ATM（Asynchronous Transfer Mode）:,,由成立于1991年的,ATM,论坛和,ITU,标准定义。,,ATM,是一种独立于介质的消息传输协议，它将消息段变成更短的固定长度为53字节的报元进行传输。,,这种技术是基于报元交换机制。,ATM,的目的是将实时和突发数据的传输合并成单一的网络技术。,,ATM,网络支持从25到51、155和622,Mbps,不同的速率，其速率越低,ATM,交换器和使用的链路

22、价格越低。,,2024/10/7,37,,国家高性能计算中心（合肥）,香港大学开发的,Pearl,机群,,2024/10/7,38,,国家高性能计算中心（合肥）,标准互连网络（5）,,代别,,类型,,以太网,,10,BaseT,快速以太网,,100,BaseT,千兆位以太网,,1,GB,引入年代,,1982,1994,1997,速度（带宽）,,10,Mb/s,100,Mb/s,1,Gb/s,最,,大,,距,,离,UTR（,非屏蔽双扭对）,100,m,100,m,25－100,m,,STP（,屏蔽双扭对）,,同轴电缆,500,m,100,m,25－100,m,,多模光纤,2,Km,412,m（,

23、半双工）,,2,Km（,全双工）,500,m,,单模光纤,25,Km,20,Km,3,Km,主要应用领域,,文件共享，,,打印机共享,COW,计算，,,C/S,结构，,,大型数据库存取等,大型图像文件，,,多媒体，,,因特网，,,内部网，,,数据仓库等,2024/10/7,39,,国家高性能计算中心（合肥）,并行计算机结构模型,,2024/10/7,40,,国家高性能计算中心（合肥）,并行计算机体系合一结构,,SMP、MPP、DSM,和,COW,并行结构渐趋一致。,,大量的节点通过高速网络互连起来,,节点遵循,Shell,结构：用专门定制的,Shell,电路将商用微处理器和节点的其它部分（包括

24、板级,Cache、,局存、,NIC,和,DISK）,连接起来。优点是,CPU,升级只需要更换,Shell。,2024/10/7,41,,国家高性能计算中心（合肥）,五种结构特性一览表,,属性,,PVP,,SMP,,MPP,,DSM,,COW,,结构类型,,MIMD,,MIMD,,MIMD,,MIMD,,MIMD,,处理器类型,,专用定制,,商用,,商用,(,可定制,),,商用,,商用,,互连网络,,定制交叉开关,,总线、交叉开关,,定制网络,,定制网络,,商用网络（以太,ATM,）,,通信机制,,共享变量,,共享变量,,消息传递,,共享变量,,消息传递,,地址空间,,单地址空间,,单地址空间,

25、,多地址空间,,单地址空间,,多地址空间,,系统存储器,,集中共享,,集中共享,,分布非共享,,分布共享,,分布非共享,,访存模型,,UMA,,UMA,,NORMA,,NUMA,,NORMA,,代表机器,,Cray C-90,，,,Cray T-90,，,,银河,1,号,,IBM R50,，,SGI Power Challenge,，,,曙光,1,号,,Intel Paragon,，,IBMSP2,，,曙光,1000/2000,,Stanford DASH,，,Cray T 3D,,Berkeley NOW,，,Alpha Farm,,2024/10/7,42,,国家高性能计算中心（合肥）,并

26、行计算机访存模型（1),,UMA,（,Uniform Memory Access,）,模型是均匀存储访问模型的简称。其特点是：,,物理存储器被所有处理器均匀共享；,,所有处理器访问任何存储字取相同的时间；,,每台处理器可带私有高速缓存；,,外围设备也可以一定形式共享。,2024/10/7,43,,国家高性能计算中心（合肥）,并行计算机访存模型（2),,NUMA(Nonuniform,Memory Access),模型是,非均匀存储访问,模型的简称。特点是：,,被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；,,处理器访问存储器的时间是不一样的；访问本

27、地存储器,LM,或群内共享存储器,CSM,较快，而访问外地的存储器或全局共享存储器,GSM,较慢,(,此即非均匀存储访问名称的由来,),；,,每台处理器照例可带私有高速缓存，外设也可以某种形式共享。,,LM,1,P,1,LM,2,P,2,LM,n,P,n,互,连,网,络,(,a),共享本地存储模型,全局互连网络,(,b),层次式机群模型,GSM,GSM,GSM,…,…,…,…,P,C,I,N,CSM,P,P,CSM,CSM,群1,…,…,P,C,I,N,CSM,群,N,P,P,CSM,CSM,…,…,2024/10/7,44,,国家高性能计算中心（合肥）,并行计算机访存模型（3),,COMA(

28、Cache-Only Memory Access),模型是,全高速缓存存储访问,的简称。其特点是：,,各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；,,利用分布的高速缓存目录,D,进行远程高速缓存的访问;,,COMA,中的高速缓存容量一般都大于,2,级高速缓存容量；,,使用,COMA,时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用到它们的地方。,,2024/10/7,45,,国家高性能计算中心（合肥）,并行计算机访存模型（4),,CC-NUMA,（,Coherent-Cache,Nonuniform,Memory Access,）,模型是,高速缓存一致性非均匀存储

29、访问,模型的简称。其特点是：,,大多数使用基于目录的高速缓存一致性协议；,,保留,SMP,结构易于编程的优点，也改善常规,SMP,的可扩放性；,,CC-NUMA,实际上是一个分布共享存储的,DSM,多处理机系统；,,它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。,,2024/10/7,46,,国家高性能计算中心（合肥）,并行计算机访存模型（5),,NORMA（No-Remote Memory Access）,模型是,非远程存储访问,模型的简称。,NORMA,的特点是：,,所有存储器

30、是私有的；,,绝大数,NUMA,都不支持远程存储器的访问；,,在,DSM,中，,NORMA,就消失了。,,2024/10/7,47,,国家高性能计算中心（合肥）,构筑并行机系统的不同存储结构,,2024/10/7,48,,国家高性能计算中心（合肥）,第二章 当代并行机系统,,2.1 共享存储多处理机系统,,2.1.1,对称多处理机,SMP,结构特性,,2.2 分布存储多计算机系统,,2.2.1,大规模并行机,MPP,结构特性,,2.3 机群系统,,2.3.1 大规模并行处理系统,MPP,机群,SP2,,2.3.2,工作站机群,COW,2024/10/7,49,,国家高性能计算中心（合肥）,对称

31、多处理机,SMP(1),,SMP:,采用商用微处理器，通常有片上和片外,Cache，,基于总线连接，集中式共享存储，,UMA,结构,,例子：,SGI Power Challenge, DEC Alpha Server,Dawning 1,2024/10/7,50,,国家高性能计算中心（合肥）,对称多处理机,SMP(2),,优点,,对称性,,单地址空间，易编程性，动态负载平衡，无需显示数据分配,,高速缓存及其一致性，数据局部性，硬件维持一致性,,低通信延迟，,Load/Store,完成,,问题,,欠可靠，,BUS,OS,SM,,通信延迟（相对于,CPU），,竞争加剧,,慢速增加的带宽（,MB d

32、ouble/3,年,,IOB,更慢）,,不可扩放性---〉,CC-NUMA,,2024/10/7,51,,国家高性能计算中心（合肥）,大规模并行机,MPP,,成百上千个处理器组成的大规模计算机系统，规模是变化的。,,NORMA,结构，高带宽低延迟定制互连。,,可扩放性：,Mem,, I/O,,平衡设计,,系统成本：商用处理器，相对稳定的结构,(shell),，,SMP,节点,,,分布,,通用性和可用性：不同的应用，,PVM,MPI,,交互，批处理，互连对用户透明，单一系统映象，故障,,通信要求,,存储器和,I/O,能力,,例子：,Intel Option Red,,,IBM SP2 Dawn

33、ing 1000,2024/10/7,52,,国家高性能计算中心（合肥）,典型,MPP,系统特性比较,,MPP,模型,,Intel/,Sandia,ASCI Option Red,,IBM SP2,,SGI/Cray Origin2000,,一个大型样机的配置,,9072,个处理器，,1.8,Tflop/s(NSL,),,400,个处理器，,100,Gflop/s(MHPCC,),,128,个处理器，,51,Gflop/s(NCSA,),,问世日期,,1996,年,12,月,,1994,年,9,月,,1996,年,10,月,,处理器类型,,200,MHz, 200Mflop/s Pentium

34、 Pro,,67,MHz,，,267Mflop/s POWER2,,200,MHz,，,400Mflop/s MIPS R10000,,节点体系结构,,和数据存储器,,2,个处理器，,32,到,256,MB,主存，共享磁盘,,1,个处理器，,64,MB,到,2,GB,本地主存，,1,GB,到,14.5,GB,本地磁盘,,2,个处理器，,64,MB,到,256,MB,分布共享主存和共享磁盘,,互连网络和主存模型,,分离两维网孔，,NORMA,,多级网络，,NORMA,,胖超立方体网络，,CC-NUMA,,节点操作系统,,轻量级内核（,LWK,）,,完全,AIX,（,IBM UNIX,）,,微内核

35、,Cellular IRIX,,自然编程机制,,基于,PUMA Portals,的,MPI,,MPI,和,PVM,,Power C,，,Power Fortran,,其他编程模型,,Nx,，,PVM,，,HPF,,HPF,，,Linda,,MPI,，,PVM,,2024/10/7,53,,国家高性能计算中心（合肥）,MPP,所用的高性能,CPU,特性比较,,属性,,Pentium Pro,,PowerPC 602,,Alpha 21164A,,Ultra SPARC II,,MIPS R10000,,工艺,,BiCMOS,,CMOS,,CMOS,,CMOS,,CMOS,,晶体管数,,5.5,M

36、/15.5M,,7,M,,9.6,M,,5.4,M,,6.8,M,,时钟频率,,150,MHz,,133,MHz,,417,MHz,,200,MHz,,200,MHz,,电压,,2.9,V,,3.3,V,,2.2,V,,2.5,V,,3.3,V,,功率,,20,W,,30,W,,20,W,,28,W,,30,W,,字长,,32,位,,64,位,,64,位,,64,位,,64,位,,I/O,,高速缓存,,8,KB/8KB,,32,KB/32KB,,8,KB/8KB,,16,KB/16KB,,32,KB/32KB,,2,级,,高速缓存,,256,KB,,(,多芯片模块,),,1~128,MB,,(

37、,片外,),,96,KB,,(,片上,),,16,MB,,(,片外,),,16,MB,,(,片外,),,执行单元,,5,个单元,,6,个单元,,4,个单元,,9,个单元,,5,个单元,,超标量,,3,路,(,Way),,4,路,,4,路,,4,路,,4,路,,流水线深度,,14,级,,4~8,级,,7~9,级,,9,级,,5~7,级,,SPECint,92,,366,,225,,>500,,350,,300,,SPECfp,92,,283,,300,,>750,,550,,600,,SPECint,95,,8.09,,225,,>11,,N/A,,7.4,,SPECfp,95,,6.70,,3

38、00,,>17,,N/A,,15,,其它特性,,CISC/RISC,混合,,短流水线长,L1,高速缓存,,最高时钟频率最大片上,2,级高速缓存,,多媒体和图形指令,,MP,机群总线可支持,4,个,CPU,,2024/10/7,54,,国家高性能计算中心（合肥）,机群型大规模并行机,SP2,,设计策略：,,机群体系结构,,标准环境,,标准编程模型,,系统可用性,,精选的单一系统映像,,系统结构：,,高性能开关,HPS,多级,Ω,网络,,宽节点、窄节点和窄节点2,2024/10/7,55,,国家高性能计算中心（合肥）,工作站机群,COW,,分布式存储，,MIMD，,工作站+商用互连网络，每个节点是

39、一个完整的计算机，有自己的磁盘和操作系统，而,MPP,中只有微内核,,优点：,,投资风险小,,系统结构灵活,,性能/价格比高,,能充分利用分散的计算资源,,可扩放性好,,问题,,通信性能,,并行编程环境,,,例子：,Berkeley NOW，Alpha Farm, FXCOW,,,,P/C,M,MIO,MIO,M,P/C,NIC,NIC,D,D,LAN,2024/10/7,56,,国家高性能计算中心（合肥）,典型的机群系统,,典型的机群系统特点一览表,,名称,,系统特点,,Princeton:SHRIMP,,PC,商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信,,Karsruhe:P

40、arastation,,用于分布并行处理的有效通信网络和软件开发,,Rice:TreadMarks,,软件实现分布共享存储的工作站机群,,Wisconsin:Wind Tunnel,,在经由商用网络互连的工作站机群上实现分布共享存储,,Chica,、,Maryl,、,Penns:NSCP,,国家可扩放机群计划：在通过因特网互连的,3,个本地机群系统上进行元计算,,Argonne:Globus,,在由,ATM,连接的北美,17,个站点的,WAN,上开发元计算平台和软件,,Syracuse:WWVM,,使用因特网和,HPCC,技术，在世界范围的虚拟机上进行高性能计算,,HKU:Pearl Clus

41、ter,,研究机群在分布式多媒体和金融数字库方面的应用,,Virgina:Legion,,在国家虚拟计算机设施上开发元计算软件,,2024/10/7,57,,国家高性能计算中心（合肥）,SMP\MPP\,机群比较,,系统特征,,SMP,,MPP,,机群,,节点数量,(,N),,,O(10),,O(100)-O(1000),,,O(100),,节点复杂度,,中粒度或细粒度,,细粒度或中粒度,,中粒度或粗粒度,,节点间通信,,,,共享存储器,,消息传递,,或共享变量（有,DSM,时）,,消息传递,,节点操作系统,,1,,N(,微内核,),,和,1,个主机,OS(,单一,),,N (,希望为同构

42、,),,支持单一系统映像,,永远,,部分,,希望,,地址空间,,单一,,多或单一（有,DSM,时）,,多个,,作业调度,,单一运行队列,,主机上单一运行队列,,协作多队列,,网络协议,,非标准,,非标准,,标准或非标准,,可用性,,通常较低,,低到中,,高可用或容错,,性能,/,价格比,,一般,,一般,,高,,互连网络,,总线,/,交叉开关,,定制,,商用,,2024/10/7,58,,国家高性能计算中心（合肥）,第三章 并行计算性能评测,,3.1 并行机的一些基本性能指标,,3.2 加速比性能定律,,3.2.1,Amdahl,定律,,3.2.2,Gustafson,定律,,3.2.3,Sun

43、,和,Ni,定律,,3.3 可扩放性评测标准,,3.3.1 并行计算的可扩放性,,3.3.2 等效率度量标准,,3.3.3 等速度度量标准,,3.3.4 平均延迟度量标准,2024/10/7,59,,国家高性能计算中心（合肥）,CPU,的某些基本性能指标,,工作负载,,执行时间,,浮点运算数,,指令数目,,,并行执行时间,T,,comput,,为计算时间，,T,paro,,为并行开销时间，,T,comm,为相互通信时间,,,T,n,= T,,comput,+ T,,paro,+ T,,comm,,,,例：估计,APRAM,模型下执行时间,,,2024/10/7,60,,国家高性能计算中心（合肥

44、）,存储器性能,,存储器的层次结构,(,C,L,B),,各层性能参数,：,容量,C,、,延迟,L,、,带宽,B,。,,,相关参数：,存储粒度、一致性粒度、层管理方案等。,2024/10/7,61,,国家高性能计算中心（合肥）,影响存储器容量,C,设计因素,：,,,与主流应用的进程数及各进程工作集尺寸等有关。,影响存储器延迟,L,设计因素,：,,与,CPU,指令系统,CPI,及指令所需数据量等有关。,影响存储器带宽,B,设计因素,：,,与应用的数据通信量、通信频率和延迟,L,等有关。,2024/10/7,62,,国家高性能计算中心（合肥）,并行与通信开销,,并行和通信开销：相对于计算很大。,,,

45、PowerPC (,每个周期,15,ns,执行,4,flops;,,,创建一个进程,1.4,ms,可执行,372000,flops),,开销的测量：乒,--,乓方法（,Ping-Pong Scheme）,节点,0,发送,m,个字节给节点,1,；节点,1,从节点,0,接收,m,个字节后，立即将消息发回节点,0,。总的时间除以,2,，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。,,可一般化为热土豆法（,Hot-Potato），,也称为救火队法（,Fire-Brigade) 0——1 —— 2 —— … —— -n-1 —— 0,,,2024/10/7,63,,国家高性能计算

46、中心（合肥）,Ping-Pong Scheme,,if （my _node _id =0） then /*,发送者*,/,,,start _time =second（ ）,,send an m-byte message to node 1,,receive an m-byte message from node 1,,end_time = second（ ）,,total_time = end_time – start_time,,communication_time[i] = total_time/2,,else if （my_node_id = 1） then /*,接收者*,/,,

47、,receive an m-byte message from node 0,,send an m-byte message to node 0,,,endif,,2024/10/7,64,,国家高性能计算中心（合肥）,并行开销的表达式：点到点通信,,通信开销,,t,(,m,) =,t,0,+,m,/,r,∞,,通信启动时间,t,0,,渐近,带宽,r,∞,,：,传送无限长的消息时的通信速率,,,半,峰值长度,m,1/2,：达到一半渐近带宽所要的消息长度,,特定性能,π,0,：表示短消息带宽,,,t,0,= m,1/2,/,,r,∞,= 1 /,π,0,2024/10/7,65,,国家高性能计

48、算中心（合肥）,并行开销的表达式：整体通信,,典型的整体通信有：,,,播送（,Broadcasting）：,处理器,0,发送,m,个字节给所有的,n,个处理器,,收集（,Gather）：,处理,0,接收所有,n,个处理器发来在消息，所以处理器,0,最终接收了,m n,个字节；,,散射（,Scatter）：,处理器,0,发送了,m,个字节的不同消息给所有,n,个处理器，因此处理器,0,最终发送了,m n,个字节；,,全交换（,Total Exchange）：,每个处理器均彼此相互发送,m,个字节的不同消息给对方，所以总通信量为,mn,2,个字节；,,循环移位（,Circular-shift）：,

49、处理器,i,发送,m,个字节给处理器,i+1，,处理器,n-1,发送,m,个字节给处理器,0,，所以通信量为,m n,个字节。,2024/10/7,66,,国家高性能计算中心（合肥）,机器的成本、价格与性,/,价比,,机器的成本与价格,,机器的性能,/,价格比,Performance/Cost Ratio ：,系指用单位代价（通常以百万美元表示）所获取的性能（通常以,MIPS,或,MFLOPS,表示）每秒执行的指令数,,利用率（,Utilization）：,可达到的速度与峰值速度之比,,2024/10/7,67,,国家高性能计算中心（合肥）,算法级性能评测,,加速比性能定律,,并行系统的加速比

50、是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。,,Amdahl,定律,,Gustafson,定律,,Sun Ni,定律,,可扩放性评测标准,,等效率度量标准,,等速度度量标准,,平均延迟度量标准,2024/10/7,68,,国家高性能计算中心（合肥）,Amdahl,定律,,P：,处理器数；,,W：,问题规模（,计算负载、工作负载，给定问题的总计算量,）；,,W,s,：,应用程序中的串行分量，,f,是串行分量比例（,f = W,s,/W， W,s,=W,1,）；,,W,P,：,应用程序中可并行化部分，,1-,f,为并行分量比例；,,W

51、,s,+W,p,=W；,,T,s,=T,1,：,串行执行时间，,T,p,：,并行执行时间；,,S：,加速比，,E：,效率；,,出发点：,,固定不变的计算负载；,,固定的计算负载分布在多个处理器上的，,,增加处理器加快执行速度，从而达到了加速的目的。,2024/10/7,69,,国家高性能计算中心（合肥）,Amdahl,定律,（,cont‘d),,固定负载的加速公式：,,,,W,s,+ W,p,可相应地表示为,f+（1-f）,,,,,,p→∞,时，上式极限为：,S= 1 / f,,W,o,为额外开销,,2024/10/7,70,,国家高性能计算中心（合肥）,Amdahl’s law (cont’

52、d),,2024/10/7,71,,国家高性能计算中心（合肥）,Gustafson,定律,,出发点：,,对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；,,除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。,,,Gustafson,加速定律,:,,,,并行开销,W,o,：,,2024/10/7,72,,国家高性能计算中心（合肥）,Gustafson,定律（,cont‘d),,2024/10/7,73,,

53、国家高性能计算中心（合肥）,Sun,和,Ni,定律,,基本思想：,,只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。,,假定在单节点上使用了全部存储容量,M,并在相应于,W,的时间内求解之，此时工作负载,W=,fW,+ （1-f）W。,,在,p,个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到,pM,。,令因子,G（p）,反应存储容量增加到,p,倍时并行工作负载的增加量，所以扩大后的工作负载,W =,fW,+ （1-f）G（p）W。,,存储受限的加速公式 ：,,,,,并行开销,W,o,:,2024/10/7,74,,国家高性能计算中心（

54、合肥）,Sun,和,Ni,定律,(,cont’d),,G（p）=1,时就是,Amdahl,加速定律；,,,G（p）=p,变为,f + p（1-f），,就是,Gustafson,加速定律,,G（p）>p,时，相应于计算机负载比存储要求增加得快，此时,Sun,和,N i,加速均比,Amdahl,加速和,Gustafson,加速为高。,2024/10/7,75,,国家高性能计算中心（合肥）,加速比讨论,,参考的加速经验公式：,p/log p≤S≤P,,线性加速比：很少通信开销的矩阵相加、内积运算等,,p/log p,的加速 比：分治类的应用问题,,通信密集类的应用问题 ：,S = 1 / C （ p

55、 ）,,超线性加速,,绝对加速：最佳并行算法与串行算法,,相对加速：同一算法在单机和并行机的运行时间,,2024/10/7,76,,国家高性能计算中心（合肥）,可扩放性评测标准,,并行计算的可扩放性（,Scalability）,也是主要性能指标,,可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理器数的增加而按比例提高的能力,,影响加速比的因素：处理器数与问题规模,,求解问题中的串行分量,,并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）,,加大的处理器数超过了算法中的并发程度,,增加问题的规模有利于提高加速的因素：,,较大的问题规模可提供较高的并发

56、度；,,额外开销的增加可能慢于有效计算的增加；,,算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题规模的增大而缩小）。,,增加处理器数会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。,2024/10/7,77,,国家高性能计算中心（合肥）,可扩放性评测标准（,cont‘d),,可扩放性,:,调整什么和按什么比例调整,,并行计算要调整的是处理数,p,和问题规模,W，,,两者可按不同比例进行调整，此比例关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。,,并行

57、算法和体系结构,,可扩放性研究的主要目的：,,确定解决某类问题用何种并行算法与何种并行体系结构的组合，可以有效地利用大量的处理器,(,算法与结构的组合,),；,,对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能；,,对固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大的加速比；,,用于指导改进并行算法和并行机体系结构，以使并行算法尽可能地充分利用可扩充的大量处理器,,目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准,2024/10/7,78,,国家高性能计算中心（合肥）,等效率度量标准,,令,t,ie,,和,t,,io,,分别是并行系统上第,

58、i,个处理器的有用计算时间和额外开销时间（包括通信、同步和空闲等待时间等）,,,,T,p,,是,p,个处理器系统上并行算法的运行时间，对于任意,i,显然有,T,p,= t,ie,+t,,io,，,且,T,e,+ T,o,=,pT,p,,问题的规模,W,为最佳串行算法所完成的计算,量,W=T,e,,,,,如果问题规模,W,保持不变，处理器数,p,增加，开销,T,o,增大，效率,E,下降。为了维持一定的效率（介于,0与1,之间），当处理,数,p,增大时，需要相应地增大问题规模,W,的值。由此定义函数,f,E,（p）,为问题规模,W,随处理器数,p,变化的函数，为等效率函数（,ISO-efficie

59、ncy Function）（Kumar1987）,2024/10/7,79,,国家高性能计算中心（合肥）,等效率度量标准（,cont‘d),,曲线,1,表示算法具有很好的扩放性；曲线,2,表示算法是可扩放的；曲线,3,表示算法是不可扩放的。,,优点：简单可定量计算的、少量的参数计算等效率函数,,缺点：如果,T,o,无法计算出（在共享存储并行机中）,,2024/10/7,80,,国家高性能计算中心（合肥）,等速度度量标准,,p,表示处理器个数，,W,表示要求解问题的工作量或称问题规模（在此可指浮点操作个数），,T,为并行执行时间，定义并行计算的速度,V,为工作量,W,除以并行时间,T,,p,个处

60、理器的并行系统的平均速度定义为并行速度,V,除以处理器个数,p：,,,W,是使用,p,个处理器时算法的工作量，令,W’,表示当处理数从,p,增大到,p’,时，为了保持整个系统的平均速度不变所需执行的工作量，则可得到处理器数从,p,到,p’,时平均速度可扩放度量标准公式,2024/10/7,81,,国家高性能计算中心（合肥）,等速度度量标准（,cont’d）,,优点：直观地使用易测量的机器性能速度指标来度量,,缺点：某些非浮点运算可能造成性能的变化,,,2024/10/7,82,,国家高性能计算中心（合肥）,平均延迟度量标准,,T,i,为,P,i,的执行时间，包括延迟,L,i,，Pi,的总延迟时间为“,L i+,启动时间,+,停止时间”。定义系统平均延迟时间为,,,,pT,para,=T,o,+ T,s,,,,,,在,p,个处理器上求解工作量为,W,问题的平均延迟,,在,p’,个处理器上求解工作量为,W’,问题的平均延迟当处理器数由,p,变到,p’，,而推持并行执行效率不变，则定义平均延迟可扩放性度量标准为,2024/10/7,83,,国家高性能计算中心（合肥）,平均延迟度量标准（,Cont’d),,优点：平均延迟能在更低层次上衡量机器的性能,,缺点：需要特定的软硬件才能获得平均延迟,,,2024/10/7,84,,国家高性能计算中心（合肥）,