Click to edit Master title style,,Click to Edit Master Text Styles Asd Gasd Glak Fdas Af Lkajds Laksdjf Hasldkf Asdkj H,,Second Level Asdf Ias;df Has;dlf As;df Asd Fasdf Asdf Asd Af Sdfs Fdsasdf Sa,,Third Level,,Fourth Level,,Fifth Level,,,并行计算性能评价,上海大学计算机工程与科学学院,,计算的本质,,串行计算模型,—,图灵机,,并行计算模型,,,计算效能评价,计算模型与效能评价,高性能计算导论,“并行计算”研究的四大分支,并行计算机,体系结构,,并行,算法,,并行,程序设计,,并行计算的,性能评测,,,而介于并行计算机,体系结构,与并行,算法,之间的是并行,计算模型,Performance Evaluation,并行计算效能评价,,,程序性能评价与优化,给定并行算法，采用并行程序设计平台，通过并行实现获得实际可运行的并行程序后，一个重要的工作就是，在并行机上运行该程序，评价该程序的实际性能，,揭示性能瓶颈，指导程序的性能优化,。
性能评价和优化是设计高效率并行程序必不可少的重要工作并行程序执行时间,评价并行程序的性能之前，必须清楚并行程序的执行时间是由哪些部分组成的众所周知，独享处理器资源时，串行程序的执行时间近似等于程序指令执行花费的,CPU,时间但是，并行程序相对复杂，其,执行时间（,execution time,）等于从并行程序开始执行，到所有进程执行完毕，墙上时钟走过的时间,，也称之为,墙上时间,（,wall time,）对各个进程，墙上时间可进一步分解为：,,计算,CPU,时间,,通信,CPU,时间,,同步开销时间,,进程空闲时间,（是由同步导致的）,,并行程序执行时间,计算,CPU,时间,,进程指令执行所花费的,CPU,时间，它可以分解为两个部分，一个是程序本身指令执行占用的,CPU,时间，即通常所说的用户时间（,user time,），主要包含指令在,CPU,内部的执行时间和内存访问时间，另一个是为了维护程序的执行，操作系统花费的,CPU,时间，即通常所说的系统时间（,system time,），主要包含内存调度和管理开销、,I/O,时间、以及维护程序执行所必需要的操作系统开销等通常地，系统时间可以忽略。
并行程序执行时间,通信,CPU,时间,,,包含进程通信花费的,CPU,时间同步开销时间,,,包含进程同步花费的时间,,进程空闲时间,,,当一个进程阻塞式等待其他进程的消息时，,CPU,通常是空闲的，或者处于等待状态进程空闲时间是指并行程序执行过程中，进程所有这些空闲时间的总和显然，进程的计算,CPU,时间小于并行程序的墙上时间，而并行程序的,墙上时间,才是用户真正关心的时间，是评价一个并行程序执行速度的时间9/30/2024,9,/59,并行算法设计及效能分析,并行算法效能分析,并行加速比,并行效率,可扩展性,（简单表述）,,处理机数,p,增加时，并行效率,E,p,不显著下降效能分析分析说明,需要说明的是，,T,1,指处理器个数为,1,时，并行程序的执行时间通常情形下，,T,1,大于,TS,，因为并行程序往往引入一些冗余的控制和管理开销加速比和效率是衡量一个并行程序性能的最基本的评价方法显然，执行最慢的进程将决定并行程序的性能在以上加速比和效率的定义中，有一个基本的假设，要求并行机的各个处理器是同构,(homogeneous),的，即并行机各个处理器的结构完全一致（包含,CPU,类型、内存大小与性能、,cache,特征等等），或者说，串行程序在各个处理器执行的墙上时间相等。
效能分析分析说明,如果并行机的各个处理器功能不一致，称之为异构并行机对此，以上加速比和效率的定义不是很合适其中，两个突出的问题就是，串行程序的执行时间是选择最快的处理器运行，还是选择最慢的处理器运行？在效率定义中，处理器个数选择为,P,是否合适？一个比较好的方法就是，将所有处理器以最快的处理器为基准，进行归一化处理并行程序性能评价方法,以上介绍的加速比和效率，只能反映并行程序的整体执行性能，但是，无法反映并行程序的性能瓶颈性能评价的主要目的在于，揭示并行程序的性能瓶颈，指导并行程序的性能优化因此，有必要进一步分解加速比和效率，提出更细致的性能评价方法并行计算性能评测,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,和存储器的某些基本性能指标,,并行通信开销,,机器的成本、价格、和性能,/,价格比等,,算法级,的性能评测,,加速比,,效率,,可扩展性,,程序级,的性能评测,,基本测试程序,,数学库测试,,并行测试程序等,并行机基本性能参数一览表,名称,符号,含义,单位,机器规模,n,处理器的数目,无量纲,时钟速率,f,时钟周期长度的倒数,MHz,工作负载,W,计算操作的数目,Mflops,顺序执行时间,T,1,程序在单处理机上的运行时间,s,并行执行时间,T,n,程序在并行机上的运行时间,s,速度,R,n,=W/T,n,每秒百万次浮点运算,Mflops,加速,S,n,=T1/T,n,衡量并行机有多快,无量纲,效率,E,n,=S,n,/n,衡量处理器的利用率,无量纲,峰值速度,R,peak,=nR,’,peak,所有处理器峰值,(R,’,peak,),速度之积,Mflops,利用率,U=R,n,/R,peak,可达速度与峰值速度之比,无量纲,通信延迟,t,0,传送,0,个字节或单字的时间,us,渐近带宽,r,∞,传送长消息通信速率,MB/,s,工作负载,工作负载（荷）：计算操作数目,,执行时间,—,掠过时间：墙上时间,,所执行的指令数目,,所完成的浮点运算数,CPU,的某些基本性能指标,工作负载,,执行时间,:,程序从开始到结束的时间。
浮点运算数,,指令数目 ：通常用百万条指令,,,并行执行时间,T,n,,：,T,,comput,,为计算时间，,T,paro,,为并行开销时间，,T,comm,为相互通信时间,,,,,T,n,= T,,comput,+ T,,paro,+ T,,comm,,,,,例：估计,APRAM,模型下执行时间,,,,,其中,T,1,为串行时间，,n,为处理器数，,T,∞,为使用无限多处理器且不考虑,T,,paro,与,T,,comm,,的并行执行时间,存储器性能,存储器的层次结构,(C, L, B),,-----,容量,C,，延迟,L,，带宽,B,,,,,,,估计存储器的带宽,,RISC,指令,add r1,r2,r3,，寄存器,,8bytes,，主频,100MHz,,B = 3*8*100*10,6,B/s= 2.4GB/s,并行与通信开销,并行和通信开销：相对于计算很大PowerPC (,每个周期,15ns,执行,4flops;,创建一个进程,1.4ms,可执行,372000flops),,开销的测量：乒,--,乓方法（,Ping-Pong Scheme,）,节点,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-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_time[i] = total_time/2,,else if,（,my_node_id = 1,）,then /*,接收者*,/,,receive an m-byte message from node 0,,send an m-byte message to node 0,,,endif,并行开销的表达式：点到点通信,通信开销,,t,(,m,) =,t,0,+,m,/,r,∞,,通信启动时间,t,0,,渐近,带宽,r,∞,,：,传送无限长的消息时的通信速率,,m,为传输的字节数,,,半,峰值长度,m,1/2,：达到一半渐近带宽所要的消息长度,,特定性能,π,0,：表示短消息带宽,,,t,0,= m,1/2,/,,r,∞,= 1 /,π,0,并行开销的表达式：组通信,典型的组通信有：,,播送,（,Broadcasting,）：,处理器,0,发送,m,个字节给所有的,n,个处理器,----,广播,,收集,（,Gather,）：,处理,0,接收所有,n,个处理器发来在消息，所以处理器,0,最终接收了,m,x,n,个字节；,,散射,（,Scatter,）：,处理器,0,发送了,m,个字节的不同消息给所有,n,个处理器，因此处理器,0,最终发送了,m,x,n,个字节；,,全交换,（,Total Exchange,）：,每个处理器均彼此相互发送,m,个字节的不同消息给对方，所以总通信量为,m,x,n,2,个字节；,,循环移位,（,Circular-shift,）：,处理器,i,发送,m,个字节给处理器,i+1,，,处理器,n-1,发送,m,个字节给处理器,0,，所以通信量为,m,x,n,个字节。
机器的成本、价格与性,/,价比,机器的成本与价格,,机器的性能,/,价格比,Performance/Cost Ratio,：,系指用单位代价（通常以百万美元表示）所获取的性能（通常以,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,基准测试程序,算法级性能评测,加速比性能定律,,并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍Amdahl,定律,,Gustafson,定律,,Sun Ni,定律,,可扩放性评测标准,,等效率度量标准,,等速度度量标准,,平均延迟度量标准,Amdahl,定律（,1967,）,参数约定,,P,：,处理器数；,,W,：,问题规模（计算负载、工作负载，给定问题的总计算量）；,,W,s,：,应用程序中的串行分量，,f,是串行分量比例 （,f = W,s,/W,，,W,s,=W,1,）；,,W,P,：,应用程序中可并行化部分，,1,-,f,,为并行分量比例；,,W,s,+W,p,=W,；,,T,s,=T,1,：,串行执行时间，,T,p,：,并行执行时间；,,S,：,加速比，,E,：,效率；,,出发点：,,固定不变的计算负载；,,固定的计算负载分布在多个处理器上；,,增加处理器加快执行速度，从而达到了加速的目的。
Amdahl,定律,（,cont‘d),固定负载的加速公式：,,,,归一化：,W,s,+ W,p,可相应地表示为,f+,（,1-f,）,,,,,,近似公式：,p→∞,时，上式极限为,S= 1 / f,,考虑额外开销,W,o,：,,Amdahl’s law (cont’d),Gustafson,定律（,1988,）,出发点：,,对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的此时为提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；,,除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义Gustafson,定律（,1988,）,,,Gustafson,加速定律,:,,,,近似公式：,p→∞,时，,S’=,p-fp,=(1-f)P,1-f,为斜率,,并行开销,W,o,：,,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,定律,存储受限的加速公式 ：,,,,,,并行开销,W,o,:,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,和,N i,加速均比,Amdahl,加速和,Gustafson,加速为高加速比讨论,参考的加速经验公式：,p/log p≤S≤P,,线性加速比：很少通信开销的矩阵相加、内积运算等,,p/log p,的加速比：分治类的应用问题,,通信密集类的应用问题 ：,S = 1 / C,（,p,）,, C,（,p,）,为与,p,有关的通信函数,,超线性加速：并行搜索，,Cache,效应,,绝对加速：最佳并行算法与串行算法,,相对加速：同一算法在单机和并行机的运行时间,可扩展分析,给定并行算法（程序）和并行机，如何调整参与并行计算的处理器个数,P,和求解问题的计算规模,W,，使得随着处理器个数的增长，并行计算的效率可以保持不变，称之为并行程序和并行机相结合的可扩展分析。
可扩展分析是并行计算一个重要研究课题，被广泛应用于描述并行算法（程序）能否有效利用可扩展的处理器个数的能力可扩展分析目的,通常地，可扩展分析具有四个目的：,,选择合理的算法与结构组合,,,确定求解某类问题的何种并行算法与何种并行机的组合，它可以有效地利用所期望的处理器规模,性能预测,,,对于运行在某台并行机上的某种算法（程序），根据算法（程序）在小处理器规模上的运行性能，预测该算法（程序）移植到大处理器规模上后运行的性能最优性能选择,,,对某类算法，假设问题规模固定，确定在某类并行机上最优的处理器个数和可获得的最优的加速比指导性能优化指导改进并行算法（程序），使得并行算法充分利用可扩展的处理器规模指导性能优化,,,指导改进并行算法（程序），使得并行算法充分利用可扩展的处理器规模可扩展分析方法（,1,）,等效率度量,,对于某类算法和并行机，如何保持问题规模,W,与处理器个数,P,之间的关系,W,p,P,q,，使得随着处理器个数,P,的增长，保持并行计算的效率不变也就是求出等效率函数：,,,,W=,,f,E,(,P),,E,固定,,,等效率值越小，则当处理器个数增多时为保持相同效率所需增加的问题规模就越小，因此就有更好的可扩展性。
可扩展分析方法（,2,）,等速度度量,,对于运行在并行机上的某个算法，当处理器个数增加时，需要增加多大的计算量，才能保持并行程序的平均速度不变定义平均速度,:,,V,为并行程序的执行速度，问题规模从,(,W, P),,变化到,(,W,’,, P,’,),，则等速度可扩展度量公式可写为：,,,越接近,1,，说明可扩展性越好并行程序性能优化,并行程序的性能优化相对于串行程序而言更加复杂，其中最主要的是选择好的并行算法及通信模式在并行算法确定之后，影响并行程序效率的主要因素是通信开销、由于数据相关性或负载不平衡引起的进程空闲等待、以及并行算法引入的冗余计算在设计并行程序时，可以采用多种技术来减少或消除这些因素对并行效率的影响并行程序优化技术,1.,减少通信量、提高通信粒度,,2.,全局通信尽量利用高效聚合通信算法,,3.,挖掘算法的并行度，减少,CPU,空闲等待,,4.,负载平衡,,5.,通信、计算的重叠,,6.,通过引入重复计算来减少通信,1.,减少通信量、提高通信粒度,在消息传递并行程序中，花费在通信上的时间是纯开销，因此如何减少通信时间是并行程序设计中首先要考虑的问题减少通信时间的途径主要有三个：减少通信量、提高通信粒度和提高通信中的并发度,(,即不同结点对间同时进行通信，要注意的是，这些手段都是相对于特定条件而言的，例如，在网络重负载的情况下，提高通信并行度并不能改善程序的性能,),。
提高通信粒度的有效方法是减少通信次数，即尽可能将可以一起传递的数据合并起来一次传递在收发不同类型的数据时，定义适当的,MPI,数据类型来避免内存中的数据拷贝2.,全局通信尽量利用高效聚合通信算法,当组织多个进程之间的聚合通信时，使用高效的通信算法可以大大提高通信效率、降低通信开销对于标准的聚合通信，如广播、归约、数据散发与收集等，尽量调用,MPI,标准库中的函数，因为这些函数往往经过专门优化但使用标准库函数的一个缺点是整个通信过程被封装起来，无法在通信的同时进行计算工作，此时，可以自行编制相应通信代码，将其与计算过程结合起来，以达到最佳的效果3.,挖掘算法的并行度，减少,CPU,空闲等待,一些具有数据相关性的计算过程会导致并行运行的部分进程空闲等待在这种情况下，可以考虑改变算法来消除数据相关性某些情况下数据相关性的消除是以增加计算量做为代价的，这方面的典型例子有用,Jacobi,迭代替换,Gauss,–,Seidel,或超松弛迭代、三对角线性方程组的并行解法等当算法在某个空间方向具有相关性时，应该考虑充分挖掘其他空间方向以及时间上的并行度，在这类问题中流水线方法往往发挥着重要的作用4.,负载平衡,负载不平衡是导致进程空闲等待的另外一个重要因素。
在设计并行算法时应该充分考虑负载平衡问题，必要时使用动态负载平衡技术，即根据各进程计算完成的情况动态地分配或调整各进程的计算任务动态调整负载时要考虑负载调整的开销及由于负载不平衡而引起的空闲等待对性能的影响，寻找最优负载调整方案5.,通信、计算的重叠,通过让通信与计算重叠进行，利用计算时间来屏蔽通信时间，是减少通信开销的非常有效的方法实现通信与计算重叠的方法一般基于非阻塞通信，先发出非阻塞的消息接收或发送命令，然后处理与收发数据无关的计算任务，完成这些计算后再等待消息收发的完成通信与计算的重叠能否实现，除了取决于算法和程序的实现方式之外，还取决于并行机的通信网络及通信协议6.,通过引入重复计算来减少通信,有时通过适当引入一些重复计算，可以减少通信量或通信次数由于当前大部分并行机的计算速度远远快于通信速度，并且一些情况下，当一个进程计算时，其他进程往往处于空闲等待状态，因而适当引入重复计算可以提高程序的总体性能例如一些公共量的计算，可以由一个进程完成然后再发送给其他进程，也可以各进程分别独立计算后一个做法在性能上通常要好于前一个做法另外一个通过引入重复计算来提高通信粒度。