第八章 流水线技术

1、 华北电力大学计算机系1130计算机组成与结构8.2流水线性能分析8.3流水线中的相关 结构相关结构相关 数据相关数据相关 控制相关控制相关8.4流水线的调度8.1流水线的基本概念第八章 流水线技术 华北电力大学计算机系2130计算机组成与结构8.1流水线原理8.1.1 流水线的基本概念 1. 产品生产流水线下面通过一个例子来说明流水线的好处下面通过一个例子来说明流水线的好处: : 两种方案两种方案 两种方案的工作过程对比两种方案的工作过程对比第八章 流水线技术 华北电力大学计算机系3211 华北电力大学计算机系4211 流水线生产过程的抽象描述流水线生产过程的抽象描述 这种流水工作方式的主要

2、特点这种流水工作方式的主要特点 华北电力大学计算机系5130计算机组成与结构8.1 流水线原理2. 2. 简单的理想指令流水线简单的理想指令流水线将处理机执行指令的过程分为三个功能段：将处理机执行指令的过程分为三个功能段：取指取指分析分析执行执行 指令经过各功能段时间分别为指令经过各功能段时间分别为t t取取、t t分分、t t执执 华北电力大学计算机系6130计算机组成与结构8.1 流水线原理(1)顺序方式顺序方式程序总执行时间为：程序总执行时间为：T顺顺ni=1(t取取+t分分+t执执)3nt取指取指i分析分析i执行执行i取指取指i+1分析分析i+1执行执行i+1 华北电力大学计算机系71

3、30计算机组成与结构8.1 流水线原理(2) 一次重叠方式一次重叠方式取指取指i-1分析分析i-1执行执行i-1取指取指i分析分析i执行执行i取指取指i+1分析分析i+1执行执行i+1程序总执行时间为：程序总执行时间为：T一次一次t取取t分分t执执ni=2(t分分+t执执)3 t (n-1)2 t(2n+1) t 华北电力大学计算机系8130计算机组成与结构8.1 流水线原理( (3) ) 二次重叠方式二次重叠方式 取指取指i-1i-1分析分析i-1i-1执行执行i-1i-1取指取指i i分析分析i i执行执行i i取指取指i+1i+1分析分析i+1i+1执行执行i+1i+1程序总执行时间为：

4、程序总执行时间为：T T二次二次i=2i=2t t取取t t分分t t执执n nt t执执3 3 t t (n-1) (n-1) t t(n+2) (n+2) t t 华北电力大学计算机系9130计算机组成与结构3. 先行控制技术先行控制技术( (1) ) 处理机结构的改变处理机结构的改变 传统的处理机是传统的处理机是控制器控制器分析指令，在控制器控制下，分析指令，在控制器控制下，由由运算器运算器完成指令的执行，它们是一个整体。完成指令的执行，它们是一个整体。 流水方式中，各功能段相互独立没有冲突，它们在流水方式中，各功能段相互独立没有冲突，它们在同一时刻可以并行工作，这就要求同一时刻可以并行

5、工作，这就要求取指取指、分析分析、执行执行三三个功能段相互独立。个功能段相互独立。8.1 流水线原理 华北电力大学计算机系10130计算机组成与结构 在处理机内部需要有独立的在处理机内部需要有独立的取指令取指令、分析指令分析指令和和执行指令执行指令的功能部件，将传统处理机中的指令控制器分解成为三个独立的功能部件，将传统处理机中的指令控制器分解成为三个独立的控制器：的控制器： 存储控制器存储控制器：负责流水线中各功能段对存储器的访问控制：负责流水线中各功能段对存储器的访问控制 包括取指令、取操作数、写回运算结果包括取指令、取操作数、写回运算结果 指令控制器指令控制器：完成取指令部件和分析指令部件

6、的控制：完成取指令部件和分析指令部件的控制 运算控制器运算控制器：对运算器的执行加以控制：对运算器的执行加以控制8.1 流水线原理 华北电力大学计算机系11130计算机组成与结构（2 2）解决多功能段访存冲突问题）解决多功能段访存冲突问题 当指令在流水线中执行时，在二次重叠方式下流水当指令在流水线中执行时，在二次重叠方式下流水线完全充满时，三个功能段同时工作。线完全充满时，三个功能段同时工作。u “ “取指取指i+1”i+1”要访问存储器取第要访问存储器取第i+1i+1条指令条指令u “ “分析分析i”i”要访问存储器取第要访问存储器取第i i条指令需要的操作数条指令需要的操作数u “ “执行

7、执行i-1”i-1”也要访存将运算结果写回存储器也要访存将运算结果写回存储器8.1 流水线原理 华北电力大学计算机系12130计算机组成与结构解决方法：解决方法： 1 1将程序地址空间和数据地址空间分开，两个地址空将程序地址空间和数据地址空间分开，两个地址空间提供独立访问的能力。间提供独立访问的能力。 2 2采用低位交叉并行访问存储器。采用低位交叉并行访问存储器。 3 3采用先行控制技术。采用先行控制技术。 8.1 流水线原理 华北电力大学计算机系13130计算机组成与结构采用先行控制技术的处理机结构采用先行控制技术的处理机结构主存主存储器储器存存储储器器控控制制器器先行取指令栈先行取指令栈先

8、行取数栈先行取数栈指令分析器指令分析器先行操作栈先行操作栈运算控制器运算控制器运算器运算器通通用用寄寄存存器器堆堆后行写数栈后行写数栈8.1 流水线原理 华北电力大学计算机系14130计算机组成与结构指令分析器现行程序计数器现行程序计数器PC采用先行取指令栈结构采用先行取指令栈结构存存储储器器控控制制器器先行程序计数器先行程序计数器PCI控制逻辑控制逻辑先行取指令栈先行取指令栈指令寄存器指令寄存器IR8.1 流水线原理 华北电力大学计算机系15130计算机组成与结构使用先行控制技术前使用先行控制技术前分析分析i-1执行执行i-1分析分析i执行执行i分析分析i+1执行执行i+1分析分析i+2执行

9、执行i+2分析分析i-1执行执行i-1分析分析i执行执行i分析分析i+1执行执行i+1分析分析i+2执行执行i+2流水线使用先行控制技术前后的不同：流水线使用先行控制技术前后的不同：使用先行控制技术后使用先行控制技术后8.1 流水线原理 华北电力大学计算机系16130计算机组成与结构4. 指令流水线指令流水线把指令的解释过程分解为把指令的解释过程分解为“分析分析”和和“执行执行”两个子过程，并让这两个子过程分别用独立的分两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。析部件和执行部件来实现。理想情况：理想情况：速度提高一倍速度提高一倍8.1 流水线原理 华北电力大学计算机系1

10、7211 华北电力大学计算机系18130计算机组成与结构5. 浮点加法流水线浮点加法流水线把浮点加法的全过程分解为把浮点加法的全过程分解为“求阶差求阶差”、“对对阶阶”、“尾数相加尾数相加”、“规格化规格化”四个子过程，四个子过程，并让并让它们分别用各自独立的部件来实现。它们分别用各自独立的部件来实现。理想情况：理想情况：速度提高速度提高3 3倍倍8.1 流水线原理 华北电力大学计算机系19130计算机组成与结构8.1 流水线原理 华北电力大学计算机系20130计算机组成与结构6. 时空图时空图时空图时空图从时间和空间两个方面描述了流水从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐

11、标代表时间，线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。纵坐标代表流水线的各个段。8.1 流水线原理 华北电力大学计算机系21211 华北电力大学计算机系22130计算机组成与结构7. 流水技术流水技术流水技术是指：将一个重复的时序过程分解是指：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。其专用功能段上与其他子过程同时执行。8流水技术的特点(1) (1) 流水过程由多个相联系的子过程组成，每个流水过程由多个相联系的子过程组成，每个子过程称为流水线的子过程称为流水线的“级级”

12、或或“段段”。“段段”的数的数目称为流水线的目称为流水线的“深度深度”。(2) (2) 每个子过程由专用的功能段实现；每个子过程由专用的功能段实现；8.1 流水线原理 华北电力大学计算机系23130计算机组成与结构(4) (4) 流水线需要有流水线需要有“通过时间通过时间”（第一个任务流出结果（第一个任务流出结果所所需的时间），在此之后流水过程才进入稳定工作状需的时间），在此之后流水过程才进入稳定工作状态，每一个时钟周期（拍）流出一个结果；态，每一个时钟周期（拍）流出一个结果；(3) (3) 各个功能段所需时间应尽量相等，否则，时间长各个功能段所需时间应尽量相等，否则，时间长的功能段将成为流水

13、线的瓶颈，会造成流水线的的功能段将成为流水线的瓶颈，会造成流水线的 “堵塞堵塞”和和“断流断流”。这个时间一般为一个时钟。这个时间一般为一个时钟周期周期（拍）；（拍）；(5) (5) 流水技术适合于大量重复的时序过程，只有输入流水技术适合于大量重复的时序过程，只有输入端能连续地提供任务，流水线的效率才能充分发端能连续地提供任务，流水线的效率才能充分发挥。挥。8.1 流水线原理 华北电力大学计算机系25130计算机组成与结构8.1.2 流水线的分类流水线可以按不同的观点进行分类。流水线可以按不同的观点进行分类。 单功能流水线：单功能流水线：只能完成一种固定功能的只能完成一种固定功能的 流水线。流

14、水线。 多功能流水线：多功能流水线：流水线的各段可以进行不同的流水线的各段可以进行不同的 连接，从而实现不同的功能。连接，从而实现不同的功能。 例如：例如： TI ASCTI ASC的多功能流水线的多功能流水线1按功能的多少来分8.1 流水线原理 华北电力大学计算机系27130计算机组成与结构在静态流水线中，只有当输入是一串相同在静态流水线中，只有当输入是一串相同的运算操作时，流水的效率才能得到发挥。的运算操作时，流水的效率才能得到发挥。动画演示动画演示2按同一时间内各段之间的连接方式来分 静态流水线：静态流水线：在同一时刻，流水线的各段只能在同一时刻，流水线的各段只能 按同一种功能的连接方式

15、工作。按同一种功能的连接方式工作。 8.1 流水线原理 华北电力大学计算机系28130计算机组成与结构 动态流水线：动态流水线：在同一时刻，流水线的各段可以在同一时刻，流水线的各段可以 按不同功能的连接方式工作。按不同功能的连接方式工作。 动画演示动画演示 这样就不是非得相同运算的一串操作才能这样就不是非得相同运算的一串操作才能 流水处理。流水处理。 优点：优点：能提高流水线的效率能提高流水线的效率 缺点：缺点：会使流水线的控制变得复杂会使流水线的控制变得复杂8.1 流水线原理 静、动态流水线时空图的对比静、动态流水线时空图的对比 华北电力大学计算机系30130计算机组成与结构3按照流水线的级

16、别来分 部件级流水线部件级流水线（运算操作流水线）：把处理机的（运算操作流水线）：把处理机的 算术逻辑部件分段，使得各种数据类型的操作能算术逻辑部件分段，使得各种数据类型的操作能 够进行流水。够进行流水。 处理机级流水线处理机级流水线（指令流水线）：把指令的解释（指令流水线）：把指令的解释 执行过程按照流水方式进行处理。执行过程按照流水方式进行处理。 例如：例如：前面把指令解释过程分解为：前面把指令解释过程分解为： 分析分析和和执行执行 DLXDLX的基本流水线把指令解释过程分解为：的基本流水线把指令解释过程分解为： 取指令、指令译码、执行、访存、写回。取指令、指令译码、执行、访存、写回。 (

17、 (图示图示) )8.1 流水线原理 华北电力大学计算机系31130计算机组成与结构8.1 流水线原理 华北电力大学计算机系32130计算机组成与结构 处理机间流水线处理机间流水线（宏流水线）：它是指由两个（宏流水线）：它是指由两个 以上的处理机串行地对同一数据流进行处理，以上的处理机串行地对同一数据流进行处理， 每个处理机完成一项任务。每个处理机完成一项任务。 动画解析动画解析8.1 流水线原理 华北电力大学计算机系33130计算机组成与结构4按照数据表示来分 向量处理机：向量处理机：具有向量指令和向量数据表示的具有向量指令和向量数据表示的 处理机。处理机。 例如：例如：TI ASC, CR

18、AY-I TI ASC, CRAY-I 等等 标量处理机：标量处理机：不具有向量指令和向量数据表示，不具有向量指令和向量数据表示， 仅对标量进行流水处理的处理机。仅对标量进行流水处理的处理机。 例如：例如：IBM860/91, Amdahl 470V/6IBM860/91, Amdahl 470V/6 等等5. 5. 按照是否有反馈回路来分按照是否有反馈回路来分 线性流水线：线性流水线：流水线中的各段串行连接，没流水线中的各段串行连接，没 有反馈回路。有反馈回路。 非线性流水线：非线性流水线：流水线中的各段除有串行连接流水线中的各段除有串行连接 外，还有反馈回路。外，还有反馈回路。 ( (举例

19、举例) )8.1 流水线原理 华北电力大学计算机系34130计算机组成与结构8.1 流水线原理 流水线的调度问题流水线的调度问题 华北电力大学计算机系36130计算机组成与结构顺序流动流水线：顺序流动流水线：流水线输出端任务流出的顺流水线输出端任务流出的顺 序与输入端任务流入的顺序序与输入端任务流入的顺序相同相同。 异步流动流水线异步流动流水线（乱序流水线）：流水线输出（乱序流水线）：流水线输出 端任务流出的顺序与输入端任务流入的顺序端任务流出的顺序与输入端任务流入的顺序 不同不同。6. 按照流动是否可以乱序来分8.1 流水线原理 华北电力大学计算机系37130计算机组成与结构8.2 流水线性

20、能分析吞吐率吞吐率是指单位时间内流水线所完成的任是指单位时间内流水线所完成的任务数或输出结果的数量。务数或输出结果的数量。1. 吞吐率(1) (1) 最大吞吐率最大吞吐率TPTPmaxmax 最大吞吐率最大吞吐率是指流水线在连续流动达到是指流水线在连续流动达到稳定状态后所得到的吞吐率。稳定状态后所得到的吞吐率。 若流水线各段的时间相等，均为若流水线各段的时间相等，均为t t0 0 ， 则：则： TPmax 1 /t0第八章 流水线技术 华北电力大学计算机系38130计算机组成与结构 若流水线各段的时间不等，则：若流水线各段的时间不等，则： 最大吞吐率取决于流水线中最慢的一段所最大吞吐率取决于流

21、水线中最慢的一段所 需的时间，这段就成了流水线的瓶颈。需的时间，这段就成了流水线的瓶颈。 消除瓶颈的方法消除瓶颈的方法 ( (举例举例) )l 细分瓶颈段细分瓶颈段 l 重复设置瓶颈段重复设置瓶颈段 ( (时时- -空图空图) )1 1maxmaxt ti i TPmax 8.2 流水线的性能分析重复设置瓶颈段重复设置瓶颈段( (时时- -空图举例空图举例) ) 华北电力大学计算机系41130计算机组成与结构 第一种情况：各段时间第一种情况：各段时间相等相等（设为（设为t t0 0） 假设流水线由假设流水线由 m m 段组成，完成段组成，完成 n n 个任务。个任务。l 时空图时空图l 完成完

22、成 n n 个任务所需的时间个任务所需的时间 T T流水流水m mt t0 0( (n n1)1)t t0 0 ( (说明说明) )(2) (2) 实际吞吐率实际吞吐率TPTP 流水线的实际吞吐率小于最大吞吐率。流水线的实际吞吐率小于最大吞吐率。8.2 流水线的性能分析 华北电力大学计算机系42211 华北电力大学计算机系43211完成完成 n n 个任务所需的时间个任务所需的时间 华北电力大学计算机系44130计算机组成与结构l 实际吞吐率实际吞吐率TP TP T T流水流水n nm mt t0 0( (n n) )t t0 0n n(1(1 ) )t t0 0 m m1 11 1TPTPm

23、axmaxn n 1 1n nm m1 1TP TP TPTPmaxmax当当n n m m 时，时，TP TP TPTPmaxmax 第二种情况：各段时间第二种情况：各段时间不等不等l 时空图时空图8.2 流水线的性能分析 华北电力大学计算机系45130计算机组成与结构8.2 流水线的性能分析 华北电力大学计算机系46130计算机组成与结构 l 完成完成 n n 个任务所需的时间个任务所需的时间 T T流水流水t ti i( (n n1)1)t tj j t tj jmaxmaxt ti i l 实际吞吐率实际吞吐率TP TP t ti i( (n n1)1)t tj jm mi=1i=1n

24、 ni=1i=1m m8.2 流水线的性能分析 华北电力大学计算机系47130计算机组成与结构加速比加速比是指流水线的速度与等功能非流水是指流水线的速度与等功能非流水线的速度之比。线的速度之比。2. 加速比S S ST T非流水非流水T T流水流水（其中（其中T T流水流水和和T T非流水非流水分别为按流水和按非流水分别为按流水和按非流水方式处理方式处理 n n 个任务所需的时间）个任务所需的时间） 若流水线为若流水线为 m m 段，且各段时间相等，均段，且各段时间相等，均为为t t0 0 ，则：，则： T T非流水非流水n mn mt t0 0 ( (解释解释) ) T T流水流水m mt

25、t0 0( (n n1)1)t t0 0 8.2 流水线的性能分析 华北电力大学计算机系48130计算机组成与结构8.2 流水线的性能分析 华北电力大学计算机系49130计算机组成与结构可以看出：可以看出：当当n n m m 时，时，S S m m想一想：想一想：n n 越大越好？越大越好？效率效率是指流水线的设备利用率。是指流水线的设备利用率。(1) (1) 由于流水线有由于流水线有通过时间和排空时间通过时间和排空时间，所以，所以 流水线的各段并不是一直满负荷地工作。流水线的各段并不是一直满负荷地工作。 故：故：E E 1 1S S T T非流水非流水T T流水流水nmnmt t0 0m m

26、t t0 0( (n n1 1) )t t0 0mnmnm mn n1 1m mn n1 1 m m1 1 8效率 E8.2 流水线的性能分析 华北电力大学计算机系50130计算机组成与结构8.2 流水线的性能分析 华北电力大学计算机系51130计算机组成与结构(2) (2) 若各段时间相等，则各段的效率若各段时间相等，则各段的效率e ei i相等，即相等，即 e e1 1e e2 2 e e8 8 e em mn nt t0 0T T流水流水 ( (解释解释) ) 整个流水线的效率为整个流水线的效率为: :当当 n n m m 时，时，E E 1 1E E n nt t0 0T T流水流水n

27、 nm mn n1 11n n1 m1(3) (3) 从时空图上看，效率实际上就是从时空图上看，效率实际上就是 n n 个任务所个任务所占的时空区与占的时空区与 m m 个段总的时空区个段总的时空区之比，即：之比，即： n n 个任务占用的时空区个任务占用的时空区E E ( (解释解释) ) m m 个段总的时空区个段总的时空区8.2 流水线的性能分析 华北电力大学计算机系52211 华北电力大学计算机系53130计算机组成与结构(4) (4) 提高流水线效率所采取的措施对于提高提高流水线效率所采取的措施对于提高 吞吐率也有好处。吞吐率也有好处。4流水线性能分析举例例例8.18.1 在在静态流

28、水线静态流水线上计算上计算 A Ai iB Bi i ， 求：吞吐率，加速比，效率。求：吞吐率，加速比，效率。4 4i i=1=18.2 流水线的性能分析 华北电力大学计算机系54130计算机组成与结构8.2 流水线的性能分析 华北电力大学计算机系55130计算机组成与结构解解：( (1) 1) 确定适合于流水处理的确定适合于流水处理的计算过程计算过程(2) (2) 画时空图画时空图 (8) (8) 计算性能计算性能 吞吐率吞吐率 TPTP7 7(20(20t t) ) 加速比加速比 S S(34(34t t) )(20(20t t) )1.71.7 效率效率 E E(4(44 43 36)6

29、)(8(820)20)0.210.218.2 流水线的性能分析 华北电力大学计算机系56211 华北电力大学计算机系57211 华北电力大学计算机系58130计算机组成与结构8.2 流水线的性能分析 华北电力大学计算机系59130计算机组成与结构可以看出，在求解此问题时，该流水线的效率可以看出，在求解此问题时，该流水线的效率不高。不高。 ( (原因原因) )动态流水线的时空图动态流水线的时空图 举例举例 8.2 流水线的性能分析 华北电力大学计算机系60130计算机组成与结构举例举例 : : 这样行不行？这样行不行？ 正确答案正确答案8.2 流水线的性能分析 华北电力大学计算机系61130计算

30、机组成与结构5有关流水线性能的若干问题(1) (1) 流水线并不能减少流水线并不能减少( (而且一般是增加而且一般是增加) )单条指单条指 令的执行时间，但却能提高吞吐率。令的执行时间，但却能提高吞吐率。(2) (2) 增加流水线的深度增加流水线的深度( (段数段数) )可以提高流水线的可以提高流水线的 性能。性能。(3) (3) 流水线的深度受限于流水线的延迟和流水线流水线的深度受限于流水线的延迟和流水线 的额外开销。的额外开销。8.2 流水线的性能分析 华北电力大学计算机系62130计算机组成与结构8.3流水线中的相关1相关的概念 流水线中的相关流水线中的相关是指相邻或相近的两条指是指相邻

31、或相近的两条指令因存在某种关联，后一条指令不能在原指定令因存在某种关联，后一条指令不能在原指定的时钟周期开始执行的时钟周期开始执行。 结构相关结构相关 当硬件资源满足不了同时重叠执行的指当硬件资源满足不了同时重叠执行的指 令的要求，而发生资源冲突时，就发生令的要求，而发生资源冲突时，就发生了结了结 构相关。构相关。2相关的分类第八章 流水线技术 华北电力大学计算机系63130计算机组成与结构 数据相关数据相关 当一条指令需要用到前面某条指令的结当一条指令需要用到前面某条指令的结 果，从而不能重叠执行时，就发生了果，从而不能重叠执行时，就发生了数据相数据相 关关。 控制相关控制相关 当流水线遇到

32、分支指令和其他能够改变当流水线遇到分支指令和其他能够改变 PCPC值的指令时，就会发生值的指令时，就会发生控制相关控制相关。3几个问题 相关有可能会使流水线停顿。相关有可能会使流水线停顿。8.3 流水线中的相关 华北电力大学计算机系64130计算机组成与结构在本章中，我们在本章中，我们约定：约定： 当一条指令被暂停时，暂停在其后发射（流出）的指令，但继续执行在其前发射的 指令。 消除相关的消除相关的基本方法：基本方法： 让流水线中的某些指令暂停，而让其它让流水线中的某些指令暂停，而让其它 指令继续执行。指令继续执行。8.3 流水线中的相关 华北电力大学计算机系65130计算机组成与结构8.3.

33、1 流水线中的结构相关2. 如果某种指令组合因资源冲突而不能顺利重 叠执行，则称该机器具有结构相关。1. 在流水线机器中，为了使各种指令组合能顺 利地重叠执行，需要把功能部件流水化，并 把资源重复设置。3. 常见的导致结构相关的原因： 功能部件不是全流水功能部件不是全流水 重复设置的资源的份数不够重复设置的资源的份数不够8.3 流水线中的相关 华北电力大学计算机系66130计算机组成与结构4. 结构相关举例：访存冲突 当数据和指令存在同一存储器中时，访当数据和指令存在同一存储器中时，访存指令会存指令会导致访存冲突导致访存冲突。解决办法解决办法： 插入暂停周期插入暂停周期 （“流水线气泡流水线气

34、泡”或或“气泡气泡”）8.3 流水线中的相关 华北电力大学计算机系69130计算机组成与结构引入暂停后的时空图引入暂停后的时空图8.3 流水线中的相关 华北电力大学计算机系70130计算机组成与结构5. 避免结构相关：6. 有些设计方案允许有结构相关 所有功能单元完全流水化所有功能单元完全流水化 设置足够的硬件资源设置足够的硬件资源硬件代价很大。硬件代价很大。 降低成本降低成本 减少部件的延迟减少部件的延迟解决方法解决方法： 设置相互独立的指令存储器和设置相互独立的指令存储器和 数据存储器或设置相互独立的数据存储器或设置相互独立的 指令指令CacheCache和数据和数据CacheCache。

35、8.3 流水线中的相关 华北电力大学计算机系71130计算机组成与结构8.3.2 流水线的数据相关1. 数据相关简介 当指令在流水线中重叠执行时，流水线有当指令在流水线中重叠执行时，流水线有 可能改变指令读可能改变指令读/ /写操作数的顺序，使之不同写操作数的顺序，使之不同 于它们在非流水实现时的顺序，这将导致数据于它们在非流水实现时的顺序，这将导致数据 相关。相关。 数据相关举例数据相关举例8.3 流水线中的相关 华北电力大学计算机系73130计算机组成与结构2. 利用定向技术减少数据相关引起的暂停 (1)(1) 定向技术的定向技术的主要思路：主要思路：在发生上述在发生上述 数据相关时，后面

36、的指令并不是马数据相关时，后面的指令并不是马 上就要用到前一条指令的计算结果。上就要用到前一条指令的计算结果。 如果能够将计算结果从其产生的地如果能够将计算结果从其产生的地 方直接送到需要它的地方，就可以方直接送到需要它的地方，就可以 避免暂停。避免暂停。 (2) (2) 采用定向技术消除上例中的相关采用定向技术消除上例中的相关 工作过程演示工作过程演示8.3 流水线中的相关 华北电力大学计算机系76130计算机组成与结构(3) (3) 当定向硬件检测到前面某条指令的结果寄存当定向硬件检测到前面某条指令的结果寄存 器就是当前指令的源寄存器时，控制逻辑会器就是当前指令的源寄存器时，控制逻辑会 将

37、前面那条指令的结果直接从其产生的地方将前面那条指令的结果直接从其产生的地方 定向到当前指令所需的位置。定向到当前指令所需的位置。(4) (4) 一个功能单元的输出不仅可以定向到其自身一个功能单元的输出不仅可以定向到其自身 的输入，而且还可以定向到其它单元的输入。的输入，而且还可以定向到其它单元的输入。 举例举例8.3 流水线中的相关 华北电力大学计算机系77130计算机组成与结构8.3 流水线中的相关 华北电力大学计算机系78130计算机组成与结构(5) (5) 在在DLXDLX中，任何流水寄存器到任何功能单元的中，任何流水寄存器到任何功能单元的 输入都可能需要定向路径。输入都可能需要定向路径

38、。(6) (6) 当两条指令对存储器同一单元进行读写时，当两条指令对存储器同一单元进行读写时， 也可能发生数据相关。但本章仅讨论有关寄也可能发生数据相关。但本章仅讨论有关寄 存器的数据相关。存器的数据相关。3. 数据相关的分类 按照指令对寄存器的读写顺序，可以将数据按照指令对寄存器的读写顺序，可以将数据相关分为以下三种类型：相关分为以下三种类型：（考虑（考虑两条指令两条指令i i和和j j ， 假设假设i i 先进入流水线）先进入流水线）8.3 流水线中的相关 华北电力大学计算机系80130计算机组成与结构(2) (2) 写后写相关写后写相关 (WAW)(WAW) 在在 i i 写入之前，写入

39、之前，j j 先写。先写。 最后写入的结果是最后写入的结果是 i i 的，错误！的，错误！(1) (1) 写后读相关写后读相关 (RAW) (RAW) ( (命名规则命名规则) ) 在在 i i 写入之前，写入之前，j j 先去读。先去读。 j j 读出的内容是错误的。读出的内容是错误的。 这是最常见的相关。这是最常见的相关。 这种相关仅出现在这样的流水线中这种相关仅出现在这样的流水线中： 流水线中有多个段可以进行写操作流水线中有多个段可以进行写操作 当某条指令在流水线中暂停时，允许其后当某条指令在流水线中暂停时，允许其后 的指令继续向前流动。的指令继续向前流动。8.3 流水线中的相关 DLX

40、 DLX整数流水线中不会发生这种相关整数流水线中不会发生这种相关 （仅在（仅在WBWB段进行写操作）段进行写操作） 若对若对DLXDLX作以下修改，则会发生作以下修改，则会发生WAWWAW相关相关： 把把ALUALU操作指令的操作指令的“写回写回”移到移到MEMMEM段段 假设访问数据存储器需占用两拍假设访问数据存储器需占用两拍 举例举例 华北电力大学计算机系82130计算机组成与结构(3) (3) 读后写相关读后写相关 (WAR)(WAR)在在 i i 读之前，读之前，j j 先写。先写。i i 读出的内容是错误的！读出的内容是错误的！ 这种相关仅出现在这样的流水线中：这种相关仅出现在这样的

41、流水线中： 有些指令是在流水线的后部读源操作数，有些指令是在流水线的后部读源操作数， 而有些指令则是在流水线的前部写结果。而有些指令则是在流水线的前部写结果。 DLX DLX流水线中不会发生这种相关；流水线中不会发生这种相关； （读在先（读在先(ID),(ID),写在后写在后(WB)(WB)） 这种相关很少发生；这种相关很少发生； （因为流水线一般是先读操作数，后写结果）（因为流水线一般是先读操作数，后写结果） 复杂指令可能导致这种相关。复杂指令可能导致这种相关。8.3 流水线中的相关 华北电力大学计算机系83130计算机组成与结构(1) (1) 并非所有的数据相关都可以用定向技术解决并非所有

42、的数据相关都可以用定向技术解决 举例举例4. 需要暂停的数据相关8.3 流水线中的相关 华北电力大学计算机系85130计算机组成与结构(2) (2) 增加流水线互锁硬件，插入增加流水线互锁硬件，插入“暂停暂停”。 当互锁硬件发现这种相关时，就当互锁硬件发现这种相关时，就 暂停流水线暂停流水线，直到相关消失。直到相关消失。 举例：举例：演示演示A A 演示演示B B 8.3 流水线中的相关 华北电力大学计算机系87130计算机组成与结构8.3 流水线中的相关 华北电力大学计算机系88130计算机组成与结构例例8.58.5 假设某指令序列中假设某指令序列中2020的指令是的指令是LoadLoad指

43、令，指令，并且紧跟在并且紧跟在LoadLoad指令之后的半数指令需要使用到载指令之后的半数指令需要使用到载入的结果，如果这种数据相关将产生一个时钟周期入的结果，如果这种数据相关将产生一个时钟周期的延迟。理想流水线（没有任何延迟，的延迟。理想流水线（没有任何延迟，CPICPI为为1 1）的）的指令执行速度要比这种真实流水线的快多少？指令执行速度要比这种真实流水线的快多少？解解：我们可以利用我们可以利用CPICPI作为衡量标准。对于真实的流作为衡量标准。对于真实的流水线而言，由于水线而言，由于LoadLoad指令之后的半数指令需要暂停，指令之后的半数指令需要暂停，所以这些被暂停指令的所以这些被暂停

44、指令的CPICPI是是2 2。又知。又知LoadLoad指令占全指令占全部指令的部指令的2020，所以真实流水线的实际，所以真实流水线的实际CPICPI为：为：(0.9(0.91+0.11+0.12)=1.12)=1.1，这表示理想流水线的指令执，这表示理想流水线的指令执行速度是其执行速度的行速度是其执行速度的1.11.1倍倍。 8.3 流水线中的相关 华北电力大学计算机系89130计算机组成与结构5对数据相关的编译调度方法 (1) (1) 流水线中常常会遇到许多种类型的暂停流水线中常常会遇到许多种类型的暂停 例如，按通常的代码生成模式，表达式例如，按通常的代码生成模式，表达式 A AB BC

45、 C的代码会导致暂停的代码会导致暂停8.3 流水线中的相关A AB BC C的代码会导致暂停的代码会导致暂停 华北电力大学计算机系91130计算机组成与结构(3) (3) 举例：举例： 例例8.68.6 请为下列表达式生成没有暂停的请为下列表达式生成没有暂停的DLXDLX 指令序列：指令序列： a ab bc c ； d de ef f ； 假设载入延迟为假设载入延迟为1 1个时钟周期。个时钟周期。 题解题解(2) (2) 编译器可以通过重新排列代码的顺序来消编译器可以通过重新排列代码的顺序来消除这种暂停，这种技术称为除这种暂停，这种技术称为流水线调度或流水线调度或 指令调度。指令调度。8.3

46、 流水线中的相关 华北电力大学计算机系93130计算机组成与结构(1) (1) 指令发射指令发射(issue)(issue)：指令从译码段：指令从译码段(ID)(ID)进入进入 执行段执行段(EX)(EX)。 相应的指令称为相应的指令称为已发射的指令已发射的指令。 (2) DLX(2) DLX整数流水线中，可以在整数流水线中，可以在IDID段检测所有的段检测所有的 数据相关；数据相关； 若数据相关，则在指令流出前，让其暂停。若数据相关，则在指令流出前，让其暂停。 (3) (3) 可以在可以在IDID段确定需要什么样的定向，并设置段确定需要什么样的定向，并设置 相应的控制；相应的控制； 这样能减

47、少硬件复杂度这样能减少硬件复杂度( (因为不必挂起已因为不必挂起已 改变了机器状态的指令）。改变了机器状态的指令）。6. 对DLX流水线控制的实现8.3 流水线中的相关 华北电力大学计算机系94130计算机组成与结构(4) (4) 也可以在需要用到操作数的那个时钟周期检测也可以在需要用到操作数的那个时钟周期检测 相关或定向；相关或定向；(5) (5) 举例说明：举例说明： 由由LoadLoad指令引起的指令引起的RAWRAW相关的互锁相关的互锁( (简称简称Load Load 互锁互锁) )可以通过可以通过IDID段的检测来实现；段的检测来实现； 到到ALUALU输入的定向可以在输入的定向可以

48、在EXEX段实现。段实现。LoadLoad互锁互锁 流水线相关硬件可以检测到的各种相关情况流水线相关硬件可以检测到的各种相关情况 可以看出，仅需把可以看出，仅需把LoadLoad指令的目的寄存指令的目的寄存 器地址与器地址与LoadLoad指令后的两条指令的源寄存器指令后的两条指令的源寄存器 地址进行比较。地址进行比较。8.3 流水线中的相关 在在IDID段检测是否需要启动段检测是否需要启动LoadLoad互锁需要进行互锁需要进行 三种比较三种比较 华北电力大学计算机系97130计算机组成与结构 当检测到相关后，控制部件必须在流水线中当检测到相关后，控制部件必须在流水线中 插入暂停周期，并使插

49、入暂停周期，并使IFIF和和IDID段中的指令停止段中的指令停止 前进。前进。l 将将ID/EXID/EX中的控制部分清中的控制部分清“O”O”。l IF/IDIF/ID内容回送到其自身入口。内容回送到其自身入口。定向逻辑定向逻辑 有更多的情况要考虑有更多的情况要考虑 关键思路：关键思路：流水线寄存器不仅包含数据，而且流水线寄存器不仅包含数据，而且 包含源寄存器和目的寄存器地址（字段）包含源寄存器和目的寄存器地址（字段）8.3 流水线中的相关 华北电力大学计算机系98130计算机组成与结构 所有的定向发生在：所有的定向发生在： ALUALU或或DMDM输出输出 ALU ALU输入，输入，DMD

50、M输入，输入， “ “O”O”检测部件检测部件 ( (图示图示) ) 华北电力大学计算机系99211 华北电力大学计算机系100130计算机组成与结构8.3.8 流水线的控制相关1. 分支指令的执行结果一、分支引起的暂停及减少分支开销的方法 转移失败：转移失败：PCPC值加值加4 4 转移成功：转移成功：将将PCPC值改变为转移目标地址值改变为转移目标地址 到到MEMMEM段的末尾才改变段的末尾才改变 一旦检测到分支指令一旦检测到分支指令( (在在IDID段段) )，就暂停，就暂停执行其后的指令，直到分支指令到达执行其后的指令，直到分支指令到达MEMMEM段，段，确定出新的确定出新的PCPC值

51、为止。值为止。2. 处理分支指令最简单的方法8.3 流水线中的相关 在在DLXDLX流水线中，分支转移成功导致流水线中，分支转移成功导致暂停暂停3 3个个时钟周期时钟周期。 若分支指令的频度为若分支指令的频度为8080，理想理想CPICPI1 1， 则则 实际实际CPICPI1 180803232 华北电力大学计算机系102130计算机组成与结构3. 减少分支开销的两种途径 在流水线中尽早判断分支转移是否成功；在流水线中尽早判断分支转移是否成功； 转移成功时，尽早计算出转移目标地址。转移成功时，尽早计算出转移目标地址。两者应同时采用，缺一不可。两者应同时采用，缺一不可。对于对于DLXDLX作如

52、下改进作如下改进: :(1) (1) 把把“0 0？”测试移至测试移至IDID段；段；8.3 流水线中的相关 华北电力大学计算机系104130计算机组成与结构(2) (2) 在在IDID段增设一个加法器，这样可以把分支段增设一个加法器，这样可以把分支 开销减少一拍。开销减少一拍。 改进后流水线的分支操作改进后流水线的分支操作 （表（表8.58.5）8.3 流水线中的相关流流 水水 段段分分 支支 指指 令令 操操 作作IFIFIDIDEXEXIF/ID.IR IF/ID.IR MemPC MemPC; IF/ID.NPC,PC ; IF/ID.NPC,PC (if ID/EX.cond (if

53、 ID/EX.cond ID/EX.NPC else PC+4); ID/EX.NPC else PC+4);ID/EX.A ID/EX.A RegsIF/ID.IR RegsIF/ID.IR6.106.10; ID/EX.B ; ID/EX.B RegsIF/ID.IR RegsIF/ID.IR11.1511.15;ID/EX.NPC ID/EX.NPC IF/ID.NPC + (IR IF/ID.NPC + (IR1616) )1616#IR#IR16.8116.81; ;ID/EX.IR ID/EX.IR IF/ID.IR; ID/EX.cond IF/ID.IR; ID/EX.cond

54、 (RegsIF/ID.IR (RegsIF/ID.IR6.106.10 op 0; op 0;ID/EX.ImmID/EX.Imm (IR (IR1616) )1616#IR#IR16.8116.81; ;MEMMEMWBWB表 8.5 改进后流水线的分支操作( (动画演示动画演示) )( (动画演示动画演示) ) 华北电力大学计算机系106130计算机组成与结构二、程序中分支的行为特点1. 各种能改变各种能改变PCPC值的指令的执行频度值的指令的执行频度 （SPECSPEC基准程序，基准程序，DLXDLX上执行）上执行） 条件分支条件分支 整数程序：整数程序：14141515 浮点程序：浮

55、点程序：8 81212 向前分支与向后分支的比：向前分支与向后分支的比： 8181 无条件分支无条件分支 绝大多数：绝大多数：448.3 流水线中的相关 华北电力大学计算机系108130计算机组成与结构2条件分支转移成功的概率条件分支转移成功的概率 平均值平均值 整数程序整数程序 向前：向前：1818无条件：无条件：4 4 向后：向后：8 8 浮点程序浮点程序 向前：向前：7 7 无条件：无条件：1 1 向右：向右：8 8所有条件分支：所有条件分支：6767向前：向前：6060向后：向后：8585（向后分支一般形成循环）（向后分支一般形成循环）8.3 流水线中的相关 华北电力大学计算机系109

56、130计算机组成与结构8.3 流水线中的相关 华北电力大学计算机系110130计算机组成与结构三、减少流水线分支损失的方法（种简单的静态方法，编译时预测）（种简单的静态方法，编译时预测）1. “冻结”或“排空”流水线 在流水线中停住或删除分支后的指令，在流水线中停住或删除分支后的指令，直到知道转移目标地址。直到知道转移目标地址。 优点：优点：简单。简单。2预测分支失败 流水线继续照常流动，就像没发生什么似的。流水线继续照常流动，就像没发生什么似的。8.3 流水线中的相关 华北电力大学计算机系111130计算机组成与结构 在知道分支结果之前，分支指令后的指令不在知道分支结果之前，分支指令后的指令

57、不 能改变机器状态，或者改变了之后能够回退。能改变机器状态，或者改变了之后能够回退。 若分支失败，则照常执行；否则，从转移目若分支失败，则照常执行；否则，从转移目 标处开始取指令执行。标处开始取指令执行。 DLXDLX流水线的处理过程流水线的处理过程8.3 流水线中的相关 华北电力大学计算机系113130计算机组成与结构3. 3. 预测分支成功预测分支成功 假设分支转移成功，并开始从分支目标地址假设分支转移成功，并开始从分支目标地址 处取指令执行。处取指令执行。 起作用的前题：先知道分支目标地址，后知起作用的前题：先知道分支目标地址，后知 道分支是否成功。道分支是否成功。 对对DLXDLX流水

58、线没有任何好处。流水线没有任何好处。8.3 流水线中的相关 华北电力大学计算机系114130计算机组成与结构4. 延迟分支 (delayed branch)(delayed branch) (1)(1) 基本概念基本概念 把分支开销为把分支开销为n n 的分支指令看成是延迟长的分支指令看成是延迟长 度为度为n n 的分支指令，其后紧跟有的分支指令，其后紧跟有n n 个延迟槽。个延迟槽。 流水线遇到分支指令时，按正常方式处理，顺流水线遇到分支指令时，按正常方式处理，顺 带执行延迟槽中的指令，从而减少分支开销。带执行延迟槽中的指令，从而减少分支开销。 延迟分支以及指令的执行顺序延迟分支以及指令的执

59、行顺序 8.3 流水线中的相关 华北电力大学计算机系116130计算机组成与结构(2)(2) 具有一个分支延迟槽的具有一个分支延迟槽的DLXDLX流水线的流水线的执行过程执行过程分支延迟槽中的指令分支延迟槽中的指令“掩盖掩盖”了流水线原来了流水线原来 必需插入的暂停周期。必需插入的暂停周期。8.3 流水线中的相关 华北电力大学计算机系117211延迟分支指令延迟分支指令(i+1) 指令指令(i+2) 指令指令(i+3) 指令指令(i+4)延迟分支指令延迟分支指令(i+1) 华北电力大学计算机系118130计算机组成与结构8.4 流水线的调度8.4.1 线性流水线的调度1. 静态调度 在指令执行

60、之前，利用软件的手段生成适在指令执行之前，利用软件的手段生成适合流水线工作特点、尽可能减少指令执行过程合流水线工作特点、尽可能减少指令执行过程相关性的机器代码，并对代码优化的调度方法。相关性的机器代码，并对代码优化的调度方法。 优化延迟转移技术优化延迟转移技术 展开循环体后调度方法展开循环体后调度方法第三章 流水线技术 华北电力大学计算机系119130计算机组成与结构2. 动态调度 在程序执行过程中，由硬件重新安排指令的执行顺在程序执行过程中，由硬件重新安排指令的执行顺序，以减少流水线停顿的方法。序，以减少流水线停顿的方法。 CDC记分牌法记分牌法 Tomasulo动态指令调度算法动态指令调度