第一章 加速比.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,高等计算机系统结构,总学时：,32,理论学时：,28,讨论：,4,平时：课堂发言，讨论等等，,10%,作业：,5,次，占总分数,30%,期末考试：,60%,上课地点：工一,508,（,1-16,周，周二,1,2,节）,高等计算机系统结构课程介绍,教材,1,Kai Huang著，王鼎兴、郑纬民、沈美明译，,高等计算机系统结构并行性可扩展性可编程性,，清华大学出版社。,2,Patterson D.A.,，,Hennesy,J.L.,，,Computer Architecture,：,A Quantitative Approach,，,Morgan,Kanfmann,Publishers,，,1995,。,3,Patterson D.A.,，,Hennesy,J.L.,，,Computer Organization&Design,：,The Hardware,Software Interface,。,高等计算机系统结构,第一章 加速比性能模型与可扩展性分析,第二章 高等计算机的核心技术,并行处理,第三章 互连与通信,第四章 划分与调度,第五章 并行存储器系统,第六章,Cache Coherence,第七章,Memory Consistency,第八章 指令级并行处理,第九章 多处理机实例,第十章 高性能微处理器,第十一章 网格计算与云计算,课程概述,系统结构研究的范围：指令集设计、功能组织、逻辑设计与实现,HPC,的性能分析：评价方法、标准,并行处理：各个功能部件、各个级别,指令集、软件的作用：程序员眼中的结构,系统集成：部件之间的配合、平衡,发展趋势：制造技术进步、设计的创新；上个世纪,90,年代后，后者带来的性能提高几乎是前者的,5,倍。,高性能计算机简介（,TOP500,）,HTC,第一章 加速比性能模型与可扩展性分析,1.1,计算机的发展变化及影响体系结构的因素,1.1.1,计算机发展历程,1.1.2,影响体系结构的因素,1.1.3,计算机性能评价,1.2,加速比性能分析,1.2.1,一般概念,1.2.2,加速比,1.2.3,三种加速比性能模型,1.3,可扩展性分析,1.1,计算机的发展变化及影响体系结构的因素,1.1.1,计算机发展历程,1.,第一代：真空管（,1946-1957,）,2.,第二代：电子管（,1957-1964,）,3.,集成电路（,1965-1971,）,4.,以后几代：,LSI VLSI(1972-,至今）,1.1.1,计算机发展历程,1.,第一代：电子真空管,代表：,ENIAC,（,1946,年）,特点：体积庞大（占地,1500,平方英尺）；功率：,200KW,；必须手动编程；,性能：读卡速度,120,张,/,分钟，加法运算,5000/,秒，除法,150/,秒，不太可靠，机器的正确率仅为,20%,。,目标：机器有,18000,真空管。在炮弹到达目标之前，,ENIAC,能够计算出大口径海军炮弹轨道。,2.,晶体管,代表：,IBM 7094,特点：磁芯存储技术；容量,32K,；周期,2,微秒；十几万个晶体管,目标：科学计算、商业应用,3.,集成电路,代表：,/,特点：存储容量,512k,；处理器周期,0.2,微秒；第一次提出“兼容性”概念；模块化设计。,目标：科学计算；商业应用。,影响：奠定大型机体系结构。,4.LSI VLSI,代表：微处理器的变化从,4004,到,Pentium II,时钟：,108K300MHZ,晶体管数：,2300750,万,晶体管尺寸：,10,微米,0.3,微米,可寻址存储器：,640bit64GB,1.1.2,影响影响体系结构的因素,1.,硬件：技术进步，改变软硬件界面；,2.,软件：兼容性，高级语言，模拟与仿真；,3.,应用：应用的规模、精度等增长对计算机速度的要求提高；,4.,价格,:,性能与价格的平衡。,1.1.3,计评价算机性能,1.,执行时间是衡量计算机性能的标准；,2.,主要标准,(1)MIPS(million instructions per second),(2)MFLOPS(million floating point operations per second),(3),基准测试程序,a.,实际应用程序,b.,核心程序,c.,基准测试程序,d.,综合基准测试程序,3.,性能的比较和总结,评价一台计算机的性能既是简单又是复杂的,（,1,）不同程序对机器的性能的不确定性；,（,2,）不同输入的不确定性；,1.1,加速比性能模型,1.1.1,一般概念,1.,处理机,时间积,处理机数目与处理时间的乘积,用以度量这些处理机运行时的资源利用率。,若一程序在,P,台处理机上运行的时间为,Tp,，,则此,P,台处理机在,Tp,时间间隔内完成的,工作最大数量,为,Tp,*P,。,可将处理机实际工作曲线对时间的积分看成是这些处理机完成的,有效工作量,。,效率,为有效工作量与最大工作量之比。,2.,并行度（,D,egree,O,f,P,arallelism,DOP,）,并行度（,DOP,）,是在一定时间间隔内执行一个程序所用的处理机的数目。,3.,并行性分布图,执行一个给定的程序时,DOP,对时间的分布图。,DOP,与对应时间的间隔之积即为处理机要完成的,工作,或,工作负载,。,下图所示为一个,并行性分布图,。,DOP,t1,t,t2,并行性分布图,1.1.2,加速比,1.,绝对加速比,将最好的串行算法与并行算法相比较,.,定义一（与具体机器有关）,将最好的串行算法在一台上的运行时间与并行算法在,N,台运行的时间相比。,定义二（与具体机器无关）,将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。,2.,相对加速比,同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。,这种定义侧重于描述算法和并行计算机本身的,可扩展性,。,线性加速比：,中间开销小，通信少，弱耦合计算,超线性加速比：,当应用需要大内存时可能出现,病态加速比：,加速比递减，可能是计算量太小,1.1.3,三种加速比性能模型,1.,固定负载加速比性能模型,Amdahl,定律,在许多实时应用领域，计算负载的大小常固定。在并行机中，此负载可分布至多台并行执行，获得的加速比称为,fixed-load speedup,。,一个问题的负载可表示如下：,W=Ws+,Wp,其中，,Ws,代表问题中不可并行化的串行部分负载，,Wp,表示可并行化的部分负载。,则,n,个节点情况下，加速比可以表示如下：,设,串行因子,为串行部分所占的比例。即,代入即得,Amdahllaw,：,不管采用多少处理机，可望达到的,最好加速比,：,效率,En,可以表示为：,处理机数目,n,越大，效率,En,越低。,Amdahl,定律告诉我们：,系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。,加速比的两个决定因素：,1.,计算机执行某个任务的总时间中可被改进部分的时间所占的百分比，即,可被改进部分占用时间,/,改进前整个任务的执行时间,，,记为,Fe,，它总小于,1,。,2.,改进部分采用改进措施后比没有采用改进措施前性能提高的倍数，即,改进前改进部分执行时间,/,改进后改进部分执行时间,，,记为,Se,。,例,1,：,假设将某系统的某一部件的处理速度加快到,10,倍，但该部件的原处理时间仅为整个运行时间的,40%,，,则整个系统的性能提高了多少？,解：,Fe=,0.4,，,Se=,10,，,例,2,：,采用哪种实现技术来求浮点数平方根,FPSQR,的操作对系统的性能影响较大。假设,FPSQR,操作占整个测试程序执行时间的,20%,。,一种实现方法是采用,FPSQR,硬件，使,FPSQR,操作的速度加快到,10,倍。另一种方法是使所有浮点数据指令的速度加快，使,FP,指令的速度加快到,2,倍，还假设,FP,指令占整个执行时间的,50%,。,请比较这两种设计方案。,解：,Fe_FPSQR,=,0.2,，,Se_FPSQR,=,10,，,Fe_FP,=,0.5,，,Se_FP,=,2,，,Amdahllaw,又称为,固定规模加速比模型,，问题规模不随处理机变化而变化。固定问题规模，看用并行技术能达到的最短时间是多少。,在,固定规模加速比模型,下，负载和执行时间随系统中处理机数目,n,变化的情况如下图：,Ws,Wp,Ws,Wp,Ws,Wp,Ws,Wp,Workload,N,1,2,3,4,Execution Time,N,Ts,Tp,1,Ts,Tp,2,Ts,Tp,3,Ts,Tp,4,固定负载,执行时间随,N,增加而减少,固定负载加速比模型下的负载和执行时间情况,当处理器数目,n=1024,，加速比,Sn,随,变化的情况如下：,得出曲线如下图：,91,Sn,1024,48,31,24,10,可以比较不同的,对加速比带来的不同影响：,=0,Sn,n,=0.01,=0.1,=0.9,=0,时得到,理想加速比,，当,值增加时，加速比性能急剧下降。,结论：,加速比曲线随,的上升急剧下降，原因是存在顺序部分,Ws,，无法用增加系统的处理机数目来解决。这一性质在过去二十年间给人们造成了对并行处理非常悲观的印象。,影响：,两种意见：,1.,劝阻制造商生产大规模并行计算机。,2.,研究并行编译器，以降低,的值，从而提高系统的性能。,固定负载加速比模型的可能应用范围：,对时间要求严格的应用问题。,2.,固定时间加速比性能模型,Gustafsun,定律,有许多应用领域强调精度而不是运行时间。,1988,年，,Gustafsun,提出了,固定时间加速比模型,。当机器的规模扩大时，,解题的规模也随着扩大,，从而得到更加精确的解，而使,运行时间保持不变,。,比如：,有限元方法做结构分析，流体动力学做天气预报解,PDE,(,偏微分方程组）就需要提高精度。,粗格要求的计算量较少，而细格的计算量多，得到的精确度也较高。天气预报模拟求解四维,PDE,，如果使每个实际方向,（,X,，,Y,，,Z,）,的格点距离减少,10,倍,，并以同一幅度增加时间步，那么可以说格点增加了,10,4,倍，因而工作负载也至少增大了,10000,倍。,模型提出的背景：,固定负载模型,有,缺陷：因为,Amdahllaw,中，,取决于问题及并行编译器的效率，无法描述系统固有的特性。,加速比的公式：,其中，,Wp,=,nWp,和,Ws+Wp,=,Ws+Wp/n,作为固定时间的条件。,Ws+Wp/n,表示在扩大负载后在增加处理机台数的情况下的平均负载（执行时间），它应当和负载没有扩大情况下的平均负载（执行时间）,Ws+Wp,相等。即有,Ws+Wp,=,Ws+Wp/n,。,同时，负载的串行部分并没有改变，即有,Ws=,Ws,。,在,固定时间加速比模型,下，负载和执行时间随系统中处理机数目,n,变化的情况如下图：,Ws,Wp,Ws,Wp,Ws,Wp,Ws,Wp,Workload,N,1,2,3,4,Execution Time,N,Ts,Tp,1,Ts,Tp,2,Ts,Tp,3,Ts,Tp,4,并行负载不断增加,执行时间固定,固定时间加速比模型下的负载和执行时间情况,增大问题规模的办法使所有处理机保持忙碌状态，在问题扩大到与可用的计算能力匹配时，程序中的顺序部分就不再是瓶颈了。,当处理器数目,n=,1024,，加速比,Sn,随,变化的情况如下：,Sn,1024,1014,1004,993,983,3.,受限于存储器的加速比模型,1993,年，由,Sun,和,Ni,提出。,大型科学计算和工程设计需要较大的存储空间，许多应用问题是存储器受限，而不是,CPU,受限或者,I/O,受限。,比如,：在分布存储系统中常遇到，总存储容量随节点数线性增加，许多节点集合起来解一个大题。,基本思想,：要在存储空间有限条件下解尽可能大的问题，这同样需要扩展工作负载，才能提供较高的加速比、较高的精度和较好的资源利用率。,加速比可以表示如下：,其中：,在单个处理机上顺序执行的工作负载与问题的规模或系统的规模无关，即：,而,G(n,),反映的是存储容量增加,n,倍时并行工作负载增加的倍数。,讨论：,1.,G(n,)=,1,，即为固定负载的情况；,2.,G(n,)=n,，即存储器增加,n,倍，负载也增加,n,倍，为固定时间的情形；,3.,G(n,)n,，计算负载的增加情况比存储器增加快，会有较高的加速比。,比较三种加速比，对于相同的处理机数量，有：,在,受限于存储器的加速比模型,下，负载和执行时间随系统中处理机数目,n,变化的情况如下图：,Ws,Wp,Ws,Wp,Ws,Wp,Ws,Wp,Workload,N,1,2,3,4,Execution Time,N,Ts,Tp,1,Ts,Tp,2,Ts,Tp,3,Ts,Tp,4,规模扩展的工作负载,执行时间稍有增加,受限于存储器的加速比模型下的负载和执行时间情况,例：,n,维矩阵乘法：,A*B=C,，其中,A,、,B,、,C,都是,n*n,的方阵。为得到,C,的每一个元素需要进行,n,次乘法、,n,次加法，所以总的计算量为：,（,n+n,)*n,2,=2n,3,。需要的存储量为,3n,2,（两个源矩阵，一个结果矩阵）。如果,n,台计算机组成多计算机系统，则存储容量扩大,n,倍，那么矩阵的维数（原来为,n,),也可以增加了，设为,N,倍，那么加速比为多少？,解：,存储容量变为：,nM,=n*3n,2,=3n,3,，而,N,维需要的存储量为,3N,2,，计算量变为,2N,3,，则有：,4.,并行计算的应用模型,随机器规模的增大，工作负载增长的模式如下图：,工作负载,（问题规模）,n,（指数）,（线性）,（亚线性）,（常数）,上图中：,采用受限于存储器的加速比模型中给出的公式，,曲线对应的,G(n,)=n,1.5,曲线对应的,G(n,)=n,曲线对应的,G(n,)=0.5n,曲线对应的,G(n,)=1,则有加速比公式,:,给定一个程序，假设,Ws/,Wp,=0.4,，那么效率为：,并行计算机的应用模型,如下图：,通信界限,存储器界限,受限于存储器模型,工作负载,（问题规模）,机器规模,固定负载模型,固定时间模型,第一章 加速比性能模型与可扩展性分析,1.3,可扩展性分析,1.3.1,可扩展性,1.3.2,可扩展性分析,1.3,可扩展性分析,1.3.1,可扩展性,1.,可扩展性与可编程性,增加,可扩展性,增加可编程性,分布存储的消息,传递型多计算机,共享存储型,多处理机,理想并行计算机,2.,可扩展性指标,机器规模（,n,）,时钟频率（,f,）,问题规模（,s,）,CPU,时间（,T,）,I/O,需求（,d,）,存储容量（,m,）,通信开销（,h,）,计算机价格（,c,）,程序设计开销（,p,）,3.,可扩展性的直观定义,对任意数量（,n,）的处理机和任意规模（,s,）的问题，若所有算法的系统效率,E=1,，则系统是可扩展的。,4.,规模可扩展性,系统性能随处理机数量线性增长，包括：,处理速度和效率,存储速度和容量,互连带宽和时延,I/O,速度和容量,软件开销,规模可扩展性与空间局部性、时间局部性以及部件瓶颈都有关系。,例子：,Cray Y-MP,：,16,台处理机范围可伸缩,CM-2,：,8K-64K,台处理机范围可伸缩,CM-5,：,1024-16K,台处理机范围可伸缩,KSR-1,：,8-1088,台处理机范围可伸缩,5.,换代（时间）可扩展性,对系统各部分更换成新技术后，性能随之易扩展，要求算法、,S/W,均能兼容运行。,6.,问题可扩展性,问题规模扩大时，系统仍能很好的运行，或说问题规模扩展到很大时，系统能在给定粒度下高效运行。,1.3.2,可扩展性,1.,恒等效率概念（,Isoefficiency,）,恒等效率,定义为一个并行算法在并行计算机上实现时，为保持效率,E,固定所需的工作负载与机器规模,n,的相对关系。,设,:,W=W,（,s,）,为工作负载，,h =h,（,s,，,n,）,为通信开销，它随,s,、,n,增加而增大。,其中，,s,为问题规模，,n,为机器规模。,则效率可以表示为：,问题的关键在于,W,（,s,）,与,h,（,s,，,n,）,之间的相对增长速度。机器规模一定，开销,h,的增长比工作负载,W,要慢。因而，对一定规模的机器来说，效率会随问题规模增大而提高。所以，假若工作负载,W,随机器规模适当增加，那么就有希望保持效率不变。,对于已知的算法来说，为了保持恒定的效率，工作负载,W,可能需要对,n,以多项式或指数规律增长。不同的算法可能需要不同的工作负载增长速率以便在,n,增加时保持效率不致下降。,一般并行算法的恒定效率函数是,n,的多项式函数，即它们为,O,（,n,k,）,，,k,1,。,n,的幂越小，并行系统的可扩展性越大（系统包括算法和结构的组合）。,2.,恒等效率函数,并行程序执行时间,Tp,=(T1+T0)/p,，,其中，,T1,为总工作负载串行执行时间，,T0,为多节点总通信延时，,p,为节点数。,那么，加速比为：,而,T1=W,t,c,，,W,为以操作次数计算的总工作负载，,t,c,为每个操作的平均执行时间。,如前面所述，工作负载,W,与开销,h,均可以表示成,n,与,s,的函数，所以，效率也可以表示如下：,为了使,E,保持不变，工作负载,W,（,s,）,应该与开销,h(s,n,),成比例增长，由此可以得出以下条件：,如果工作负载,W(s,),与,h,(s,n,),一样快的增长，那么已知算法,结构,组合就能使效率保持恒定。,这个结论和前面的结论是一致的。,此时，,W(s,),与,h,(s,n,),是相同的，只要求出了,W(s,),的数量级，就可知道,h,(s,n,),了。为了得到恒等效率，只要使,W(s,),与,h(s,n,),同一个数量级就可以了。,例,1,：,矩阵乘法的,W(s,)=O,（,s,3,）,（其中,s,为维数），还设,h,（,s,，,n,）,=O,（,nlogn+s,2,n,0.5,）。,求,f,E,(n,),。,解：,要满足,W,与,h,同数量级的条件，需要在两式中选出大的：,例,2,：,W(s,)=O,（,s,3,），,h,（,s,，,n,）,=O,（,nlogn+s,2,n,1/3,logn,）。,求,f,E,(n,),。,解：,比较两个式子，选出较大的：,例,3,：,W(s,)=O,（,s,3,），,h,（,s,，,n,）,=O,（,nlogn+s,3,）。,求,f,E,(n,),。,解：,第二个式子显然成立，故,例,4,：,在,n,台处理机网格和超立方体计算机上分别计算,1,维,s,点的,FFT,，其工作负载,W(s,)=O,（,slogs,），,已知：,超立方体计算机上：,h,1,（,s,，,n,）,=O,（,nlogn+slogn,），,网格计算机上：,h,2,（,s,，,n,）,=O,（,nlogn+sn,0.5,），,问哪一种扩展性好？,解：,对超立方体计算机，,对网格计算机，,为了得到恒等效率，对网格计算机，它的负载必须以指数增长，而超立方体的负载的增长不超过多项式增长速度，,结论：,超立方体具有更好的可扩展性。,对于相同的效率,E,，设,k=2,，它们的,机器规模,-,问题规模曲线,可能如下图所示：,问题规模,s,机器规模,n,网格,超立方体,