高性能计算导论：并行计算性能评价.ppt

《高性能计算导论：并行计算性能评价.ppt》由会员分享，可在线阅读，更多相关《高性能计算导论：并行计算性能评价.ppt（48页珍藏版）》请在三一办公上搜索。

1、并行计算性能评价,上海大学计算机工程与科学学院,计算的本质串行计算模型图灵机并行计算模型 计算效能评价,计算模型与效能评价,高性能计算导论,“并行计算”研究的四大分支,并行计算机体系结构并行算法并行程序设计并行计算的性能评测而介于并行计算机体系结构与并行算法之间的是并行计算模型。,Performance Evaluation,并行计算效能评价,程序性能评价与优化,给定并行算法，采用并行程序设计平台，通过并行实现获得实际可运行的并行程序后，一个重要的工作就是，在并行机上运行该程序，评价该程序的实际性能，揭示性能瓶颈，指导程序的性能优化。性能评价和优化是设计高效率并行程序必不可少的重要工作。,并行

2、程序执行时间,评价并行程序的性能之前，必须清楚并行程序的执行时间是由哪些部分组成的。众所周知，独享处理器资源时，串行程序的执行时间近似等于程序指令执行花费的CPU 时间。但是，并行程序相对复杂，其执行时间（execution time）等于从并行程序开始执行，到所有进程执行完毕，墙上时钟走过的时间，也称之为墙上时间（wall time）。对各个进程，墙上时间可进一步分解为：计算CPU 时间通信CPU 时间同步开销时间进程空闲时间（是由同步导致的）,并行程序执行时间,计算CPU 时间 进程指令执行所花费的CPU 时间，它可以分解为两个部分，一个是程序本身指令执行占用的CPU 时间，即通常所说的用

3、户时间（user time），主要包含指令在CPU 内部的执行时间和内存访问时间，另一个是为了维护程序的执行，操作系统花费的CPU 时间，即通常所说的系统时间（system time），主要包含内存调度和管理开销、I/O 时间、以及维护程序执行所必需要的操作系统开销等。通常地，系统时间可以忽略。,并行程序执行时间,通信CPU 时间 包含进程通信花费的CPU 时间。同步开销时间 包含进程同步花费的时间进程空闲时间 当一个进程阻塞式等待其他进程的消息时，CPU 通常是空闲的，或者处于等待状态。进程空闲时间是指并行程序执行过程中，进程所有这些空闲时间的总和。显然，进程的计算CPU 时间小于并行程序的

4、墙上时间，而并行程序的墙上时间才是用户真正关心的时间，是评价一个并行程序执行速度的时间。,2023/11/6,9/59,并行算法设计及效能分析,并行算法效能分析,并行加速比,并行效率,可扩展性（简单表述）处理机数p增加时，并行效率Ep不显著下降。,效能分析分析说明,需要说明的是，T1 指处理器个数为1 时，并行程序的执行时间。通常情形下，T1 大于TS，因为并行程序往往引入一些冗余的控制和管理开销。加速比和效率是衡量一个并行程序性能的最基本的评价方法。显然，执行最慢的进程将决定并行程序的性能。在以上加速比和效率的定义中，有一个基本的假设，要求并行机的各个处理器是同构(homogeneous)的

5、，即并行机各个处理器的结构完全一致（包含CPU 类型、内存大小与性能、cache 特征等等），或者说，串行程序在各个处理器执行的墙上时间相等。,效能分析分析说明,如果并行机的各个处理器功能不一致，称之为异构并行机。对此，以上加速比和效率的定义不是很合适。其中，两个突出的问题就是，串行程序的执行时间是选择最快的处理器运行，还是选择最慢的处理器运行？在效率定义中，处理器个数选择为P 是否合适？一个比较好的方法就是，将所有处理器以最快的处理器为基准，进行归一化处理。,并行程序性能评价方法,以上介绍的加速比和效率，只能反映并行程序的整体执行性能，但是，无法反映并行程序的性能瓶颈。性能评价的主要目的在于

6、，揭示并行程序的性能瓶颈，指导并行程序的性能优化。因此，有必要进一步分解加速比和效率，提出更细致的性能评价方法。,并行计算性能评测,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 平均延迟度量标准 3.4 基准测试程序,并行计算的性能评测,机器级的性能评测CPU和存储器的某些基本性能指标并行通信开销机器的成本、价格、和性能/价格比等算法级的性能评测加速比效率可扩展性程序级的性能评测基

7、本测试程序数学库测试并行测试程序等,并行机基本性能参数一览表,工作负载,工作负载（荷）：计算操作数目执行时间掠过时间：墙上时间所执行的指令数目所完成的浮点运算数,CPU的某些基本性能指标,工作负载执行时间:程序从开始到结束的时间。浮点运算数 指令数目：通常用百万条指令并行执行时间T n：T comput 为计算时间，T paro 为并行开销时间，T comm为相互通信时间 T n=T comput+T paro+T comm 例：估计APRAM模型下执行时间 其中T1为串行时间，n为处理器数，T为使用无限多处理器且不考虑T paro与T comm 的并行执行时间,存储器性能,存储器的层次结构(

8、C,L,B)-容量C，延迟L，带宽B估计存储器的带宽RISC指令 add r1,r2,r3，寄存器 8bytes，主频 100MHzB=3*8*100*106 B/s=2.4GB/s,并行与通信开销,并行和通信开销：相对于计算很大。PowerPC(每个周期 15ns 执行4flops;创建一个进程1.4ms 可执行372000flops)开销的测量：乒-乓方法（Ping-Pong Scheme）节点0发送m个字节给节点1；节点1从节点0接收m个字节后，立即将消息发回节点0。总的时间除以2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。可一般化为热土豆法（Hot-Potato），也

9、称为救火队法（Fire-Brigade)01 2 n-1 0 即从节点0发送m字节给1，节点1给节点2，依次类推，最后节点n-1再将其返回给0，最后时间再除以n即可。,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_timei=total_

10、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,并行开销的表达式：点到点通信,通信开销 t(m)=t0+m/r通信启动时间 t0渐近带宽r：传送无限长的消息时的通信速率m为传输的字节数 半峰值长度m1/2：达到一半渐近带宽所要的消息长度 特定性能0：表示短消息带宽 t0=m1/2/r=1/0,并行开销的表达式：组通信,典型的组通信有：播送（Broadcasting）：处理器0发送m个字节给所有的n个处理器-广播收集

11、（Gather）：处理0接收所有n个处理器发来在消息，所以处理器0最终接收了m x n个字节；散射（Scatter）：处理器0发送了m个字节的不同消息给所有n个处理器，因此处理器0最终发送了m x n个字节；全交换（Total Exchange）：每个处理器均彼此相互发送m个字节的不同消息给对方，所以总通信量为mxn2个字节；循环移位（Circular-shift）：处理器i发送m个字节给处理器i+1，处理器n-1发送m个字节给处理器0，所以通信量为m x n个字节。,机器的成本、价格与性/价比,机器的成本与价格机器的性能/价格比 Performance/Cost Ratio：系指用单位代价（

12、通常以百万美元表示）所获取的性能（通常以MIPS或MFLOPS表示）利用率（Utilization）：可达到的速度与峰值速度之比,并行计算性能评测,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 平均延迟度量标准 3.4 基准测试程序,算法级性能评测,加速比性能定律并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少

13、倍。Amdahl 定律Gustafson定律Sun Ni定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准,Amdahl 定律（1967）,参数约定P：处理器数；W：问题规模（计算负载、工作负载，给定问题的总计算量）；Ws：应用程序中的串行分量，f 是串行分量比例（f=Ws/W，Ws=W1）；WP：应用程序中可并行化部分，1-f 为并行分量比例；Ws+W p=W；Ts=T1：串行执行时间，T p：并行执行时间；S：加速比，E：效率；出发点：固定不变的计算负载；固定的计算负载分布在多个处理器上；增加处理器加快执行速度，从而达到了加速的目的。,Amdahl定律（contd),固定负载

14、的加速公式：归一化：W s+W p可相应地表示为f+（1-f）近似公式：p时，上式极限为 S=1/f 考虑额外开销Wo：,Amdahls law(contd),Gustafson定律（1988）,出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。,Gustafson定律（1988）,Gustafson加速定律:近似公式：p时，S=p-fp=(1-f)

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

16、contd),讨论：G（p）=1时，就是Amdahl加速定律；G（p）=p 时,s变为 f+p（1-f），就是Gustafson加速定律G（p）p时，相应于计算机负载比存储要求增加得快，此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。,加速比讨论,参考的加速经验公式：p/log pSP 线性加速比：很少通信开销的矩阵相加、内积运算等p/log p的加速比：分治类的应用问题 通信密集类的应用问题：S=1/C（p）,C（p）为与p有关的通信函数超线性加速：并行搜索，Cache效应绝对加速：最佳并行算法与串行算法相对加速：同一算法在单机和并行机的运行时间,可扩展

17、分析,给定并行算法（程序）和并行机，如何调整参与并行计算的处理器个数P 和求解问题的计算规模W，使得随着处理器个数的增长，并行计算的效率可以保持不变，称之为并行程序和并行机相结合的可扩展分析。可扩展分析是并行计算一个重要研究课题，被广泛应用于描述并行算法（程序）能否有效利用可扩展的处理器个数的能力。,可扩展分析目的,通常地，可扩展分析具有四个目的：选择合理的算法与结构组合 确定求解某类问题的何种并行算法与何种并行机的组合，它可以有效地利用所期望的处理器规模。性能预测 对于运行在某台并行机上的某种算法（程序），根据算法（程序）在小处理器规模上的运行性能，预测该算法（程序）移植到大处理器规模上后运

18、行的性能。最优性能选择 对某类算法，假设问题规模固定，确定在某类并行机上最优的处理器个数和可获得的最优的加速比。指导性能优化指导改进并行算法（程序），使得并行算法充分利用可扩展的处理器规模。指导性能优化 指导改进并行算法（程序），使得并行算法充分利用可扩展的处理器规模。,可扩展分析方法（1）,等效率度量 对于某类算法和并行机，如何保持问题规模W 与处理器个数P 之间的关系WpPq，使得随着处理器个数P 的增长，保持并行计算的效率不变。也就是求出等效率函数：W=fE(P)E 固定 等效率值越小，则当处理器个数增多时为保持相同效率所需增加的问题规模就越小，因此就有更好的可扩展性。,可扩展分析方法（

19、2）,等速度度量 对于运行在并行机上的某个算法，当处理器个数增加时，需要增加多大的计算量，才能保持并行程序的平均速度不变。定义平均速度:V 为并行程序的执行速度，问题规模从(W,P)变化到(W,P)，则等速度可扩展度量公式可写为：越接近1，说明可扩展性越好。,并行程序性能优化,并行程序的性能优化相对于串行程序而言更加复杂，其中最主要的是选择好的并行算法及通信模式。在并行算法确定之后，影响并行程序效率的主要因素是通信开销、由于数据相关性或负载不平衡引起的进程空闲等待、以及并行算法引入的冗余计算。在设计并行程序时，可以采用多种技术来减少或消除这些因素对并行效率的影响。,并行程序优化技术,1.减少通

20、信量、提高通信粒度2.全局通信尽量利用高效聚合通信算法3.挖掘算法的并行度，减少CPU 空闲等待4.负载平衡5.通信、计算的重叠6.通过引入重复计算来减少通信,1.减少通信量、提高通信粒度,在消息传递并行程序中，花费在通信上的时间是纯开销，因此如何减少通信时间是并行程序设计中首先要考虑的问题。减少通信时间的途径主要有三个：减少通信量、提高通信粒度和提高通信中的并发度(即不同结点对间同时进行通信，要注意的是，这些手段都是相对于特定条件而言的，例如，在网络重负载的情况下，提高通信并行度并不能改善程序的性能)。提高通信粒度的有效方法是减少通信次数，即尽可能将可以一起传递的数据合并起来一次传递。在收发

21、不同类型的数据时，定义适当的MPI 数据类型来避免内存中的数据拷贝。,2.全局通信尽量利用高效聚合通信算法,当组织多个进程之间的聚合通信时，使用高效的通信算法可以大大提高通信效率、降低通信开销。对于标准的聚合通信，如广播、归约、数据散发与收集等，尽量调用MPI 标准库中的函数，因为这些函数往往经过专门优化。但使用标准库函数的一个缺点是整个通信过程被封装起来，无法在通信的同时进行计算工作，此时，可以自行编制相应通信代码，将其与计算过程结合起来，以达到最佳的效果。,3.挖掘算法的并行度，减少CPU 空闲等待,一些具有数据相关性的计算过程会导致并行运行的部分进程空闲等待。在这种情况下，可以考虑改变算

22、法来消除数据相关性。某些情况下数据相关性的消除是以增加计算量做为代价的，这方面的典型例子有用Jacobi 迭代替换GaussSeidel 或超松弛迭代、三对角线性方程组的并行解法等。当算法在某个空间方向具有相关性时，应该考虑充分挖掘其他空间方向以及时间上的并行度，在这类问题中流水线方法往往发挥着重要的作用。,4.负载平衡,负载不平衡是导致进程空闲等待的另外一个重要因素。在设计并行算法时应该充分考虑负载平衡问题，必要时使用动态负载平衡技术，即根据各进程计算完成的情况动态地分配或调整各进程的计算任务。动态调整负载时要考虑负载调整的开销及由于负载不平衡而引起的空闲等待对性能的影响，寻找最优负载调整方

23、案。,5.通信、计算的重叠,通过让通信与计算重叠进行，利用计算时间来屏蔽通信时间，是减少通信开销的非常有效的方法。实现通信与计算重叠的方法一般基于非阻塞通信，先发出非阻塞的消息接收或发送命令，然后处理与收发数据无关的计算任务，完成这些计算后再等待消息收发的完成。通信与计算的重叠能否实现，除了取决于算法和程序的实现方式之外，还取决于并行机的通信网络及通信协议。,6.通过引入重复计算来减少通信,有时通过适当引入一些重复计算，可以减少通信量或通信次数。由于当前大部分并行机的计算速度远远快于通信速度，并且一些情况下，当一个进程计算时，其他进程往往处于空闲等待状态，因而适当引入重复计算可以提高程序的总体性能。例如一些公共量的计算，可以由一个进程完成然后再发送给其他进程，也可以各进程分别独立计算。后一个做法在性能上通常要好于前一个做法。另外一个通过引入重复计算来提高通信粒度。,