并行计算概述1课件

并行计算并行计算结构结构算法算法编程编程国家高性能计算中心（合肥）22024/6/17并行计算并行计算结构结构算法算法编程编程第一篇第一篇 并行计算的基础并行计算的基础第一章第一章 并行计算机系统及其结构模型并行计算机系统及其结构模型第二章第二章 当代并行机系统：当代并行机系统：SMP、MPP和和Cluster第三章第三章 并行计算性能评测并行计算性能评测第二篇第二篇 并行算法的设计并行算法的设计第四章第四章 并行算法的设计基础并行算法的设计基础第五章第五章 并行算法的一般设计方法并行算法的一般设计方法第六章第六章 并行算法的基本设计技术并行算法的基本设计技术第七章第七章 并行算法的一般设计过程并行算法的一般设计过程国家高性能计算中心（合肥）32024/6/17并行计算并行计算结构结构算法算法编程编程第三篇第三篇 并行数值算法并行数值算法第八章第八章 基本通信操作基本通信操作第九章第九章 稠密矩阵运算稠密矩阵运算第十章第十章 线性方程组的求解线性方程组的求解第十一章第十一章 快速傅里叶变换快速傅里叶变换第四篇第四篇 并行程序设计并行程序设计第十二章第十二章 并行程序设计基础并行程序设计基础第十三章第十三章 并行程序设计模型和共享存储系统编程并行程序设计模型和共享存储系统编程第十四章第十四章 分布存储系统并行编程分布存储系统并行编程第十五章第十五章 并行程序设计环境与工具并行程序设计环境与工具国家高性能计算中心（合肥）42024/6/17第一章并行计算机系统及结构模型第一章并行计算机系统及结构模型1.1 并行计算并行计算1.1.1 并行计算与计算科学并行计算与计算科学1.1.2 当代科学与工程问题的计算需求当代科学与工程问题的计算需求1.2 并行计算机系统互连并行计算机系统互连1.2.1 系统互连系统互连1.2.2 静态互联网络静态互联网络1.2.3 动态互连网络动态互连网络1.2.4 标准互联网络标准互联网络1.3 并行计算机系统结构并行计算机系统结构1.3.1 并行计算机结构模型并行计算机结构模型1.3.2 并行计算机访存模型并行计算机访存模型国家高性能计算中心（合肥）52024/6/17并行计算并行计算并行计算：并行机上所作的计算，又称高性能计算或并行计算：并行机上所作的计算，又称高性能计算或超级计算。超级计算。三大学科：计算科学，理论科学和实验科学三大学科：计算科学，理论科学和实验科学 所有的学科都转向定量化和精确化。所有的学科都转向定量化和精确化。计算科学是一个交叉学科，用计算的方法来解决应计算科学是一个交叉学科，用计算的方法来解决应用问题。用问题。适用于理论模型复杂或尚未建立，实验费用昂贵或适用于理论模型复杂或尚未建立，实验费用昂贵或无法进行无法进行计算科学：计算物理、计算化学、计算生物学等计算科学：计算物理、计算化学、计算生物学等科学与工程问题的需求：气象预报、油藏模拟、核武科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。器数值模拟、航天器设计、基因测序等。需求类型：计算密集、数据密集、网络密集。需求类型：计算密集、数据密集、网络密集。国家高性能计算中心（合肥）62024/6/17国家高性能计算中心（合肥）72024/6/17国家高性能计算中心（合肥）82024/6/17并行计算并行计算美国美国HPCC计划：高性能计算和通信，重大挑战性课计划：高性能计算和通信，重大挑战性课题，题，3T性能性能美国美国Petaflops研究项目：研究项目：Pflop/s。美国美国ASCI计划：加速战略计算创新，核武器数值模计划：加速战略计算创新，核武器数值模拟。高性能拟。高性能国家高性能计算中心（合肥）92024/6/17国家高性能计算中心（合肥）102024/6/17国家高性能计算中心（合肥）112024/6/17国家高性能计算中心（合肥）122024/6/17国家高性能计算中心（合肥）132024/6/17国家高性能计算中心（合肥）142024/6/17高性能计算机高性能计算机Intel（Option Red)：1Tflops,1997,Pentium ProSGI(Option Blue Mountain):3Tflops,1998,MIPS10000IBM(Option White):7Tflops,Top4,2001,Power3日本日本Earth Simulator:35Tflops,Top1,2002,VPHewlett-Packard ASCI Q：7Tflops,Top2,3,2002,Alpha Server中国联想：中国联想：1Tflops,Top43,2002国家高性能计算中心（合肥）152024/6/17系统互连系统互连不同带宽与距离的互连技术不同带宽与距离的互连技术:总线、总线、SAN、LAN、MAN、WAN国家高性能计算中心（合肥）162024/6/17局部总线、局部总线、I/O总线、总线、SAN和和LAN国家高性能计算中心（合肥）172024/6/17网络性能指标网络性能指标节点度（节点度（Node Degree）：）：射入或射出一个节点的射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为边数。在单向网络中，入射和出射边之和称为节点度。节点度。网络直径（网络直径（Network Diameter）：）：网络中任何两网络中任何两个节点之间的最长距离，即最大路径数。个节点之间的最长距离，即最大路径数。对剖宽度（对剖宽度（Bisection Width）：对分网络各半所对分网络各半所必须移去的最少边数必须移去的最少边数对剖带宽（对剖带宽（Bisection Bandwidth）:每秒钟内，在最小的对剖每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称网络为对如果从任一节点观看网络都一样，则称网络为对称的（称的（Symmetry）国家高性能计算中心（合肥）182024/6/17静态互连网络静态互连网络 与动态互连网络与动态互连网络静态互连网络：处理单元间有着固定连接的一类静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。括总线、交叉开关和多级互连网络等。国家高性能计算中心（合肥）192024/6/17静态互连网络（静态互连网络（1）一维线性阵列（一维线性阵列（1-D Linear Array）：）：并行机中最简单、最基本的互连方式，并行机中最简单、最基本的互连方式，每个节点只与其左、右近邻相连，也叫二近邻连每个节点只与其左、右近邻相连，也叫二近邻连接，接，N个节点用个节点用N-1条边串接之，内节点度为条边串接之，内节点度为2，直径，直径为为N-1，对剖宽度为对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，结构上等同于环，环可以是单向的或双向的，其节点度恒为其节点度恒为2，直径或为，直径或为 （双向环）或为（双向环）或为N-1（单向环），对剖宽度为单向环），对剖宽度为2 国家高性能计算中心（合肥）202024/6/17静态互连网络（静态互连网络（2）二维网孔（二维网孔（2-D Mesh）：）：每个节点只与其上、下、左、右的近邻相连每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为（边界节点除外），节点度为4，网络直径，网络直径为为 ，对剖宽度为，对剖宽度为 在垂直方向上带环绕，水平方向呈蛇状，就变在垂直方向上带环绕，水平方向呈蛇状，就变成成Illiac网孔了，节点度恒为网孔了，节点度恒为4，网络直径为，网络直径为 ，而对剖宽度为，而对剖宽度为 垂直和水平方向均带环绕，则变成了垂直和水平方向均带环绕，则变成了2-D环绕环绕（2-D Torus），），节点度恒为节点度恒为4，网络直径为，网络直径为 ，对剖宽度为，对剖宽度为 国家高性能计算中心（合肥）212024/6/17静态互连网络（静态互连网络（3）二叉树：二叉树：除了根、叶节点，每个内节点只与其父节点和除了根、叶节点，每个内节点只与其父节点和两个子节点相连。两个子节点相连。节点度为节点度为3，对剖宽度为，对剖宽度为1，而树的直径为，而树的直径为 如果尽量增大节点度为，如果尽量增大节点度为，则直径缩小为则直径缩小为2，此，此时就变成了星形网络，其对剖宽度为时就变成了星形网络，其对剖宽度为传统二叉树的主要问题是根易成为通信瓶颈。传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。胖树节点间的通路自叶向根逐渐变宽。国家高性能计算中心（合肥）222024/6/17静态互连网络（静态互连网络（4）超立方超立方：一个一个n-立方由立方由 个顶点组成，个顶点组成，3-立方如图立方如图(a)所示；所示；4-立方如图立方如图(b)所示，由两个所示，由两个3-立立方的对应顶点连接而成。方的对应顶点连接而成。n-立方的节点度为立方的节点度为n，网络直径也是网络直径也是n，而对剖而对剖宽度为宽度为 。如果将如果将3-立方的每个顶点代之以一个环就构成立方的每个顶点代之以一个环就构成了如图了如图(d)所示的所示的3-立方环，此时每个顶点的立方环，此时每个顶点的度为度为3，而不像超立方那样节点度为，而不像超立方那样节点度为n。国家高性能计算中心（合肥）232024/6/17嵌入嵌入将网络中的各节点映射到另一个网络中去将网络中的各节点映射到另一个网络中去用膨胀（用膨胀（Dilation）系数来描述嵌入的质量，它是指）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数应所需的最大链路数 如果该系数为如果该系数为1，则称为完美嵌入。，则称为完美嵌入。环网可完美嵌入到环网可完美嵌入到2-D环绕网中环绕网中 超立方网可完美嵌入到超立方网可完美嵌入到2D环绕网中环绕网中 国家高性能计算中心（合肥）242024/6/17嵌入嵌入国家高性能计算中心（合肥）252024/6/17网网网网络络名称名称名称名称网网网网络规络规模模模模节节点度点度点度点度网网网网络络直径直径直径直径对对剖剖剖剖宽宽度度度度对对称称称称链链路数路数路数路数线线性性性性阵阵列列列列2 21 1非非非非环环形形形形2 2 （双（双（双（双向）向）向）向）2 2是是是是2-2-D D网孔网孔网孔网孔 4 4非非非非IlliacIlliac网孔网孔网孔网孔 4 4非非非非2-2-D D环绕环绕4 4是是是是二叉二叉二叉二叉树树3 31 1非非非非星形星形星形星形2 2非非非非超立方超立方超立方超立方 n n n n是是是是立方立方立方立方环环3 3是是是是静态互连网络特性比较静态互连网络特性比较国家高性能计算中心（合肥）262024/6/17动态互连网络动态互连网络(1)总线：总线：PCI、VME、Multics、Sbus、MicroChannel 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等国家高性能计算中心（合肥）272024/6/17动态互连网络动态互连网络（2）交叉开关（交叉开关（CrossbarCrossbar）：）：单级交换网络，可为每个端口提供更高的带宽。象电话交换机单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于一样，交叉点开关可由程序控制动态设置其处于“开开”或或“关关”状态，而能提供所有（源、目的）对之间的动态连接。状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于多计算机机群中的处理器间的通信；另一种是用于SMPSMP服务器服务器或向量超级计算机中处理器和存储器之间的存取。或向量超级计算机中处理器和存储器之间的存取。国家高性能计算中心（合肥）282024/6/17动态互联网络动态互联网络（3）单级交叉开关级联起来形成多级互连网络单级交叉开关级联起来形成多级互连网络MIN（Multistage Interconnection Network）国家高性能计算中心（合肥）292024/6/17动态互连网络（动态互连网络（4）交换开关模块：交换开关模块：一个交换开关模块有一个交换开关模块有n个输入和个输入和n个输出，每个个输出，每个输入可连接到任意输出端口，但只允许一对输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突因为这将发生输出冲突 级间互连（级间互连（Interstage Connection）：）：均匀洗牌、蝶网、多路均匀洗牌、交叉开关、均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接立方连接n输入的输入的网络需要网络需要 级级 开关，在开关，在Ilinois大学的大学的Cedar2多处理机系统中采用了多处理机系统中采用了网络网络 Cray Y/MP多级网络，该网络用来支持多级网络，该网络用来支持8个向量个向量处理器和处理器和256个存储器模块之间的数据传输。个存储器模块之间的数据传输。网络能够避免网络能够避免8个处理器同时进行存储器存个处理器同时进行存储器存取时的冲突。取时的冲突。国家高性能计算中心（合肥）302024/6/17动态互连网络比较动态互连网络比较 n,节点规模节点规模 w，数据宽度数据宽度动态动态互互互互连连网网网网络络的复的复的复的复杂杂度和度和度和度和带宽带宽性能一性能一性能一性能一览览表表表表网网网网络络特性特性特性特性总线总线系系系系统统多多多多级级互互互互连连网网网网络络交叉开关交叉开关交叉开关交叉开关硬件复硬件复硬件复硬件复杂杂度度度度每个每个每个每个处处理器理器理器理器带宽带宽 报报道的聚集道的聚集道的聚集道的聚集带宽带宽SunFireSunFire服服服服务务器器器器中的中的中的中的GigaplaneGigaplane总线总线：2.672.67GB/sGB/sIBM SP2IBM SP2中的中的中的中的512512节节点的点的点的点的HPSHPS：10.24GB/s10.24GB/sDigitalDigital的千兆开的千兆开的千兆开的千兆开关：关：关：关：3.43.4GB/sGB/s国家高性能计算中心（合肥）312024/6/17标准互联网络（标准互联网络（1）Myrinet:Myrinet是由是由Myricom公司设计的千兆位包交换公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。统互连成为一种商业产品。Myrinet是基于加州理工学院开发的多计算机是基于加州理工学院开发的多计算机和和VLSI技术以及在南加州大学开发的技术以及在南加州大学开发的ATOMIC/LAN技术。技术。Myrinet能假设任意拓扑能假设任意拓扑结构，不必限定为开关网孔或任何规则的结结构，不必限定为开关网孔或任何规则的结构。构。Myrinet在数据链路层具有可变长的包格式，在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。切通选路法以及定制的可编程的主机接口。在物理层上，在物理层上，Myrinet网使用全双工网使用全双工SAN链路，链路，最长可达最长可达3米，峰值速率为（米，峰值速率为（1.281.28）Gbps（目前有目前有2.56+2.56)Myrinet交换开关交换开关:8,12,16端口端口Myrinet主机接口主机接口:32位的称作位的称作LANai芯片的用芯片的用户定制的户定制的VLSI处理器，它带有处理器，它带有Myrinet接口、接口、包接口、包接口、DMA引擎和快速静态随机存取存储引擎和快速静态随机存取存储器器SRAM。140 of the November 2002 TOP500 use Myrinet,including 15 of the top 100 国家高性能计算中心（合肥）322024/6/17Myrinet连接的连接的LAN/Cluster国家高性能计算中心（合肥）332024/6/17标准互连网络（标准互连网络（2)高性能并行接口（高性能并行接口（HiPPI）Los Alamos国家实验室于国家实验室于1987年提出的一个标年提出的一个标准，其目的是试图统一来自不同产商生产的准，其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口。在大型机所有大型机和超级计算机的接口。在大型机和超级计算机工业界，和超级计算机工业界，HiPPI作为短距离的系作为短距离的系统到系统以及系统到外设连接的高速统到系统以及系统到外设连接的高速I/O通道。通道。1993年，年，ANSI X3T9.3委员会认可了委员会认可了HiPPI标准，标准，它覆盖了物理和数据链路层，但在这两层之它覆盖了物理和数据链路层，但在这两层之上的任何规定却取决于用户。上的任何规定却取决于用户。HiPPI是个单工的点到点的数据传输接口，其速是个单工的点到点的数据传输接口，其速率可达率可达800Mbps到到1.6Gbps。开发成功了一种能提供潜在的开发成功了一种能提供潜在的6.4Gbps速率，速率，比比HiPPI快快8倍且有很低时延的超级倍且有很低时延的超级HiPPI技术，技术，SGI公司和公司和Los Alamos国家实验室都开发了用来国家实验室都开发了用来构筑速率高达构筑速率高达25.6Gbps的的HiPPI交换开关的交换开关的HiPPI技术。技术。HiPPI通道和通道和HiPPI交换开关被用在交换开关被用在SGI Power Challenge服务器、服务器、IBM 390主机、主机、Cray Y/MP、C90和和T3D/T3E等系统等系统 国家高性能计算中心（合肥）342024/6/17使用使用HiPPI通道和开关构筑的通道和开关构筑的LAN主干主干网网 国家高性能计算中心（合肥）352024/6/17标准互连网络（标准互连网络（3）光纤通道光纤通道FC（Fiber Channel）:通道和网络标准的集成通道和网络标准的集成 光纤通道既可以是共享介质，也可以是一种交光纤通道既可以是共享介质，也可以是一种交换技术换技术 光纤通道操作速度范围可从光纤通道操作速度范围可从100到到133、200、400和和800Mbps。FCSI厂商也正在推出未来具厂商也正在推出未来具有更高速度（有更高速度（1、2或或4Gbps）的光纤通道的光纤通道 光纤通道的价值已被现在的某些千兆位局域网光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术所证实，这些局域网就是基于光纤通道技术的的 连网拓扑结构的灵活性是光纤通道的主要财富，连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、仲裁环及交换光纤连接它支持点到点、仲裁环及交换光纤连接 FDDI:光纤分布式数据接口光纤分布式数据接口FDDI（Fiber Distributed Data Interface）FDDI采用双向光纤令牌环可提供采用双向光纤令牌环可提供100-200Mbps数据传输速率数据传输速率 FDDI具有互连大量设备的能力具有互连大量设备的能力 传统的传统的FDDI仅以异步方式操作仅以异步方式操作 国家高性能计算中心（合肥）362024/6/17双向双向FDDI环作为主干网环作为主干网 国家高性能计算中心（合肥）372024/6/17标准互联网络（标准互联网络（4）ATM（Asynchronous Transfer Mode）:由成立于由成立于1991年的年的ATM论坛和论坛和ITU标准定义。标准定义。ATM是一种独立于介质的消息传输协议，它将是一种独立于介质的消息传输协议，它将消息段变成更短的固定长度为消息段变成更短的固定长度为53字节的报元字节的报元进行传输。进行传输。这种技术是基于报元交换机制。这种技术是基于报元交换机制。ATM的目的是的目的是将实时和突发数据的传输合并成单一的网络将实时和突发数据的传输合并成单一的网络技术。技术。ATM网络支持从网络支持从25到到51、155和和622Mbps不同不同的速率，其速率越低的速率，其速率越低ATM交换器和使用的链交换器和使用的链路价格越低。路价格越低。国家高性能计算中心（合肥）382024/6/17香港大学开发的香港大学开发的Pearl机群机群 国家高性能计算中心（合肥）392024/6/17标准互连网络（标准互连网络（5）代代代代别别类类型型型型以太网以太网以太网以太网10101010BaseTBaseTBaseTBaseT快速以太网快速以太网快速以太网快速以太网100100100100BaseTBaseTBaseTBaseT千兆位以太网千兆位以太网千兆位以太网千兆位以太网1 1 1 1GBGBGBGB引入年代引入年代引入年代引入年代198219821982198219941994199419941997199719971997速度（速度（速度（速度（带宽带宽）10101010Mb/sMb/sMb/sMb/s100100100100Mb/sMb/sMb/sMb/s1 1 1 1Gb/sGb/sGb/sGb/s最最最最大大大大距距距距离离离离UTRUTRUTRUTR（非屏蔽双扭非屏蔽双扭非屏蔽双扭非屏蔽双扭对对）100100100100m m m m100100100100m m m m25252525100100100100m m m mSTPSTPSTPSTP（屏蔽双扭屏蔽双扭屏蔽双扭屏蔽双扭对对）同同同同轴电缆轴电缆500500500500m m m m100100100100m m m m25252525100100100100m m m m多模光多模光多模光多模光纤纤2 2 2 2KmKmKmKm412412412412m m m m（半双工）半双工）半双工）半双工）2 2 2 2KmKmKmKm（全双工）全双工）全双工）全双工）500500500500m m m m单单模光模光模光模光纤纤25252525KmKmKmKm20202020KmKmKmKm3 3 3 3KmKmKmKm主要主要主要主要应应用用用用领领域域域域文件共享，文件共享，文件共享，文件共享，打印机共享打印机共享打印机共享打印机共享COWCOWCOWCOW计计算，算，算，算，C/SC/SC/SC/S结结构，构，构，构，大型数据大型数据大型数据大型数据库库存取等存取等存取等存取等大型大型大型大型图图像文件，像文件，像文件，像文件，多媒体，多媒体，多媒体，多媒体，因特网，因特网，因特网，因特网，内部网，内部网，内部网，内部网，数据数据数据数据仓库仓库等等等等国家高性能计算中心（合肥）402024/6/17并行计算机结构模型并行计算机结构模型 国家高性能计算中心（合肥）412024/6/17并行计算机体系合一结构并行计算机体系合一结构 SMP、MPP、DSM和和COW并行结构渐趋一致。并行结构渐趋一致。大量的节点通过高速网络互连起来大量的节点通过高速网络互连起来节点遵循节点遵循Shell结构：用专门定制的结构：用专门定制的Shell电路将商电路将商用微处理器和节点的其它部分（包括板级用微处理器和节点的其它部分（包括板级Cache、局存、局存、NIC和和DISK）连接起来。优点是连接起来。优点是CPU升升级只需要更换级只需要更换Shell。国家高性能计算中心（合肥）422024/6/17五种结构特性一览表五种结构特性一览表属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD处理器类型专用定制商用商用(可定制)商用商用互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（以太ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器Cray C-90，Cray T-90，银河1号IBM R50，SGI Power Challenge，曙光1号Intel Paragon，IBMSP2，曙光1000/2000Stanford DASH，Cray T 3DBerkeley NOW，Alpha Farm国家高性能计算中心（合肥）432024/6/17并行计算机访存模型（并行计算机访存模型（1)UMA（Uniform Memory Access）模型是均匀存模型是均匀存储访问模型的简称。其特点是：储访问模型的简称。其特点是：物理存储器被所有处理器均匀共享；物理存储器被所有处理器均匀共享；所有处理器访问任何存储字取相同的时间；所有处理器访问任何存储字取相同的时间；每台处理器可带私有高速缓存；每台处理器可带私有高速缓存；外围设备也可以一定形式共享。外围设备也可以一定形式共享。国家高性能计算中心（合肥）442024/6/17并行计算机访存模型（并行计算机访存模型（2)NUMA(Nonuniform Memory Access)模模型型是是非非均均匀存储访问模型的简称。特点是：匀存储访问模型的简称。特点是：被被共共享享的的存存储储器器在在物物理理上上是是分分布布在在所所有有的的处处理理器器中中的的，其其所所有有本本地地存存储储器器的的集集合合就就组组成成了了全局地址空间；全局地址空间；处处理理器器访访问问存存储储器器的的时时间间是是不不一一样样的的；访访问问本本地地存存储储器器LM或或群群内内共共享享存存储储器器CSM较较快快，而而访访问问外外地地的的存存储储器器或或全全局局共共享享存存储储器器GSM较慢较慢(此即非均匀存储访问名称的由来此即非均匀存储访问名称的由来)；每每台台处处理理器器照照例例可可带带私私有有高高速速缓缓存存，外外设设也也可可以某种形式共享。以某种形式共享。LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSM国家高性能计算中心（合肥）452024/6/17并行计算机访存模型（并行计算机访存模型（3)COMA(Cache-Only Memory Access)模模型型是是全全高高速缓存存储访问的简称。其特点是：速缓存存储访问的简称。其特点是：各各处处理理器器节节点点中中没没有有存存储储层层次次结结构构，全全部部高高速速缓存组成了全局地址空间；缓存组成了全局地址空间；利利用用分分布布的的高高速速缓缓存存目目录录D进进行行远远程程高高速速缓缓存存的访问的访问;COMA中中的的高高速速缓缓存存容容量量一一般般都都大大于于2 级级高高速速缓存容量；缓存容量；使使用用COMA时时，数数据据开开始始时时可可任任意意分分配配，因因为为在在运运行行时时它它最最终终会会被被迁迁移移到到要要用用到到它它们们的的地地方。方。国家高性能计算中心（合肥）462024/6/17并行计算机访存模型（并行计算机访存模型（4)CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是高速缓存一致性非均模型是高速缓存一致性非均匀存储访问模型的简称。其特点是：匀存储访问模型的简称。其特点是：大多数使用基于目录的高速缓存一致性协议；大多数使用基于目录的高速缓存一致性协议；保留保留SMP结构易于编程的优点，也改善常规结构易于编程的优点，也改善常规SMP的可扩放性；的可扩放性；CC-NUMA实际上是一个分布共享存储的实际上是一个分布共享存储的DSM多处理机系统；多处理机系统；它最显著的优点是程序员无需明确地在节点上它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的致性硬件会自动地将数据迁移至要用到它的地方。地方。国家高性能计算中心（合肥）472024/6/17并行计算机访存模型（并行计算机访存模型（5)NORMANORMA（No-Remote No-Remote Memory Memory AccessAccess）模模型型是是非非非非远远远远程程程程存存存存储储储储访访访访问问问问模模型型的的简简称。称。NORMANORMA的特点是：的特点是：所有存储器是私有的；所有存储器是私有的；绝大数绝大数NUMANUMA都不支持远程存储器的访问；都不支持远程存储器的访问；在在DSMDSM中，中，NORMANORMA就消失了。就消失了。国家高性能计算中心（合肥）482024/6/17构筑并行机系统的不同存储结构构筑并行机系统的不同存储结构国家高性能计算中心（合肥）492024/6/17第二章第二章 当代并行机系统当代并行机系统2.1 共享存储多处理机系统共享存储多处理机系统2.1.1 对称多处理机对称多处理机SMP结构特性结构特性2.2 分布存储多计算机系统分布存储多计算机系统2.2.1 大规模并行机大规模并行机MPP结构特性结构特性2.3 机群系统机群系统2.3.1 大规模并行处理系统大规模并行处理系统MPP机群机群SP22.3.2 工作站机群工作站机群COW国家高性能计算中心（合肥）502024/6/17对称多处理机对称多处理机SMP(1)SMP:采用商用微处理器，通常有片上和片外采用商用微处理器，通常有片上和片外Cache，基于总线连接，集基于总线连接，集中式共享存储，中式共享存储，UMA结构结构例子：例子：SGI Power Challenge,DEC Alpha Server,Dawning 1国家高性能计算中心（合肥）512024/6/17对称多处理机对称多处理机SMP(2)优点优点对称性对称性单地址空间，易编程性，动态负载平衡，无需显示数据分配单地址空间，易编程性，动态负载平衡，无需显示数据分配高速缓存及其一致性，数据局部性，硬件维持一致性高速缓存及其一致性，数据局部性，硬件维持一致性低通信延迟，低通信延迟，Load/Store完成完成问题问题欠可靠，欠可靠，BUS,OS,SM通信延迟（相对于通信延迟（相对于CPU），），竞争加剧竞争加剧慢速增加的带宽（慢速增加的带宽（MB double/3年年,IOB更慢）更慢）不可扩放性不可扩放性-CC-NUMA国家高性能计算中心（合肥）522024/6/17大规模并行机大规模并行机MPP成百上千个处理器组成的大规模计算机系统，规模是变化的。成百上千个处理器组成的大规模计算机系统，规模是变化的。NORMA结构，高带宽低延迟定制互连。结构，高带宽低延迟定制互连。可扩放性：可扩放性：Mem,I/O,平衡设计平衡设计系统成本：商用处理器，相对稳定的结构系统成本：商用处理器，相对稳定的结构(shell)，SMP节点节点,分布分布通用性和可用性：不同的应用，通用性和可用性：不同的应用，PVM,MPI,交互，批处理，互连对用户交互，批处理，互连对用户透明，单一系统映象，故障透明，单一系统映象，故障通信要求通信要求存储器和存储器和I/O能力能力例子：例子：Intel Option Red IBM SP2 Dawning 1000国家高性能计算中心（合肥）532024/6/17典型典型MPP系统特性比较系统特性比较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节点体系结构和数据存储器2个处理器，32到256MB主存，共享磁盘1个处理器，64MB到2GB本地主存，1GB到14.5GB本地磁盘2个处理器，64MB到256MB分布共享主存和共享磁盘互连网络和主存模型分离两维网孔，NORMA多级网络，NORMA胖超立方体网络，CC-NUMA节点操作系统轻量级内核（LWK）完全AIX（IBM UNIX）微内核Cellular IRIX自然编程机制基于PUMA Portals的MPIMPI和PVMPower C，Power Fortran其他编程模型Nx，PVM，HPFHPF，LindaMPI，PVM国家高性能计算中心（合肥）542024/6/17MPP所用的高性能所用的高性能CPU特性比较特性比较属性Pentium ProPowerPC 602Alpha 21164AUltra SPARC IIMIPS R10000工艺BiCMOSCMOSCMOSCMOSCMOS晶体管数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(片外)执行单元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国家高性能计算中心（合肥）552024/6/17机群型大规模并行机机群型大规模并行机SP2设计策略：设计策略：机群体系结构机群体系结构 标准环境标准环境 标准编程模型标准编程模型 系统可用性系统可用性 精选的单一系统映像精选的单一系统映像 系统结构：系统结构：高性能开关高性能开关 HPS 多级多级网络网络 宽节点、窄节点和窄节点宽节点、窄节点和窄节点2 国家高性能计算中心（合肥）562024/6/17工作站机群工作站机群COW分布式存储，分布式存储，MIMD，工作站工作站+商用互连网络，每个节点是一个完整的计算机，有商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而自己的磁盘和操作系统，而MPP中只有微内核中只有微内核优点：优点：投资风险小投资风险小系统结构灵活系统结构灵活性能性能/价格比高价格比高能充分利用分散的计算资源能充分利用分散的计算资源可扩放性好可扩放性好问题问题通信性能通信性能并行编程环境并行编程环境例子：例子：Berkeley NOW，Alpha Farm,FXCOWP/CMMIOMIOMP/CNICNICDDLAN国家高性能计算中心（合肥）572024/6/17典型的机群系统典型的机群系统典型的机群系统特点一览表名称系统特点Princeton:SHRIMPPC商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信Karsruhe:Parastation用于分布并行处理的有效通信网络和软件开发Rice:TreadMarks软件实现分布共享存储的工作站机群Wisconsin:Wind Tunnel在经由商用网络互连的工作站机群上实现分布共享存储Chica、Maryl、Penns:NSCP国家可扩放机群计划：在通过因特网互连的3个本地机群系统上进行元计算Argonne:Globus在由ATM连接的北美17个站点的WAN上开发元计算平台和软件Syracuse:WWVM使用因特网和HPCC技术，在世界范围的虚拟机上进行高性能计算HKU:Pearl Cluster研究机群在分布式多媒体和金融数字库方面的应用Virgina:Legion在国家虚拟计算机设施上开发元计算软件国家高性能计算中心（合肥）582024/6/17SMPMPP机群比较机群比较系统特征SMPMPP机群节点数量(N)O(10)O(100)-O(1000)O(100)节点复杂度中粒度或细粒度细粒度或中粒度中粒度或粗粒度节点间通信共享存储器消息传递或共享变量（有DSM时）消息传递节点操作系统1N(微内核)和1个主机OS(单一)N(希望为同构)支持单一系统映像永远部分希望地址空间单一多或单一（有DSM时）多个作业调度单一运行队列主机上单一运行队列协作多队列网络协议非标准非标准标准或非标准可用性通常较低低到中高可用或容错性能/价格比一般一般高互连网络总线/交叉开关定制商用国家高性能计算中心（合肥）592024/6/17第三章第三章 并行计算性能评测并行计算性能评测3.1 并行机的一些基本性能指标并行机的一些基本性能指标3.2 加速比性能定律加速比性能定律3.2.1 Amdahl定律定律3.2.2 Gustafson定律定律3.2.3 Sun和和Ni定律定律3.3 可扩放性评测标准可扩放性评测标准3.3.1 并行计算的可扩放性并行计算的可扩放性3.3.2 等效率度量标准等效率度量标准3.3.3 等速度度量标准等速度度量标准3.3.4 平均延迟度量标准平均延迟度量标准国家高性能计算中心（合肥）602024/6/17CPU的某些基本性能指标的某些基本性能指标工作负载工作负载执行时间执行时间 浮点运算数浮点运算数 指令数目指令数目 并行执行时间并行执行时间 T comput 为计算时间，为计算时间，T paro 为并行开为并行开销时间，销时间，T comm为相互通信时间为相互通信时间 T n=T comput+T paro+T comm 例：估计例：估计APRAM模型下执行时间模型下执行时间 国家高性能计算中心（合肥）612024/6/17存储器性能存储器性能存储器的层次结构存储器的层次结构(C,L,B)各层性能参数：各层性能参数：容量容量C C、延迟、延迟L L、带宽、带宽B B。相关参数：相关参数：存储粒度、一致性粒度、层管理方案等。存储粒度、一致性粒度、层管理方案等。国家高性能计算中心（合肥）622024/6/17 影响存储器容量影响存储器容量C C设计因素：设计因素：与主流应用的进程数及各进程工作集尺寸等有关。与主流应用的进程数及各进程工作集尺寸等有关。影响存储器延迟影响存储器延迟L L设计因素：设计因素：与与CPUCPU指令系统指令系统CPICPI及指令所需数据量等有关。及指令所需数据量等有关。影响存储器带宽影响存储器带宽B B设计因素：设计因素：与应用的数据通信量、通信频率和延迟与应用的数据通信量、通信频率和延迟L L等有关。等有关。国家高性能计算中心（合肥）632024/6/17并行与通信开销并行与通信开销并行和通信开销：相对于计算很大。并行和通信开销：相对于计算很大。PowerPC (每个周期每个周期 15ns 执行执行4flops;创建一个进程创建一个进程1.4ms 可执行可执行372000flops)开销的测量：乒开销的测量：乒-乓方法（乓方法（Ping-Pong Scheme）节节点点0发送发送m个字节给节点个字节给节点1；节点；节点1从节点从节点0接收接收m个字节后，立即将消息发回节点个字节后，立即将消息发回节点0。总的时间除。总的时间除以以2，即可得到点到点通信时间，也就是执行单，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。一发送或接收操作的时间。可一般化为热土豆法（可一般化为热土豆法（Hot-Potato），），也称为救火也称为救火队法（队法（Fire-Brigade)01 2 -n-1 0 国家高性能计算中心（合肥）642024/6/17Ping-Pong Schemeif（my _node _id=0）then/*发送者发送者*/start _time=second（）send an m-byte message to node 1 receive an m-byte message from node 1end_time=second（）total_time=end_time start_time communication_timei=total_time/2 else if（my_node_id=1）then /*接收者接收者*/receive an m-byte message from node 0 send an m-byte message to node 0endif国家高性能计算中心（合肥）652024/6/17并行开销的表达式：点到点通信并行开销的表达式：点到点通信通信开销通信开销 t(m)=t0+m/r通信启动时间通信启动时间 t0渐近渐近带宽带宽r：传送无限长的消息时的通信速率传送无限长的消息时的通信速率半半峰值长度峰值长度m1/2：达到一半渐近带宽所要的消息：达到一半渐近带宽所要的消息长度长度特定性能特定性能0：表示短消息带宽：表示短消息带宽 t0=m1/2/r=1/0国家高性能计算中心（合肥）662024/6/17并行开销的表达式：整体通信并行开销的表达式：整体通信典型的整体通信有：典型的整体通信有：播送（播送（Broadcasting）：）：处理器处理器0发送发送m个字节个字节给所有的给所有的n个处理器个处理器收集（收集（Gather）：）：处理处理0接收所有接收所有n个处理器发个处理器发来在消息，所以处理器来在消息，所以处理器0最终接收了最终接收了m n个字个字节；节；散射（散射（Scatter）：）：处理器处理器0发送了发送了m个字节的不个字节的不同消息给所有同消息给所有n个处理器，因此处理器个处理器，因此处理器0最终最终发送了发送了m n个字节；个字节；全交换（全交换（Total Exchange）：）：每个处理器均彼此每个处理器均彼此相互发送相互发送m个字节的不同消息给对方，所以个字节的不同消息给对方，所以总通信量为总通信量为mn2个字节；个字节；循环移位（循环移位（Circular-shift）：）：处理器处理器i发送发送m个个字节给处理器字节给处理器i+1，处理器处理器n-1发送发送m个字节给个字节给处理器处理器0，所以通信量为，所以通信量为m n个字节。个字节。国家高性能计算中心（合肥）672024/6/17机器的成本、价格与性机器的成本、价格与性/价比价比机器的成本与价格机器的成本与价格机器的性能机器的性能/价格比价格比 Performance/Cost Ratio：系系指用单位代价（通常以百万美元表示）所获取指用单位代价（通常以百万美元表示）所获取的性能（通常以的性能（通常以MIPS或或MFLOPS表示）每秒执行表示）每秒执行的指令数的指令数 利用率（利用率（Utilization）：）：可达到的速度与峰值速度可达到的速度与峰值速度之比之比 国家高性能计算中心（合肥）682024/6/17算法级性能评测算法级性能评测加速比性能定律加速比性能定律并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。Amdahl 定律定律Gustafson定律定律Sun Ni定律定律可扩放性评测标准可扩放性评测标准等效率度量标准等效率度量标准等速度度量标准等速度度量标准平均延迟度量标准平均延迟度量标准国家高性能计算中心（合肥）692024/6/17Amdahl 定律定律P：处理器数；处理器数；W：问题规模（问题规模（计算负载、工作负载，给定问题的总计算量计算负载、工作负载，给定问题的总计算量）；）；Ws：应用程序中的串行分量，应用程序中的串行分量，f是串行分量比例（是串行分量比例（f=Ws/W，Ws=W1）；）；WP：应用程序中可并行化部分，应用程序中可并行化部分，1-f为并行分量比为并行分量比例；例；Ws+W p=W；Ts=T1：串行执行时间，串行执行时间，T p：并行执行时间；并行执行时间；S：加速比，加速比，E：效率；效率；出发点：出发点：固定不变的计算负载；固定不变的计算负载；固定的计算负载分布在多个处理器上的，固定的计算负载分布在多个处理器上的，增加处理器加快执行速度，从而达到了加速的目增加处理器加快执行速度，从而达到了加速的目的。的。国家高性能计算中心（合肥）702024/6/17Amdahl定律（定律（contd)固定负载的加速公式：固定负载的加速公式：W s+W p可相应地表示为可相应地表示为f+（1-f）p时，上式极限为：时，上式极限为：S=1/f W o为额外开销为额外开销 国家高性能计算中心（合肥）712024/6/17Amdahls law(contd)国家高性能计算中心（合肥）722024/6/17Gustafson定律定律 出发点：出发点：对于很多大型计算，精度要求很高，即在此类对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持算量，相应地亦必须增多处理器数才能维持时间不变；时间不变；除非学术研究，在实际应用中没有必要固定工除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才上，增多处理器必须相应地增大问题规模才有实际意义。有实际意义。Gustafson加速定律加速定律:并行开销并行开销W o：国家高性能计算中心（合肥）732024/6/17Gustafson定律（定律（contd)国家高性能计算中心（合肥）742024/6/17Sun 和和 Ni定律定律 基本思想：基本思想：只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。时可能使执行时间略有增加）。假定在单节点上使用了全部存储容量假定在单节点上使用了全部存储容量M并在相应于并在相应于W的时间内求解之，的时间内求解之，此时工作负载此时工作负载W=fW+（1-f）W。在在p 个节点的并行系统上，能够求解较大规模的问题是因为存储容量可个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到增加到pM。令因子令因子G（p）反应存储容量增加到反应存储容量增加到p倍时并行工作负载的倍时并行工作负载的增加量，所以扩大后的工作负载增加量，所以扩大后的工作负载W=fW+（1-f）G（p）W。存储受限的加速公式存储受限的加速公式：并行开销并行开销W o:国家高性能计算中心（合肥）752024/6/17Sun 和和 Ni定律定