程序性能评价与优化

《程序性能评价与优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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+

2、tcomm对COW而言，通信时间一般近似地表示为：tcomm=tstartup+ntdata在对计算时间进行计时，常采用程序中需要执行的计算步来表示。4.1.2并行算法的时间复杂性令f(n)和g(n)是定义在自然数集合N上的两个函数,定义1：如果存在两个正数c和n0，使得对于所有的nn0均有f(n)cg(n)，则标记为：f(n)=(g(n))我们称g(n)为f(n)的上界。定义2：如果存在两个正数c和n0，使得对于所有的nn0均有f(n)cg(n)，则标记为：f(n)=(g(n))我们称g(n)为

3、f(n)的下界。定义3：如果存在正数c1、c2和n0，使得对于所有的nn0均有c1g(n)f(n)c2g(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增加时，通信开销往往会随之增加；我们希望计算/通信比大

4、于1，当问题规模n增加时，通信开销会随之相对减少。例如：通信时间=(n)，而计算时间=(n2)，当n增大到一定值后，计算时间将支配整个并行算法的执行时间。4.1.2并行算法的时间复杂性并行算法的代价：并行算法的运行时间t与所需的处理器数p之积，即c=t*p。如果一个并行算法的代价与相应的（最佳）串行算法的执行时间在同一个数量级上，则称该并行算法为代价最优的。4.1.3代价最优算法4.2并行程序的性能评价4.2并行程序的性能评价并行程序性能评测与并行计算机体系结构、并行算法、并行程序设计一起构成了“并行计算

5、”研究的四大分支。在并行计算系统上进行计算的主要目标就是要加速整个计算过程，所以研究并行系统（并行算法、并行程序）加速性能十分重要。随着计算规模的增加和机器规模的扩大，研究计算系统的性能是否能随着处理器数目的增加而按比例的增加，就是并行计算的可扩展问题。为了方便地、可比较地评价并行计算机系统的性能，人们提出了许多基准程序，了解这些基准测试程序对于我们客观公正地评价并行计算机系统非常重要。在给定的并行计算系统上给定的应用，并行程序的执行速度相对于串行程序加快的倍数，就是该并行程序的加速比。4.2.1加速比定律我

6、们要给出两个加速比性能模型：适用于固定计算负载的Amdahl定律适用于扩展问题的Gustsfson定律4.2.1加速比定律Amdahl定律的出发点：固定不变的计算负载；固定的计算负载分布在多个处理器上的，增加处理器加快执行速度，从而达到加速的目的。Gustsfson定律的出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目

7、的处理器上，增多处理器必须相应地增大问题规模才有实际意义。4.2.1加速比定律参数定义：P：并行计算系统的处理器数W：问题规模WS：应用程序中的串行分量WP：可并行化部分f：串行分量的比例（f=WS/W），1-f：并行分量的比例TS=T1：串行执行时间，TP：并行计算时间S：加速比，E：并行效率4.2.1加速比定律1)适用于固定计算负载的Amdahl定律当并行计算机中处理器数目增加时，固定负载就被分配给更多的处理器去并行执行，其主要目的是想尽可能快地的得出结果，即计算任务的实时性要求更高。Amdahl定律(1

8、967)：设f为给定计算任务中必须串行执行的部分所占比例(0≤f≤1)，对于一台含有p个处理器的并行计算机，其最大可能的加速比为：4.2.1加速比定律S=1f+(1-f)/p。。。。。。ts(1-f)tsfts多处理机：：：p个处理机单处理机串行部分可并行化部分tp(1-f)ts/p……4.2.1加速比定律S=Ws+WpWs+Wp/p=fW+(1-f)WfW+((1-f)W)/p=f+(1-f)f+