3章 加速比

第三章加速比性能模型与可扩展性分析3.1加速比性能模型3.1.1一般概念1．（MillionInstructionsPerSecond）MIPS=IN/（TE×106）每秒百万次指令TE：CPU执行IN条指令所花的时间。IN：要执行程序中的指令总数，不仅包括运算指令，还包括所有的服务性指令，如存取数、转移等，而浮点运算时是不包括服务性指令的。2．MFLOPS（MillionFloatingpointoperationsPerSecond）MFLOPS=INF/（TE×106）每秒百万次浮点运算。INF：表示程序中的浮点运算次数。同一程序运行在不同的计算机上时往往会执行不同数量的指令数，但浮点运算数常常是相同的。MFLOPS的值不仅随整数与浮点数的混合比例的不同而不同，还随快速与慢速浮点操作运算的混合比例而变化。（如浮点加比浮点除快）3．并行度（Degree Of Parallelism—DOP）并行度（DOP）是在一定时间间隔内执行一个程序所用的处理机的数目。4．并行性分布图执行一个给定的程序时DOP对时间的分布图，如图3-1所示。DOP与对应时间之积为处理机要完成的工作或工作负载。图3-1并行性分布图5．处理机数与时间积处理机数目P与处理时间Tp的乘积用以度量这些处理机运行时的工作量W。若一程序在P台处理机上运行的时间为Tp，则此P台处理机在Tp时间间隔内完成的工作最大数量为Tp*P。（在Tp时间内处理机数是可变的，但不会超过P。）6．平均并行性A完成的工作量总量W与所用时间之比。W=ΔwΣPi*ti i=1~mm：最大并行性Δw：单台处理机的处理能力Pi：并行度ti：DOP=Pi的时间总和A=W/Σti7．效率处理机实际工作曲线对时间的积分是这些处理机完成的有效工作量。效率为有效工作量与最大工作量之比。3.1.2加速比1．加速比在单机方式中，流水线方式相对于非流水线顺序串行方式速度提高的比值称加速比（Sp）。设：流水线段数m，指令有n条，各段经过的时间均为Δt则：此外，还有某种流水处理机相对于另一种流水处理机的加速比。如超标量流水处理机相对于常规标量流水处理机的加速比。在并行处理中也有加速比的概念。2．绝对加速比将最好的串行算法与并行算法相比较。定义一（与具体机器有关）将最好的串行算法在1台机器上的运行时间与并行算法在N台上运行的时间相比。定义二（与具体机器无关）将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。S=T(N)Tbest​​3．相对加速比同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。这种定义侧重于描述算法和并行计算机本身的可扩展性。S=T(N)T(1)​3.1.3三种加速比性能模型1．固定负载加速比性能模型—Amdahl定律在许多实时应用领域，计算负载的大小常固定。在并行机中，此负载可分布至多台并行执行，获得的加速比称为fixed-loadspeedup。1）Amdahl定律的推导一个问题的负载可表示如下：W=WsWp其中，Ws代表问题中不可并行化的串行部分负载，Wp表示可并行化的部分负载。则n个节点情况下，加速比可以表示如下：Sn=WsWp/nWsWp​设串行因子α为串行部分所占的比例。即α=WsWpWs​或1−α=WsWpWp​代入即得Amdahl定律：∴Sn=WsWpWs​WsWpWp/n​WsWpWsWp​​=α(1−α)/n1​不管采用多少处理机，可望达到的最好加速比：Sn=n→∞lim​α(1−α)/n1​=α1​效率En可以表示为：En=nSn​=[α(1−α)/n]×n1​=nα1−α1​=1(n−1)α1​处理机数目n越大，效率En越低。Amdahl定律告诉我们：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。加速比=没有采用改进措施前的性能采用改进措施后的性能​=采用改进措施后执行某任务的时间没有采用改进措施前执行某任务的时间​2）加速比的两个决定因素：（1）计算机执行某个任务的总时间中可被改进部分的时间所占的百分比，即可被改进部分占用时间/改进前整个任务的执行时间，记为Fe，它总小于1。（2）改进部分采用改进措施后比没有采用改进措施前性能提高的倍数，即：改进前改进部分执行时间/改进后改进部分执行时间，记为Se。∴S=(1−Fe)SeFe​1​例1假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40%，则整个系统的性能提高了多少？解：Fe=0.4，Se=10，∴S=(1−0.4)100.4​1​=1.56例2采用哪种实现技术来求浮点数平方根FPSQR的操作对系统的性能影响较大。假设FPSQR操作占整个测试程序执行时间的20%。一种实现方法是采用FPSQR硬件，使FPSQR操作的速度加快到10倍。另一种方法是使所有浮点数据指令的速度加快，使FP指令的速度加快到2倍，还假设FP指令占整个执行时间的50%。请比较这两种 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。解：Fe_FPSQR=0.2，Se_FPSQR=10，Fe_FP=0.5，Se_FP=2，∴SFPSQR​=(1−0.2)100.2​1​=1.22∴SFP​=(1−0.5)20.5​1​=1.333）固定问题规模的图形表示Amdahl定律又称为固定规模加速比模型，问题的规模不随处理机变化而变化。固定问题规模，看用并行技术能达到的最短时间是多少。在固定规模加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：固定负载WorkloadN执行时间随N增加而减少WsWpWsWpWsWsWp1234ExecutionTimeNTsTp1TsTp2TsTp3TsTp4Wp图3-2固定负载加速比模型下的负载和执行时间情况当处理器数目n=1024，加速比Sn随α变化的情况如下：S1024​=1(1024−1)α1024​=11023α1024​得出曲线如下图：α10243148911024图3-3n=1024时加速比Sn随α变化曲线Sn可以比较不同的α对加速比带来的不同影响：α=0Snnα=0.01α=0.1α=0.91α(1-α)/nSn=图3-4特定串行因子α下处理机数n与加速比Sn的关系曲线α=0时得到理想加速比，当α值增加时，加速比性能急剧下降。结论：加速比曲线随α的上升急剧下降，原因是存在顺序部分Ws，无法用增加系统的处理机数目来解决。这一性质在过去二十年间给人们造成了对并行处理非常悲观的印象。两种观点：a.劝阻制造商生产大规模并行计算机。b.研究并行编译器，以降低α的值，从而提高系统的性能。固定负载加速比模型的可能应用范围：一些对时间要求严格的应用问题。2．固定时间加速比性能模型—Gustafson定律小机器上解小问题，大机器上解大问题，（杀鸡不用宰牛刀），两者的执行时间大体相同。1）固定负载模型有缺陷：（1）因为Amdahl’law中，α取决于问题及并行编译器的效率，无法描述系统固有的特性。（2）当机器的规模扩大时，解题的规模不能随之扩大，从而防碍了系统性能的进一步扩展。2）Gustafson定律有许多应用领域强调运算精度而不是运行时间。1988年，Gustafson提出了固定时间加速比模型。当机器的规模扩大时，解题的规模也随着扩大，从而得到更加精确的解，而使运行时间保持不变。比如：有限元方法做结构分析，流体动力学做天气预报解PDE(偏微分方程组）就需要提高精度。粗格要求的计算量较少，而细格的计算量多，得到的精确度也较高。加速比的公式：Sn′=Ws′Wp′/nWs′Wp′​=WsWpWsnWp​=α(1−α)αn(1−α)​=n−α(n−1)其中，Wp’=nWp和WsWp=Ws’Wp’/n作为固定时间的条件，Wp’=nWp说明并行工作的负载线性地增加了n倍。Ws’Wp’/n表示在扩大负载后在增加处理机台数的情况下的平均负载（执行时间），它应当和负载没有扩大情况下的平均负载（执行时间）WsWp相等。即有WsWp=Ws’Wp’/n。同时，负载的串行部分并没有改变，即有Ws=Ws’。在固定时间加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：WsWpWsWpWsWpWsWpWorkloadN123ExecutionTimeNTsTp1TsTpTsTpTsTp并行负载不断增加执行时间固定4432图3-5 固定时间加速比模型下的负载和执行时间情况增大问题规模的办法使所有处理机保持忙碌状态，在问题扩大到与可用的计算能力匹配时，程序中的顺序部分就不再是瓶颈了。当处理器数目n=1024，加速比Sn随α变化的情况如下：S1024′​=n−α(n−1)=1024−1023αα图3-6固定时间加速比Sn随α变化曲线3.受限于存储器的加速比模型1993年，由Sun和Ni提出。大型科学计算和工程设计需要较大的存储空间，许多应用问题是存储器受限，而不是CPU受限或者I/O受限。解决方法：在分布存储系统中，根据总存储容量随节点数增加而线性增加，采用许多节点集合起来解一个大题。基本思想：要在存储空间有限条件下解尽可能大的问题，这同样需要扩展工作负载，才能提供更高的加速比、较高的精度和较好的资源利用率。加速比可以表示如下：Sn∗​=Ws∗​Wp∗​/nWs∗​Wp∗​​=WsG(n)Wp/nWsG(n)Wp​其中：在单个处理机上顺序执行的工作负载与问题的规模及系统的规模无关，即：Ws=Ws′=Ws∗​而G(n)反映的是存储容量增加n倍时并行工作负载增加的倍数。G(n)=W*扩大后W原来讨论：1.  G(n)=1，即为固定负载的情况；2.  G(n)=n，即存储器增加n倍，负载也增加n倍，为固定时间的情形；3.  G(n)>n，计算负载的增加情况比存储器增加快，会有较高的加速比。比较三种加速比，对于相同的处理机数量，有：Sn∗​≥Sn′​≥Sn​在受限于存储器的加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：1WsWsWpWsWpWsWpWpWorkloadn234ExecutionTimenTsTp1TsTp2TsTp3TsTp4规模扩展的工作负载执行时间稍有增加图3-7 受限于存储器的加速比模型下负载和执行时间情况例：n维矩阵乘法：A*B=C，其中A、B、C都是n*n的方阵。为得到C的每一个元素需要进行n次乘法、n-1→n次加法，所以总的计算量为：（nn)*n2=2n3。需要的存储量为3n2（两个源矩阵，一个结果矩阵）。如果n台计算机组成多计算机系统，则存储容量扩大n倍，那么矩阵的维数（原来为n)也可以增加了，设增加到N，那么加速比为多少？解：设每台计算机的容量为M，总存储容量变为：nM=n*3n2=3n3，而N维需要的存储量为3N2，计算量变为2N3，则有：3n3=3N2⇔N=n1.5∴G(n)=W原来​W扩大后∗​​=2n32N3​=2n32n4.5​=n1.5∴S∗=Ws​n1.5Wp​/nWs​n1.5Wp​​=Ws​n0.5Wp​Ws​n1.5Wp​​4.并行计算的应用模型随机器规模的增大，工作负载增长的模式如图3-8所示。在图3-8中，采用受限于存储器的加速比模型中给出的公式：θ曲线对应的G(n)=n1.5γ曲线对应的G(n)=nβ曲线对应的G(n)=0.5nSn∗​=WsG(n)Wp/nWsG(n)Wp​α曲线对应的G(n)=1则有加速比公式:5.效率在多机系统中，每个处理机平均提供的加速比。给定一个程序，假设Ws/Wp=0.4，那么效率为：0.4G(n)0.4G(n)/nE=nSn∗​​θ（指数）γ（线性）工作负载（问题规模）β（亚线性）α（常数）n图3-8 受限于存储器的加速比模型下机器规模与工作负载的关系相应的处理器数目—效率曲线如下图：效率θ（指数）n=3E=0.8745γ（线性）β（亚线性）nα（常数）图3-8 受限于存储器的加速比模型下机器规模与效率的关系结论：1.如果工作负载（问题规模）保持不变，那么效率E随机器规模的增大而迅速下降，其原因是开销比机器规模增加得快，为了使效率保持在一定的水平上，我们可以按比例增大机器规模和问题规模。2.如果工作负载按指数增长模式，效率要保持恒定或保持良好的加速比，必须使问题规模猛增才行，这样就会超过存储器或I/O限制，而问题规模只允许在计算机存储器可用的限度以内增长。并行计算机的应用模型如下图：3.2可扩展性分析3.2.1可扩展性概念1.可扩展性与可编程性增加可扩展性增加可编程性分布存储的消息传递型多计算机共享存储型多处理机理想并行计算机2.可扩展性指标机器规模（n）、问题规模（s）、存储容量（m）、I/O需求（d）、时钟频率（f）、CPU时间（T）、通信开销（h）、程序设计开销（p）、计算机价格（c）3.可扩展性的直观定义对任意数量（n）的处理机和任意规模（s）的问题，若所有算法的系统效率E=1，则系统是可扩展的。4.规模可扩展性系统性能随处理机数量线性增长，包括处理速度和效率、存储速度和容量、互连带宽和时延、I/O速度和容量、软件开销5.换代（时间）可扩展性对系统各部分更换成新技术后，性能随之易扩展，要求算法、S/W均能兼容运行。6.问题可扩展性问题规模扩大时，系统仍能很好的运行，或说问题规模扩展到很大时，系统能在给定粒度下高效运行。3.2.2可扩展性恒等效率函数1.恒等效率概念恒等效率定义为一个并行算法在并行计算机上实现时，为保持效率E固定所需的工作负载与机器规模n的相对关系。设:W=W（s）为工作负载，h=h（s，n）为通信开销，它随s、n增加而增大。其中，s为问题规模，n为机器规模。则效率可以表示为：E=W(s)h(s,n)W(s)​问题的关键在于W（s）与h（s，n）之间的相对增长速度。机器规模一定，开销h的增长比工作负载W要慢。因而，对一定规模的机器来说，效率会随问题规模增大而提高。所以，假若工作负载W随机器规模适当增加，那么就有希望保持效率不变。对于已知的算法来说，为了保持恒定的效率，工作负载W可能需要对n以多项式或指数规律增长。不同的算法可能需要不同的工作负载增长速率以便在n增加时保持效率不致下降。一般并行算法的恒定效率函数是n的多项式函数，即它们为O（nk），k1。n的幂越小，并行系统的可扩展性越大（系统包括算法和结构的组合）。2.恒等效率函数E=1h(s,n)/W(s)1​如前面所述，工作负载W与开销h均可以表示成n与s的函数，所以，效率也可以表示如下：W(s)=1−EE​×h(s,n)∵1−EE​为常数,用C表示,则恒等效率函数为：fE​(n)=C×h(s,n)为了使E保持不变，工作负载W（s）应该与开销h(s,n)成比例增长，由此可以得出以下条件：如果工作负载W(s)与fE(n)一样快的增长，那么已知算法机构组合就能使效率保持恒定。这个结论和前面的结论是一致的。此时，W(s)与fE(n)是相同的，只要求出了W(s)的数量级，就可知道fE(n)了。为了得到恒等效率，只要使W(s)与h(s,n)同一个数量级就可以了。例1 矩阵乘法的W(s)=O（s3）（其中s为维数），算法总开销：h（s，n）=O（nlogns2n0.5）。求fE(n)。W(s)=h(s)O(s3)=O(nlogns2n​)即O(s3)=O(nlogn)或者O(s3)=O(s2n​)⇒O(s)=O(n​)⇒O(s3)=O(n1.5)解：要满足W与h同数量级的条件，需要在两式中选出大的：∴O(s3)=O(n1.5)∴fE​(n)=O(n1.5)例2 W(s)=O（s3），算法总开销：h（s，n）=O（nlogns2n1/3logn）。求fE(n)。W(s)=h(s)O(s3)=O(nlogns2n1/3logn)即O(s3)=O(nlogn)或者O(s3)=O(s2n1/3logn)⇒O(s3)=O(n(logn)3)解：比较两个式子，选出较大的：∴O(s3)=O(n(logn)3)∴fE​(n)=O(n(logn)3)例3 W(s)=O（s3），h（s，n）=O（nlogns3）。求fE(n)。W(s)=h(s)O(s3)=O(nlogns3)即O(s3)=O(nlogn)或者O(s3)=O(s3)解：第二个式子显然成立，故∴O(s3)=O(nlogn)∴fE​(n)=O(nlogn)例4 在n台处理机网格和超立方体计算机上分别计算1维s点的FFT，其工作负载W(s)=O（slogs），已知：超立方体计算机上：h1（s，n）=O（nlognslogn），网格计算机上：h2（s，n）=O（nlognsn0.5），问哪一种扩展性好？解：对超立方体计算机，有O(slogs)=O(nlogn)⇒s=n或者O(slogs)=O(slogn)⇒s=n∴f1​=W(s)=O(nlogn)对网格计算机，有O(slogs)=O(nlogn)⇒s=n或者O(slogk​s)=O(sn​)⇒s=kn​∴f2​=W(s)=O(slogs)=O(kn​n​)为了得到恒等效率，对网格计算机，它的负载必须以指数增长，而超立方体的负载的增长不超过多项式增长速度，结论：超立方体具有更好的可扩展性。对于相同的效率E，设k=2，它们的机器规模-问题规模曲线可能如下图所示：问题规模s网格超立方体机器规模n