Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,,‹#›,,,,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,,*,,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,,*,,,第二章,,并行计算机系统的性能度量,并行计算机系统的性能度量,硬件效率、各功能部件之间的性能平衡,软件效率,软硬件和需求之间的性能匹配理想的系统应该是无瓶颈的平衡系统、结构支持应用，应用适应结构,理想的计算机是为应用量身定制的计算机,并行计算机系统的性能度量,衡量计算机性能的指标,,计算速度、存储容量、响应时间、通信带宽和系统吞吐率、每条指令的平均执行时间,,为了降低计算机成本，我们通过硬件功能的软化实现，比如我们将视频解压卡换为信息解压软件2.1,计算机速度,计算机通过运行程序来完成工作不能用一段程序的运行时间来衡量计算机的性能，往往一段程序的运行与它跟计算机适应的程序相关,为了客观综合描述计算机系能，我们往往用大量程序运行的运行速度进行衡量，或者我们还可以用所谓的制定运行库来衡量计算机性能。
2.1,计算机速度,为了定量讨论机器速度，定义下列参数,ζ,：时钟周期,f=1/,ζ,：时钟频率,CPI,：执行每条指令的平均周期数IPC=1/CPI,：平均每拍流出的指令数Ic,：给定程序的指令数,T,：给定程序的执行时间TFU,：功能部件时间常数，一般为功能部件的流水线段数,+2.,2.1,计算机速度,指令条数,Ic,的程序的执行时间为,T=Ic*CPI*,ζ,指令的执行：取指令、指令译码、取操作数、操作、存操作数指令部件和功能部件协同完成在流水线中，指令流出时就完成了译码，所以每条指令有一个与操作相关的功能部件时间常数和数据传送的最小执行周期数对,R-R,型指令，,CPI=TFU,2.1,计算机速度,对,m-m,型指令，,CPI=TFU+mk,其中,k,为存储器周期与时钟周期之比，,m,为访存次数当访存出现冲突时，导致,CPI,增加2.1,计算机速度,T=Ic*,（,TFU+mk,）,*,ζ,Ic,：与应用程序、指令系统和编译有关；,ζ,：机器主频的倒数受限于指令功能的复杂程度、器件的水平和采用的技术，与指令系统和实现技术有关,m,：与存储系统结构和访存指令类型有关,k,：与存储器结构、实现技术和,ζ,有关。
TFU,：与指令功能、实现技术和,ζ,有关2.1.1 MIPS,、,Flops,和,PDR,MIPS,速率,设,C,为执行已知程序的时钟周期数则,T=C*t,MIPS M,指令,/,秒MIPS=I/,（,T*10,6,）,=f/(CPI*10,6,),MIPS,与时钟频率成正比，与,CPI,成反比,计算机系统中的指令系统、编译器、处理器和存储技术对,MIPS,都有影响2.1.1 MIPS,、,Flops,和,PDR,MIPS,提高,MIPS,的最有效的办法就是提高主频和每拍流出的指令条数为提高主频：指令尽量简洁，功能实现的逻辑时间短，推动了,RISC,的发展,为提高,IPC,：超长指令字，超标量和并行处理机2.1.1 MIPS,、,Flops,和,PDR,Mflops,：,反映计算机每秒产生的结果数，不计指令仅计结果比,MIPS,公正MIPS,和,Mflops,都没有考虑机器的字长或数据的精度但是精度与机器性能直接相关2.1.1 MIPS,、,Flops,和,PDR,PDR,：,对不同操作和字长加权后的每秒处理多少位数据用以衡量计算机的速度,PDR=L/R,L=0.85*,定点指令位数,+0.15*,浮点指令数,+0.4*,定点数字长,+0.15*,浮点数字长,R=0.85*,定点加时间,+0.09*,浮点加时间,+0.06*,浮点乘时间,2.1.2 SPEC,和,TPS,SPEC,：,为了公正的评价计算机的性能，推出基准测试程序，用这些程序在被测机上运行的时间除对应程序的参考时间所得值的几何平均值就是所谓的,SPEC,分数值。
SPEC,主要针对处理器、存储器和编译性能的测试，不针对,I/O,和通信性能测试，尤其不适合于多机系统的性能评价2.1.2 SPEC,和,TPS,TPS,：,TPS,评价更佳侧重于事务处理，单位时间内完成的交易主要取决于计算机硬件的计算、,I/O,和通信速度，也取决于操作系统和数据库等软件性能2.2,并行计算机的速度计算,并行化的应用程序在并行计算机上的执行时间最能反映并行系统的处理性能与系统提供的性能支持、应用程序特性、并行算法、并行程序和并行编译水平有关应能最大程度地利用并行系统中处理机资源，发挥其性能潜力2.2.1,算术平均速度,2.2.2,调和平均速度,2.2.3,几何平均速度,2.3,并行计算机的加速比和效率,程序的并行性,并行度：并行化程序在有,p,个处理机的系统上运行，使用的处理机的数目，为时间的函数，记作,DOP,（,t,）,<=p,t0-t1,期间并行度的算术平均值，称为程序的并行性,A,2.3.2,加速比通式,加速比反映并行系统运行并行程序时系统并行能力发挥的程度加速比定义为,,其中,T(1),是程序在单处理机上执行完的时间，,T(n),是程序以并行度,i,（,i<=P,，其中,P,为处理机数目）并行执行完程序的时间。
1<=S(p)<=P,2.3.2,加速比通式,多机运行过程中，一定会有多个计算机之间的通信,,,设总工作量为,W,，并设程序中并行度为,i,的工作量为,W,i,=f,i,W,则，其中,V1,为单机运行速度2.3.2,加速比通式,当程序的并行度大于系统的处理机数时（,i>P,），应该将,i,按,P,进行分组，需要运行的次数为,i/P,次，此时的加速比,,,,其中,O(n),为并行开销，包括并行化开销、交互开销和通信开销等，是一个与硬件、软件和应用均有关的函数目前,O(n),已经是影响大规模并行处理系统性能发挥的瓶颈2.3.2,加速比通式,为了突出并行度对加速比的贡献，有些加速比公式中，往往假设,O(n)=0,，加速比公式将转化为,,,其实现在多机系统中,O(n),程序研制并行系统的关键技术之一，无法忽视为,0,上述的,S(p),仅仅是理想状态下的值书,19,页例题,2.1,，,2.2,,,,,2.3.3,固定负载加速比,固定负载加速比中，假设只有两种工作：串行工作和全并行工作，所谓全并行工作就是,P,台处理器全部工作设串行工作量,W,1,=f,1,W,，,W,p,=,（,1-f,1,）,W,。
此时,S(P),转化为,,,,希望,f,1,越小越好，也被称作串行瓶颈2.3.3,固定负载加速比,固定负载加速比中，我们发现只要增加并行工作的工作量比如我们把并行工作的工作量增大,P,倍，则加速比工作可以转化为,,,,我们可以发现，当并行工作量增加,P,倍的时候，在,P,台处理机上执行的时间和在一台处理机上执行的时间相同但是大家有没有发现公式的问题呢？,2.3.4,固定时间加速比,在刚刚的公式中，我们发现公式的问题也就是并行工作量增加了,p,倍之后，分子上的并行工作量并未随着发生改变在此基础上我们导出固定时间加速比,,,,,,,2.3.5,固定存储加速比,在多机系统中，处理机数扩展至,P,倍，系统的存储能力也应该做相应的增加对于有些空间复杂性低于时间复杂性的科学计算问题，系统存储容量的增大，可支持更大的并行工作量的增加，增加的倍数为,G(p),倍（,G(P)>=P,）G(P),受限于存储器的容量则得到如下加速比公式,,,,,,2.3.5,固定存储加速比,在上面的公式中，如果多计算系统中的存储器不是全局共享，则,G(P)=P,，此时变成固定时间加速比当并行负载并不增加时，变成固定负载加速比。
一般情况下随着存储容量的增加，其并行工作量的增加,G(P)>P,，所以固定负载加速比会比固定时间加速比有更好的加速能力和可扩展性书,22,页例题,2.3,2.3.6,粒度匹配加速比模型,前面我们提到的并行程序不包括并行化和任务间的互操作开销并行化包括进行的管理、分配和查询等操作，开销来自软件系统；互操作包括进程间的同步、通信和集散等操作，开销取决于同步与通信系统的性能而并行化和互操作开销往往与程序的粒度紧密结合2.3.6,粒度匹配加速比模型,补充：粒度及相关概念,粒度：衡量软件进程包含计算量的尺度比如程序段中的指令数目粒度分为粗、中、细三种粒度时延：各子系统之间通信开销的时间度量例如存储器的时延就是存储器完成一次读写锁完成的时间，处理器时间就是各个处理器之间互相同步的时间存储器容量越大时延越大，处理器数目越多时延越大粒度与时延密切相关2.3.6 粒度匹配加速比模型,作业或程序,子程序，部分作业或程序,过程、子程序和任务,非递归循环或迭代,指令或语句,并,行,性,程,度,,,,细粒度,中粒度,粗粒度,通,信,开,销,增,加,2.3.6 粒度匹配加速比模型,指令级：粒度一般包含的指令数小于,20,。
细粒度的并行性在,2~,数千范围变化优点：可以充分利用机器资源细粒度并行性的开发可以借助于优化编译器，自动检测并行性，并将源代码变成运行时系统能识别的并行形式2.3.6 粒度匹配加速比模型,循环级：循环操作在连续迭代中不相关，循环级并行性是在并行或者向量计算机上运行的最有程序结构但是递归循环的并行性优化难以实现2.3.6 粒度匹配加速比模型,作业级：对应在并行处理机上并行执行的独立作业，粒度在单个程序中可以达到数万条指令作业级并行性一般由加载程序和操作系统来处理2.3.6 粒度匹配加速比模型,细粒度并行性在指令级或循环级上借助并行化或向量化编译器来开发，中粒度并行性的开发需要程序员和编译器协同工作，粗粒度级的并行性取决于高效的操作系统和算法效率共享变量通信支持细粒度和中粒度，消息传递多计算机用于中粒度和粗粒度2.3.6 粒度匹配加速比模型,通信时延：不同的通信时延是由计算机体系结构、实现技术和通信方式决定的时延是机器规模扩展的限制因素比如存储器时延随着容量的增加而增大，所以存储器的容量不能无限制的增大通信方式由算法和系统结构决定并行系统：缩小通信时延、防止死锁、优化粒度,2.3.6 粒度匹配加速比模型,并行程序设计的两个基本问题：,,1.,如何将一个程序分解为合适的粒度。
以便获得尽可能短的运行时间2.,在计算中最佳的并行粒度是多大2.3.6 粒度匹配加速比模型,组合粒度前程序图,细粒度,每个节点用（,n,s,）,表示n,为节点名,s,为节点粒度两个节点之间的边,记为（,v,d,），,v,表示,输出或者输入的变量,d,表示节点之间的通,信延时,,组合粒度后,程序图,粗粒度,,粗细粒度比较,2.3.6 粒度匹配加速比模型,粒度组合先用细粒度获得较高的并行度，然后分析加大粒度是否会消除一些不必要的通信延迟或降低总的调度开销细粒度可以更好的利用资源，但是可能需要更多的处理机之间的通信粒度组合需要在并行性和调度开销中间取折中,2.3.6 粒度匹配加速比模型,单一依靠粒度组合，不一定就能得到一个好的调度调度方案动态处理机调度是,NP,难解问题，通常需要采用启发式方法以便得到局部优解我们主要介绍静态处理机调度方式2.3.6 粒度匹配加速比模型,结点复制：将某一处理机上的数据复制到其他处理机，达到降低处理机间通信延迟的目标结点复制前后调服方案,2.3.6 粒度匹配加速比模型,通常需要将粒度组合和结点复制结合起来来确定最佳力度和调度方案步骤：,,1.,构造细粒度程序图,,2.,调度细粒度运算,,3.,进行力度组合得到粗粒度,,4.,在组合图基础上产生并行调度方案,2.3.6 粒度匹配加速比模型,静态多处理机调度的程序分解,2.3.6 粒度匹配加速比模型,1.,细粒度分解：,乘法器,101,个周期,加法器,8,个周期,2.3.6 粒度匹配加速比模型,1.,细粒度分解：通信时间分析,T1=T2=T4=T5=20,T3=32,串行通信时间,T6= 100,通信软件协议延迟,d=T1+T2+T3+T4+T5+T6,M,M,2.3.6 粒度匹配加速比模型,2.,调度细粒度运算：,,2.3.6 粒度匹配加速比模型,2.,评价：,,2.3.6 粒度匹配加速比模型,3.,进行粒度组合得到粗粒度：,,2.3.6 粒度匹配加速比模型,3.,组合得到粗粒度产生并行调度方案：,,2.3.6,粒度匹配加速比模型,下面我们进行粒度分析,V1,：节点机的平均速度；,P,：节点机数目；,W,：网络的统计平均通信带宽；,t,：每次同步的平均时间,Ic,：程序的指令条数；,f1,：串行瓶颈；,1-f1,：程序中,P,并行度指令百分比；,e,m,：并行负载系数,N,：程序执行过程中的同步次数；,B:,每次通讯时一个节点向另一个节点发送的字节数,K:,每次通信时一个节点需要通信的节点数,T0:,每次通信的软件开销,Tb,：每次通信的平均延迟时间,β,：通信隐藏系数，并行计算与通信重叠时间占通信时间的百分比,2.3.6,粒度匹配加速比模型,设在,P,台机器上执行的时间为,T(P),，同步时间为,Ts,，通信时间为,Tc,2.3.6,粒度匹配加速比模型,2.3.6,粒度匹配加速比模型,G,s,=V,1,t,，被称为同步粒度，为每次同步损失的节点计算量。
与系统同步机制和结点速度有关G,o,=V,1,T,0,，系统开销粒度，每次通信的系统开销时间损失的节点计算量与系统通信机制和节点速度有关,G,b,=V,1,T,b,，系统延迟粒度，每次通信时建立时间和阻塞时间引起的延迟损失的节点计算量与节点存储器、网络接口、特性、消息特性和节点速度有关G,c,=V,1,/W,，系统通信带宽对节点速度的支持能力，与网络带宽和节点速度有关2.3.6,粒度匹配加速比模型,g,s,=I,c,/N,，应用同步粒度，两次同步间平均执行的指令条数取决于程序特性,g,b,=I,c,/NK,，应用延迟粒度，每次通信延迟时间内执行的指令条数g,c,=I,c,/NPKB,，通信的单位字节平均支持的指令条数,e,m,反映各节点不行负载的不平衡程度，,e,m,=1,说明各个结点负载时平衡的书,25,页，例题,2.4,并行系统的效率和可扩展性,加速比,S(P),的最大值，应该是系统的结点数,P,实际受到串行瓶颈、负载不平衡、同步和通信开销等问题，实际,S(p) 并行性好的系统，加速比应随并行度的增加而线性增加，或者效率随并行度的增加而保持常数我们用,C(P),来表示可扩展性并行系统的效率和可扩展性,C(P)=E(P)/E’(P),，其中,E’(P),是忽略了并行开销时的系统效率C(P)= E(P)/E’(P)= S(P)/S’(P)=1/[1+O(P)/T(P)],C(P),值越大系统可扩展性越好这里的,O(P),是总的并行开销，包括同步和通信开销并行系统的效率和可扩展性,为考察相对量的变化对可扩展性的影响，将,C,（,P,）定义为,,,,当,C(P)<=0,时，系统是不可扩展的；,0 U(P)=R(P)E(P),如果处理机的,CPI=1,，则有,I(1)=T(1),，此时有,2.3.8,并行系统的并行质量,,并行计算质量是用加速比、效率和冗余度的综合效果来表征在并行系统上并行计算的相对性能并行计算的质量用,Q(P),来表示Q(P)=S(P)E(P)/R(P),,,,,内容总结,第二章 并行计算机系统的性能度量TFU：功能部件时间常数，一般为功能部件的流水线段数+2.指令部件和功能部件协同完成对R-R型指令，CPI=TFU对m-m型指令，CPI=TFU+mkMIPS与时钟频率成正比，与CPI成反比MIPS和Mflops都没有考虑机器的字长或数据的精度t0-t1期间并行度的算术平均值，称为程序的并行性A上述的S(p)仅仅是理想状态下的值比如我们把并行工作的工作量增大P倍，则加速比工作可以转化为当并行负载并不增加时，变成固定负载加速比前面我们提到的并行程序不包括并行化和任务间的互操作开销存储器容量越大时延越大，处理器数目越多时延越大作业级：对应在并行处理机上并行执行的独立作业，粒度在单个程序中可以达到数万条指令单一依靠粒度组合，不一定就能得到一个好的调度调度方案gc=Ic/NPKB，通信的单位字节平均支持的指令条数。 0
