第5章计算机流水线技术.ppt

1、第五章 流水线处理技术,5.1 流水处理概述,5.2 流水线工作方式,5.3 流水线性能分析,5.4 超标量超流水计算机,5.5 向量处理机器,5.1 流水线处理概述,一、CPU主要工作方式: 顺序 重叠 流水 和铺地板的原理相似,5.1 流水线处理概述,。,每阶段时间为t，共n条指令,顺序串行（sequence）：,设指令工作方式分成取指令、分析、执行指令,若各阶段执行时间相等，则共需3 n t,优点：控制简单； 缺点：速度慢，机器各部件的利用率很低。,重叠（Overlap）：在两条相近指令的解释过程中，某些不同解释阶段在时间上存在重叠部分。 包括一次重叠、先行控制技术和多操作部件并行。,将

2、相邻两条指令的重叠时间再往前提前一个阶段；T=3t+（n-1）t=（n+2）t 一次重叠：把取指令操作隐含在分析、执行指令过程中，则在任何时候只允许上条指令“执行”与下条指令“分析”相重叠。 T=（n+1）t,实际执行时间：,若各段时间不等时，有,先行控制：分析部件和执行部件能分别连续不断地分析和执行指令，预取和缓冲相结合的技术 ，通过对指令流和数据流的先行控制，使指令分析器和执行部件能尽量连续并行工作。 执行时间：,多操作部件并行：采用有多个功能部件的处理机，把ALU的多种功能分散到几个具有专门功能的部件中，这些功能部件可以并行工作，使指令流出速度大大提高。,先行控制： 现代计算机指令系统是

3、复杂的，“分析”和“执行”所需要的时间往往相差很大，从而造成功能部件的浪费，因此，需要采用先行控制技术。,分析k 执行k,分析k+1,执行k+1,分析k+2,执行k+2,分析k 分析k+1,执行k,执行k+1,分析k +2 分析k+3,执行k +2,执行k+3,分析指令和执行指令时间不等时的一次重叠方式,采用先行缓冲栈时指令执行过程的一种表示方法,功能部件浪费,先行控制： 一般采用先行缓冲栈的方式实现： 一般设置四种缓冲栈： 先行指令缓冲栈当主存比较忙时，指令分析器能够从先行指令缓冲栈中得到所需指令。 先行操作栈对于条件转移等使用。 先行读书栈主存储器和运算器之间的缓冲存储器，用来平缓运算器和

4、主存储器之间的工作。 后行写数栈 当前没有完全写道主存的数据可以暂存到写数栈,先行控制的处理机结构：,主 存 储 器,存 储 控 制 器,先行指令缓冲栈,先行读数栈,后行写书栈,指令分析器,运算器,通 用 寄 存 器,先行控制中的缓冲深度设计： 通过一种极端情况计算举例： 假设先行指令缓冲栈已经完全充满，缓冲深度是D1。 此时指令缓冲栈输出端，指令流出速度最快，而输入端，流入最慢 假设指令序列的最大长度是L1，平均分析一条指令的时间是t1 而此时更坏的是取指令很慢，平均取一条指令的时间是t2 假设先行控制栈充满到被取空的过程中指令分析条数是L1 则此时有： L1t1 = (L1-D1)t2 可

5、以计算深度：,1、流水的概念特点,流水：把一个重复时序过程分成若干个子过程，每个子过程 都可有效的在其专用功能段上和其它子过程同时执行 的一种技术。,5.2、流水工作方式,取指,访存,执行,译码,写回,IF,ID,EX,MEM,WB,S1,S2,S3,S4,S5,输入,输出,指令的流水处理,流水线的基本结构中主要包括三大部分：锁存器、时钟、功能站。 流水线中每个站都是由一些执行算术和逻辑功能的组合逻辑线路组成的，它们可以互相独立地对流过的信息进行某种操作，相邻两站由高速锁存器（latch）隔开，信息在各站间的流动靠同时送到各站的时钟信号来控制。,S1,S2,Sk,输入,输出,流水线的基本结构,

6、.,.,时钟,1,2,3,4,t0, t0, t0, t0,T0=m t0,(n-1) t0,填入 正常 排空,流水时空图,空间,时间,2、流水线特点： 1）流水一定重叠，比重叠更苛刻。 2）一条流水线通常有多个流水段组成。 3）每段有专用功能部件，各部件顺序连接，不断流。 4）流水线有建立时间、满载时间、排空时间， 5）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。 6）给出指标如最大吞吐率，为满负载最佳指标。,建立时间：在流水线开始时有一段流水线填入时间，使得流水线填满。 正常流动时间：流水线正常工作，各功能段源源不断满载工作。 排空时间：在流水线第一条指令结束时，其他指令还需要一段释放

7、时间。,3、流水的分级、分类,分级：（处理的级别分类） 部件级：将复杂的算逻运算组成流水工作方式； 指令级：把一条指令解释过程分成多个子过程 ； 处理机级：每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中,其他分类： 功能：单功能流水线（如CRAY-1）、多功能流水线 （如TI-ASC） 工作方式：静态流水线、动态流水线 连接方式：线性、非线性 处理数据：标量流水、向量流水,3、流水的分级、分类,静态流水线：（功能负担软件多，便宜）。 同一时间内各功能段只能按一种方式联接工作，只有当进入的是一串相同运算指令时，流水线中各功能段才能高效满负荷工作。 动态流

8、水线：（功能负担硬件多，高效） 。 同一时间内各功能段可按不同运算或功能的联接方式工作，对吞吐率和设备利用率都有好处，但控制复杂，成本明显增加。,3、流水的分级、分类,线性流水线： 非线性流水线：,1,2,3,4,出,入,非线性流水线,(1)ASC算术运算流水线（多功能）,4、流水线举例,浮点加,定点乘,静态多功能流水线时-空图,静态流水线：只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。,动态多功能流水线时-空图,区别：如果从软硬功能分配的观点上来看，静态流水线其实是把功能负担较多地加到软件上，以简化硬件，动态流水线则是把功能负担

9、较多地加在硬件上，以提高流水的效能。,（1）VAX8600的流水结构 a. I部件：预取指令，操作码译码，预取操作数，并存放运算结果。 b. E部件：执行指令。 c. F部件；浮点加速器。 d. M部件：控制CPU和输入输出设备对主存的访问，有16k字节的cache和把虚存地址转换成实存地址的地址转换表（快表） e. 操作台：提供同操作员，引导设备和远程诊断的界面。,指令流水线：一条指令的取指令、译码、取操作数和执行等几个过程能同它前后的指令在时间上重叠，用这种指令重叠的方法构成的流水线就是指令流水线，又叫指令先行控制。,2VAX8600和长城386计算机的指令流水线,VAX8600的CPU结

10、构图,VAX8600指令流水线的工作顺序,实框：表示CPU在执行一条典型的指令时的动作顺序。 虚线：表示6个动作是各自分开进行的，可以同其它指令的动作并行进行。,（2）长城386指令流水线 内部有六个部件 总线接口部件：同外部的接口 取指令、读写数据。 I部件： 指令预取部件：取指令放在 16个字节指令预取队列。 指令译码部件：形成指令微码，指令队列中可放3条指令 E部件： 执行部件：控制、数据部件、保护测试部件 分段部件 分页部件,存储管理部件,相关处理 定义 ：相近指令出现某种关联使不能同时执行。 资源相关 数据相关 控制相关 另一种分类： 局部相关 全局相关,1. 资源相关,资源相关是指

11、当有多条指令进入流水线后在同一机器周期内争用同一功能部件所发生的冲突,例1：,两条指令同时要用一个加法器,指 令,流水段,不同类型指令中各流水段进行的操作,两条指令同时访存造成资源相关,冲突,取指 译码 执行 访存 写回,例2：,使i+3指令停顿一拍进入流水线，以解决访存相关 或重复设置一个存储器,解决方法：,例：有i 和j两条指令，i指令在前，j指令在后，则三种不同类型的数据相关的含义为： RAW读写(先写后读) - 指令 j 试图在指令 i 写入寄存器前就读出该寄存器内容，这样，指令j就会错误地读出该寄存器旧的内容。 （改用相关） i: R1+R2-R3 j: R3*R4-R5 WAR写读

12、(先读后写) - 指令 j 试图在指令 i读出寄存器之前就写入该寄存器，这样，指令i就错误地读得该寄存器新的内容。 （用改相关）i: R3*R4-R5 j: R1+R2-R3 WAW写写(先写后写) - 指令j试图在指令i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令i写入的值成为该寄存器内容。 （改改相关） i: R1*R2-R3 j: R4+R5-R3,2. 数据相关,顺序流动,不按顺序流动,不按顺序流动,例1：如果流水线要执行以下的两条指令 X1=X2+X3 X4=X1-X5,这是一个典型的先写后读（RAW）相关。,例2：结果寄存器的冲突 X6=X1+X2

13、X6=X4*X5,这是个先写后写的写-写相关，两条指令都要用X6存放结果，此时第二条指令也要等待第一条指令完成后才能写。,例3：一条指令要把结果存放到上一条指令存放操作数的寄存器中时发生的冲突。 X5=X4*X3 X4=X0+X6,这是个先读后写的写-读相关。如果这两条指令接连地送到乘法功能部件和加法功能部件中，由于加法比乘法快得多，第二条的结果X4先产生，但必须等待第一条指令做完后才能送X4。,解决办法主要用软件和硬件技术： 时间推后法(延迟执行) 旁路技术或相关专用通路技术,例子：流水执行和相关 （资源相关） 有四段流水线：IF（取指令 ），ID（译码，取数） ， EX（执行）WR（写回）

14、 PC值 指令 流水各段 n : load A IF ID EX WR n+1: load B IF ID EX WR n+2: add A,B IF ID 气泡 EX WR n+3: store C IF ID 气泡 EX WR n+4 : jump K IF ID EX WR n+5: load E 停顿 停顿 停顿。 n+6 停顿 。 K: IF ID EX 例子中有资源相关、有控制转移相关，这将影响流水线的指标。,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,ADD R1,

15、R2,R3,SUB R4,R1,R5,AND R6,R1,R7,OR R8,R1,R9,XOR R10,R1,R11,定向传递R1值,数据相关和定向传递指令,ADD R1,R2,R3,SUB R4,R1,R5,AND R6,R1,R7,OR R8,R1,R9,XOR R10,R1,R11,定向传递R1值,减少定向传送次数的方法,将ID段读寄存器堆操作安排在后半部分，将WB段写寄存器堆 操作安排在前半部分，以减少定向传输操作，同时缩短等待。,ALU 运算结果,写RF,RF,读RF,ALU 操作数寄存器,专用通路（旁路）,寄存器堆RF,多路开关,多路开关,ALU,R4,R1,缓冲寄存器（R1，R4

16、）,旁路,定义： 由条件转移或者程序中断引起的相关成为全局相关。 控制转移冲突:无条件转移和条件转移引起的 （转移指令概率占1/4左右，不可忽视） 中断虽然比例不大，但是中断发生在哪一条指令，哪一个功能段都是不确定的。 因此，处理好条件转移和中断引起的全局相关是至关重要： 确保流水线能够正常工作 减少“断流”引起的吞吐率和效率的下降,3.转移处理（全局相关）,转移处理（全局相关）,i-1,i,i-1,i-1,i+k-3,i+k-2,P,P+1,P+k-4,P+k-3,转移不成功,转移成功,条件转移指令,形成条件码,输入,时间t,输出,输出,减少条件转移对于指令流水的方法 优化延迟转移技术 a.

17、将转移指令前的那条指令调度到延迟槽中； b.将转移目标处的那条指令调度到延迟槽中； c.将转移不发生时该执行的那条指令调度到延迟槽中。 指令取消技术 和前面RISC中介绍的相似。,减少条件转移对于指令流水影响的方法 静态转移预测技术： 正如“先行控制技术”中介绍的那样，静态转移预测是指在处理机的硬件和软件设计完成以后，转移方法已经确定。 在程序执行过程中，转移方向不能改变。 例如：TI公司的SuperSPARC处理机采用了这种技术，而且设置有转移目标缓冲栈，在两个方向上都预取指令,减少条件转移对于指令流水影响的方法 动态转移预测技术： 方法1：在指令Cache中记录转移历史信息 方法2：设置转

18、移目标地址缓冲栈 方法3：设置转移目标指令缓冲栈,TT,NT,NN,TN,N,N,N,N,N,T,T,T,T,TT:最近两次转移都成功 NN:最近两次转移都不成功 TN:最近一次转移成功，前一次不成功 NT:最近一次转移不成功，前一次成功,动态硬件预测转移方法 在程序运行时，借助硬件来动态地预测转移方向。实际上，这是一种尽早生成转移目标地址的方法，它将过去发生过的转移指令地址存入一个由类似cache、称为BTB（Branch target buffer）的转移目标缓冲器中。其中，转移指令地址作为标志，供检测用。,三. 中断 流水机器处理中断的关键不在于如何缩短断流时间，而是如何处理好断点现场及

19、中断后的恢复问题。 不精确断点法(同外部设备中断处理一样)：不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入 精确断点法：不论第i条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第i条的，在第i条之后进入流水线的指令的原有现场都能恢复 (增加设备，加许多缓冲器，各功能段状态保留）,5.3 流水线性能分析计算,一 技术指标,衡量流水线处理机的性能主要是吞吐率、加速比和效率。 1吞吐率：单位时间内能处理的指令条数或能输出的数据量。吞吐率越高，计算机系统的处理能力就越强。就流水线而言，吞吐率就是单位时间内能流出的任务数或能流出的结果数。,吞

20、吐率 的基本计算公式： 其中n表示任务量，Tk表示执行时间。,最大吞吐率：流水线达到稳定状态后可获得的吞吐率。 （1）Tpmax=1/t （2）TPmax=1/ maxt1，t2，t3，t4,吞吐率,子过程3为瓶颈段的时空图,最大吞吐率TPmax=1/3t,瓶颈段细分,重复设置瓶颈流水段,解决瓶颈有两种方法,A： B：,T,重复设置瓶颈流水段后的工作时空图,实际吞吐率（一个K段线形流水）,（1）完成n条指令的解释共需时间 T=kt+(n-1) t=(k+n-1) t （2）流水线的实际吞吐率为 可以看出不仅实际的吞吐率总是小于最大的吞吐率，而且只有当nk时，实际的吞吐率才能接近于理想的最大吞吐

21、率。,进入（出）流水耗时,解释指令耗时,时钟周期,实际吞吐率（一个K段线形流水）,T,S,S1,S2,S4,t1,S3,时间长的占用了一些空余时间,1,2,3,n-1,n,2,3,n,2,3,n,1,2,3,n-1,n,1,2,3,n-1,n,1,2,3,n-1,n,实际吞吐率（一个K段线形流水）,（1）当流水线各段时间不等时完成n条指令,T,S,S1,S2,S4,t1,t12,t17,S3,时间长的占用了一些空余时间,n,K-1,1,2,3,n,1,2,3,n-1,n,1,2,3,n,1,2,3,n,2. 效率：设备的利用率，直接反映了处理机结构有效程度。 流水线有建立时间、排空时间，不总是

22、满负载工作。,各段时间相等，并且输入的n个任务是连续的：,各段时间不等：,最费时环节,通过工作时空图计算效率,=,E,其中，分母为k个段总的加权时空区，分子为n个任务总的加权时空区,设备利用率占整个系统设备利用率的比重不同，可以给每个段赋予不同的“权”值i，这样，线性流水线总效率的一般式为：,各段时间相等:,各段时间不等:,3. 加速比：K段流水线的速度与等效的非流水线的速度之比。,3. 加速比：K段流水线的速度与等效的非流水线的速度之比。,讨论： 1减少瓶颈的办法：多套并行和细分慢的子过程。 2指令串不相同，需功能切换（尽量相同）向量流水。 3非线性流水控制输入，使不碰头。 4T尽量小，尽量

23、一致，减少相关。 5指标给的为最佳值 。,五. 实例分析:性能分析（实测法, 分析法, 时空图法）. 例1. 四段流水线, t1=t3=t4=t, t2=3t,4个任务、10个任务时TP，E、SP 。,（1）分析法: 各段时间不等,时间,1,2,3,1,2,3,1,2,3,4,4,4,4,4,3t,3t,空间,(2) 时空图法:,比较:,N=4 0.267,N=10 0.303,N=100 0.33,40%,45%,49%,1.6,1.8,1.98,E,Sp,Tp(1/t),n=4,m=4,说明:Nk流水性能才发挥得更好,例2. 以浮点加法运算为例（四段流水线）各段时间相等，如何求吞吐率、效率

24、。 求Z=A+B+C+D+E+F+G+H，TP、E、Sp 注意有相关,时间,空间,5,5,5,5,6,6,6,6,7,7,7,7,例3. ASC计算机功能算术运算流水线各段时间相等，6次浮点加、 5次定点乘的吞吐率,效率,加速比 K=8,N=11.,分析：T加=6+(6-1)*1=11 (t) T乘=4+(5-1)*1=8 (t),则 TP= 11/(11+8)t =11/19 t Sp= 56 t /19 t =2.94 E = (6*6+5*4) t /(19*8t)=6/52=7/19,5.4、流水中指令级并行性的进一步开发,粗粒度并行性：在多处理机上分别运行多个进程，由多台处理机合作完

25、成一个程序； 细粒度并行性：指在一个进程中进行操作一级或指令一级的并行处理。 RISC机进一步开发细粒度并行性,5.4.1 超级标量方法,每个时钟周期内能启动n条指令,主要特点： （1）配置有多个性能不同的处理部件，采用多条流水线并行处理。 （2）能同时对若干条指令进行译码，将可并行的指令送往不同的执行部件，从而达到每个周期启动多条指令。 （3）在程序运行期间由硬件（通常是状态记录部件和调度部件）完成指令调度。,每拍启动3条指令 要求并行度=3,超级标量机,1超级标量计算机的原理：,配置多个功能部件 多个译码器，寄存器 端口，总线，能同时 执行多个操作。,2. 超标量流水线调度,按序发射按序完

26、成 按序发射无序完成 无序发射无序完成 无论那种调度策略，都要保证程序运行的最终结果是正确的， Pentium处理器采用的是按序发射按序完成策略PentiumII/III处理器采用的是按序发射无序完成,指令发射：启动指令进入执行段的过程； 指令发射策略：指令发射所使用的协议或规则。 按序发射：当指令按策划功能序的次序发射时，称之为按序发射（in-order issue）。 无序发射：为改善流水线性能，可以将有相关的指令推后发射，而将后面的无相关性的指令提前发射，即不按程序原有次序发射指令，称之为无序发射（out-of-order）。,以一条长指令实现多个操作的并行执行，减少存储器访问,主要特点

27、： （1）单一的控制流。只有一个控制器，每个周期启动一条指 令。 （2）超长指令字被分成多个控制字段，每个字段直接独立地 控制每个功能部件。 （3）含有大量的数据通路和功能部件，由于编译器在编译时 间已考虑可能出现的数据相关和资源相关，故控制硬件较简 单。 （4）在编译阶段完成超长指令中多个可并行执行操作的调度。,5.4.2 超长指令字计算机,每拍启动一条长指令，执行3个操作，相当于3条指令，要求并行度=3,超长指令字计算机（VLIW）的原理结构,5.4.3 超级流水方法,特点：超流水结构是把每一个流水级（一个周期）分成多个（例如3个）子流水级，而在每一个子流水级中取出的仍只有一条指令，但总的

28、来看，在一个周期内取出了三条指令。对于超流水线结构，其中指令部件可以只有一套，也可以有多套独立的执行部件。它虽然每个机器周期只能流出一条指令，但它的周期比其它机器短，一台m度的超级流水线计算机的周期为一般机器周期的1/m，它的一个操作需要m个周期，因而在流水线能充分发挥作用时，其并行度能达到m。,每1/2拍启动一条指令，要求并行度=2,超级流水线的原理结构图,这种方法主要通过提高流水线运行速度来增强机器性能。为提高运行速度，必须要加深流水深度，既增加流水段数，以减少每一段的延迟时间，这样就可加快流水线的运行频率。 下面是R4000超级流水情况分8段：取指1（IF），取指2（IS） 读RF，执行

29、（EX），取数1（DF），取数2（ DS），标记检查（TC），写RF（WB）,5.4.4 超级流水标量计算机,可以把超标量技术与超流水技术结合在一起，这就是超标量超流水线处理机。超标量超流水线处理机在一个时钟周期内要发射指令n次，每次发射指令m条，因此，超标量超流水线处理机每个时钟周期总共要发射指令m*n条。,超标量超流水线处理机的指令执行时空图,5.4.5 超标量（流水）标量处理机的性能,为了比较，单流水普通标量处理机的指令并行度记为(1,1) 超级标量处理机的指令级并行度记做(m,1) 超级流水处理机的指令级并行度记做(1,n) 超标量超流水处理机的指令级并行度记做(m,n) 在理想情况下，N条没有冲突、没有相关的指令在单流水线普通标量处理机上的处理时间是： 把N条指令在一台每个周期发射m条指令的超标