高性能计算导论：并行计算性能评价1

并行计算性能评价上海大学计算机工程与科学学院计算的本质串行计算模型—图灵机并行计算模型计算效能评价计算模型与效能评价高性能计算导论“并行计算”研究的四大分支并行计算机体系结构并行算法并行程序设计并行计算的性能评测而介于并行计算机体系结构与并行算法之间的是并行计算模型。PerformanceEvaluation并行计算效能评价程序性能评价与优化给定并行算法，采用并行程序设计平台，通过并行实现获得实际可运行的并行程序后，一个重要的工作就是，在并行机上运行该程序，评价该程序的实际性能，揭示性能瓶颈，指导程序的性能优化。性能评价和优化是设计高效率并行程序必不可少的重要工作。并行程序执行时间评价并行程序的性能之前，必须清楚并行程序的执行时间是由哪些部分组成的。众所周知，独享处理器资源时，串行程序的执行时间近似等于程序指令执行花费的CPU时间。但是，并行程序相对复杂，其执行时间（executiontime）等于从并行程序开始执行，到所有进程执行完毕，墙上时钟走过的时间，也称之为墙上时间（walltime）。对各个进程，墙上时间可进一步分解为：计算CPU时间通信CPU时间同步开销时间进程空闲时间（是由同步导致的）并行程序执行时间计算CPU时间进程指令执行所花费的CPU时间，它可以分解为两个部分，一个是程序本身指令执行占用的CPU时间，即通常所说的用户时间（usertime），主要包含指令在CPU内部的执行时间和内存访问时间，另一个是为了维护程序的执行，操作系统花费的CPU时间，即通常所说的系统时间（systemtime），主要包含内存调度和管理开销、I/O时间、以及维护程序执行所必需要的操作系统开销等。通常地，系统时间可以忽略。并行程序执行时间通信CPU时间包含进程通信花费的CPU时间。同步开销时间包含进程同步花费的时间进程空闲时间当一个进程阻塞式等待其他进程的消息时，CPU通常是空闲的，或者处于等待状态。进程空闲时间是指并行程序执行过程中，进程所有这些空闲时间的总和。显然，进程的计算CPU时间小于并行程序的墙上时间，而并行程序的墙上时间才是用户真正关心的时间，是评价一个并行程序执行速度的时间。2020/4/139/59并行算法设计及效能分析并行算法效能分析并行加速比时间台处理机并行所需要的串行计算所需要的时间PTTSpp1并行效率%100pppEpSE一般地可扩展性（简单表述）处理机数p增加时，并行效率Ep不显著下降。效能分析分析说明需要说明的是，T1指处理器个数为1时，并行程序的执行时间。通常情形下，T1大于TS，因为并行程序往往引入一些冗余的控制和管理开销。加速比和效率是衡量一个并行程序性能的最基本的评价方法。显然，执行最慢的进程将决定并行程序的性能。在以上加速比和效率的定义中，有一个基本的假设，要求并行机的各个处理器是同构(homogeneous)的，即并行机各个处理器的结构完全一致（包含CPU类型、内存大小与性能、cache特征等等），或者说，串行程序在各个处理器执行的墙上时间相等。效能分析分析说明如果并行机的各个处理器功能不一致，称之为异构并行机。对此，以上加速比和效率的定义不是很合适。其中，两个突出的问题就是，串行程序的执行时间是选择最快的处理器运行，还是选择最慢的处理器运行？在效率定义中，处理器个数选择为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基准测试程序并行计算的性能评测机器级的性能评测1.CPU和存储器的某些基本性能指标2.并行通信开销3.机器的成本、价格、和性能/价格比等算法级的性能评测1.加速比2.效率3.可扩展性程序级的性能评测1.基本测试程序2.数学库测试3.并行测试程序等并行机基本性能参数一览表名称符号含义单位机器规模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工作负载工作负载（荷）：计算操作数目1.执行时间—掠过时间：墙上时间2.所执行的指令数目3.所完成的浮点运算数CPU的某些基本性能指标工作负载•执行时间:程序从开始到结束的时间。•浮点运算数•指令数目：通常用百万条指令并行执行时间Tn：Tcomput为计算时间，Tparo为并行开销时间，Tcomm为相互通信时间Tn=Tcomput+Tparo+Tcomm例：估计APRAM模型下执行时间其中T1为串行时间，n为处理器数，T∞为使用无限多处理器且不考虑Tparo与Tcomm的并行执行时间TnTTTnTn11,max存储器性能存储器的层次结构(C,L,B)-----容量C，延迟L，带宽B估计存储器的带宽•RISC指令addr1,r2,r3，寄存器8bytes，主频100MHz•B=3*8*100*106B/s=2.4GB/s寄存器1级高速缓存2级高速缓存主存磁盘远程存储器C2KBL=0周期B=1-32GB/S4-256KB0-2周期1-16GB/S64KB-4MB2-10周期1-4GB/S16MB-16GB10-100周期0.4-2GB/S1-100GB100K-1M周期1-16MB/S1-100GB100-100K周期1-300MB/S并行与通信开销并行和通信开销：相对于计算很大。•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/2elseif（my_node_id=1）then/*接收者*/receiveanm-bytemessagefromnode0sendanm-bytemessagetonode0endif并行开销的表达式：点到点通信通信开销t(m)=t0+m/r∞•通信启动时间t0•渐近带宽r∞：传送无限长的消息时的通信速率•m为传输的字节数半峰值长度m1/2：达到一半渐近带宽所要的消息长度特定性能π0：表示短消息带宽t0=m1/2/r∞=1/π0并行开销的表达式：组通信典型的组通信有：•播送（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基准测试程序算法级性能评测加速比性能定律•并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。•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定律（cont‘d)固定负载的加速公式：归一化：Ws+Wp可相应地表示为f+（1-f）近似公式：p→∞时，上式极限为S=1/f考虑额外开销Wo：pWWsWpWsSP/)1(11)1(pfppffffSWpWpfpWpfWf)1(1)1(Amdahl’slaw(cont’d)程序中顺序部分的百分比f(c)0%1%2%3%4%100%加速比SS1024=1024/(1+1023f)1024x91x48x31x24x1xWpWpWpWpWpWpW1W1W1W1W1W1工作负载W处理器数P(a)123456T1T1TpTpTpTpTpTpT1T1T1执行时间T处理器数P(b)T1123456Gustafson定律（1988）出发点：•对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；•除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。Gustafson定律（1988）Gustafson加速定律:近似公式：p→∞时，S’=p-fp=(1-f)P,1-f为斜率并行开销Wo：PSSSSWWpWpWpWppWpWpWS/')p-f(p--p)f(p-f)p(fS'111