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,并行计算效能评价,Performance Evaluation并行计算效能评价,程序性能评价与优化,给定并行算法，采用并行程序设计平台，通过并行实现获得实际可运行的并行程序后，一个重要的工作就是，在并行机上运行该程序，评价该程序的实际性能，,揭示性能瓶颈，指导程序的性能优化,。,性能评价和优化是设计高效率并行程序必不可少的重要工作。,程序性能评价与优化给定并行算法，采用并行程序设计平台，通过并,并行程序执行时间,评价并行程序的性能之前，必须清楚并行程序的执行时间是由哪些部分组成的。众所周知，独享处理器资源时，串行程序的执行时间近似等于程序指令执行花费的CPU 时间。但是，并行程序相对复杂，其,执行时间（execution time）等于从并行程序开始执行，到所有进程执行完毕，墙上时钟走过的时间,，也称之为,墙上时间,（wall time）。,对各个进程，墙上时间可进一步分解为：,计算CPU 时间,通信CPU 时间,同步开销时间,进程空闲时间,（是由同步导致的）,并行程序执行时间评价并行程序的性能之前，必须清楚并行程序的执,并行程序执行时间,计算CPU 时间,进程指令执行所花费的CPU 时间，它可以分解为两个部分，一个是程序本身指令执行占用的CPU 时间，即通常所说的用户时间（user time），主要包含指令在CPU 内部的执行时间和内存访问时间，另一个是为了维护程序的执行，操作系统花费的CPU 时间，即通常所说的系统时间（system time），主要包含内存调度和管理开销、I/O 时间、以及维护程序执行所必需要的操作系统开销等。通常地，系统时间可以忽略。,并行程序执行时间计算CPU 时间,并行程序执行时间,通信CPU 时间,包含进程通信花费的CPU 时间。,同步开销时间,包含进程同步花费的时间,进程空闲时间,当一个进程阻塞式等待其他进程的消息时，CPU 通常是空闲的，或者处于等待状态。进程空闲时间是指并行程序执行过程中，进程所有这些空闲时间的总和。,显然，进程的计算CPU 时间小于并行程序的墙上时间，而并行程序的,墙上时间,才是用户真正关心的时间，是评价一个并行程序执行速度的时间。,并行程序执行时间通信CPU 时间,11/15/2024,9,/59,并行算法设计及效能分析,并行算法效能分析,并行加速比,并行效率,可扩展性,（简单表述）,处理机数,p,增加时，并行效率,E,p,不显著下降。,8/8/20239/59并行算法设计及效能分析并行算法效能分,效能分析分析说明,需要说明的是，,T,1 指处理器个数为1 时，并行程序的执行时间。通常情形下，,T,1 大于,TS,，因为并行程序往往引入一些冗余的控制和管理开销。,加速比和效率是衡量一个并行程序性能的最基本的评价方法。显然，执行最慢的进程将决定并行程序的性能。,在以上加速比和效率的定义中，有一个基本的假设，要求并行机的各个处理器是同构(homogeneous)的，即并行机各个处理器的结构完全一致（包含CPU 类型、内存大小与性能、cache 特征等等），或者说，串行程序在各个处理器执行的墙上时间相等。,效能分析分析说明需要说明的是，T1 指处理器个数为1 时，并,效能分析分析说明,如果并行机的各个处理器功能不一致，称之为异构并行机。对此，以上加速比和效率的定义不是很合适。其中，两个突出的问题就是，串行程序的执行时间是选择最快的处理器运行，还是选择最慢的处理器运行？在效率定义中，处理器个数选择为,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 基准测试程序,并行计算性能评测3.1 并行机的一些基本性能指标,并行计算的性能评测,机器级,的性能评测,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,并行机基本性能参数一览表名称符号含义单位机器规模n处理器的数,工作负载,工作负载（荷）：计算操作数目,执行时间掠过时间：墙上时间,所执行的指令数目,所完成的浮点运算数,工作负载工作负载（荷）：计算操作数目,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,的并行执行时间,CPU的某些基本性能指标工作负载,存储器性能,存储器的层次结构(C,L,B),-容量C，延迟L，带宽B,估计存储器的带宽,RISC指令 add r1,r2,r3，寄存器 8bytes，主频 100MHz,B=3*8*100*10,6,B/s=2.4GB/s,存储器性能存储器的层次结构(C,L,B),并行与通信开销,并行和通信开销：相对于计算很大。,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,Ping-Pong Schemeif（my _node _,并行开销的表达式：点到点通信,通信开销,t,(,m,)=,t,0,+,m,/,r,通信启动时间,t,0,渐近带宽r,：传送无限长的消息时的通信速率,m为传输的字节数,半峰值长度m,1/2,：达到一半渐近带宽所要的消息长度,特定性能,0,：表示短消息带宽,t,0,=m,1/2,/,r,=1/,0,并行开销的表达式：点到点通信 通信开销 t(m)=t0,并行开销的表达式：组通信,典型的组通信有：,播送,（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 基准测试程序,并行计算性能评测3.1 并行机的一些基本性能指标,算法级性能评测,加速比性能定律,并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）