并行计算结构算法编程2021/5/231并行计算结构算法编程 第一篇第一篇 并行计算的基础并行计算的基础 第一章第一章 并行计算机系统及其结构模型并行计算机系统及其结构模型 第二章第二章 当代并行机系统：当代并行机系统：SMPSMP、MPPMPP和和ClusterCluster 第三章第三章 并行计算性能评测并行计算性能评测 第二篇第二篇 并行算法的设计并行算法的设计 第四章第四章 并行算法的设计基础并行算法的设计基础 第五章第五章 并行算法的一般设计方法并行算法的一般设计方法 第六章第六章 并行算法的基本设计技术并行算法的基本设计技术 第七章第七章 并行算法的一般设计过程并行算法的一般设计过程2021/5/232并行计算结构算法编程 第三篇第三篇 并行数值算法并行数值算法 第八章第八章 基本通信操作基本通信操作 第九章第九章 稠密矩阵运算稠密矩阵运算 第十章第十章 线性方程组的求解线性方程组的求解 第十一章第十一章 快速傅里叶变换快速傅里叶变换 第四篇第四篇 并行程序设计并行程序设计 第十二章第十二章 并行程序设计基础并行程序设计基础 第十三章第十三章 并行程序设计模型和共享存储系统编程并行程序设计模型和共享存储系统编程 第十四章第十四章 分布存储系统并行编程分布存储系统并行编程 第十五章第十五章 并行程序设计环境与工具并行程序设计环境与工具2021/5/233第一章并行计算机系统及结构模型 1.1 1.1 并行计算并行计算 1.1.1 1.1.1 并行计算与计算科学并行计算与计算科学 1.1.2 1.1.2 当代科学与工程问题的计算需求当代科学与工程问题的计算需求 1.2 1.2 并行计算机系统互连并行计算机系统互连 1.2.1 1.2.1 系统互连系统互连 1.2.2 1.2.2 静态互联网络静态互联网络 1.2.3 1.2.3 动态互连网络动态互连网络 1.2.4 1.2.4 标准互联网络标准互联网络 1.3 1.3 并行计算机系统结构并行计算机系统结构 1.3.1 1.3.1 并行计算机结构模型并行计算机结构模型 1.3.2 1.3.2 并行计算机访存模型并行计算机访存模型2021/5/234并行计算 并行计算：并行机上所作的计算，又称高性能计算或超级计并行计算：并行机上所作的计算，又称高性能计算或超级计算。算。 三大学科：计算科学，理论科学和实验科学三大学科：计算科学，理论科学和实验科学 所有的学科都转向定量化和精确化。所有的学科都转向定量化和精确化。 计算科学是一个交叉学科，用计算的方法来解决应用问题。计算科学是一个交叉学科，用计算的方法来解决应用问题。 适用于理论模型复杂或尚未建立，实验费用昂贵或无法进行适用于理论模型复杂或尚未建立，实验费用昂贵或无法进行 计算科学：计算物理、计算化学、计算生物学等计算科学：计算物理、计算化学、计算生物学等 科学与工程问题的需求：气象预报、油藏模拟、核武器数值科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。模拟、航天器设计、基因测序等。 需求类型：计算密集、数据密集、网络密集。需求类型：计算密集、数据密集、网络密集。2021/5/2352021/5/2362021/5/237并行计算美国美国HPCCHPCC计划：高性能计算和通信，重大挑战计划：高性能计算和通信，重大挑战性课题，性课题，3 3T T性能性能美国美国PetaflopsPetaflops研究项目：研究项目：Pflop/sPflop/s。美国美国ASCIASCI计划：加速战略计算创新，核武器数计划：加速战略计算创新，核武器数值模拟。高性能值模拟。高性能2021/5/2382021/5/2392021/5/23102021/5/23112021/5/23122021/5/2313高性能计算机 IntelIntel（Option Red)Option Red)：1Tflops,1997,Pentium Pro1Tflops,1997,Pentium Pro SGI(Option Blue Mountain): SGI(Option Blue Mountain): 3Tflops,1998,MIPS100003Tflops,1998,MIPS10000 IBM(Option White): IBM(Option White): 7Tflops,Top4,2001,Power37Tflops,Top4,2001,Power3 日本日本Earth Simulator: Earth Simulator: 35Tflops,Top1,2002,VP35Tflops,Top1,2002,VP Hewlett-Packard ASCI QHewlett-Packard ASCI Q： 7Tflops ,Top2,3,2002, Alpha Server7Tflops ,Top2,3,2002, Alpha Server 中国联想：中国联想：1 1Tflops,Top43,2002Tflops,Top43,20022021/5/2314系统互连 不同带宽与距离的互连技术不同带宽与距离的互连技术: : 总线、总线、SANSAN、LANLAN、MANMAN、WANWAN2021/5/2315局部总线、I/O总线、SAN和LAN2021/5/2316网络性能指标 节点度（节点度（Node DegreeNode Degree）：）：射入或射出一个节点的边射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。数。在单向网络中，入射和出射边之和称为节点度。 网络直径（网络直径（Network DiameterNetwork Diameter）：）： 网络中任何两个网络中任何两个节点之间的最长距离，即最大路径数。节点之间的最长距离，即最大路径数。 对剖宽度（对剖宽度（Bisection WidthBisection Width） ：对分网络各半所必须对分网络各半所必须移去的最少边数移去的最少边数 对剖带宽（对剖带宽（ Bisection BandwidthBisection Bandwidth）: :每秒钟内，在最小的对每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数剖平面上通过所有连线的最大信息位（或字节）数 如果从任一节点观看网络都一样，则称网络为对称的如果从任一节点观看网络都一样，则称网络为对称的（SymmetrySymmetry） 2021/5/2317静态互连网络 与动态互连网络 静态互连网络：处理单元间有着固定连接的一类网络，静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等网络、立方环、洗牌交换网、蝶形网络等 动态网络：用交换开关构成的，可按应用程序的要求动动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。关和多级互连网络等。2021/5/2318静态互连网络（1） 一维线性阵列（一维线性阵列（1-1-D Linear ArrayD Linear Array）：）： 并行机中最简单、最基本的互连方式，并行机中最简单、最基本的互连方式， 每个节点只与其左、右近邻相连，也叫二近邻连接，每个节点只与其左、右近邻相连，也叫二近邻连接， NN个节点用个节点用N-1N-1条边串接之，内节点度为条边串接之，内节点度为2 2，直径为，直径为N-1N-1，对剖宽对剖宽度为度为1 1 当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为环可以是单向的或双向的，其节点度恒为2 2，直径或为，直径或为 （双向（双向环）或为环）或为N-1N-1（单向环），对剖宽度为单向环），对剖宽度为2 2 2021/5/2319静态互连网络（2） 二维网孔（二维网孔（2-2-D MeshD Mesh）：）： 每个节点只与其上、下、左、右的近邻相连（边界节点除外），每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为节点度为4 4，网络直径为，网络直径为 ，对剖宽度为，对剖宽度为 在垂直方向上带环绕，水平方向呈蛇状，就变成在垂直方向上带环绕，水平方向呈蛇状，就变成IlliacIlliac网孔了，网孔了，节点度恒为节点度恒为4 4，网络直径为，网络直径为 ，而对剖宽度为，而对剖宽度为 垂直和水平方向均带环绕，则变成了垂直和水平方向均带环绕，则变成了2-2-D D环绕（环绕（2-2-D TorusD Torus），），节点度恒为节点度恒为4 4，网络直径为，网络直径为 ，对剖宽度为，对剖宽度为 2021/5/2320静态互连网络（3） 二叉树：二叉树： 除了根、叶节点，每个内节点只与其父节点和两个子节点相连。除了根、叶节点，每个内节点只与其父节点和两个子节点相连。 节点度为节点度为3 3，对剖宽度为，对剖宽度为1 1，而树的直径为，而树的直径为 如果尽量增大节点度为，如果尽量增大节点度为， 则直径缩小为则直径缩小为2 2，此时就变成了星形，此时就变成了星形网络，其对剖宽度为网络，其对剖宽度为 传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。路自叶向根逐渐变宽。2021/5/2321静态互连网络（4） 超立方超立方 ： 一个一个n-n-立方由立方由 个顶点组成，个顶点组成，3-3-立方如图立方如图( (a)a)所示；所示；4-4-立立方如图方如图( (b)b)所示，由两个所示，由两个3-3-立方的对应顶点连接而成。立方的对应顶点连接而成。 n-n-立方的节点度为立方的节点度为n n，网络直径也是网络直径也是n n ，而对剖宽度为而对剖宽度为 。 如果将如果将3-3-立方的每个顶点代之以一个环就构成了如图立方的每个顶点代之以一个环就构成了如图( (d)d)所示所示的的3-3-立方环，此时每个顶点的度为立方环，此时每个顶点的度为3 3，而不像超立方那样节点，而不像超立方那样节点度为度为n n。2021/5/2322嵌入 将网络中的各节点映射到另一个网络中去将网络中的各节点映射到另一个网络中去 用用膨胀膨胀膨胀膨胀（DilationDilation）系数来描述嵌入的质量，它是指被）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数最大链路数 如果该系数为如果该系数为1 1，则称为完美嵌入。，则称为完美嵌入。 环网可完美嵌入到环网可完美嵌入到2-D2-D环绕网中环绕网中 超立方网可完美嵌入到超立方网可完美嵌入到2 2D D环绕网中环绕网中 2021/5/2323嵌入2021/5/2324静态互连网络特性比较2021/5/2325动态互连网络 (1) 总线：总线：PCIPCI、VMEVME、MulticsMultics、SbusSbus、MicroChannel MicroChannel 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等2021/5/2326动态互连网络 （2） 交叉开关（交叉开关（CrossbarCrossbar）：）： 单级交换网络，可为每个端口提供更高的带宽。象电话交换机单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于一样，交叉点开关可由程序控制动态设置其处于“ “开开” ”或或“ “关关” ”状态，而能提供所有（源、目的）对之间的动态连接。状态，而能提供所有（源、目的）对之间的动态连接。 交叉开关一般有两种使用方式：一种是用于对称的多处理机或交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于多计算机机群中的处理器间的通信；另一种是用于SMPSMP服务器服务器或向量超级计算机中处理器和存储器之间的存取。或向量超级计算机中处理器和存储器之间的存取。2021/5/2327动态互联网络 （3） 单级交叉开关级联起来形成多级互连网络单级交叉开关级联起来形成多级互连网络MINMIN（Multistage Interconnection NetworkMultistage Interconnection Network） 2021/5/2328动态互连网络（4） 交换开关模块：交换开关模块： 一个交换开关模块有一个交换开关模块有n n个输入和个输入和n n个输出，每个输入可连接到任个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突的映射，因为这将发生输出冲突 级间互连（级间互连（Interstage Connection Interstage Connection ）：）： 均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接 n n输入的输入的网络需要网络需要 级级 开关，在开关，在IlinoisIlinois大学的大学的Cedar2Cedar2多处理机系统中采用了多处理机系统中采用了网络网络 Cray Y/MPCray Y/MP多级网络，该网络用来支持多级网络，该网络用来支持8 8个向量处理器和个向量处理器和256256个存储器模块之间的数据传输。网络能够避免个存储器模块之间的数据传输。网络能够避免8 8个处理器同时个处理器同时进行存储器存取时的冲突。进行存储器存取时的冲突。 2021/5/2329动态互连网络比较 n,n,节点规模节点规模 w w，数据宽度数据宽度2021/5/2330标准互联网络（1） Myrinet:Myrinet: MyrinetMyrinet是由是由MyricomMyricom公司设计的千兆位包交换网络，其目的公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。是为了构筑计算机机群，使系统互连成为一种商业产品。 MyrinetMyrinet是基于加州理工学院开发的多计算机和是基于加州理工学院开发的多计算机和VLSIVLSI技术以及技术以及在南加州大学开发的在南加州大学开发的ATOMIC/LANATOMIC/LAN技术。技术。MyrinetMyrinet能假设任能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。意拓扑结构，不必限定为开关网孔或任何规则的结构。 MyrinetMyrinet在数据链路层具有可变长的包格式，对每条链路施行在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，机接口。在物理层上，MyrinetMyrinet网使用全双工网使用全双工SANSAN链路，最长链路，最长可达可达3 3米，峰值速率为（米，峰值速率为（1.281.281.281.28）GbpsGbps（目前有目前有2.56+2.56)2.56+2.56) MyrinetMyrinet交换开关交换开关 :8,12,16 :8,12,16端口端口 MyrinetMyrinet主机接口主机接口 : 32 : 32位的称作位的称作LANaiLANai芯片的用户定制的芯片的用户定制的VLSIVLSI处理器，它带有处理器，它带有MyrinetMyrinet接口、包接口、接口、包接口、DMADMA引擎和快引擎和快速静态随机存取存储器速静态随机存取存储器SRAMSRAM。 140 140 of the November 2002 TOP500 use Myrinet, of the November 2002 TOP500 use Myrinet, including 15 of the top 100 including 15 of the top 100 2021/5/2331Myrinet连接的LAN/Cluster2021/5/2332标准互连网络（2) 高性能并行接口（高性能并行接口（HiPPIHiPPI） Los AlamosLos Alamos国家实验室于国家实验室于19871987年提出的一个标准，其目的是年提出的一个标准，其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口。试图统一来自不同产商生产的所有大型机和超级计算机的接口。在大型机和超级计算机工业界，在大型机和超级计算机工业界，HiPPIHiPPI作为短距离的系统到系作为短距离的系统到系统以及系统到外设连接的高速统以及系统到外设连接的高速I/OI/O通道。通道。 19931993年，年，ANSI X3T9.3ANSI X3T9.3委员会认可了委员会认可了HiPPIHiPPI标准，它覆盖了标准，它覆盖了物理和数据链路层，但在这两层之上的任何规定却取决于用户。物理和数据链路层，但在这两层之上的任何规定却取决于用户。 HiPPIHiPPI是个单工的点到点的数据传输接口，其速率可达是个单工的点到点的数据传输接口，其速率可达800800MbpsMbps到到1.61.6GbpsGbps。 开发成功了一种能提供潜在的开发成功了一种能提供潜在的6.46.4GbpsGbps速率，比速率，比HiPPIHiPPI快快8 8倍且倍且有很低时延的超级有很低时延的超级HiPPIHiPPI技术，技术， SGISGI公司和公司和Los AlamosLos Alamos国家实验室都开发了用来构筑速率高达国家实验室都开发了用来构筑速率高达25.625.6GbpsGbps的的HiPPIHiPPI交换开关的交换开关的HiPPIHiPPI技术。技术。 HiPPIHiPPI通道和通道和HiPPIHiPPI交换开关被用在交换开关被用在SGI Power ChallengeSGI Power Challenge服务服务器、器、IBM 390IBM 390主机、主机、Cray Y/MPCray Y/MP、C90C90和和T3D/T3ET3D/T3E等系统等系统 2021/5/2333使用HiPPI通道和开关构筑的LAN主干网 2021/5/2334标准互连网络（3） 光纤通道光纤通道FCFC（Fiber ChannelFiber Channel） : : 通道和网络标准的集成通道和网络标准的集成 光纤通道既可以是共享介质，也可以是一种交换技术光纤通道既可以是共享介质，也可以是一种交换技术 光纤通道操作速度范围可从光纤通道操作速度范围可从100100到到133133、200200、400400和和800800MbpsMbps。FCSIFCSI厂商也正在推出未来具有更高速度（厂商也正在推出未来具有更高速度（1 1、2 2或或4 4GbpsGbps）的光纤通道的光纤通道 光纤通道的价值已被现在的某些千兆位局域网所证实，这些局光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术的域网就是基于光纤通道技术的 连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、仲裁环及交换光纤连接仲裁环及交换光纤连接 FDDI :FDDI : 光纤分布式数据接口光纤分布式数据接口FDDIFDDI（Fiber Distributed Data Fiber Distributed Data InterfaceInterface） FDDIFDDI采用双向光纤令牌环可提供采用双向光纤令牌环可提供100-200100-200MbpsMbps数据传输速率数据传输速率 FDDIFDDI具有互连大量设备的能力具有互连大量设备的能力 传统的传统的FDDIFDDI仅以异步方式操作仅以异步方式操作 2021/5/2335双向FDDI环作为主干网 2021/5/2336标准互联网络（4） ATMATM（Asynchronous Transfer ModeAsynchronous Transfer Mode）: : 由成立于由成立于19911991年的年的ATMATM论坛和论坛和ITUITU标准定义。标准定义。 ATMATM是一种独立于介质的消息传输协议，它将消息段变成更是一种独立于介质的消息传输协议，它将消息段变成更短的固定长度为短的固定长度为5353字节的报元进行传输。字节的报元进行传输。 这种技术是基于报元交换机制。这种技术是基于报元交换机制。ATMATM的目的是将实时和突发的目的是将实时和突发数据的传输合并成单一的网络技术。数据的传输合并成单一的网络技术。 ATMATM网络支持从网络支持从2525到到5151、155155和和622622MbpsMbps不同的速率，其速不同的速率，其速率越低率越低ATMATM交换器和使用的链路价格越低。交换器和使用的链路价格越低。2021/5/2337香港大学开发的Pearl机群 2021/5/2338标准互连网络（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结结构，构，构，构，大型数据大型数据大型数据大型数据库库存取等存取等存取等存取等大型大型大型大型图图像文件，像文件，像文件，像文件，多媒体，多媒体，多媒体，多媒体，因特网，因特网，因特网，因特网，内部网，内部网，内部网，内部网，数据数据数据数据仓库仓库等等等等2021/5/2339并行计算机结构模型 2021/5/2340并行计算机体系合一结构 SMPSMP、MPPMPP、DSMDSM和和COWCOW并行结构渐趋一致。并行结构渐趋一致。 大量的节点通过高速网络互连起来大量的节点通过高速网络互连起来 节点遵循节点遵循ShellShell结构：用专门定制的结构：用专门定制的ShellShell电路将商用微处理器电路将商用微处理器和节点的其它部分（包括板级和节点的其它部分（包括板级CacheCache、局存、局存、NICNIC和和DISKDISK）连连接起来。优点是接起来。优点是CPUCPU升级只需要更换升级只需要更换ShellShell。2021/5/2341五种结构特性一览表属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD处理器类型专用定制商用商用(可定制)商用商用互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（以太ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器CrayC-90，CrayT-90，银河1号IBM R50，SGIPowerChallenge，曙光1号IntelParagon，IBMSP2，曙光1000/2000StanfordDASH，CrayT3DBerkeleyNOW，AlphaFarm2021/5/2342并行计算机访存模型（1) UMAUMA（UniformMemoryAccessUniformMemoryAccess）模型是均匀存储访问模型是均匀存储访问模型的简称。其特点是：模型的简称。其特点是： 物理存储器被所有处理器均匀共享；物理存储器被所有处理器均匀共享； 所有处理器访问任何存储字取相同的时间；所有处理器访问任何存储字取相同的时间； 每台处理器可带私有高速缓存；每台处理器可带私有高速缓存； 外围设备也可以一定形式共享。外围设备也可以一定形式共享。2021/5/2343并行计算机访存模型（2) NUMA(NonuniformNUMA(NonuniformMemoryMemoryAccess)Access)模模型型是是非非非非均均均均匀匀匀匀存存存存储储储储访问访问访问访问模型的简称。特点是：模型的简称。特点是： 被被共共享享的的存存储储器器在在物物理理上上是是分分布布在在所所有有的的处处理理器器中中的的，其其所所有有本地存储器的集合就组成了全局地址空间；本地存储器的集合就组成了全局地址空间； 处处理理器器访访问问存存储储器器的的时时间间是是不不一一样样的的；访访问问本本地地存存储储器器LMLM或或群群内内共共享享存存储储器器CSMCSM较较快快，而而访访问问外外地地的的存存储储器器或或全全局局共共享享存存储器储器GSMGSM较慢较慢( (此即非均匀存储访问名称的由来此即非均匀存储访问名称的由来) )； 每台处理器照例可带私有高速缓存，外设也可以某种形式共享。每台处理器照例可带私有高速缓存，外设也可以某种形式共享。 LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSM2021/5/2344并行计算机访存模型（3) COMA(Cache-OnlyCOMA(Cache-OnlyMemoryMemoryAccess)Access)模模型型是是全全全全高高高高速速速速缓缓缓缓存存存存存储访问存储访问存储访问存储访问的简称。其特点是：的简称。其特点是： 各各处处理理器器节节点点中中没没有有存存储储层层次次结结构构，全全部部高高速速缓缓存存组组成成了了全全局局地址空间；地址空间； 利用分布的高速缓存目录利用分布的高速缓存目录D D进行远程高速缓存的访问进行远程高速缓存的访问; ; COMACOMA中的高速缓存容量一般都大于中的高速缓存容量一般都大于2 2级高速缓存容量；级高速缓存容量； 使使用用COMACOMA时时，数数据据开开始始时时可可任任意意分分配配，因因为为在在运运行行时时它它最最终终会被迁移到要用到它们的地方。会被迁移到要用到它们的地方。 2021/5/2345并行计算机访存模型（4) CC-NUMACC-NUMA（Coherent-CacheNonuniformMemoryCoherent-CacheNonuniformMemoryAccessAccess）模型是模型是高速缓存一致性非均匀存储访问高速缓存一致性非均匀存储访问高速缓存一致性非均匀存储访问高速缓存一致性非均匀存储访问模型的模型的简称。其特点是：简称。其特点是： 大多数使用基于目录的高速缓存一致性协议；大多数使用基于目录的高速缓存一致性协议； 保留保留SMPSMP结构易于编程的优点，也改善常规结构易于编程的优点，也改善常规SMPSMP的可扩放性；的可扩放性； CC-NUMACC-NUMA实际上是一个分布共享存储的实际上是一个分布共享存储的DSMDSM多处理机系统；多处理机系统； 它最显著的优点是程序员无需明确地在节点上分配数据，系统它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。速缓存一致性硬件会自动地将数据迁移至要用到它的地方。 2021/5/2346并行计算机访存模型（5) NORMANORMA（No-RemoteNo-RemoteMemoryMemoryAccessAccess）模模型型是是非非非非远远远远程程程程存储访问存储访问存储访问存储访问模型的简称。模型的简称。NORMANORMA的特点是：的特点是： 所有存储器是私有的；所有存储器是私有的； 绝大数绝大数NUMANUMA都不支持远程存储器的访问；都不支持远程存储器的访问； 在在DSMDSM中，中，NORMANORMA就消失了。就消失了。 2021/5/2347构筑并行机系统的不同存储结构2021/5/2348第二章 当代并行机系统 2.1 2.1 共享存储多处理机系统共享存储多处理机系统 2.1.1 2.1.1 对称多处理机对称多处理机SMPSMP结构特性结构特性 2.2 2.2 分布存储多计算机系统分布存储多计算机系统 2.2.1 2.2.1 大规模并行机大规模并行机MPPMPP结构特性结构特性 2.3 2.3 机群系统机群系统 2.3.1 2.3.1 大规模并行处理系统大规模并行处理系统MPPMPP机群机群SP2SP2 2.3.2 2.3.2 工作站机群工作站机群COWCOW2021/5/2349对称多处理机SMP(1) SMP: SMP: 采用商用微处理器，通常有片上和片外采用商用微处理器，通常有片上和片外CacheCache，基于总线连基于总线连接，集中式共享存储，接，集中式共享存储，UMAUMA结构结构 例子：例子：SGI Power Challenge, DEC Alpha SGI Power Challenge, DEC Alpha Server,Dawning 1Server,Dawning 12021/5/2350对称多处理机SMP(2) 优点优点 对称性对称性 单地址空间，易编程性，动态负载平衡，无需显示数据分配单地址空间，易编程性，动态负载平衡，无需显示数据分配 高速缓存及其一致性，数据局部性，硬件维持一致性高速缓存及其一致性，数据局部性，硬件维持一致性 低通信延迟，低通信延迟，Load/StoreLoad/Store完成完成 问题问题 欠可靠，欠可靠，BUS,OS,SMBUS,OS,SM 通信延迟（相对于通信延迟（相对于CPUCPU），），竞争加剧竞争加剧 慢速增加的带宽（慢速增加的带宽（MB double/3MB double/3年年, ,IOBIOB更慢）更慢） 不可扩放性不可扩放性-CC-NUMACC-NUMA2021/5/2351大规模并行机MPP 成百上千个处理器组成的大规模计算机系统，规模是变化的。成百上千个处理器组成的大规模计算机系统，规模是变化的。 NORMANORMA结构，高带宽低延迟定制互连。结构，高带宽低延迟定制互连。 可扩放性：可扩放性：Mem, I/O,Mem, I/O,平衡设计平衡设计 系统成本：商用处理器，相对稳定的结构系统成本：商用处理器，相对稳定的结构(shell)(shell)，SMPSMP节点节点, ,分布分布 通用性和可用性：不同的应用，通用性和可用性：不同的应用，PVM,MPI,PVM,MPI,交互，批处理，互连对交互，批处理，互连对用户透明，单一系统映象，故障用户透明，单一系统映象，故障 通信要求通信要求 存储器和存储器和I/OI/O能力能力 例子：例子：Intel Option RedIntel Option Red IBM SP2 Dawning 1000IBM SP2 Dawning 10002021/5/2352典型MPP系统特性比较MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000一个大型样机的配置9072个处理器，1.8Tflop/s(NSL)400个处理器，100Gflop/s(MHPCC)128个处理器，51Gflop/s(NCSA)问世日期1996年12月1994年9月1996年10月处理器类型200MHz,200Mflop/sPentiumPro67MHz，267Mflop/sPOWER2200MHz，400Mflop/sMIPSR10000节点体系结构和数据存储器2个处理器，32到256MB主存，共享磁盘1个处理器，64MB到2GB本地主存，1GB到14.5GB本地磁盘2个处理器，64MB到256MB分布共享主存和共享磁盘互连网络和主存模型分离两维网孔，NORMA多级网络，NORMA胖超立方体网络，CC-NUMA节点操作系统轻量级内核（LWK）完全AIX（IBMUNIX）微内核CellularIRIX自然编程机制基于PUMAPortals的MPIMPI和PVMPowerC，PowerFortran其他编程模型Nx，PVM，HPFHPF，LindaMPI，PVM2021/5/2353MPP所用的高性能CPU特性比较属性PentiumProPowerPC602Alpha21164AUltraSPARCIIMIPSR10000工艺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级SPECint92366225500350300SPECfp92283300750550600SPECint958.0922511N/A7.4SPECfp956.7030017N/A15其它特性CISC/RISC混合短流水线长L1高速缓存最高时钟频率最大片上2级高速缓存多媒体和图形指令MP机群总线可支持4个CPU2021/5/2354机群型大规模并行机SP2 设计策略：设计策略： 机群体系结构机群体系结构 标准环境标准环境 标准编程模型标准编程模型 系统可用性系统可用性 精选的单一系统映像精选的单一系统映像 系统结构：系统结构： 高性能开关高性能开关 HPS HPS 多级多级网络网络 宽节点、窄节点和窄节点宽节点、窄节点和窄节点2 2 2021/5/2355工作站机群COW 分布式存储，分布式存储，MIMDMIMD，工作站工作站+ +商用互连网络，每个节点是一个完整的计商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而算机，有自己的磁盘和操作系统，而MPPMPP中只有微内核中只有微内核 优点：优点： 投资风险小投资风险小 系统结构灵活系统结构灵活 性能性能/ /价格比高价格比高 能充分利用分散的计算资源能充分利用分散的计算资源 可扩放性好可扩放性好 问题问题 通信性能通信性能 并行编程环境并行编程环境 例子：例子：Berkeley NOWBerkeley NOW，Alpha Farm, FXCOWAlpha Farm, FXCOWP/CMMIOMIOMP/CNICNICDDLAN2021/5/2356典型的机群系统典型的机群系统特点一览表名称系统特点Princeton:SHRIMPPC商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信Karsruhe:Parastation用于分布并行处理的有效通信网络和软件开发Rice:TreadMarks软件实现分布共享存储的工作站机群Wisconsin:WindTunnel在经由商用网络互连的工作站机群上实现分布共享存储Chica、Maryl、Penns:NSCP国家可扩放机群计划：在通过因特网互连的3个本地机群系统上进行元计算Argonne:Globus在由ATM连接的北美17个站点的WAN上开发元计算平台和软件Syracuse:WWVM使用因特网和HPCC技术，在世界范围的虚拟机上进行高性能计算HKU:PearlCluster研究机群在分布式多媒体和金融数字库方面的应用Virgina:Legion在国家虚拟计算机设施上开发元计算软件2021/5/2357SMPMPP机群比较系统特征SMPMPP机群节点数量(N)O(10)O(100)-O(1000)O(100)节点复杂度中粒度或细粒度细粒度或中粒度中粒度或粗粒度节点间通信共享存储器消息传递或共享变量（有DSM时）消息传递节点操作系统1N(微内核)和1个主机OS(单一)N(希望为同构)支持单一系统映像永远部分希望地址空间单一多或单一（有DSM时）多个作业调度单一运行队列主机上单一运行队列协作多队列网络协议非标准非标准标准或非标准可用性通常较低低到中高可用或容错性能/价格比一般一般高互连网络总线/交叉开关定制商用2021/5/2358第三章 并行计算性能评测 3.1 3.1 并行机的一些基本性能指标并行机的一些基本性能指标 3.2 3.2 加速比性能定律加速比性能定律 3.2.1 3.2.1 AmdahlAmdahl定律定律 3.2.2 3.2.2 GustafsonGustafson定律定律 3.2.3 3.2.3 SunSun和和NiNi定律定律 3.3 3.3 可扩放性评测标准可扩放性评测标准 3.3.1 3.3.1 并行计算的可扩放性并行计算的可扩放性 3.3.2 3.3.2 等效率度量标准等效率度量标准 3.3.3 3.3.3 等速度度量标准等速度度量标准 3.3.4 3.3.4 平均延迟度量标准平均延迟度量标准2021/5/2359CPU的某些基本性能指标 工作负载工作负载 执行时间执行时间 浮点运算数浮点运算数 指令数目指令数目 并行执行时间并行执行时间 T T comput comput 为计算时间，为计算时间，T T paro paro 为并行开销为并行开销时间，时间，T T commcomm为相互通信时间为相互通信时间 T T n n = T = T comput comput + T + T paro paro+ T+ T comm comm 例：估计例：估计APRAMAPRAM模型下执行时间模型下执行时间 2021/5/2360存储器性能 存储器的层次结构存储器的层次结构(C,L,B)(C,L,B) 各层性能参数：各层性能参数：容量容量C C、延迟、延迟L L、带宽、带宽B B。 相关参数：相关参数：存储粒度、一致性粒度、层管理方案等。存储粒度、一致性粒度、层管理方案等。2021/5/2361 影响存储器容量影响存储器容量C C设计因素：设计因素： 与主流应用的进程数及各进程工作集尺寸等有关。与主流应用的进程数及各进程工作集尺寸等有关。 影响存储器延迟影响存储器延迟L L设计因素：设计因素： 与与CPUCPU指令系统指令系统CPICPI及指令所需数据量等有关。及指令所需数据量等有关。 影响存储器带宽影响存储器带宽B B设计因素：设计因素： 与应用的数据通信量、通信频率和延迟与应用的数据通信量、通信频率和延迟L L等有关。等有关。2021/5/2362并行与通信开销并行和通信开销：相对于计算很大。并行和通信开销：相对于计算很大。 PowerPC (PowerPC (每个周期每个周期 15 15ns ns 执行执行4 4flops;flops; 创建一个进程创建一个进程1.41.4ms ms 可执行可执行372000372000flops)flops)开销的测量：乒开销的测量：乒-乓方法（乓方法（Ping-Pong SchemePing-Pong Scheme）节点节点0 0发送发送mm个字节给节点个字节给节点1 1；节点；节点1 1从节点从节点0 0接收接收mm个字节后，立即将消息发回节点个字节后，立即将消息发回节点0 0。总的时间除。总的时间除以以2 2，即可得到点到点通信时间，也就是执行单，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。一发送或接收操作的时间。可一般化为热土豆法（可一般化为热土豆法（Hot-PotatoHot-Potato），），也称为救也称为救火队法（火队法（Fire-Brigade) 01 2 Fire-Brigade) 01 2 -n-1 0 -n-1 0 2021/5/2363Ping-Pong Scheme if if （my _node _id =0my _node _id =0） then /* then /*发送者发送者*/*/ start _time =secondstart _time =second（ ） send an m-byte message to node 1send an m-byte message to node 1 receive an m-byte message from node 1receive an m-byte message from node 1 end_time = secondend_time = second（ ） total_time = end_time start_timetotal_time = end_time start_time communication_timei = total_time/2 communication_timei = total_time/2 else if else if （my_node_id = 1my_node_id = 1） then /* then /*接收者接收者*/*/ receive an m-byte message from node 0receive an m-byte message from node 0 send an m-byte message to node 0send an m-byte message to node 0 endifendif2021/5/2364并行开销的表达式：点到点通信 通信开销通信开销 t t( (mm) = ) = t t0 0 + + mm/ / r r 通信启动时间通信启动时间 t t0 0 渐近渐近带宽带宽r r ：传送无限长的消息时的通信速率传送无限长的消息时的通信速率 半半峰值长度峰值长度mm1/2 1/2 ：达到一半渐近带宽所要的消息长度：达到一半渐近带宽所要的消息长度 特定性能特定性能 0 0：表示短消息带宽：表示短消息带宽 t t0 0 = m = m1/2 1/2 / / r r = 1 /= 1 / 0 02021/5/2365并行开销的表达式：整体通信 典型的整体通信有：典型的整体通信有： 播送（播送（BroadcastingBroadcasting）：）：处理器处理器0 0发送发送mm个字节给所有的个字节给所有的n n个个处理器处理器 收集（收集（GatherGather）：）：处理处理0 0接收所有接收所有n n个处理器发来在消息，所个处理器发来在消息，所以处理器以处理器0 0最终接收了最终接收了m nm n个字节；个字节； 散射（散射（ScatterScatter）：）：处理器处理器0 0发送了发送了mm个字节的不同消息给所有个字节的不同消息给所有n n个处理器，因此处理器个处理器，因此处理器0 0最终发送了最终发送了m nm n个字节；个字节； 全交换（全交换（Total ExchangeTotal Exchange）：）：每个处理器均彼此相互发送每个处理器均彼此相互发送mm个个字节的不同消息给对方，所以总通信量为字节的不同消息给对方，所以总通信量为mnmn2 2个字节；个字节； 循环移位（循环移位（Circular-shiftCircular-shift）：）：处理器处理器i i发送发送mm个字节给处理器个字节给处理器i+1i+1，处理器处理器n-1n-1发送发送mm个字节给处理器个字节给处理器0 0，所以通信量为，所以通信量为m nm n个个字节。字节。2021/5/2366机器的成本、价格与性/价比 机器的成本与价格机器的成本与价格 机器的性能机器的性能/ /价格比价格比 Performance/Cost Ratio Performance/Cost Ratio ：系指：系指用单位代价（通常以百万美元表示）所获取的性能（通用单位代价（通常以百万美元表示）所获取的性能（通常以常以MIPSMIPS或或MFLOPSMFLOPS表示）每秒执行的指令数表示）每秒执行的指令数 利用率（利用率（UtilizationUtilization）：可达到的速度与峰值速度之比）：可达到的速度与峰值速度之比 2021/5/2367算法级性能评测 加速比性能定律加速比性能定律 并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。 Amdahl Amdahl 定律定律 GustafsonGustafson定律定律 Sun NiSun Ni定律定律 可扩放性评测标准可扩放性评测标准 等效率度量标准等效率度量标准 等速度度量标准等速度度量标准 平均延迟度量标准平均延迟度量标准2021/5/2368Amdahl 定律 P P：处理器数；处理器数； WW：问题规模（问题规模（计算负载、工作负载，给定问题的总计算量计算负载、工作负载，给定问题的总计算量）；）； WWs s：应用程序中的串行分量，应用程序中的串行分量，f f是串行分量比例（是串行分量比例（f = Wf = Ws s/W/W， WWs s=W=W1 1）；）； WWP P：应用程序中可并行化部分，应用程序中可并行化部分，1-1-f f为并行分量比例；为并行分量比例； WWs s +W +W p p =W =W； T Ts s=T=T1 1 ：串行执行时间，串行执行时间，T T p p ：并行执行时间；并行执行时间； S S：加速比，加速比，E E：效率；效率； 出发点：出发点： 固定不变的计算负载；固定不变的计算负载； 固定的计算负载分布在多个处理器上的，固定的计算负载分布在多个处理器上的， 增加处理器加快执行速度，从而达到了加速的目的。增加处理器加快执行速度，从而达到了加速的目的。 2021/5/2369Amdahl定律（contd) 固定负载的加速公式：固定负载的加速公式： W W s s+ W + W p p可相应地表示为可相应地表示为f+f+（1-f1-f） p p时，上式极限为：时，上式极限为： S= 1 / f S= 1 / f W W o o为额外开销为额外开销 2021/5/2370Amdahls law (contd)2021/5/2371Gustafson定律 出发点：出发点： 对于很多大型计算，精度要求很高，即在此类应用中精度是个对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；须加大计算量，相应地亦必须增多处理器数才能维持时间不变； 除非学术研究，在实际应用中没有必要固定工作负载而计算程除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。题规模才有实际意义。 GustafsonGustafson加速定律加速定律 : : 并行开销并行开销WW o o ：2021/5/2372Gustafson定律（contd)2021/5/2373Sun 和 Ni定律 基本思想：基本思想： 只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。（此时可能使执行时间略有增加）。 假定在单节点上使用了全部存储容量假定在单节点上使用了全部存储容量MM并在相应于并在相应于WW的时间内求解之，的时间内求解之，此时工作负载此时工作负载W= fW + W= fW + （1-f1-f）WW。 在在p p 个节点的并行系统上，能够求解较大规模的问题是因为存储容量个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到可增加到pMpM。令因子令因子G G（p p）反应存储容量增加到反应存储容量增加到p p倍时并行工作负载倍时并行工作负载的增加量，所以扩大后的工作负载的增加量，所以扩大后的工作负载W = fW + W = fW + （1-f1-f）G G（p p）WW。 存储受限的加速公式存储受限的加速公式 ： 并行开销并行开销W W o o: :2021/5/2374Sun 和 Ni定律(contd) G G（p p）=1=1时就是时就是AmdahlAmdahl加速定律；加速定律； G G（p p）=p =p 变为变为 f + pf + p（1-f1-f），），就是就是GustafsonGustafson加速定律加速定律 G G（p p）pp时，相应于计算机负载比存储要求增加得快，时，相应于计算机负载比存储要求增加得快，此时此时 SunSun和和 N i N i 加速均比加速均比 Amdahl Amdahl 加速和加速和 Gustafson Gustafson 加加速为高。速为高。 2021/5/2375加速比讨论 参考的加速经验公式：参考的加速经验公式： p/log pSP p/log pSP 线性加速比：很少通信开销的矩阵相加、内积运算等线性加速比：很少通信开销的矩阵相加、内积运算等 p/log pp/log p的加速的加速 比：分治类的应用问题比：分治类的应用问题 通信密集类的应用问题通信密集类的应用问题 ：S = 1 / C S = 1 / C （ p p ） 超线性加速超线性加速 绝对加速：最佳并行算法与串行算法绝对加速：最佳并行算法与串行算法 相对加速：同一算法在单机和并行机的运行时间相对加速：同一算法在单机和并行机的运行时间2021/5/2376可扩放性评测标准 并行计算的可扩放性（并行计算的可扩放性（ScalabilityScalability）也是主要性能指标也是主要性能指标 可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理器数的增加而按比例提高的能力程序等）性能随处理器数的增加而按比例提高的能力 影响加速比的因素：处理器数与问题规模影响加速比的因素：处理器数与问题规模 求解问题中的串行分量求解问题中的串行分量 并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等） 加大的处理器数超过了算法中的并发程度加大的处理器数超过了算法中的并发程度 增加问题的规模有利于提高加速的因素：增加问题的规模有利于提高加速的因素： 较大的问题规模可提供较高的并发度；较大的问题规模可提供较高的并发度； 额外开销的增加可能慢于有效计算的增加；额外开销的增加可能慢于有效计算的增加； 算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题规模的增大而缩小）。规模的增大而缩小）。 增加处理器数会增大额外开销和降低处理器利用率，所以对于一个增加处理器数会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。 2021/5/2377可扩放性评测标准（contd) 可扩放性可扩放性: :调整什么和按什么比例调整调整什么和按什么比例调整 并行计算要调整的是处理数并行计算要调整的是处理数p p和问题规模和问题规模WW， 两者可按不同比例进行调整，此比例关系（可能是线性的，多两者可按不同比例进行调整，此比例关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。项式的或指数的等）就反映了可扩放的程度。 并行算法和体系结构并行算法和体系结构 可扩放性研究的主要目的：可扩放性研究的主要目的： 确定解决某类问题用何种并行算法与何种并行体系结构的组合，确定解决某类问题用何种并行算法与何种并行体系结构的组合，可以有效地利用大量的处理器可以有效地利用大量的处理器( (算法与结构的组合算法与结构的组合) )； 对于运行于某种体系结构的并行机上的某种算法当移植到大规对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能；模处理机上后运行的性能； 对固定的问题规模，确定在某类并行机上最优的处理器数与可对固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大的加速比；获得的最大的加速比； 用于指导改进并行算法和并行机体系结构，以使并行算法尽可用于指导改进并行算法和并行机体系结构，以使并行算法尽可能地充分利用可扩充的大量处理器能地充分利用可扩充的大量处理器 目前无一个公认的、标准的和被普遍接受的严格定义和目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准评判它的标准 2021/5/2378等效率度量标准 令令t tie ie 和和t t io io 分别是并行系统上第分别是并行系统上第i i个处理器的有用计算时间个处理器的有用计算时间和额外开销时间（包括通信、同步和空闲等待时间等）和额外开销时间（包括通信、同步和空闲等待时间等） T T p p 是是p p个处理器系统上并行算法的运行时间，对于任意个处理器系统上并行算法的运行时间，对于任意i i显显然有然有T T p p = t = tie ie +t+t io io ，且且 T T e e+ T + T o o= pT p = pT p 问题的规模问题的规模WW为最佳串行算法所完成的计算量为最佳串行算法所完成的计算量W=TW=Te e 如果问题规模如果问题规模W W 保持不变，处理器数保持不变，处理器数p p增加，开销增加，开销T To o增大，增大，效率效率E E下降。为了维持一定的效率（介于下降。为了维持一定的效率（介于0 0与与1 1之间），当处之间），当处理数理数p p增大时，需要相应地增大问题规模增大时，需要相应地增大问题规模WW的值。由此定义的值。由此定义函数函数f f E E（p p）为问题规模为问题规模WW随处理器数随处理器数p p变化的函数，为等变化的函数，为等效率函数（效率函数（ISO-efficiency FunctionISO-efficiency Function）（）（Kumar1987Kumar1987） 2021/5/2379等效率度量标准（contd) 曲线曲线1 1表示算法具有很好的扩放性；曲线表示算法具有很好的扩放性；曲线2 2表示算法是表示算法是可扩放的；曲线可扩放的；曲线 3 3表示算法是不可扩放的。表示算法是不可扩放的。 优点：简单可定量计算的、少量的参数计算等效率函数优点：简单可定量计算的、少量的参数计算等效率函数 缺点：如果缺点：如果T To o无法计算出（在共享存储并行机中）无法计算出（在共享存储并行机中）2021/5/2380等速度度量标准 p p 表示处理器个数，表示处理器个数，WW表示要求解问题的工作量或称问题规模表示要求解问题的工作量或称问题规模（在此可指浮点操作个数），（在此可指浮点操作个数），T T为并行执行时间，定义并行计算的为并行执行时间，定义并行计算的速度速度V V为工作量为工作量WW除以并行时间除以并行时间T T p p个处理器的并行系统的平均速度定义为并行速度个处理器的并行系统的平均速度定义为并行速度V V除以处理器个除以处理器个数数 p p： WW是使用是使用p p个处理器时算法的工作量，令个处理器时算法的工作量，令WW表示当处理数从表示当处理数从p p增大增大到到p p时，为了保持整个系统的平均速度不变所需执行的工作量，则时，为了保持整个系统的平均速度不变所需执行的工作量，则可得到处理器数从可得到处理器数从 p p到到p p时平均速度可扩放度量标准公式时平均速度可扩放度量标准公式 2021/5/2381等速度度量标准（contd） 优点：直观地使用易测量的机器性能速度指标来度量优点：直观地使用易测量的机器性能速度指标来度量 缺点：某些非浮点运算可能造成性能的变化缺点：某些非浮点运算可能造成性能的变化2021/5/2382平均延迟度量标准 T Ti i为为P Pi i的执行时间，包括延迟的执行时间，包括延迟L Li i，PiPi的总延迟时间为的总延迟时间为“ “L i+L i+启动时间启动时间+ +停止时间停止时间” ”。定义系统平均延迟时间为。定义系统平均延迟时间为 pTpTparapara =T =To o+ T+ Ts s 在在p p个处理器上求解工作量为个处理器上求解工作量为WW问题的平均延迟问题的平均延迟 在在p p个处理器上求解工作量为个处理器上求解工作量为WW问题的平均延迟当处理器问题的平均延迟当处理器数由数由p p变到变到p p，而推持并行执行效率不变，则定义平均延迟可扩放而推持并行执行效率不变，则定义平均延迟可扩放性度量标准为性度量标准为 2021/5/2383平均延迟度量标准（Contd) 优点：平均延迟能在更低层次上衡量机器的性能优点：平均延迟能在更低层次上衡量机器的性能 缺点：需要特定的软硬件才能获得平均延迟缺点：需要特定的软硬件才能获得平均延迟2021/5/2384部分资料从网络收集整理而来，供大家参考，感谢您的关注！