《程序性能评价与优化.ppt》由会员分享，可在线阅读，更多相关《程序性能评价与优化.ppt（37页珍藏版）》请在三一办公上搜索。
1、第四章 程序性能评价与优化,第四章 程序性能评价与优化,4.1 并行程序的执行时间和并行算法的时间复杂性 4.1.1 并行程序的执行时间 4.1.2 并行算法的时间复杂性 4.1.3 代价最优算法4.2 并行程序的性能评价 4.2.1 加速比定律 4.2.2 基准测试程序4.3 程序的性能优化 4.3.1 串行程序性能优化 4.3.2 并行程序性能优化,4.1 并行程序的执行时间和并行算法的时间复杂性,4.1.1 并行程序的执行时间,在消息传递系统中，求解一个算法的整个执行时间 tp 应包括：计算时间 tcomp 通信时间 tcomm 即：tp=tcomp+tcomm对 COW 而言，通信时间
2、一般近似地表示为：tcomm=tstartup+n tdata在对计算时间进行计时，常采用程序中需要执行的计算步来表示。,4.1.2 并行算法的时间复杂性,令 f(n)和 g(n)是定义在自然数集合N 上的两个函数,定义1：如果存在两个正数 c 和 n0，使得对于所有的 n n0 均有f(n)c g(n)，则标记为：f(n)=(g(n)我们称 g(n)为 f(n)的上界。定义2：如果存在两个正数 c 和 n0，使得对于所有的 n n0 均有f(n)c g(n)，则标记为：f(n)=(g(n)我们称 g(n)为 f(n)的下界。,定义3：如果存在正数 c1、c2 和 n0，使得对于所有的n n0
3、 均有c1 g(n)f(n)c2 g(n)，则标记为 f(n)=(g(n)我们称 g(n)为 f(n)的紧致界。即：如果 f(n)=(g(n)且 f(n)=(g(n)则 f(n)=(g(n)算法的执行时间也称算法的时间复杂性，常用其上界、下界 和紧致界 表示。,4.1.2 并行算法的时间复杂性,计算/通信比：tcomp/tcomm如果计算和通信时间具有相同的时间复杂性，则当问题规模 n 增加时，通信开销往往会随之增加；我们希望计算/通信比大于1，当问题规模 n 增加时，通信开销会随之相对减少。例如：通信时间=(n)，而计算时间=(n2)，当 n 增大到一定值后，计算时间将支配整个并行算法的执行
4、时间。,4.1.2 并行算法的时间复杂性,并行算法的代价：并行算法的运行时间 t与所需的处理器数 p 之积，即 c=t*p。如果一个并行算法的代价与相应的（最佳）串行算法的执行时间在同一个数量级上，则称该并行算法为代价最优的。,4.1.3 代价最优算法,4.2 并行程序的性能评价,4.2 并行程序的性能评价,并行程序性能评测与并行计算机体系结构、并行算法、并行程序设计一起构成了“并行计算”研究的四大分支。在并行计算系统上进行计算的主要目标就是要加速整个计算过程，所以研究并行系统（并行算法、并行程序）加速性能十分重要。随着计算规模的增加和机器规模的扩大，研究计算系统的性能是否能随着处理器数目的增
5、加而按比例的增加，就是并行计算的可扩展问题。为了方便地、可比较地评价并行计算机系统的性能，人们提出了许多基准程序，了解这些基准测试程序对于我们客观公正地评价并行计算机系统非常重要。,在给定的并行计算系统上给定的应用，并行程序的执行速度相对于串行程序加快的倍数，就是该并行程序的加速比。,4.2.1 加速比定律,我们要给出两个加速比性能模型：适用于固定计算负载的 Amdahl 定律 适用于扩展问题的 Gustsfson 定律,4.2.1 加速比定律,Amdahl 定律的出发点：固定不变的计算负载；固定的计算负载分布在多个处理器上的，增加处理器加快执行速度，从而达到加速的目的。Gustsfson 定
6、律的出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。,4.2.1 加速比定律,参数定义：P：并行计算系统的处理器数W：问题规模WS：应用程序中的串行分量WP：可并行化部分f：串行分量的比例（f=WS/W），1-f：并行分量的比例TS=T1：串行执行时间，TP：并行计算时间S：加速比，E：并行效率,4.2.1 加速比定律,1)适用于固定计算负载的A
7、mdahl定律当并行计算机中处理器数目增加时，固定负载就被分配给更多的处理器去并行执行，其主要目的是想尽可能快地的得出结果，即计算任务的实时性要求更高。Amdahl 定律(1967)：设 f 为给定计算任务中必须串行执行的部分所占比例(0f 1)，对于一台含有 p 个处理器的并行计算机，其最大可能的加速比为：,4.2.1 加速比定律,4.2.1 加速比定律,S=,S=,当 p 无限增加时，加速比趋于 1/f,对于部分问题，如实时性计算方面问题，一般为固定工作负载。但对于许多问题，扩大计算机规模是为了解决更大规模的问题，因此在对并行程序（并行算法）进行评价时，采用Amdahl定律就不能反映算法的
8、可扩展性。,4.2.1 加速比定律,2)适用于扩展问题的Gustafson定律有些计算任务要求在给定的时间内希望提高计算精度，即在给定的时间内增加处理器的数量使计算量提高，如我们希望数值天气预报的数据采样模型单位更小。在精度占主导位置的应用领域中，我们希望象在小机器上解小问题一样在大机器上能解规模大的问题，并使二者所花费的时间大体相同。,4.2.1 加速比定律,Gustafson定律(1988)：对于一台并行计算机，当问题中可并行部分扩大 p 倍时，其加速比也随之增长：,4.2.1 加速比定律,4.2.1 加速比定律,若我们用 f 来表示，可将上式变为：,=f+p(1-f),基准测试程序（be
9、nchmark）用于测试计算机系统的性能，试图提供一种客观、公正的评价机器性能的标准。目前在高性能计算领域，比较有影响的基准测试程序有HINT测试、Perf 测试、IOzone测试，以及Linpack测试、NAS Parallel Benchmark、SPEC HPC测试等。这些基准测试可以在一定程度上对并行计算机系统方案进行评价，可以对并行计算机系统的市场销售提供参考，另外，在基准测试中形成的优化方法对应用程序设计与优化具有重要的指导意义。,4.2.2 基准测试程序,4.3 程序的性能优化,串行程序性能的优化是并行程序性能优化的基础。一个好的并行程序首先应该拥有良好的单机性能。影响程序单机性
10、能的主要因素是程序的计算流程和处理器的体系结构。在基于微处理器的高性能计算机上，提高程序单机性能的关键是改善程序的访存性能、提高cache 命中率、以及充分挖掘CPU 多运算部件、流水线的处理能力。,4.3.1 串行程序性能优化,1.调用高性能库充分利用已有的高性能程序库是提高应用程序实际性能最有效的途径之一。许多著名的高性能数学程序库如优化的BLAS、FFTW 等，由于经过厂商或第三方针对特定处理机进行的专门优化，其性能一般大大优于用户自行编写的同样功能的程序段或子程序。合理地调用这些高性能库中的子程序，可以成倍、甚至成数量级地提升应用程序的性能，达到事半功倍的效果。,4.3.1 串行程序性
11、能优化,2.选择适当的编译器优化选项现代编译器在编译时能够对程序进行优化从而提高所生成的目标代码的性能。这些优化功能通常通过一组编译选项来控制。比较通用的优化选项有“-O”、“-O0”、“-O2”、“-O3”等，“-O0”表示不做优化，“-O1”、“-O2”、“-O3”等表示不同级别的优化，优化级别越高，生成的代码的性能可能会越好，但采用过高级别的优化会大大降低编译速度，并且可能导致错误的运行结果。通常，“-O2”的优化被认为是安全的，它可以保证程序运行的正确性。对于一般程序的编译而言，使用优化选项“-O2”或“-O3”就可以了，进一步的优化可以参考所使用的编译器的手册，通过实验比较来找出一组
12、理想的优化选项组合。,4.3.1 串行程序性能优化,3.合理定义数组维数现代计算机提高内存带宽的一个重要手段是采用多体交叉并行存储系统，即使用多个独立的内存体，对它们统一编址，将数据以字为单位采用循环交替方式均匀地分布在不同的内存体中。为了充分利用多体存储，在进行连续数据访问时应该使得地址的增量与内存体数的最大公约数尽量小，特别要避免地址增量正好是体数的倍数的情况，因为此时所有的访问将集中在一个存储体中。对于组关联的cache 结构也有类似的问题，应该使被访问的数据均匀地分布在尽可能多的cache 组中才能获得好的执行性能。由于内存体数和cache 组数通常是2 的幂，因此连续数据访问时应该避
13、免地址增量正好是2 的幂的情形。,4.3.1 串行程序性能优化,4.注意嵌套循环的顺序提高cache 使用效率的一个简单原则是尽量改善数据访问的局部性。数据访问的局部性分为空间局部性和时间局部性。空间局部性指访问了一个地址后，应该接着访问它的邻居，而时间局部性则指对同一地址的多次访问应该在尽可能相邻的时间内完成。在嵌套的多重循环中，循环顺序往往对循环中数据访问的局部性有很大的影响。,4.3.1 串行程序性能优化,5.数据分块当处理大数组时，对数组、循环进行适当分块有助于同时改善访存的时间和空间局部性。数据分块是一项比较复杂的优化技术，好的分块方式与分块参数的确定需要对代码及cache 结构进行
14、非常细致的分析或通过大量的实验才能得到，因此该项技术一般只在对一些关键代码段进行深层次优化时才使用。,4.3.1 串行程序性能优化,6.循环展开循环展开是另一个非常有效的程序优化技术。它除了能够改善数据访问的时间和空间局部性外，还由于增加了每步循环中的指令与运算的数目，亦有助于CPU 多个运算部件的充分利用。,4.3.1 串行程序性能优化,并行程序的性能优化相对于串行程序而言更加复杂，其中最主要的是选择好的并行算法及通信模式。在并行算法确定之后，影响并行程序效率的主要因素是通信开销、由于数据相关性或负载不平衡引起的进程空闲等待、以及并行算法引入的冗余计算。在设计并行程序时，可以采用多种技术来减
15、少或消除这些因素对并行效率的影响。,4.3.2 并行程序性能优化,1.减少通信量、提高通信粒度在消息传递并行程序中，花费在通信上的时间是纯开销，因此如何减少通信时间是并行程序设计中首先要考虑的问题。减少通信时间的途径主要有三个：减少通信量、提高通信粒度和提高通信中的并发度(即不同结点对间同时进行通信，要注意的是，这些手段都是相对于特定条件而言的，例如，在网络重负载的情况下，提高通信并行度并不能改善程序的性能)。提高通信粒度的有效方法是减少通信次数，即尽可能将可以一起传递的数据合并起来一次传递。在收发不同类型的数据时，定义适当的MPI 数据类型来避免内存中的数据拷贝。,4.3.2 并行程序性能优
16、化,2.全局通信尽量利用高效群体通信算法当组织多个进程之间的群体通信时，使用高效的通信算法可以大大提高通信效率、降低通信开销。对于标准的群体通信，如广播、归约、数据散发与收集等，尽量调用MPI 标准库中的函数，因为这些函数往往经过专门优化。但使用标准库函数的一个缺点是整个通信过程被封装起来，无法在通信的同时进行计算工作，此时，可以自行编制相应通信代码，将其与计算过程结合起来，以达到最佳的效果。,4.3.2 并行程序性能优化,3.挖掘算法的并行度，减少CPU 空闲等待一些具有数据相关性的计算过程会导致并行运行的部分进程空闲等待。在这种情况下，可以考虑改变算法来消除数据相关性。某些情况下数据相关性
17、的消除是以增加计算量做为代价的，这方面的典型例子有用Jacobi 迭代替换GaussSeidel 或超松弛迭代、三对角线性方程组的并行解法等。当算法在某个空间方向具有相关性时，应该考虑充分挖掘其他空间方向以及时间上的并行度，在这类问题中流水线方法往往发挥着重要的作用。,4.3.2 并行程序性能优化,4.负载平衡负载不平衡是导致进程空闲等待的另外一个重要因素。在设计并行算法时应该充分考虑负载平衡问题，必要时使用动态负载平衡技术，即根据各进程计算完成的情况动态地分配或调整各进程的计算任务。动态调整负载时要考虑负载调整的开销及由于负载不平衡而引起的空闲等待对性能的影响，寻找最优负载调整方案。,4.3
18、.2 并行程序性能优化,5.通信、计算的重叠通过让通信与计算重叠进行，利用计算时间来屏蔽通信时间，是减少通信开销的非常有效的方法。实现通信与计算重叠的方法一般基于非阻塞通信，先发出非阻塞的消息接收或发送命令，然后处理与收发数据无关的计算任务，完成这些计算后再等待消息收发的完成。通信与计算的重叠能否实现，除了取决于算法和程序的实现方式之外，还取决于并行机的通信网络及通信协议。,4.3.2 并行程序性能优化,6.通过引入重复计算来减少通信有时通过适当引入一些重复计算，可以减少通信量或通信次数。由于当前大部分并行机的计算速度远远快于通信速度，并且一些情况下，当一个进程计算时，其他进程往往处于空闲等待状态，因而适当引入重复计算可以提高程序的总体性能。,4.3.2 并行程序性能优化,
