并行计算机体系结构第二章.ppt
第二章 并行计算机系统的性能度量,并行计算机系统的性能度量,硬件效率、各功能部件之间的性能平衡软件效率软硬件和需求之间的性能匹配。理想的系统应该是无瓶颈的平衡系统、结构支持应用，应用适应结构理想的计算机是为应用量身定制的计算机,并行计算机系统的性能度量,衡量计算机性能的指标 计算速度、存储容量、响应时间、通信带宽和系统吞吐率、每条指令的平均执行时间为了降低计算机成本，我们通过硬件功能的软化实现，比如我们将视频解压卡换为信息解压软件。,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*106）=f/(CPI*106)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的工作量为Wi=fiW则，其中V1为单机运行速度。,2.3.2 加速比通式,当程序的并行度大于系统的处理机数时（iP），应该将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台处理器全部工作。设串行工作量W1=f1W，Wp=（1-f1）W。此时S(P)转化为希望f1越小越好，也被称作串行瓶颈。,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=20T3=32 串行通信时间T6=100 通信软件协议延迟d=T1+T2+T3+T4+T5+T6,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并行度指令百分比；em：并行负载系数,N：程序执行过程中的同步次数；B:每次通讯时一个节点向另一个节点发送的字节数K:每次通信时一个节点需要通信的节点数T0:每次通信的软件开销Tb：每次通信的平均延迟时间：通信隐藏系数，并行计算与通信重叠时间占通信时间的百分比,2.3.6 粒度匹配加速比模型,设在P台机器上执行的时间为T(P)，同步时间为Ts，通信时间为Tc,2.3.6 粒度匹配加速比模型,2.3.6 粒度匹配加速比模型,Gs=V1t，被称为同步粒度，为每次同步损失的节点计算量。与系统同步机制和结点速度有关。Go=V1T0，系统开销粒度，每次通信的系统开销时间损失的节点计算量。与系统通信机制和节点速度有关Gb=V1Tb，系统延迟粒度，每次通信时建立时间和阻塞时间引起的延迟损失的节点计算量。与节点存储器、网络接口、特性、消息特性和节点速度有关。Gc=V1/W，系统通信带宽对节点速度的支持能力，与网络带宽和节点速度有关。,2.3.6 粒度匹配加速比模型,gs=Ic/N，应用同步粒度，两次同步间平均执行的指令条数。取决于程序特性gb=Ic/NK，应用延迟粒度，每次通信延迟时间内执行的指令条数。gc=Ic/NPKB，通信的单位字节平均支持的指令条数em反映各节点不行负载的不平衡程度，em=1说明各个结点负载时平衡的。书25页，例题2.4,并行系统的效率和可扩展性,加速比S(P)的最大值，应该是系统的结点数P。实际受到串行瓶颈、负载不平衡、同步和通信开销等问题，实际S(p)P。为了表征并行系统加速比接近P的程序，用效率E(P)进行描述。E(P)=S(p)/P。E(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)=1时，是超线性可扩展的。,2.3.8 并行系统的并行质量,并行计算冗余度表示程序并行化后负载增加的程度，也可以用来分析软硬件之间并行性的匹配程度。设程序在P处理机和单处理机上运行的总操作数分别为I(P)和I(1)，则并行计算的冗余度R(P)定义为 R(P)=I(P)/I(1),2.3.8 并行系统的并行质量,并行系统利用率U(P)表示并行程序在并行处理机上运行时保持忙碌状态资源的百分比。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),
