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,时间小于并行程序的墙上时间，而并行程序的,墙上时间,才是用户真正关心的时间，是评价一个并行程序执行速度的时间11/3/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)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_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,定律,（,contd),固定负载的加速公式：,归一化：,W,s,+W,p,可相应地表示为,f+,（,1-f,）,近似公式：,p,时，上式极限为,S=1/f,考虑额外开销,W,o,：,Amdahls law(co。