高性能计算导论并行计算性能评价课件

并行计算性能评价并行计算性能评价上海大学计算机工程与科学学院

计算的本质串行计算模型—图灵机并行计算模型

计算效能评价计算模型与效能评价高性能计算导论上海大学计算机工程与科学学院计算的本质计算模型与效能评价高“并行计算”研究的四大分支并行计算机体系结构并行算法并行程序设计并行计算的性能评测而介于并行计算机体系结构与并行算法之间的是并行计算模型。“并行计算”研究的四大分支并行计算机体系结构PerformanceEvaluation并行计算效能评价PerformanceEvaluation并行计算效能评价程序性能评价与优化给定并行算法，采用并行程序设计平台，通过并行实现获得实际可运行的并行程序后，一个重要的工作就是，在并行机上运行该程序，评价该程序的实际性能，揭示性能瓶颈，指导程序的性能优化。性能评价和优化是设计高效率并行程序必不可少的重要工作。程序性能评价与优化给定并行算法，采用并行程序设计平台，通过并并行程序执行时间评价并行程序的性能之前，必须清楚并行程序的执行时间是由哪些部分组成的。众所周知，独享处理器资源时，串行程序的执行时间近似等于程序指令执行花费的CPU时间。但是，并行程序相对复杂，其执行时间（executiontime）等于从并行程序开始执行，到所有进程执行完毕，墙上时钟走过的时间，也称之为墙上时间（walltime）。对各个进程，墙上时间可进一步分解为：计算CPU时间通信CPU时间同步开销时间进程空闲时间（是由同步导致的）并行程序执行时间评价并行程序的性能之前，必须清楚并行程序的执并行程序执行时间计算CPU时间进程指令执行所花费的CPU时间，它可以分解为两个部分，一个是程序本身指令执行占用的CPU时间，即通常所说的用户时间（usertime），主要包含指令在CPU内部的执行时间和内存访问时间，另一个是为了维护程序的执行，操作系统花费的CPU时间，即通常所说的系统时间（systemtime），主要包含内存调度和管理开销、I/O时间、以及维护程序执行所必需要的操作系统开销等。通常地，系统时间可以忽略。并行程序执行时间计算CPU时间并行程序执行时间通信CPU时间

包含进程通信花费的CPU时间。同步开销时间

包含进程同步花费的时间进程空闲时间

当一个进程阻塞式等待其他进程的消息时，CPU通常是空闲的，或者处于等待状态。进程空闲时间是指并行程序执行过程中，进程所有这些空闲时间的总和。显然，进程的计算CPU时间小于并行程序的墙上时间，而并行程序的墙上时间才是用户真正关心的时间，是评价一个并行程序执行速度的时间。并行程序执行时间通信CPU时间8/10/20239/59并行算法设计及效能分析并行算法效能分析并行加速比并行效率可扩展性（简单表述）处理机数p增加时，并行效率Ep不显著下降。8/8/20239/59并行算法设计及效能分析并行算法效能分效能分析分析说明需要说明的是，T1指处理器个数为1时，并行程序的执行时间。通常情形下，T1大于TS，因为并行程序往往引入一些冗余的控制和管理开销。加速比和效率是衡量一个并行程序性能的最基本的评价方法。显然，执行最慢的进程将决定并行程序的性能。在以上加速比和效率的定义中，有一个基本的假设，要求并行机的各个处理器是同构(homogeneous)的，即并行机各个处理器的结构完全一致（包含CPU类型、内存大小与性能、cache特征等等），或者说，串行程序在各个处理器执行的墙上时间相等。效能分析分析说明需要说明的是，T1指处理器个数为1时，并效能分析分析说明如果并行机的各个处理器功能不一致，称之为异构并行机。对此，以上加速比和效率的定义不是很合适。其中，两个突出的问题就是，串行程序的执行时间是选择最快的处理器运行，还是选择最慢的处理器运行？在效率定义中，处理器个数选择为P是否合适？一个比较好的方法就是，将所有处理器以最快的处理器为基准，进行归一化处理。效能分析分析说明如果并行机的各个处理器功能不一致，称之为异构并行程序性能评价方法以上介绍的加速比和效率，只能反映并行程序的整体执行性能，但是，无法反映并行程序的性能瓶颈。性能评价的主要目的在于，揭示并行程序的性能瓶颈，指导并行程序的性能优化。因此，有必要进一步分解加速比和效率，提出更细致的性能评价方法。并行程序性能评价方法以上介绍的加速比和效率，只能反映并行程序并行计算性能评测3.1并行机的一些基本性能指标3.2加速比性能定律3.2.1Amdahl定律3.2.2Gustafson定律3.2.3Sun和Ni定律3.3可扩放性评测标准3.3.1并行计算的可扩放性3.3.2等效率度量标准3.3.3等速度度量标准3.3.4平均延迟度量标准 ﹡3.4基准测试程序并行计算性能评测3.1并行机的一些基本性能指标并行计算的性能评测机器级的性能评测CPU和存储器的某些基本性能指标并行通信开销机器的成本、价格、和性能/价格比等算法级的性能评测加速比效率可扩展性程序级的性能评测基本测试程序数学库测试并行测试程序等并行计算的性能评测机器级的性能评测并行机基本性能参数一览表名称符号含义单位机器规模n处理器的数目无量纲时钟速率f时钟周期长度的倒数MHz工作负载W计算操作的数目Mflops顺序执行时间T1程序在单处理机上的运行时间s并行执行时间Tn程序在并行机上的运行时间s速度Rn=W/Tn每秒百万次浮点运算Mflops加速Sn=T1/Tn衡量并行机有多快无量纲效率En=Sn/n衡量处理器的利用率无量纲峰值速度Rpeak=nR’peak所有处理器峰值(R’peak)速度之积Mflops利用率U=Rn/Rpeak可达速度与峰值速度之比无量纲通信延迟t0传送0个字节或单字的时间us渐近带宽r∞传送长消息通信速率MB/s并行机基本性能参数一览表名称符号含义单位机器规模n处理器的数工作负载工作负载（荷）：计算操作数目执行时间—掠过时间：墙上时间所执行的指令数目所完成的浮点运算数工作负载工作负载（荷）：计算操作数目CPU的某些基本性能指标工作负载执行时间:程序从开始到结束的时间。浮点运算数指令数目：通常用百万条指令并行执行时间Tn：Tcomput为计算时间，Tparo为并行开销时间，Tcomm为相互通信时间

Tn=Tcomput+Tparo+Tcomm 例：估计APRAM模型下执行时间其中T1为串行时间，n为处理器数，T∞为使用无限多处理器且不考虑

Tparo与Tcomm的并行执行时间CPU的某些基本性能指标工作负载存储器性能存储器的层次结构(C,L,B)-----容量C，延迟L，带宽B估计存储器的带宽RISC指令addr1,r2,r3，寄存器8bytes，主频100MHzB=3*8*100*106B/s=2.4GB/s存储器性能存储器的层次结构(C,L,B)并行与通信开销并行和通信开销：相对于计算很大。PowerPC(每个周期15ns执行4flops;

创建一个进程1.4ms可执行372000flops)开销的测量：乒--乓方法（Ping-PongScheme）节点0发送m个字节给节点1；节点1从节点0接收m个字节后，立即将消息发回节点0。总的时间除以2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。可一般化为热土豆法（Hot-Potato），也称为救火队法（Fire-Brigade)0——1——2——…——n-1——0即从节点0发送m字节给1，节点1给节点2，依次类推，最后节点n-1再将其返回给0，最后时间再除以n即可。并行与通信开销并行和通信开销：相对于计算很大。Ping-PongSchemeif（my_node_id=0）then/*发送者*/ start_time=second（） sendanm-bytemessagetonode1//发送 receiveanm-bytemessagefromnode1//接收 end_time=second（） total_time=end_time–start_timecommunication_time[i]=total_time/2 elseif（my_node_id=1）then/*接收者*/ receiveanm-bytemessagefromnode0 sendanm-bytemessagetonode0 endifPing-PongSchemeif（my_node_并行开销的表达式：点到点通信通信开销

t(m)=t0+m/r∞通信启动时间t0渐近带宽r∞

：传送无限长的消息时的通信速率m为传输的字节数半峰值长度m1/2：达到一半渐近带宽所要的消息长度特定性能π0：表示短消息带宽

t0=m1/2/

r∞=1/π0并行开销的表达式：点到点通信通信开销t(m)=t0并行开销的表达式：组通信典型的组通信有：播送（Broadcasting）：处理器0发送m个字节给所有的n个处理器----广播收集（Gather）：处理0接收所有n个处理器发来在消息，所以处理器0最终接收了mxn个字节；散射（Scatter）：处理器0发送了m个字节的不同消息给所有n个处理器，因此处理器0最终发送了mxn个字节；全交换（TotalExchange）：每个处理器均彼此相互发送m个字节的不同消息给对方，所以总通信量为mxn2个字节；循环移位（Circular-shift）：处理器i发送m个字节给处理器i+1，处理器n-1发送m个字节给处理器0，所以通信量为mxn个字节。并行开销的表达式：组通信典型的组通信有：机器的成本、价格与性/价比机器的成本与价格机器的性能/价格比Performance/CostRatio：系指用单位代价（通常以百万美元表示）所获取的性能（通常以MIPS或MFLOPS表示）利用率（Utilization）：可达到的速度与峰值速度之比机器的成本、价格与性/价比机器的成本与价格并行计算性能评测3.1并行机的一些基本性能指标3.2加速比性能定律3.2.1Amdahl定律3.2.2Gustafson定律3.2.3Sun和Ni定律3.3可扩放性评测标准3.3.1并行计算的可扩放性3.3.2等效率度量标准3.3.3等速度度量标准3.3.4平均延迟度量标准 ﹡3.4基准测试程序并行计算性能评测3.1并行机的一些基本性能指标算法级性能评测加速比性能定律并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。Amdahl定律Gustafson定律SunNi定律可扩放性评测标准等效率度量标准等速度度量标准平均延迟度量标准算法级性能评测加速比性能定律Amdahl定律（1967）参数约定P：处理器数；W：问题规模（计算负载、工作负载，给定问题的总计算量）；Ws：应用程序中的串行分量，f是串行分量比例

（f=Ws/W，Ws=W1）；WP：应用程序中可并行化部分，1-f为并行分量比例；Ws+Wp=W；Ts=T1：串行执行时间，Tp：并行执行时间；S：加速比，E：效率；出发点：固定不变的计算负载；固定的计算负载分布在多个处理器上；增加处理器加快执行速度，从而达到了加速的目的。Amdahl定律（1967）参数约定Amdahl定律（cont‘d)固定负载的加速公式：

归一化：Ws+Wp可相应地表示为f+（1-f）

近似公式：p→∞时，上式极限为S=1/f考虑额外开销Wo： Amdahl定律（cont‘d)固定负载的加速公式：Amdahl’slaw(cont’d)Amdahl’slaw(cont’d)Gustafson定律（1988）出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。Gustafson定律（1988）出发点：Gustafson定律（1988）Gustafson加速定律:近似公式：p→∞时，S’=p-fp=(1-f)P,1-f为斜率并行开销Wo：Gustafson定律（1988）Gustafson定律（cont‘d)Gustafson定律（cont‘d)Sun和Ni定律基本思想：只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之，此时工作负载W=fW+（1-f）W。在p个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到pM。令因子G（p）反应存储容量增加到p倍时并行工作负载的增加量，所以扩大后的工作负载W=fW+（1-f）G（p）W。Sun和Ni定律基本思想：Sun和Ni定律存储受限的加速公式：并行开销Wo:Sun和Ni定律存储受限的加速公式：Sun和Ni定律(cont’d)Sun和Ni定律(cont’d)Sun和Ni定律(cont’d)讨论：G（p）=1时，就是Amdahl加速定律；G（p）=p时,s’’变为f+p（1-f），就是Gustafson加速定律G（p）>p时，相应于计算机负载比存储要求增加得快，此时Sun和Ni加速均比Amdahl加速和Gustafson加速为高。Sun和Ni定律(cont’d)讨论：加速比讨论参考的加速经验公式：p/logp≤S≤P线性加速比：很少通信开销的矩阵相加、内积运算等p/logp的加速比：分治类的应用问题通信密集类的应用问题：S=1/C（p）,C（p）为与p有关的通信函数超线性加速：并行搜索，Cache效应绝对加速：最佳并行算法与串行算法相对加速：同一算法在单机和并行机的运行时间加速比讨论参考的加速经验公式：p/logp≤S≤P可扩展分析给定并行算法（程序）和并行机，如何调整参与并行计算的处理器个数P和求解问题的计算规模W，使得随着处理器个数的增长，并行计算的效率可以保持不变，称之为并行程序和并行机相结合的可扩展分析。可扩展分析是并行计算一个重要研究课题，被广泛应用于描述并行算法（程序）能否有效利用可扩展的处理器个数的能力。可扩展分析给定并行算法（程序）和并行机，如何调整参与并行计算可扩展分析目的通常地，可扩展分析具有四个目的：选择合理的算法与结构组合

确定求解某类问题的何种并行算法与何种并行机的组合，它可以有效地利用所期望的处理器规模。性能预测

对于运行在某台并行机上的某种算法（程序），根据算法（程序）在小处理器规模上的运行性能，预测该算法（程序）移植到大处理器规模上后运行的性能。最优性能选择

对某类算法，假设问题规模固定，确定在某类并行机上最优的处理器个数和可获得的最优的加速比。指导性能优化指导改进并行算法（程序），使得并行算法充分利用可扩展的处理器规模。指导性能优化

指导改进并行算法（程序），使得并行算法充分利用可扩展的处理器规模。可扩展分析目的通常地，可扩展分析具有四个目的：可扩展分析方法（1）等效率度量对于某类算法和并行机，如何保持问题规模W与处理器个数P之间的关系WpPq，使得随着处理器个数P的增长，保持并行计算的效率不变。也就是求出等效率函数：W=

fE(P)

E固定等效率值越小，则当处理器个数增多时为保持相同效率所需增加的问题规模就越小，因此就有更好的可扩展性。可扩展分析方法（1）等效率度量可扩展分析方法（2）等速度度量对于运行在并行机上的某个算法，当处理器个数增加时，需要增加多大的计算量，才能保持并行程序的平均速度不变。定义平均速度:V为并行程序的执行速度，问题规模从(W,P)变化到(W’,P’)，则等速度可扩展度量公式可写为：越接近1，说明可扩展性越好。可扩展分析方法（2）等速度度量并行程序性能优化并行程序的性能优化相对于串行程序而言更加复杂，其中最主要的是选择好的并行算法及通信模式。在并行算法确定之后，影响并行程序效率的主要因素是通信开销、由于数据相关性或负载不平衡引起的进程空闲等待、以及并行算法引入的冗余计算。在设计并行程序时，可以采用多种技术来减少或消除这些因素对并行效率的影响。并行程序性能优化并行程序的性能优化相对于串行程序而言更加复杂并行程序优化技术1.减少通信量、提高通信粒度2.全局通信尽量利用高效聚合通信算法3.挖掘算法的并行度，减少CPU空闲等待4.负载平衡5.通信、计算的重叠6.通过引入重复计算来减少通信并行程序优化技术1.减少通信量、提高通信粒度1.减少通信量、提高通信粒度在消息传递并行程序中，花费在通信上的时间是纯开销，因此如何减少通信时间是并行程序设计中首先要考虑的问题。减少通信时间的途径主要有三个：减少通信量、提高通信粒度和提高通信中的并发度(即不同结点对间同时进行通信，要注意的是，这些手段都是相对于特定条件而言的，例如，在网络重负载的情况下，提高通信并行度并不能改善程序的性能)。提高通信粒度的有效方法是减少通信次数，即尽可能将可以一起传递的数据合并起来一次传递。在收发不同类型的数据时，定义适当的MPI数据类型来避免内存中的数据拷贝。1.减少通信量、提高通信粒度在消息传递并行程序中，花费在通2.全局通信尽量利用高效聚合通信算法当组织多个进程之间的聚合通信时，使用高效的通信算法可以大大提高通信效率、降低通信开销。对于标准的聚合通信，如广播、归约、数据散发与收集等，尽量调用MPI标准库中的函数，因为这些函数往往经过专门优化。但使用标准库函数的一个缺点是整个通信过程被封装起来，无法在通信的同时进行计算工作，此时，可以自行编制相应通信代码，