《流水和现代处理器技术.ppt》由会员分享，可在线阅读，更多相关《流水和现代处理器技术.ppt（208页珍藏版）》请在三一办公上搜索。
1、第五章 重叠、流水和现代处理器技术,北京航空航天大学计算机学院2005 年 4 月,主要内容：基本问题流水线技术向量流水技术现代处理器技术,基本问题,如何提高CPU执行效率？TCPU=IN*CPI*TC IN：执行程序中的指令总数；CPI：执行每条指令所需的平均时钟周期数；TC：时钟周期的时间长度。,基本问题,其中：Ii 表示第i种指令在程序中执行次数,CPII表示执行一条第i类指令所需的平均时钟周期数,IN 为程序中所有的指令类数.,顺序执行方式 一条指令的执行过程：取指令-分析-执行执行n条指令所用的时间为：如每段时间都为t，则执行n条指令所用的时间为：T=3nt主要优点：控制简单，节省设
2、备。主要缺点：执行指令的速度慢，功能部件的利用率很低。,指令执行方式分析,此时，执行n条指令的时间为：T=(2+2n)t主要优点：指令的执行时间缩短功能部件的利用率明显提高主要缺点：需要增加一些硬件控制过程稍复杂,一次重叠执行方式(一种最简单的流水线方式),二次重叠执行方式,把取第k+1条指令提前到分析第k条指令同时执行如果三个过程的时间相等，执行n条指令的时间为：T=(2+n)t理想情况下同时有三条指令在执行处理机的结构要作比较大的改变（必须采用先行控制方式）,主要内容：基本问题流水线技术向量流水技术现代处理器技术,流水线技术,包含以下内容：流水线的分类流水线的表示方法流水线的特点流水线的性
3、能分析非线性流水线技术,流水线的分类,从流水线具有功能多少来看，可以分为单功能流水线和多功能流水线。单功能流水线只能实现一种功能的流水处理。,多功能流水线是指同一流水线的各段之间可以通过不同的连接方式实现多种不同的运算或功能。,流水线的分类,流水功能段,浮点加、减法运算,定点乘法运算,按多功能流水线的各段能否允许同时用多种不同功能连接流水，可把流水线分为静态流水线和动态流水线。静态流水线在某一时间内各段只能按一种功能连接流水。动态流水线的各段在同一时间内可按不同运算或功能连接。,流水线的分类,可同时进行浮点加、减运算和定点乘法运算的流水线,流水线的分类,从流水线中各功能段之间是否有反馈回路，可
4、以把流水线分为线性流水线和非线性流水线。,流水线的分类,流水线的表示方法,流水线的表示法有三种：连接图、时空图、预约表。主要考虑前二种。1、简单流水线的连接图表示流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。一个流水阶段与另一个流水阶段相连形成流水线。指令从流水线一端进入，经过流水线的处理，从另一端流出。有些复杂指令 在执行阶段也采用流水线方式工作，称为操作流水线。,2、一种指令流水线一般4至12个流水段，等于及大于8个流水段的称为超流水线处理机。,流水线的表示方法,3、流水线的时空图采用“时空图”表示流水线的工作过程。一条简单流水线的时空
5、图：,流水线的表示方法,一个浮点加法器流水线的时空图(由求阶差、对阶、尾数加和规格化4个流水段组成)：,流水线的表示方法,在流水线的每一个功能部件的后面都要有一个缓冲器，称为锁存器、闸门寄存器等，它的作用是保存本流水段的执行结果。各流水段的时间应尽量相等，否则回引起阻塞、断流等。只有连续提供同类任务才能充分发挥流水线的效率。在流水线的每一个流水线段中都要设置一个流水锁存器。流水线需要有“装入时间”和“排空时间”。只有流水线完全充满时，整个流水线的效率才能得到充分发挥。,流水线的主要特点,衡量流水线性能的主要指标有：吞吐率、加速比和效率1、吞吐率（Though Put）求流水线吞吐率的最基本公式
6、：TP=n/Tkn为任务数,Tk为完成n个任务所用时间各段执行时间相等，输入连续任务情况下完成n个连续任务需要的总时间为：Tk=(k+n-1)Dt k为流水线的段数，D t为时钟周期,线性流水线的性能分析,线性流水线的性能分析,吞吐率：最大吞吐率为：各段执行时间不相等、输入连续任务情况下：吞吐率为：最大吞吐率为：,线性流水线的性能分析,流水线各段执行时间不相等的解决办法,线性流水线的性能分析,一是将“瓶颈”流水段细分(如果可分的话)：二是将“瓶颈”流水段重复设置：,线性流水线的性能分析,流水段重复设置的流水线,线性流水线的性能分析,2、加速比（Speedup）计算流水线加速比的基本公式：S=顺
7、序执行时间T0/流水线执行时间Tk各段执行时间相等，输入连续任务情况下加速比为：最大加速比为：各段执行时间不等，输入连续任务情况下实际加速比为：,线性流水线的性能分析,线性流水线的性能分析,3、效率（Efficiency）计算流水线效率的一般公式：各流水段执行时间相等，输入n个连续任务流水线的效率为：流水线的最高效率为：,线性流水线的性能分析,线性流水线的性能分析,各流水段执行时间不等，输入n个连续任务流水线的效率为：,线性流水线的性能分析,线性流水线的性能分析,流水线的吞吐率、加速比与效率的关系：因为因此：E=TP Dt，S=kE,线性流水线的性能分析,4、流水线性能分析举例 对于单功能线性
8、流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。例5.2：用一条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGH,线性流水线的性能分析,解：Z=(A+B)+(C+D)+(E+F)+(G+H),1,时间,空间,2,3,求阶差,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,对阶,尾数加,规格化,加数,A,C,E,G,A+B,E+F,B,D,F,H,C+D,G+H,A+B+C+D,E+F+G+H,结果,A+B,C+D,E+F,G+H,A+B+C+D,E+F+G+H,Z,线性流水线的性能分析,7个浮点
9、加法共用了15个时钟周期。流水线的吞吐率为：流水线的加速比为：流水线的效率为：,线性流水线的性能分析,什么是非线性流水线？如果存在反馈回路，当一个任务在流水线中流过时，在同一个流水段中可能要经过多次。不能每一个时钟周期向流水线输入一个新任务。这样的流水线就是非线性流水线。非线性流水线的调度问题就是要解决要隔多少个时钟周期向流水线输入一个新任务才能使流水线 的各个流水段都不发生冲突。表示一个非线性流水线需要用到连接图和预约表。,非线性流水线技术,S1,S2,S3,S4,输出,输入,反馈线,非线性流水线1的连接图,非线性流水线的预约表,S1,S2,S3,S4,输出,输入,反馈线,非线性流水线2的连
10、接图,非线性流水线的预约表,预约表横坐标表示流水线的时钟周期，纵坐标表示流水线的各个流水段，中间有“X”表示该流水段在这一个时钟周期处于工作状态，空白表示该流水段在这一个时钟周期不工作。一行中可以有多个“X”，表示一个任务在不同时钟周期重复使用了同一流水段；一列中有多个“X”表示在同一个时钟周期同时占用了多个流水段。预约表的行数是流水线的段数，预约表的列数是一个任务从进入流水线到流水线中输出所经过的时钟周期数。向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离，以时钟周期数表示。,非线性流水线技术,当使用某些启动距离时，将在某些流水段发生冲突，即两个或两个以上任
11、务同时争用一个流水段。引起非线性流水线流水段冲突的启动距离称为禁启动止距离。不发生冲突的启动距离是一个循环数列。使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。,非线性流水线技术,启动距离为5的流水线预约表,（5）是一个循环，称为恒定循环。,非线性流水线技术,启动距离为（1，7）循环时的流水线预约表,要正确地调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。所有禁止启动启动距离组合在一起成为一个数列，称为禁止向量。,非线性流水线技术,由预约表得到禁止向量的方法：将预约表的每一行中任意两个“X”之间的距离都计算出来，去掉重复的，这种数组成
12、的一个数列就是这条非线性流水线的禁止向量。例如：前述的非线性流水线，其禁止向量为（3，4，6）。把一个启动循环内的所有启动距离相加，然后再除以这个循环内的启动距离个数，就得到这个启动循环的平均启动距离。非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有流水段在任何时间都没有冲突。,非线性流水线技术,例子：一条有4个流水段的非线性流水线，每个流水段的延迟时间都相等，它的预约表如下图：,非线性流水线技术,（1）写出流水线的禁止向量和初始冲突向量（2）画出调度流水线的状态图（3）求流水线的最小启动循
13、环和最小启动距离（4）求平均启动距离最小的恒定循环。,解：（1）禁止向量为（2，4，6）冲突向量：用二进制表示，长度是禁止向量的最大距离。冲突向量C=（C6C5C4C3C2C1），由禁止向量，C2=C4=C6=1，其余位为0，冲突向量为 C=（101010）。,非线性流水线技术,（2）由冲突向量构造一张图：将C放到一个6位逻辑右移移位器，当从移位器右移出0，用移位器中的值与初始冲突向量做“按位或”，得到一个新的冲突向量。当移位器移出1，不做任何处理。重复这个步骤。对产生的每一个新的冲突向量做同样处理。在初始冲突向量和所有形成的冲突向量之间，箭头连接。,非线性流水线技术,（3）从状态图中可以找到
14、许多不发生流水段冲突的启动循环。，只要找到简单循环，进而确定平均启动距离最小的启动循环。它们是：（1，7）、（3，5，7）、（5，7）等,最小启动循环是具有最小平均最小启动距离的启动循环。,非线性流水线技术,最小循环为（1，7）、（3，5）最小恒定循环为（5）,最小启动循环为（3，5）的流水线工作状态,非线性流水线技术,最小启动循环为（1，7）的流水线工作状态,非线性流水线技术,恒定启动循环（5）的流水线工作状态,启动周期,重复启动周期,非线性流水线技术,主要内容：基本问题流水线技术向量流水技术现代处理器技术,向量流水技术,向量处理的特点向量处理机的基本结构向量处理的方法向量处理的关键技术,向
15、量流水处理的主要特点,1、向量流水处理的主要特点(1)各个元素的操作一般相同且数据相互独立，不存在相关。非常适合于流水处理；(2)一条向量指令相当于一个标量循环,可降低对指令访问带宽的要求；(3)一般采用多体交叉存储，支持跨步长度访问,向量处理机的基本概念,具有向量数据表示和向量指令系统的处理机称为向量处理机。向量处理机是解决数值计算问题的一种高性能计算机结构。向量处理机一般都采用流水线结构，往往有多条流水线并行 工作。向量处理机通常属大型或巨型机，也可以用微机加一台向量 协处理器组成。一般向量计算机中包括有一台高性能标量处理机。必须把要解决的问题转化为向量运算，向量处理机才能充分 发挥作用。
16、,一个典型向量求解问题:Y=a*X+Y 其中X和Y为向量,初始值存放在存储器中,a为标量。通常,根据这一求解表达式是单精度还是双精度操作,分别称为SAXPY(Single-precision AX plus Y)或DAXPY循环,表示是单精度或双精度的A乘X后再加Y。,若用向量机来完成同样操作,则有:LD F0,a;标量a装入F0 LV V1,Rx;装入向量X,LV为向量取指令 MULTV V2,F0,V1;向量X与标量a相乘 LV V3,Ry;装入向量Y ADDV V4,V2,V3;向量加aX+Y SV Ry,V4;存结果向量,SV为向量存指令 向量机只需执行6条指令,从而可大大降低对指令带
17、宽要求,向量处理机的基本结构,向量处理机的基本结构形式 按向量操作对象及结果主要存放方式分类：1）存储器存储器工作方式向量机 利用多个独立的存储器模块并行工作。2）寄存器寄存器工作方式向量机 主要利用向量寄存器。,存储器存储器结构,采用多个存储体交叉和并行访问来提高存储器速度；操作数缓冲栈和写结果缓冲栈主要用于解决访问存储器冲突；主要优缺点：硬件结构简单，造价低。速度相对比较低。早期的向量处理多采用这种存储器-存储器结构。,寄存器寄存器结构（Cray1）,寄存器寄存器结构,把存储器-存储器结构中的缓冲栈改为向量寄存器，运算部件需要的操作数从向量寄存器中读取，运算的中间结果也写到向量寄存器中。向
18、量寄存器与标量寄存器的主要差别是：一个向量寄存器能够保存一个向量，例如：64个64位寄存器。采用寄存器-寄存器结构的主要优点：降低主存储器的流量。例如：寄存器-寄存器结构的CRAY-1与存储器-存储器结构的STAR-100比较，运算速度高3倍多（时钟周期为40：12.5），主存储器流量低2.5倍。,1976年，CRAY公司推出CRAY-1向量机，开始了向量机的蓬勃发展，其峰值速度为0.1 Gflops。,Cray 1,1985年，CRAY-2，1G flops1990年,SX-3,22G flops1991年，Cray-YMP-C90,16Gflops,Cray 2,Cray XMP/4,CR
19、AY Y-MP816系统结构,1991年多向量处理器时间并行+空间并行256交叉存储16MB1GB大量使用寄存器64位浮点/定点,1983年12月,银河-I巨型计算机由国防科技大学计算机研究所研制成功。银河-II并行巨型计算机由国防科技大学计算机研究所于1992年11月研制成功。,银河1,银河2,向量处理方法,向量处理方式有三种类型：1横向处理方式：向量计算是按行的方式从左至右横向地进行。也称水平处理方式，横向加工方式等。2纵向处理方式：向量计算是按列的方式自上而下纵向地进行。也称垂直处理方式，纵向加工方式等。3纵横处理方式：横向处理和纵向处理相结合的方式。也称分组处理方式，纵横向加工方式等。
20、以一个简单的C语言编写的程序为例，说明向量的三种处理方式的工作原理。for(i=1；i=N；i+)yi=ai(bi+ci);,逐个分量进行处理：假设中间结果为T(I)。计算第1个分量：T(1)=B(1)+C(1)Y(1)=A(1)T(1)计算第2个分量：T(2)=B(2)+C(2)Y(2)=A(2)T(2)计算最后一个分量：T(N)=B(N)+C(N)Y(N)=A(N)T(N)即逐个求Y中的N个分量,先进行相加t1b1+c1,其中t1为暂存单元,然后相乘y1t1a1。,横向处理方式,横向处理方式,存在两个问题：在计算向量的每个分量时，都发生写读数据相关。流水线效率低。如果采用多功能流水线，必须
21、频繁进行流水线切换。结论：这种加工方式不适合于向量流水处理。,纵向处理方式,先纵向加工所有B和C向量中元素对的相加操作,中间结果暂存到t1tN中,然后再纵向加工所有对应元素的乘法操作。T(1)=B(1)+C(1)T(2)=B(2)+C(2)T(n)=B(n)+C(n)Y(1)=A(1)T(1)Y(2)=A(2)T(2)Y(n)=A(n)T(n)用向量指令形式表示时,变成:T=B+C Y=TA,纵向处理方式,特点：流水线功能的切换只需一次。可获得较高的吞吐率。数据相关不影响流水线连续工作，可采用向量链接技术。结论：这种处理方式适用于向量处理机。,纵横处理方式,纵横向加工(或称为分组加工)以寄存器
22、寄存器方式工作的向量机都采用这种加工方式。因为向量寄存器的长度有限(如CRAY-1的长度为64)。当向量长度超过向量寄存器可表示的最大限度n时,就不得不分组加以处理。假设向量长度为N,则有N=kn+r,其中nN,rn,n、k、r均为正整数,k为组数,r为余数(余下的部分也作为一组处理)。它的加工方式是:组内纵向加工,组间为横向加工。第一组计算:t1n=b1n+c1n y1n=a1n+t1n再算第二组:tn+12n=bn+12n+cn+12n yn+12n=an+12n+tn+12n,向量处理的关键技术,向量与标量性能的平衡向量链接技术向量循环开采技术,向量与标量性能的平衡,实际的应用问题中通常
23、既有向量计算又有标量计算，而且两类计算有一定的比例。向量平衡点(vector balance point)：为了使向量硬件设备和标量硬件设备的利用率相等，一个程序中向量代码所占的百分比。关键问题是：向量硬件和标量硬件都能充分利用，都不空闲。向量处理机的向量平衡点必须与用户程序的向量化程度相匹配。,向量与标量性能的平衡,几种超级计算机向量和标量的性能,向量链接技术,向量运算中的相关和冲突 向量运算中的数据相关和功能部件冲突主要有：写读数据相关；读读数据相关，或向量寄存器冲突；运算部件冲突。V0V1V2 V0V1V2V3V4 V5 V3V0 V4(a)不相关的指令(b)写读数据相关V0V1V2 V
24、0V1V2V3V4V5 V3V1 V4(c)功能部件冲突(d)读读数据相关,向量链接技术,利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术。具体的说，结果寄存器可能成为后继指令的操作数寄存器，两条有数据相关的向量指令并行执行。例如：ADDV V1,V2,V3;V1V2+V3 MULTV V4,V1,V5;V4V1V5 分析：这两条指令间对V1向量寄存器存在先写后读相关,通常必须等加法指令做完后才可开始乘法指令,但如果使向量寄存器(例中的V1)在同一时钟周期内,既接收一个功能部件送来的运算结果,又可把这一结果作为下一个向量指令运算所需的源操作数送给另一个功能部
25、件,那就可使这两个部件链接起来进行操作。当链接进入充分流水操作状态后,在一个时钟周期内就可同时获取两个操作结果。,向量链接技术,以CRAY-1为例,设有如下向量运算:D=A(B+C)假设向量长度64,且B和C已由存储器取至V0和V1,则下面3条向量指令就可完成上述运算:LD V3,A;V3a ADDV V2,V0,V1;V2V0+V1 MULTV V4,V2,V3;V4V2V3,向量链接技术,LD V3,A;V3a ADDV V2,V0,V1;V2V0+V1 MULTV V4,V2,V3;V4V2xV3,情况一：若这三条指令全部用串行方法则所需时间为:(1+6+1)+N-1+(1+6+1)+N
26、-1+(1+7+1)+N-1=3N+22,情况二：若前两条指令并行执行,第三条指令串行执行,则所需时间为:(1+6+1)+N-1+(1+7+1)+N-1=2N+15拍,情况三：采用并行和链接加速技术后,执行所需时间为:(1+6+1)+(1+7+1)+(N-1)=17+N-1=N+16拍,设被加工向量长度为N,向量链接技术,链接的条件：链接两条或多条指令存在先写后读相关只有当前一指令的第一个结果分量送入结果向量寄存器的那一个时钟周期方可链接当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时,要求先行的两条指令产生运算结果的时间必须相等,即要求有关功能部件的延迟时间相等链接的两条向量指令
27、的向量长度必须相等针对不同的向量机,可能对链接还有其他特殊限制。如CRAY-1中,允许自存储器取数操作参与链接,但不允许向存储器写数操作实现链接,因为CRAY-1并不提供这种链接功能。,向量循环开采技术,当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，采用循环结构处理这个长向量，这种技术称为向量循环开采技术，也称为向量分段开采技术。例如：A和B为长度N的向量。for(i=1;i=N;i+)ai=5*b(i)+c;,向量循环开采技术,当N为64或更小时，产生A数组的7条指令序列是：1：S15.0在标量寄存器内设置常数2：S2C 将常数C装入标量寄存器3：VLN 在VL寄存器内设
28、置向量长度4：V0B 将B向量读入向量寄存器5：V1S1 V0 B数组的每个分量和常数相乘6：V2S2V1 C和5B(i)相加7：AV2将结果向量存入A数组 第4、5、6、7条指令可以采用向量链接执行。当N超过64时，就需要采用向量循环。,向量循环开采技术,向量的分段开采：low=1 VL=(N mod MVL)*找出零头长度值 do 20 j=0,(N/MVL)*外循环 do 10 i=low,low+VL-1*以长度VL操作 4：V0B 5：V1S1 V0 6：V2S2V1 主要操作 7：AV2 10 continue low=low+VL*下一向量的开始 VL=MVL*将长度值恢复成MV
29、L 20 contine 经分段处理后,第一段长度为n mod MVL,而以后各段的长度均为MVL（向量寄存器的长度）。,主要内容：基本问题流水线技术向量流水技术现代处理器技术,不能回避的问题,So Easy?No!进一步的思考：采用流水线技术所带来的问题。,研究相关性，不但可作为是否可指令调度的依据，而且可了解程序固有的并行性以及可以获得的并行性。相关 意味指令的运行、结果产生的顺序有要求，意味指令的并行运行和改变顺序可能会产生问题，是否意味指令的流水线运行一定会产生停顿。,流水线的主要障碍:相关(Hazard),流水线3类相关结构相关:硬件不能支持两条指令同时访问同一个资源 two dog
30、s fighting for the same bone数据相关:指令依赖于前面尚在流水线中的指令的执行结果控制相关:在判断转移条件之前，就试图决策转移方向(分支指令、跳转指令)解决相关性问题，提高处理器执行效率，是推动处理器新技术产生的动力源泉。,流水线的主要障碍:相关(Hazard),结构相关单口存储器,指令和数据共用同一个存储器存储器为单口存储器冲突发生条件Instr 1存储器访问指令读写存储器Instr 2取指令,结构相关单口存储器,结构相关解决方案之一：气泡,消除结构相关,原因：资源争用方法1:等待第一步：检测第二步：插入等待(空操作/气泡)方法2:投入更多的硬件资源双存储器(“Ha
31、rvard Architecture”)多端口存储器（寄存器堆）,三类数据相关,Read After Write(RAW)先写后读(写未完成，读即发出)InstrJ在InstrI完成写之前读起因：基于变量的通讯RAW相关是程序相关性中最本质的相关性之一。,Write After Read(WAR)先读后写InstrJ在InstrI完成读之前进行写操作反相关起因：r1的重用,三类数据相关,Write After Write(WAW)写后写InstrJ在InstrI完成写之前进行写操作输出相关起因是r1的重用,三类数据相关,无妨假设处理器执行如下形式的操作：rk(ri)op(rj)则：rk(ri)
32、op(rj)rm(rk)op(rn)称为RAW（Read After Write）相关；ri(rk)op(rj)rk(rm)op(rn)称为WAR（Write After Read）相关；rk(ri)op(rj)rk(rm)op(rn)称为WAW（Write After Write）相关。,三类数据相关（一般性定义）,指令的范围（Range)和域(Domain)：R(i):指令i所修改的寄存器（或存储器单元）的集合。D(i):指令i所读取的寄存器（或存储器单元）的集合。假设指令j在程序的执行顺序中是指令i的后续指令。若指令j提前于指令i执行，则可能引起：RAW相关冲突，如果 R(i)D(j);
33、WAR相关冲突，如果 D(i)R(j);WAW相关冲突，如果 R(i)R(j);,三类数据相关（判别）,RAW相关的解决策略流水线旁路,时间(时钟周期),RAW相关的解决策略流水线旁路,时间(时钟周期),RAW相关仍然存在Load指令,旁路未能解决所有问题,流水线互锁解决Load引发的RAW相关,时间(时钟周期),or r8,r1,r9,指令执行次序,ld r1,4(r2),sub r4,r1,r6,and r6,r1,r7,ALU,DMem,Bubble,WAR和WAW相关,WAR：WAW：这两类相关由寄存器重用引起；指令顺序不能改变；在单功能流水线中不可能发生。,多功能流水线,I:Fdiv
34、 r4,r1,r3 J:add r1,r2,r3K:mul r6,r1,r7,I:Fmul r1,r4,r3 J:add r1,r2,r3K:mul r6,r1,r7,定点指令：1 clock浮点指令：3 clocks,对于多功能流水线：由每个功能单元的执行时间不同（如定点和浮点运算）WAR和WAW相关可能引起执行错误。解决WAR和WAW相关的最简单的方法：停顿（暂停）。指令的可以按程序顺序发射（In-order-Issue），但完成顺序则可能与程序顺序不同，即乱序完成（Out-of-order Complete）。,多功能流水线,数据相关的解决策略指令调度,指令调度：通过改变指令在程序中的位
35、置，将相关指令之间的距离加大到不小于指令执行延迟的时钟数，使相关指令成为实际上的无关指令。指令调度（静态）通常由编译完成。指令调度（动态）通常采用硬件实现。,动机编译时某些情况无法判断，可以利用那些只有运行时才能看到的信息；简化编译器设计；代码的可移植性好。核心思路允许暂停后的指令执行；寄存器重命名。,硬件动态调度算法,硬件动态调度算法,记分板(Scoreboard)命名起源于CDC 6600，其基本结构：,硬件动态调度算法,其基本控制阶段：发射(Issue)指令译码检测结构相关、写写相关当前指令被阻塞后续指令被阻塞读操作数(Read operands)在没有数据相关的前提下读取操作数执行(E
36、xecution)功能部件执行完后通知记分板控制系统写回结果(Write Result)记分板检测功能部件的写回，若发现有相关冲突则暂停,记分板主要部件：指令状态表指令处于哪个阶段功能部件状态表功能部件当前状态，9个域Busy是否正在使用Op运算类型(/)Fi目标寄存器Fj,Fk源寄存器Qj,Qk产生Fj，Fk的功能部件Rj,RkFj,Fk就绪标志寄存器结果状态表指示哪个功能部件将写入该寄存器。如果没有指令写该寄存器，则为空。,硬件动态调度算法,记分板算法对CDC6600的加速比：对FORTRAN语言，性能提高1.7倍；对手写汇编程序，性能提高2.5倍。6600记分板局限性：指令窗口小指令调度
37、有限；功能部件少结构冒险(整数load/store部件)；结构冒险暂停发射。,硬件动态调度算法,硬件动态调度算法,Tomasulo算法1.采用于IBM 360/91浮点部件(1967年)；2.将记分牌技术和寄存器重命名技术结合起来，更有效地解决写后写、读后写相关；1967年，IBM公司的Robert Tomasulo 开创性的提出了解决上述问题的方法-寄存器重命名（Rrgister Renaming)。寄存器重命名技术使得在不改变指令系统前提下实际寄存器数量得到增加。换句话说，可以使用比ISA（Industry Standard Architecture)更多的寄存器而依然保持与ISA的兼容性
38、。,硬件动态调度算法,硬件动态调度算法,保留站的组成：Op:功能单元运算类型(+或)Vj,Vk:源操作数值Qj,Qk:产生源操作数的保留站Qj,Qk=0 数据就绪Busy:保留站或相关FU忙寄存器结果状态表指示哪个FU要写哪个寄存器如果没有将写入寄存器的未决指令，则该域为空,硬件动态调度算法,发射丛FP操作队列中取指令如果保留站空闲(没有结构冒险)，则控制单元发射指令&发送操作数(对寄存器进行换名)执行对操作数进行操作(EX)如果两个操作数都就绪执行如果未就绪监控CDB写回完成执行(WB)通过CDB将结构写入所有等待的功能单元中标记保留站可用公共数据总线:数据+源(“来源”总线)64位数据+4
39、位功能单元源地址如果与期望的功能单元匹配则写入(产生结果)广播模式,Tomsulo算法的基本思想：只要操作数一有效就取至保留栈；要执行的指令将从保留栈中取得操作数；一条指令发射时，取操作数的寄存器被重新命名为该寄存器保留站的名称。通过指令发射逻辑和保留站的结合实现寄存器重命名。,硬件动态调度算法,例：执行时间I1 LD f2,34(r2)1I2 LD f4,45(r3)很长I3 MULTD f6,f4,f2 3I4 SUBD f8,f5,f2 1I5 DIVD f4,f2,f8 4I6 ADDD f10,f6,f4 1,顺序发射：1(2,1).2 3 4 4 3 5.5 6 6,调度算法如何提
40、高执行效率？,分析,指令4与指令3无关，是否可以在指令3等待指令2完成之前，先执行指令4？进一步思考，指令是否可以通过乱序发射（Out-of-order Issue）或乱序执行（Out-of-order Execution）提高执行效率？实现方法？对一组指令的数据相关情况进行分析，找出无RAW,WAR,WAW相关冲突指令，送入空闲执行单元（即无结构相关）执行。,例：执行时间I1 LD f2,34(r2)1I2 LD f4,45(r3)很长I3 MULTD f6,f4,f2 3I4 SUBD f8,f5,f2 1I5 DIVD f4,f2,f8 4I6 ADDD f10,f6,f4 1,乱序发射
41、（执行）并未提高流水线的效率！,顺序发射：1(2,1).2 3 4 4 3 5.5 6 6,乱序发射（执行）：1(2,1)4 4.2 3.3 5.5 6 6,乱序发射（乱序执行）,问题：什么因素限制了流水线中指令执行的条数？程序中的那些特征限制了流水线中的可执行指令的数目？结论：寄存器的数目是限制流水线中可执行指令条数的关键因素。仅使用少量寄存器通常不能使流水线工作在满负荷状态。如何解决？,原因分析,例：执行时间I1 LD f2,34(r2)1I2 LD f4,45(r3)很长I3 MULTD f6,f4,f2 3I4 SUBD f8,f5,f2 1I5 DIVD f4,f2,f8 4I6 A
42、DDD f10,f6,f4 1,顺序发射：1(2,1).2 3 4 4 3 5.5 6 6,乱序发射：1(2,1)4 4 5.2 3 5.3 6 6,流水线的效率提高了！,寄存器重命名,硬件动态调度算法,控制相关,控制相关：在判断转移条件之前，就试图决策转移方向(分支指令、跳转指令)为解决控制相关问题，必须能够进行转移预测。如果预测在编译时进行（或固定）-控制相关的静态解决技术执行时进行动态进行-控制相关的动态解决技术,动机：由于转移引起的流水线效率降低极大的影响了处理器的性能。现代处理器中的转移预测机制可以很大程度上（95%）消除转移引起的性能下降。需要硬件的支持：指令预测单元的基本构件：B
43、HT（Branch History Table)，BTB(Branch Target Buffer),转移预测,向后转移90%,向前转移50%,统计表明，转移指令中转移发生的概率为6070%。,静态转移预测,动态转移预测,动态转移预测就是通过对程序中分支指令过去的行为考察，预测当前转移指令的行为。时间相关性 一条分支指令的历史行为很可能决定着该指令当前的行为。空间相关性 一些分支指令的行为可能是相互关联的。考虑空间相关性问题，例：if(xi 7)y+=1;if(xi 5)c-=4;如果第一个语句的条件不成立，则第二条语句的条件亦不成立。,转移预测方法,基本思想：基于该分支指令的历史记录-根据该
44、分支指令在最近一次或几次的运行情况(转移成功或失败)，来预测该分支指令的本次运行情况(转移成功或失败)。实现方法：建立一片缓冲区，记录各运行过的分支指令的运行情况(转移成功或失败)。缓冲区如何寻址-根据分支指令地址的低位，究竟多少位取决于缓冲区大小。缓冲区的内容-预测位，其长度(多少位)决定能记录该指令前多少次运行情况。,转移预测方法,转移指令的执行过程：(1)现场保留。(2)按预测方向取后继指令。(3)得到分支结果后如果预测成功，继续运行；如果预测失败，恢复保留的现场，从分支处重新执行；(4)修改预测位。,转移预测方法,(1)预测位长度为1预测位内容：记录该指令最近一次分支是否成功,如“1”
45、表示分支成功，“0”表示分 支失败。预测方法：如果该指令最近一次分支成功则预测分支成功，反之则预测分支失败。预测位修改：如果实际运行该指令发现分支成功，则置预测位为“1”，反之为“0”。,转移预测方法,(2)预测位长度为n预测位内容：为 0 到 2n-1 计数器，每次分支结果出来后，如分支成功则加 1，分支失则减 1，计数器值增加到 2n-1 后不再增加，减小到 0 后不再减小。预测方法：如果计数器值大于或等于最大值的一半 2n-1，预测分支成功，反之预测分支失败。,转移预测方法,N 为 2 时的预测位：,转移预测方法,转移预测方法,实际试验：(1)预测位为 2 和预测位为 n 的预测性能差别
46、不大。(2)预测缓冲区大小增加到 4096 个记录项后预测性 能不再明显增加(只用取指令地址的低 12 位)(3)在预测位为 2，预测缓冲区为 4096 个记录项情 况下，预测准确率为8299，即预测失败率为 118。起作用的前提：目标地址的计算要快于分支结果计算。,进一步减少分支延迟：分支目标缓冲分支指令无延迟的前提：分支预测成功分支预测和目标地址计算都在 IF 阶段就能完成。基本思想：设立一个缓冲区(称为分支目标缓冲区，或BTB)，其中存放最近一次运行时分支成功的分支指令的信息(指令地址、分支目标 PC)，如果当前指令属于分支目标缓冲(与其中某一条指令的地址相同)，则确定该指令是分支指令，
47、并预测分支成功，从分支目标缓冲直接获得目标 PC；反之，则顺序取指令(普通指令或预测分支失败的分支指令)。,转移预测方法,转移预测方法,转移预测方法,转移预测方法,现代处理器,超标量处理器超流水线处理器超标量超流水线处理器三种处理器的比较VLIW处理器,超标量处理机：一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机，它必须有两条或两条以上能够同时工作的指令流水线。超标量处理机典型结构：多条指令流水线、多个功能部件。先进的超标量处理机有：定点处理部件CPU，浮点处理部件FPU，图形加速部件GPU，大量的通用寄存器，两个一级高速Cache，标量处理机的指令级并行度大于1。,超标量处理器定
48、义和典型结构,Motorola公司的MC88110：10个操作部件：整数（2）、位操作、浮点加、浮点乘、浮点除、图形（2）、Load/Store和指令分配转移部件。两个寄存器堆：整数部件通用寄存器堆，32个32位寄存器；浮点部件扩展寄存器堆，32个80位寄存器。每个寄存器堆有8个端口，分别与8条内部总线相连接，有一个缓冲深度为4的先行读数栈和一个缓冲深度为3的后行写数栈。,超标量处理器,两个独立的高速Cache：一个数据Cache和一个指令Cache，容量各为8KB，采用两路组相联方式。一个转移目标指令Cache：在有两路分支时，存放其中一路分支上的指令。,超标量处理器,超标量处理器MC881
49、10的结构,超标量处理器单发射和多发射,单发射处理器：每个周期只取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果；取指部件和译码部件各设置一套；可以只设置一个多功能操作部件，也可以设置多个独立的操作部件；操作部件中可以采用流水线结构，也可以不采用流水线结构；设计目标是每个时钟周期平均执行一条指令，ILP的期望值1。,单发射处理器的指令流水线时空图,IF：取指令 ID：指令译码 EX：执行指令 WR：写回结果,超标量处理器,超标量处理器,由4个操作部件组成的单发射处理器,多发射处理器：每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果；需要多个取指令部
50、件，多个指令译码部件和多个写结果部件设置多个指令执行部件，复杂的指令执行部件一般采用流水线结构设计目标是每个时钟周期平均执行多条指令，ILP的期望值大于1,超标量处理器,多发射处理器的指令流水线时空图,超标量处理器,超标量处理器,先行指令窗口：能够从指令Cache中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突的检测。窗口的大小：一般为2至8条指令，采用目前的指令调度技术，每个周期发射2至4条指令比较合理。例如：Intel公司的i860、i960、Pentium处理机，Motolora公司的MC88110处理机，IBM公司的Power 6000处理机等每个周期都发射两条指令；
