计算机体系结构：第3章 流水线技术

《计算机体系结构：第3章 流水线技术》由会员分享，可在线阅读，更多相关《计算机体系结构：第3章 流水线技术（162页珍藏版）》请在金锄头文库上搜索。

1、1 1/157/157第3章 流水线技术2 2/157/1573.1流水线的基本概念3.2流水线的性能指标3.3 非线性流水线的调度3.4流水线的相关与冲突 3.5流水线的实现3 3/157/1573加快计算机语言的解释速度的方法1.选用更高速的硬件、用更好的运算方法、提高指选用更高速的硬件、用更好的运算方法、提高指令内各微操作的并行程度、减少解释过程所需的令内各微操作的并行程度、减少解释过程所需的拍数等措施。拍数等措施。2.采用同时解释两条、多条以至整段程序的控制方采用同时解释两条、多条以至整段程序的控制方式。式。重叠和流水是其中常用的控制方式重叠和流水是其中常用的控制方式。本章主。本章主要

2、讲述这两种方式的基本原理、实现中要解决的要讲述这两种方式的基本原理、实现中要解决的主要问题和办法，以及性能分析。主要问题和办法，以及性能分析。4 4/157/1574时间重叠的基本原理时间重叠的基本原理1.张三，李四，王五，赵六每人要洗一包衣服。张三，李四，王五，赵六每人要洗一包衣服。2.洗衣服的过程包括：洗衣服的过程包括：用洗衣机用洗衣机30分钟分钟烘干机烘干机30分钟分钟熨烫熨烫30分钟分钟把衣服打包需把衣服打包需30分钟分钟5 5/157/1575串行洗衣店串行洗衣店1.串行洗衣店需要8个小时完成4个工作量2.如果他们采用时间重叠技术呢？6 6/157/1576流水化的洗衣店、尽可能早的

3、开始工作流水化的洗衣店、尽可能早的开始工作1.流水化洗衣店3.5个小时完成4个工作量7 7/157/15771 流水线的基本概念1.流水线名词来源2.流水线技术内涵3.流水线描述图示工业装配流水线工艺将一个重复的处理过程分解成若干个字处理过程，每个子过程可以与其他的子过程同时处理。流水线的关键问题：1、任务分解2、瓶颈问题-每个子功能部件工作时间相同3、速度-吞吐率取决于子任务稳定添加速度比较：一条指令的执行时间流水执行的指令时间8 8/157/1571.工业生产流水线 下面通过一个例子来说明流水线的好处:两种方案两种方案的工作过程对比流水线生产过程的抽象描述这种流水工作方式的主要特点3.1

4、流水线的基本概念3.1.1 什么是流水线9 9/157/1573.1 流水线的基本概念2.流水线技术把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其它的子过程并行进行。3.流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。1010/157/1573.1 流水线的基本概念4.指令流水线把指令的解释过程分解为分析和执行两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。理想情况：速度提高一倍4段指令流水线 1111/157/1573.

5、1 流水线的基本概念5.浮点加法流水线把流水线技术应用于运算的执行过程，就形成了 运算操作流水线，也称为部件级流水线。把浮点加法的全过程分解为求阶差、对阶、尾数 相加、规格化四个子过程。 理想情况：速度提高3倍6.时空图时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。 浮点加法流水线的时空图1313/157/1573.1 流水线的基本概念7.流水技术的特点流水线把一个处理过程分解为若干个子过程（段），每个子过程由一个专门的功能部件来实现。流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。 时间最长的段将成为时间最长的段将成为流水线

6、的瓶颈。流水线的瓶颈。流水线每一个段的后面都要有一个缓冲寄存器（锁存器），称为流水寄存器。q作用：作用：在相邻的两段之间传送数据，以保证提供后在相邻的两段之间传送数据，以保证提供后 面要用到的信息，并把各段的处理工作相互隔离。面要用到的信息，并把各段的处理工作相互隔离。1414/157/1573.1 流水线的基本概念流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。 流水线需要有通过时间和排空时间。q通过时间：通过时间：第一个任务从进入流水线到流出结果第一个任务从进入流水线到流出结果 所需的时间。所需的时间。q排空时间：排空时间：最后一个任务从进入流水线到

7、流出结最后一个任务从进入流水线到流出结 果所需的时间。果所需的时间。1515/157/1573.1 流水线的基本概念1.部件级、处理机级及处理机间流水线（按照流水技术用于计算机系统的等级不同）（按照流水技术用于计算机系统的等级不同）部件级流水线（运算操作流水线）：把处理机中的部件分段，再把这些分段相互连接起来，使得各种类型的运算操作能够按流水方式进行。处理机级流水线（指令流水线）：把指令的执行过程按照流水方式处理。把一条指令的执行过程3.1.2 流水线的分类从不同的角度和观点，把流水线分成多种不同的种类。1616/157/1573.1 流水线的基本概念 分解为若干个子过程，每个子过程在独立的功

8、能 部件中执行。 系统级流水线（宏流水线）：把多台处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。 动画解析1717/157/1573.1 流水线的基本概念2.单功能流水线与多功能流水线 （按照流水线所完成的功能来分类）（按照流水线所完成的功能来分类）单功能流水线：只能完成一种固定功能的流水线。多功能流水线：流水线的各段可以进行不同的 连接，以实现不同的功能。例：例： ASCASC的多功能流水线的多功能流水线1919/157/1573.1 流水线的基本概念3.静态流水线与动态流水线（按照同一时间内各段之间的连接方式对多功能流水线作（按照同一时间内各段之间的连接方式对

9、多功能流水线作进一步的分类）进一步的分类）静态流水线：在同一时间内，多功能流水线中的 各段只能按同一种功能的连接方式工作。q对于静态流水线来说，只有当输入的是一串相同的对于静态流水线来说，只有当输入的是一串相同的 运算任务时，流水的效率才能得到充分的发挥。运算任务时，流水的效率才能得到充分的发挥。例如：例如：ASCASC的的8 8段流水线段流水线2020/157/1573.2 流水线的基本概念动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。 动画q优点优点 灵活，能够提高流水线各段的使用率，从而灵活，能够提高流水线各段的使用率，从而 提高处理速度。提高处

10、理速度。q缺点缺点 控制复杂。控制复杂。静、动态流水线时空图的对比2222/157/1573.1 流水线的基本概念4.线性流水线与非线性流水线（按照流水线中是否有反馈回路来进行分类）（按照流水线中是否有反馈回路来进行分类）线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。非线性流水线：流水线中除了有串行的连接外，还有反馈回路。 （举例）非线性流水线的调度问题q确定什么时候向流水线引进新的任务，才能使该任务不确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突会与先前进入流水线的任务发生冲突争用流水段。争用流水段。 23

11、23/157/1573.1 流水线的基本概念2424/157/1573.1 流水线的基本概念5.顺序流水线与乱序流水线（根据任务流入和流出的顺序是否相同来进行分类（根据任务流入和流出的顺序是否相同来进行分类）顺序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序完全相同。每一个任务在流 水线的各段中是一个跟着一个顺序流动的。乱序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序可以不同，允许后进入流水 线的任务先完成（从输出端流出）。 也称为无序流水线、错序流水线、异步流水线也称为无序流水线、错序流水线、异步流水线2525/157/1573.1 流水线的基本概念6.标量处理机与

12、向量流水处理机 把指令执行部件中采用了流水线的处理机称为流 水线处理机。标量处理机：处理机不具有向量数据表示和向量 指令，仅对标量数据进行流水处理。向量流水处理机：具有向量数据表示和向量指令 的处理机。 向量数据表示和流水技术的结合。向量数据表示和流水技术的结合。2626/157/157 吞吐率：在单位时间内流水线所完成的任务数量或输 出结果的数量。3.2 流水线的性能指标3.2.1 吞吐率n：任务数Tk：处理完成n个任务所用的时间2727/157/1573.2 流水线的性能指标1.各段时间均相等的流水线各段时间均相等的流水线时空图2828/157/1573.2 流水线的性能指标流水线完成n个

13、连续任务所需要的总时间为：（假设一条（假设一条k k段段线性流水线）线性流水线）Tkkt(n1)t(kn1)t 流水线的实际吞吐率最大吞吐率2929/157/1573.2 流水线的性能指标最大吞吐率与实际吞吐率的关系 q流水线的实际吞吐率小于最大吞吐率，它除了与每流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数个段的时间有关外，还与流水线的段数k k以及输入到以及输入到流水线中的任务数流水线中的任务数n n等有关。等有关。q只有当只有当nknk时，才有时，才有TPTPTPTPmaxmax。 3030/157/1573.2 流水线的性能指标2.各段时间不完全相等的流

14、水线 各段时间不等的流水线及其时空图 举例1（时空图）q一条一条4 4段段的流水线的流水线qS1S1，S3S3，S4S4各段的时间：各段的时间：ttqS2S2的时间：的时间：3t 3t （瓶颈段）瓶颈段）流水线中这种时间最长的段称为流水线的瓶颈段。 3131/157/1573.2 流水线的性能指标举例2：一条5段的流水线qS S1 1，S S2 2，S S3 3，S S5 5各段的时间：各段的时间：ttqS S4 4的时间：的时间：3t 3t （瓶颈段）瓶颈段）3333/157/1573.2 流水线的性能指标各段时间不等的流水线的实际吞吐率为：（ tti i为第为第i i段的时间，共有段的时间

15、，共有k k个段个段 ）流水线的最大吞吐率为： 3434/157/1573.2 流水线的性能指标对前面举例2中的5段流水线最大吞吐率为： 3535/157/1573.2 流水线的性能指标3.解决流水线瓶颈问题的常用方法 举例细分瓶颈段 例如：例如：对前面的对前面的5 5段段流水线流水线把瓶颈段把瓶颈段S S4 4细分为细分为3 3个子流水线段：个子流水线段：S S4-14-1，S S4-24-2，S S4-34-3改进后的流水线的吞吐率改进后的流水线的吞吐率 ：3636/157/1573.2 流水线的性能指标重复设置瓶颈段q举例：举例：时时- -空图空图q缺点：缺点：控制逻辑比较复杂，所需的硬

16、件增加了。控制逻辑比较复杂，所需的硬件增加了。例如：例如：对前面的对前面的5 5段流水线段流水线 重复设置瓶颈段重复设置瓶颈段S S4 4：S S4a4a，S S4b4b，S S4c4c3737/157/1573.2 流水线的性能指标重复设置瓶颈段后的时空图重复设置瓶颈段后的时空图3838/157/1573.2 流水线的性能指标加速比：完成同样一批任务，不使用流水线所用的时间 与使用流水线所用的时间之比。假设：不使用流水线（即顺序执行）所用的时假设：不使用流水线（即顺序执行）所用的时间为间为T Ts s，使用流水线后所用的时间为，使用流水线后所用的时间为T Tk k，则该流，则该流水线的加速比

17、为：水线的加速比为：3.2.2 流水线的加速比3939/157/1573.2 流水线的性能指标1.流水线各段时间相等（都是t）一条k段流水线完成n个连续任务 所需要的时间为：所需要的时间为： Tk = (kn1)t顺序执行n个任务 所需要的时间：所需要的时间： Ts= nkt （解释解释）流水线的实际加速比为：4040/157/1573.2 流水线的性能指标最大加速比当当nknk时，时，S S k k思考：思考：流水线的段数愈多愈好？流水线的段数愈多愈好？ 4141/157/1573.2 流水线的性能指标2.流水线的各段时间不完全相等时一条k段流水线完成n个连续任务的实际加速比为： 4242/

18、157/1573.2 流水线的性能指标 流水线的效率：流水线中的设备实际使用时间与整个运行时间的比值，即流水线设备的利用率。 由于流水线有通过时间和排空时间，所以在连续由于流水线有通过时间和排空时间，所以在连续完成完成n n个个任务的时间内，各段并不是满负荷地工作。任务的时间内，各段并不是满负荷地工作。1.各段时间相等各段的效率ei相同 (解释)3.2.3 流水线的效率4343/157/1573.2 流水线的性能指标整条流水线的效率为： 可以写成： 最高效率为： 当当nknk时，时，E1E1。 4444/157/1573.2 流水线的性能指标当流水线各段时间相等时，流水线的效率与吞吐率 成正比

19、。 E=TPt 2.流水线的效率是流水线的实际加速比S与它的最大加速 比k的比值。 当当E=1E=1时，时，S=kS=k，实际加速比达到最大。，实际加速比达到最大。4545/157/1573.2 流水线的性能指标3.从时空图上看，效率就是n个任务占用的时空面积和 k个段总的时空面积之比。当各段时间不相等时：4646/157/1573.2 流水线的性能指标 例例3.13.1 设在下图所示的静态流水线上计算：设在下图所示的静态流水线上计算： 流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，试计算其吞吐率、加速比和效率。试计算其吞吐

20、率、加速比和效率。3.2.4 流水线的性能分析举例( (每段的时间都为每段的时间都为t t) )4747/157/1573.2 流水线的性能指标解解：（1 1）选择适合于流水线工作的算法选择适合于流水线工作的算法q先计算先计算A A1 1+B+B1 1、A A2 2+B+B2 2、A A3 3+B+B3 3和和A A4 4+B+B4 4；q再计算再计算(A(A1 1+B+B1 1) )(A(A2 2+B+B2 2) )和和(A(A3 3+B+B3 3) )(A(A4 4+B+B4 4) )；q然后求总的乘积结果。然后求总的乘积结果。（2 2）画出时空图）画出时空图 4949/157/1573.

21、2 流水线的性能指标p在在1818个个t t时间中，给出了时间中，给出了7 7个个结果。吞吐率为：结果。吞吐率为： p 不用流水线，由于一次求和需不用流水线，由于一次求和需66t t，一次求积需一次求积需44t t， 则产生上述则产生上述7 7个结果共需个结果共需（4 46+36+34 4）t t = 36 = 36t t 加速比为：加速比为： （3 3）计算性能）计算性能5050/157/1573.2 流水线的性能指标p 流水线的效率流水线的效率 可以看出，在求解此问题时，该流水线的效率不高。 (原因)5151/157/1573.2 流水线的性能指标主要原因q多功能流水线在做某一种运算时，总

22、有一些段是空多功能流水线在做某一种运算时，总有一些段是空闲的；闲的；q静态流水线在进行功能切换时，要等前一种运算全静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算；部流出流水线后才能进行后面的运算；q运算之间存在关联，后面有些运算要用到前面运算运算之间存在关联，后面有些运算要用到前面运算的结果；的结果；q流水线的工作过程有建立与排空部分。流水线的工作过程有建立与排空部分。 5252/157/1573.2 流水线的性能指标 例例3.2 3.2 有一条动态多功能流水线由有一条动态多功能流水线由5 5段组成，加法用段组成，加法用1 1、3 3、4 4、5 5段，乘法用段，

23、乘法用1 1、2 2、5 5段，第段，第4 4段的时间为段的时间为2t2t，其余各段时间均，其余各段时间均为为t t，而且流水线的输出可以直接返回输入端或暂存于相应的，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算流水寄存器中。若在该流水线上计算: : 试计算其吞吐率、加速比和效率。试计算其吞吐率、加速比和效率。5353/157/1573.2 流水线的性能指标解解: : (1) (1) 选择适合于流水线工作的算法选择适合于流水线工作的算法p应先计算应先计算A A1 1B B1 1、A A2 2B B2 2、A A3 3B B3 3和和A A4 4B B4 4；

24、p再计算再计算(A(A1 1B B1 1) )(A(A2 2B B2 2) ) (A (A3 3B B3 3) )(A(A4 4B B4 4) )；p然后求总的累加结果。然后求总的累加结果。(2) (2) 画出时空图画出时空图(3) (3) 计算性能计算性能5454/157/1573.2 流水线的性能指标5555/157/1573.2 流水线的性能指标 下面我们再看一个例子：下面我们再看一个例子： 例例 在在静态流水线静态流水线上计算上计算: : 求：吞吐率，加速比，效率。求：吞吐率，加速比，效率。解：解： (1) (1) 确定适合于流水处理的确定适合于流水处理的计算过程计算过程 (2) (2

25、) 画时空图画时空图 (3) (3) 计算性能计算性能 吞吐率吞吐率 TPTP7 7(20(20tt) ) 加速比加速比 S S(34(34tt) )(20(20tt) )1.71.7 效率效率 E E(4(44 43 36)6)(8(820)20)0.210.215656/157/1573.2 流水线的性能指标5757/157/1573.2 流水线的性能指标可以看出，在求解此问题时，该流水线的效率不高。 动态流水线的时空图 举例举例 : 这样行不行？ 正确答案5858/157/1573.2 流水线的性能指标1.瓶颈问题理想情况下，流水线在工作时，其中的任务是同步地每一个时钟周期往前流动一段。

26、当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间。在设计流水线时，要尽可能使各段时间相等。2.流水线的额外开销p流水寄存器延迟流水寄存器延迟p时钟偏移开销时钟偏移开销3.2.5 流水线设计中的若干问题5959/157/1573.2 流水线的性能指标流水寄存器需要建立时间和传输延迟q建立时间：建立时间：在触发写操作的时钟信号到达之前，寄在触发写操作的时钟信号到达之前，寄 存器输入必须保持稳定的时间。存器输入必须保持稳定的时间。q传输延迟：传输延迟：时钟信号到达后到寄存器输出可用的时时钟信号到达后到寄存器输出可用的时 间。间。时钟偏移开销q流水线中，时钟到达各流水寄存器的最大差值时间。流

27、水线中，时钟到达各流水寄存器的最大差值时间。（时钟到达各流水寄存器的时间不是完全相同）（时钟到达各流水寄存器的时间不是完全相同）6060/157/1573.2 流水线的性能指标几个问题q流水线并不能减少（而且一般是增加）单条指令的流水线并不能减少（而且一般是增加）单条指令的执行时间，但却能提高吞吐率。执行时间，但却能提高吞吐率。q增加流水线的深度（段数）可以提高流水线的性能。增加流水线的深度（段数）可以提高流水线的性能。q流水线的深度受限于流水线的额外开销。流水线的深度受限于流水线的额外开销。q当时钟周期小到与额外开销相同时，流水已没意义。当时钟周期小到与额外开销相同时，流水已没意义。因为这时

28、在每一个时钟周期中已没有时间来做有用因为这时在每一个时钟周期中已没有时间来做有用的工作。的工作。3.冲突问题 流水线设计中要解决的重要问题之一。 6161/157/157在非线性流水线中，存在反馈回路，当一个任务在流水线中流过时，可能要多次经过某些段。 流水线调度要解决的问题： 应按什么样的时间间隔向流水线输入新任务，才能既应按什么样的时间间隔向流水线输入新任务，才能既不发生功能段使用冲突，又能使流水线有较高的吞吐率和不发生功能段使用冲突，又能使流水线有较高的吞吐率和效率？效率？3.3 非线性流水线的调度6262/157/1573.3 非线性流水线的调度向一条非线性流水线的输入端连续输入两个任

29、务之间的时间间隔称为非线性流水线的启动距离。会引起非线性流水线功能段使用冲突的启动距离则称为禁用启动距离。启动距离和禁用启动距离一般都用时钟周期数来表示，是一个正整数。预约表 q横向（向右）：时间（一般用时钟周期表示）横向（向右）：时间（一般用时钟周期表示）q纵向（向下）：流水线的段纵向（向下）：流水线的段3.3.1 单功能非线性流水线的最优调度例：一个例：一个5功能段非线性流水线预约表功能段非线性流水线预约表 q如果在第如果在第n个时钟周期使用第个时钟周期使用第k段，则在第段，则在第k行和第行和第n列的交叉处的格子里有一个列的交叉处的格子里有一个。q如果在第如果在第k行和第行和第n列的交叉处

30、的格子里有一个列的交叉处的格子里有一个，则，则表示在第表示在第n个时钟周期要使用第个时钟周期要使用第k段。段。 6464/157/1573.3 非线性流水线的调度1.根据预约表写出禁止表F禁止表F：一个由禁用启动距离构成的集合。 具体方法 对于预约表的每一行的任何一对对于预约表的每一行的任何一对，用它们所在，用它们所在的列号相减（大的减小的），列出各种可能的差值，的列号相减（大的减小的），列出各种可能的差值，然后删除相同的，剩下的就是禁止表的元素。然后删除相同的，剩下的就是禁止表的元素。 在上例中q第一行的差值只有一个：第一行的差值只有一个：8；q第二行的差值有第二行的差值有3个：个：1，5，

31、6；q第第3行只有一个行只有一个，没有差值；，没有差值；q第第4和第和第5行的差值都只有一个：行的差值都只有一个：1； 其禁止表是：其禁止表是：F= 1，5，6，8 6565/157/1573.3 非线性流水线的调度2.根据禁止表F写出初始冲突向量C0（进行从一个集合到一个二进制位串的变换（进行从一个集合到一个二进制位串的变换 ）冲突向量C：一个N位的二进制位串。设C0=（cNcN-1cic2c1），则：qci=0 ：允许间隔：允许间隔i个时钟周期后送入后续任务个时钟周期后送入后续任务qci=1 ：不允许间隔：不允许间隔i个时钟周期后送入后续任务个时钟周期后送入后续任务 对于上面的例子 F=

32、1，5，6，8 C0=（10110001） 6666/157/1573.3 非线性流水线的调度3.根据初始冲突向量C0画出状态转换图当第一个任务流入流水线后，初始冲突向量C0决定了下一个任务需间隔多少个时钟周期才可以流入。在第二个任务流入后，新的冲突向量是怎样的呢？ q假设第二个任务是在与第一个任务间隔假设第二个任务是在与第一个任务间隔j个时钟周期个时钟周期流入，这时，由于第一个任务已经在流水线中前进了流入，这时，由于第一个任务已经在流水线中前进了j个时钟周期，其相应的禁止表中各元素的值都应该个时钟周期，其相应的禁止表中各元素的值都应该减去减去j，并丢弃小于等于，并丢弃小于等于0的值。的值。q

33、对冲突向量来说，就是对冲突向量来说，就是逻辑右移逻辑右移j位位（左边补（左边补0）。）。 6767/157/1573.3 非线性流水线的调度q在冲突向量上，就是对它们的冲突向量进行在冲突向量上，就是对它们的冲突向量进行“或或”运运算算。 SHR(j)（C0）C0 其中其中:SHR(j)表示逻辑右移表示逻辑右移j位位 推广到更一般的情况假设假设: Ck：当前的冲突向量：当前的冲突向量 j: 允许的时间间隔允许的时间间隔则新的冲突向量为：则新的冲突向量为： SHR(j)（Ck）C0对于所有允许的时间间隔都按上述步骤求出其新的冲突向量，并且把新的冲突向量作为当前冲突向量，反复使用上述步骤，直到不再产

34、生新的冲突向量为止。6868/157/1573.3 非线性流水线的调度从初始冲突向量C0出发，反复应用上述步骤，可以求得所有的冲突向量以及产生这些向量所对应的时间间隔。由此可以画出用冲突向量表示的流水线状态转移图。q有向弧有向弧：表示状态转移的方向：表示状态转移的方向q弧上的数字弧上的数字：表示引入后续任务（从而产生新的冲突：表示引入后续任务（从而产生新的冲突向量）所用的时间间隔（时钟周期数）向量）所用的时间间隔（时钟周期数）6969/157/1573.3 非线性流水线的调度对于上面的例子对于上面的例子（1 1） C C0 0= =（1011000110110001） 引入后续任务可用的时间间

35、隔为：引入后续任务可用的时间间隔为：2 2、3 3、4 4、7 7个时钟周期个时钟周期 如果采用如果采用2 2，则新的冲突向量为：，则新的冲突向量为： （0010110000101100）（1011000110110001）= = （1011110110111101） 如果采用如果采用3 3，则新的冲突向量为：，则新的冲突向量为： （0001011000010110）（1011000110110001）= = （1011011110110111） 如果采用如果采用4 4，则新的冲突向量为：，则新的冲突向量为： （0000101100001011）（1011000110110001）= = （1

36、011101110111011） 如果采用如果采用7 7，则新的冲突向量为：，则新的冲突向量为： （0000000100000001）（1011000110110001）= = （1011000110110001）（2 2）对于新向量）对于新向量（1011110110111101），其可用的时间间隔为，其可用的时间间隔为2 2个个和和7 7个个时钟时钟 周期。用类似上面的方法，可以求出其后续的冲突向量分别为周期。用类似上面的方法，可以求出其后续的冲突向量分别为 （1011110110111101）和和（1011000110110001）。（3 3）对于其他新向量，也照此处理。）对于其他新向量，

37、也照此处理。（4 4）在此基础上，画出状态转移示意图。）在此基础上，画出状态转移示意图。7171/157/1573.3 非线性流水线的调度4.根据状态转换图写出最优调度方案 根据流水线状态图，由初始状态出发，任何一个闭合回路即为一种调度方案。 列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其最小者即为最优调度方案。 上例中，各种调度方案及其平均间隔时间。 q最佳方案：最佳方案：（3，4） 平均间隔时间：平均间隔时间：3.5个时钟周期（吞吐率最高）个时钟周期（吞吐率最高） q方案（方案（4，3）的平均间隔时间也是）的平均间隔时间也是3.5 ，但它不是最，但它不是最佳方案，为什么？

38、佳方案，为什么？7272/157/1573.3 非线性流水线的调度调度策略 平均延迟拍数 (2,7)(2,2,7)(3,7)(3,4)(3,4,3,7)(3,4,7)(4,3,7)(4,7)（7） 4.53.6753.54.254.674.675.57 各种调度策略及平均延迟拍数各种调度策略及平均延迟拍数 7373/157/1573.3 非线性流水线的调度方案（3，4）是一种不等时间间隔的调度方案，与等间隔的调度方案相比，在控制上要复杂得多。为了简化控制，也可以采用等间隔时间的调度方案，但吞吐率和效率往往会下降不少。q在上述例子中，等时间间隔的方案只有一个：在上述例子中，等时间间隔的方案只有一

39、个：（7），其吞吐率下降了一半。其吞吐率下降了一半。7474/157/1573.3 非线性流水线的调度 以双功能（功能A和B）非线性流水线为例。 1.状态转移图中结点状态的表示由两个冲突向量构成的冲突矩阵，这两个冲突向量分别对应于下一个任务的功能是A类和B类的情况。2.初始结点有两个，分别对应于第一个任务是A类和B类的情况。 当第一个任务是A类时，冲突矩阵为M(0)A。当第一个任务是B类时，冲突矩阵为M(0)B。 3.3.2 多功能非线性流水线的调度7575/157/1573.3 非线性流水线的调度其中：qCpq（p,qA, B）表示的是：在一个）表示的是：在一个p类任务流入流类任务流入流水线

40、后，对后续水线后，对后续q类任务的冲突向量。类任务的冲突向量。 它们可以由预约表求得。它们可以由预约表求得。qCpq共有共有22=4个。个。q对于对于N功能流水线，这种冲突向量有功能流水线，这种冲突向量有N2个。个。7676/157/1573.3 非线性流水线的调度3.由下式求得后续状态的冲突矩阵 SHR(i)（Mk）Mr(0)其中：qMk：当前状态：当前状态qr：下一个流入任务的类型（：下一个流入任务的类型（A或或B）qi：当前状态允许的流入：当前状态允许的流入r型任务的时间间隔型任务的时间间隔qSHR(i)（Mk）：把当前状态中的各冲突向量逻辑右移：把当前状态中的各冲突向量逻辑右移i位位例

41、如：例如：SHR(3)（Mk）MA(0)表示的是：把当前状态表示的是：把当前状态Mk中中的各冲突向量逻辑右移的各冲突向量逻辑右移3位，再与初始矩阵位，再与初始矩阵MA(0)进行进行“或或”运算。运算。 4.举例说明双功能非线性流水线的最优调度7777/157/1573.3 非线性流水线的调度 例例3.3 有一条有一条3段双功能非线性流水线，实现的功能是段双功能非线性流水线，实现的功能是A和和B，其预约，其预约表分别如表分别如表表1和和表表2所示。各段的通过时间都是一个时钟周期。请找出该所示。各段的通过时间都是一个时钟周期。请找出该流水线单独处理流水线单独处理A类任务和单独处理类任务和单独处理B

42、类任务以及混合处理两类任务的最类任务以及混合处理两类任务的最优调度方案。优调度方案。 1 12 23 34 45 5S1S1S2S2S3S3时间时间段段 1 12 23 34 45 5S1S1S2S2S3S3时间时间段段表表1 A类对象预约表类对象预约表表表2 B类对象预约表类对象预约表7878/157/1573.3 非线性流水线的调度解：解：（1） 把两个预约表重叠起来，得到如表把两个预约表重叠起来，得到如表3所示的预约表。所示的预约表。 （2）由预约表求初始冲突向量和初始冲突矩阵）由预约表求初始冲突向量和初始冲突矩阵 1 12 23 34 45 5S1S1A AB BA AB BS2S2A

43、 AB BS3S3B BABABA A时间时间段段7979/157/1573.3 非线性流水线的调度qCAA：一个：一个A类任务流入流水线后，对下一个类任务流入流水线后，对下一个A类任务进入流水类任务进入流水线的时间间隔的限制。线的时间间隔的限制。 根据预约表表根据预约表表1可知，禁用时间间隔是可知，禁用时间间隔是2和和3，故禁止表为：，故禁止表为：2，3，所以，所以CAA=（0110）。qCBB：一个：一个B类任务流入流水线后，对下一个类任务流入流水线后，对下一个B类任务进入流水类任务进入流水线的时间间隔的限制。线的时间间隔的限制。 根据预约表表根据预约表表2可知，禁用时间间隔是可知，禁用时

44、间间隔是2和和3，所以，所以CBB=（0110）。）。qCAB：一个：一个A类任务流入流水线后，对下一个类任务流入流水线后，对下一个B类任务进入流水类任务进入流水线的时间间隔的限制。根据预约表表线的时间间隔的限制。根据预约表表3可知：可知：n为了避免在为了避免在S1发生冲突，禁用时间间隔是：发生冲突，禁用时间间隔是：4-2=2 8080/157/1573.3 非线性流水线的调度n在在S2，不会发生冲突，这是因为根据表，不会发生冲突，这是因为根据表3，A类任务先于类任务先于B类任务通过类任务通过S2，而现在的实际情况又是，而现在的实际情况又是A类任务先于类任务先于B类任类任务流入流水线；务流入流

45、水线；n为了避免在为了避免在S3发生冲突，禁用时间间隔是：发生冲突，禁用时间间隔是： 3-1=2，5-1=4，5-3=2n综合起来，有：综合起来，有：CAB=（1010） qCBA表示一个表示一个B类任务流入流水线后，对下一个类任务流入流水线后，对下一个A类任务进入流类任务进入流水线的时间间隔的限制。根据预约表表水线的时间间隔的限制。根据预约表表3可知：可知：n为了避免在为了避免在S1发生冲突，禁用时间间隔有：发生冲突，禁用时间间隔有： 2-1=1，5-1=4，5-4=1n为了避免在为了避免在S2发生冲突，禁用时间间隔是：发生冲突，禁用时间间隔是：4-2=28181/157/1573.3 非线

46、性流水线的调度n在在S3，不会发生冲突，这是因为根据表，不会发生冲突，这是因为根据表3，B类类任务先于任务先于A类任务通过类任务通过S3，或者同时通过，或者同时通过S3（第（第3个时钟周期），而现在的实际情况又是个时钟周期），而现在的实际情况又是B类任类任务先于务先于A类任务流入流水线。类任务流入流水线。n综合起来，有：综合起来，有：CAB=（1011） 初始矩阵为：初始矩阵为： 8282/157/1573.3 非线性流水线的调度（3）由初始冲突矩阵画出状态图）由初始冲突矩阵画出状态图 如果第一个流入的任务是如果第一个流入的任务是A类，初始状态就是类，初始状态就是MA (0) ；如果；如果第一

47、个流入的任务是第一个流入的任务是B类，则初始状态是类，则初始状态是MB (0) 。 求所有后续状态的冲突矩阵：求所有后续状态的冲突矩阵： 例如：在流入一个例如：在流入一个A A类任务后，从类任务后，从C CAAAA= =（01100110）可知，可以隔可知，可以隔一一个个或或4 4个个时钟周期再流入一个时钟周期再流入一个A A类任务。类任务。 假设是前者，则把初始状态假设是前者，则把初始状态MA (0)中的各冲突向量同时中的各冲突向量同时右移右移一位一位（即进行（即进行SHRSHR(1)(1)操作），再与操作），再与MA (0)进行或运算，可以得到新进行或运算，可以得到新的冲突矩阵。根据该矩阵

48、的第一个冲突向量的冲突矩阵。根据该矩阵的第一个冲突向量（01110111）可知，只有可知，只有隔隔4 4个时钟周期流入一个个时钟周期流入一个A A类任务，才能不发生冲突。把冲突矩阵类任务，才能不发生冲突。把冲突矩阵中的各冲突向量同时右移中的各冲突向量同时右移4 4位（即进行位（即进行SHRSHR(4)(4)操作），再与操作），再与MA (0)进行按位或运算，可以得到新的冲突矩阵。进行按位或运算，可以得到新的冲突矩阵。 8383/157/1573.3 非线性流水线的调度 再如，在流入一个再如，在流入一个A类任务后，从类任务后，从CAB=（1010）可知，可以可知，可以隔隔一个一个或或3个个时钟周

49、期再流入一个时钟周期再流入一个B类任务。假设是前者，则把类任务。假设是前者，则把初始状态初始状态MA (0)中的各冲突向量同时中的各冲突向量同时右移一位右移一位（即进行（即进行SHR(1)操操作），再与作），再与MB (0)进行或运算，可以得到新的冲突矩阵。进行或运算，可以得到新的冲突矩阵。 据此可知，允许的流入为：或者是隔据此可知，允许的流入为：或者是隔3个时钟周期流入一个个时钟周期流入一个A类任务，或者是隔类任务，或者是隔4个时钟周期流入一个个时钟周期流入一个B类任务。按类似与上类任务。按类似与上述类似的方法，又可以得到新的冲突矩阵。述类似的方法，又可以得到新的冲突矩阵。 求出所有可能的状

50、态后，就可以画出状态图。求出所有可能的状态后，就可以画出状态图。 弧线上的标记弧线上的标记“r.i”表示：隔表示：隔i个时钟周期流入个时钟周期流入r类的任务。类的任务。 8484/157/1573.3 非线性流水线的调度双功能非线性流水线的状态图双功能非线性流水线的状态图 8585/157/1573.3 非线性流水线的调度（4）由状态图得出最优调度方案）由状态图得出最优调度方案 从状态图可以找出各种情况下的从状态图可以找出各种情况下的最优调度方案最优调度方案： 只流入只流入A类任务的最优调度方案是：类任务的最优调度方案是：（A.1，A.4） 流入流入B类任务的最优调度方案是：类任务的最优调度方

51、案是：（B.1，B.4） 混合流入混合流入A、B两类任务的最优调度方案是：两类任务的最优调度方案是：（B.1，A.3，A.4）8686/157/157介绍一条经典的5段RISC流水线 首先讨论在非流水情况下是如何实现的1.一条指令的执行过程分为以下5个周期：取指令周期（IF）q以程序计数器以程序计数器PC中的内容作为地址，从存储器中取中的内容作为地址，从存储器中取出指令并放入指令寄存器出指令并放入指令寄存器IR；q同时同时PC值加值加4（假设每条指令占（假设每条指令占4个字节），指向顺个字节），指向顺序的下一条指令。序的下一条指令。3.4 流水线的相关与冲突3.4.1 一条经典的5段流水线87

52、87/157/1573.4 流水线的相关与冲突指令译码/读寄存器周期（ID） 对指令进行译码，并用对指令进行译码，并用IR中的寄存器地址去访问中的寄存器地址去访问通用寄存器组，读出所需的操作数。通用寄存器组，读出所需的操作数。 执行/有效地址计算周期（EX） 不同指令所进行的操作不同：qload和和store指令指令：ALU把指令中所指定的寄存器的内把指令中所指定的寄存器的内容与偏移量相加，形成访存有效地址。容与偏移量相加，形成访存有效地址。q寄存器寄存器寄存器寄存器ALU指令指令：ALU按照操作码指定的按照操作码指定的操作对从通用寄存器组中读出的数据进行运算。操作对从通用寄存器组中读出的数据

53、进行运算。8888/157/1573.4 流水线的相关与冲突q寄存器立即数寄存器立即数ALU指令指令：ALU按照操作码指定的操作按照操作码指定的操作对从通用寄存器组中读出的操作数和指令中给出的立即对从通用寄存器组中读出的操作数和指令中给出的立即数进行运算。数进行运算。q分支指令分支指令：ALU把指令中给出的偏移量与把指令中给出的偏移量与PC值相加，形值相加，形成转移目标的地址。同时，对在前一个周期读出的操作成转移目标的地址。同时，对在前一个周期读出的操作数进行判断，确定分支是否成功。数进行判断，确定分支是否成功。存储器访问分支完成周期（MEM） 该周期处理的指令只有load、store和分支指

54、令。 其它类型的指令在此周期不做任何操作。8989/157/1573.4 流水线的相关与冲突qloadload和和storestore指令指令loadload指令：指令：用上一个周期计算出的有效地址从存储器中用上一个周期计算出的有效地址从存储器中 读出相应的数据；读出相应的数据；storestore指令：指令：把指定的数据写入这个有效地址所指出的存把指定的数据写入这个有效地址所指出的存 储器单元。储器单元。q分支指令分支指令 分支分支“成功成功”，就把转移目标地址送入，就把转移目标地址送入PCPC。 分支指令执行完成。分支指令执行完成。9090/157/1573.4 流水线的相关与冲突写回周期

55、（WB） ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。 ALUALU运算指令：运算指令：结果数据来自结果数据来自ALUALU。 loadload指令：指令：结果数据来自存储器。结果数据来自存储器。 在这个实现方案中：p分支指令需要分支指令需要4 4个时钟个时钟周期（如果把分支指令的执行周期（如果把分支指令的执行 提前到提前到IDID周期，则只需要周期，则只需要2 2个个周期）；周期）；pstorestore指令需要指令需要4 4个个周期；周期；p其它指令需要其它指令需要5 5个个周期才能完成。周期才能完成。2.将上述实现方案修改为流水线实现一条经典的5段流水线 q每一个周

56、期作为一个流水段；每一个周期作为一个流水段；q在各段之间加上锁存器（流水寄存器）。在各段之间加上锁存器（流水寄存器）。 9292/157/157 3.采用流水线方式实现时，应解决好以下几个问题：要保证不会在同一时钟周期要求同一个功能段做 两件不同的工作。例如：不能要求例如：不能要求ALUALU同时做有效地址计算和算术运算。同时做有效地址计算和算术运算。避免IF段的访存（取指令）与MEM段的访存（读/写数据）发生冲突。q可以采用分离的指令存储器和数据存储器；可以采用分离的指令存储器和数据存储器；q一般采用分离的指令一般采用分离的指令CacheCache和数据和数据CacheCache。ID段和W

57、B段都要访问同一寄存器文件。 IDID段：读段：读WBWB段：写段：写3.4 流水线的相关与冲突9393/157/1573.4 流水线的相关与冲突如何解决对同一寄存器的访问冲突？如何解决对同一寄存器的访问冲突？ 把写操作安排在时钟周期的前半拍完成，把读操作把写操作安排在时钟周期的前半拍完成，把读操作安排在后半拍完成。安排在后半拍完成。考虑PC的问题q流水线为了能够每个时钟周期启动一条新的指令，流水线为了能够每个时钟周期启动一条新的指令，就必须在每个时钟周期进行就必须在每个时钟周期进行PCPC值的加值的加4 4操作，并保留操作，并保留新的新的PCPC值。这种操作值。这种操作必须在必须在IFIF段

58、完成，段完成，以便为取下以便为取下一条指令做好准备。一条指令做好准备。 （需设置一个专门的加法器）（需设置一个专门的加法器）q但分支指令也可能改变但分支指令也可能改变P PC C的值，而且是在的值，而且是在MEMMEM段段进行，进行，这会导致冲突。这会导致冲突。请考虑一下，如何处理分支指令？请考虑一下，如何处理分支指令？9494/157/1573.4 流水线的相关与冲突4.5段流水线的两种描述方式q第一种描述第一种描述（类似于时空图）（类似于时空图）第二种描述（按时间错开的数据通路序列）9696/157/1573.4 流水线的相关与冲突相关：两条指令之间存在某种依赖关系。 如果两条指令相关，则

59、它们就有可能不能在流如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。水线中重叠执行或者只能部分重叠执行。相关有3种类型q数据相关（也称真数据相关）数据相关（也称真数据相关）q名相关名相关q控制相关控制相关3.4.2 相关与流水线冲突3.4.2.1 相关9797/157/1573.4 流水线的相关与冲突1.数据相关 对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。 q指令指令j j使用指令使用指令i i产生的结果；产生的结果；q指令指令j j与指令与指令k k数据相关，而指令数据相关，而指令k k又与指令又与指令i i

60、数据相关。数据相关。数据相关具有传递性。 数据相关反映了数据的流动关系，即如何从其产 生者流动到其消费者。 9898/157/1573.4 流水线的相关与冲突 例如：例如：下面这一段代码存在数据相关。下面这一段代码存在数据相关。LoopLoop： L.D L.D F0F0，0 0（R1R1）/ F0/ F0为数组元素为数组元素 ADD.D ADD.D F4F4，F0F0，F2F2/ / 加上加上F2F2中的值中的值 S.D S.D F4F4，0 0（R1R1）/ / 保存结果保存结果 DADDIU DADDIU R1R1，R1R1，8 8/ / 数组指针递减数组指针递减8 8个字节个字节 BN

61、E BNE R1R1，R2R2，LoopLoop/ / 如果如果R1R2R1R2，则分支，则分支 9999/157/1573.4 流水线的相关与冲突当数据的流动是经过寄存器时，相关的检测比较 直观和容易。当数据的流动是经过存储器时，检测比较复杂。q相同形式的地址其有效地址未必相同；相同形式的地址其有效地址未必相同；q形式不同的地址其有效地址却可能相同。形式不同的地址其有效地址却可能相同。2.名相关名：指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。100100/157/1573.4 流水线的相关与冲突指令j与指令i之间的名相

62、关有两种：q反相关：反相关：如果指令如果指令j j写的名与指令写的名与指令i i读的名相同，则读的名相同，则 称指令称指令i i和和j j发生了反相关。发生了反相关。 指令指令j j写的名指令写的名指令i i读的名读的名q输出相关：输出相关：如果指令如果指令j j和指令和指令i i写相同的名，则称指写相同的名，则称指 令令i i和和j j发生了输出相关。发生了输出相关。 指令指令j j写的名指令写的名指令i i写的名写的名101101/157/1573.4 流水线的相关与冲突名相关的两条指令之间并没有数据的传送。如果一条指令中的名改变了，并不影响另外一条指令的执行。换名技术q换名技术：换名技术

63、：通过改变指令中操作数的名来消除名相关。通过改变指令中操作数的名来消除名相关。q对于寄存器操作数进行换名称为对于寄存器操作数进行换名称为寄存器换名。寄存器换名。既可以用编译器静态实现，也可以用硬件动态完成。既可以用编译器静态实现，也可以用硬件动态完成。102102/157/1573.4 流水线的相关与冲突例如：例如：考虑下述代码：考虑下述代码： DIV.DDIV.DF2F2，F8F8，F4F4 ADD.D ADD.DF8F8，F0F0，F12F12 SUB.D SUB.DF10F10，F8F8，F14F14 DIV.DDIV.D和和ADD.DADD.D存在反相关。存在反相关。 进行寄存器换名（

64、进行寄存器换名（F6F6换成换成S S）后，变成：）后，变成： DIV.DDIV.DF2F2，F8F8，F4F4 ADD.D ADD.DS S，F0F0，F12F12 SUB.D SUB.DF10F10，S S，F14 F14 103103/157/1573.4 流水线的相关与冲突3.控制相关 控制相关是指由分支指令引起的相关。q为了保证程序应有的执行顺序，必须严格按控制相为了保证程序应有的执行顺序，必须严格按控制相 关确定的顺序执行。关确定的顺序执行。典型的程序结构是“if-then”结构。请看一个示例：if p1 if p1 S1 S1； ；S S；if p2 if p2 S2 S2； ；

65、104104/157/1573.4 流水线的相关与冲突控制相关带来了以下两个限制：q与一条分支指令控制相关的指令不能被移到该分支与一条分支指令控制相关的指令不能被移到该分支 之前。否则这些指令就不受该分支控制了。之前。否则这些指令就不受该分支控制了。 对于上述的例子，对于上述的例子，thenthen 部分中的指令不能移到部分中的指令不能移到ifif语语句之前。句之前。 q如果一条指令与某分支指令不存在控制相关，就不如果一条指令与某分支指令不存在控制相关，就不 能把该指令移到该分支之后。能把该指令移到该分支之后。对于上述的例子，不能把对于上述的例子，不能把S S移到移到ifif语句的语句的the

66、nthen 部分中。部分中。105105/157/1573.4 流水线的相关与冲突 流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。 流水线冲突有3种类型：q结构冲突：结构冲突：因硬件资源满足不了指令重叠执行的要因硬件资源满足不了指令重叠执行的要 求而发生的冲突。求而发生的冲突。q数据冲突：数据冲突：当指令在流水线中重叠执行时，因需要当指令在流水线中重叠执行时，因需要 用到前面指令的执行结果而发生的冲突。用到前面指令的执行结果而发生的冲突。q控制冲突：控制冲突：流水线遇到分支指令和其它会改变流水线遇到分支指令和其它会改变PCPC值值 的指令

67、所引起的冲突。的指令所引起的冲突。3.4.2.2 流水线冲突106106/157/1573.4 流水线的相关与冲突带来的几个问题：导致错误的执行结果。流水线可能会出现停顿，从而降低流水线的效率 和实际的加速比。我们约定 当一条指令被暂停时，在该暂停指令之后流出的所当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行（否则就永远无法消除冲突）。继续进行（否则就永远无法消除冲突）。107107/157/1573.4 流水线的相关与冲突1.结构冲突在流水线处理机中，为了能够使各种组合的指令 都能顺利地重叠

68、执行，需要对功能部件进行流水 或重复设置资源。如果某种指令组合因为资源冲突而不能正常执 行，则称该处理机有结构冲突。常见的导致结构冲突的原因：q功能部件不是完全流水功能部件不是完全流水q资源份数不够资源份数不够108108/157/1573.4 流水线的相关与冲突结构冲突举例：访存冲突 有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突。q解决办法解决办法：插入暂停周期插入暂停周期 （“流水线气泡流水线气泡”或或“气泡气泡”） 引入暂停后的时空图引入暂停后的时空图q解决方法解决方法： 设置相互独立的指令存储器和数据存储器设置相互独立的指令存储器和数据存储器 或设置相互

69、独立的指令或设置相互独立的指令CacheCache和数据和数据CacheCache。109109/157/1573.4 流水线的相关与冲突由于访问同一个存储器而引起的结构冲突由于访问同一个存储器而引起的结构冲突 110110/157/1573.4 流水线的相关与冲突为消除结构冲突而插入的流水线气泡为消除结构冲突而插入的流水线气泡 111111/157/1573.4 流水线的相关与冲突引入暂停后的时空图引入暂停后的时空图指令编号指令编号 时钟周期时钟周期 1 12 23 34 45 56 67 78 89 91010指令指令i i IF IF ID ID EX EX MEM MEM WB WB

70、指令指令i+1 i+1 IF IF ID ID EX EX MEM MEM WB WB 指令指令i+2 i+2 IF IF ID ID EX EX MEM MEM WB WB WB WB 指令指令i+3 i+3 stallstall IFIFID ID EX EX MEM MEM WB WB 指令指令i+4 i+4 IFIFID ID EX EX MEM MEM WB WB 指令指令i+5 i+5 IFIFIDIDEX EX MEM MEM 112112/157/1573.4 流水线的相关与冲突有时流水线设计者允许结构冲突的存在主要原因：主要原因：减少硬件成本减少硬件成本q如果把流水线中的所有

71、功能单元完全流水化，或者如果把流水线中的所有功能单元完全流水化，或者 重复设置足够份数，那么所花费的成本将相当高。重复设置足够份数，那么所花费的成本将相当高。2.数据冲突 当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们串行执行时的顺序，则发生了数据冲突。 113113/157/1573.4 流水线的相关与冲突举例： DADD DADD R1R1，R2R2，R3R3 DSUB R4 DSUB R4，R1R1，R5R5 XOR R6 XOR R6，R1R1，R7R7 AND R8 AND R8，R1R1，R9R9 OR R10 OR R1

72、0，R1R1，R11R11114114/157/1573.4 流水线的相关与冲突流水线的数据冲突举例流水线的数据冲突举例 115115/157/1573.4 流水线的相关与冲突根据指令读访问和写访问的顺序，可以将数据冲 突分为3种类型。 考虑考虑两条指令两条指令i i和和j j ，且，且i i在在j j之前进入流水线，之前进入流水线，可能发生的数据冲突有：可能发生的数据冲突有：q写后读冲突（写后读冲突（RAWRAW） 在在 i i 写入之前，写入之前，j j 先去读。先去读。 j j 读出的内容是错误的。读出的内容是错误的。 这是最常见的一种数据冲突，它对应于真数据相这是最常见的一种数据冲突，

73、它对应于真数据相关。关。 116116/157/1573.4 流水线的相关与冲突q写后写冲突（写后写冲突（WAWWAW） 在在 i i 写入之前，写入之前，j j 先写。先写。 最后写入的结果是最后写入的结果是 i i 的。错误！的。错误！ 这种冲突对应于输出相关。这种冲突对应于输出相关。 写后写冲突仅发生在这样的流水线中：n流水线中不只一个段可以进行写操作；流水线中不只一个段可以进行写操作；n指令被重新排序了。指令被重新排序了。 前面介绍的5段流水线不会发生写后写冲突。（只在（只在WBWB段写寄存器）段写寄存器） 117117/157/1573.4 流水线的相关与冲突q读后写冲突（读后写冲突

74、（WARWAR） 在在 i i 读之前，读之前，j j 先写。先写。 i i 读出的内容是错误的！读出的内容是错误的！ 由反相关引起。由反相关引起。 这种冲突仅发生在这样的情况下：n有些指令的写结果操作提前了，而且有些指令有些指令的写结果操作提前了，而且有些指令 的读操作滞后了；的读操作滞后了；n指令被重新排序了。指令被重新排序了。 118118/157/1573.4 流水线的相关与冲突通过定向技术减少数据冲突引起的停顿 （定向技术也称为旁路或短路）（定向技术也称为旁路或短路）q关键思想：关键思想：在计算结果尚未出来之前，后面等待使用在计算结果尚未出来之前，后面等待使用该结果的指令并不真正立即

75、需要该计算结果，如果能该结果的指令并不真正立即需要该计算结果，如果能够将该计算结果从其产生的地方直接送到其它指令需够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免停顿。要它的地方，那么就可以避免停顿。q采用定向技术消除上例中的相关采用定向技术消除上例中的相关 工作过程演示工作过程演示119119/157/1573.4 流水线的相关与冲突采用定向技术后的流水线数据通路采用定向技术后的流水线数据通路 120120/157/1573.4 流水线的相关与冲突q定向的实现定向的实现nEX段和段和MEM段之间的流水寄存器中保存的段之间的流水寄存器中保存的ALU运算结果总是回送到运算

76、结果总是回送到ALU的入口。的入口。n当定向硬件检测到前一个当定向硬件检测到前一个ALU运算结果写入的寄运算结果写入的寄存器就是当前存器就是当前ALU操作的源寄存器时，那么控制操作的源寄存器时，那么控制逻辑就选择定向的数据作为逻辑就选择定向的数据作为ALU的输入，而不采的输入，而不采用从通用寄存器组读出的数据。用从通用寄存器组读出的数据。q结果数据不仅可以从某一功能部件的输出定向到其自身结果数据不仅可以从某一功能部件的输出定向到其自身的输入，而且还可以定向到其它功能部件的输入。的输入，而且还可以定向到其它功能部件的输入。 121121/157/1573.4 流水线的相关与冲突需要停顿的数据冲突

77、 q并不是所有的数据冲突都可以用定向技术来解决。并不是所有的数据冲突都可以用定向技术来解决。 举例举例: LD LD R1R1，0 0（R2R2）DADD R4DADD R4，R1R1，R5R5AND R6AND R6，R1R1，R7R7XOR R8XOR R8，R1R1，R9R9q增加流水线互锁机制，插入增加流水线互锁机制，插入“暂停暂停”。 作用：作用：检测发现数据冲突，并使检测发现数据冲突，并使流水线停顿流水线停顿，直至，直至冲突消失。冲突消失。 举例：举例：演示演示A A 演示演示B B122122/157/1573.4 流水线的相关与冲突无法将无法将LDLD指令的结果定向到指令的结果

78、定向到DADDDADD指令指令 123123/157/1573.4 流水线的相关与冲突依靠编译器解决数据冲突 让编译器重新组织指令顺序来消除冲突，这种技术让编译器重新组织指令顺序来消除冲突，这种技术称为称为指令调度指令调度或或流水线调度。流水线调度。调度前的代码调度前的代码 调度后的代码调度后的代码 LD RbLD Rb，B BLD RcLD Rc，C CDADD RaDADD Ra，RbRb，Rc Rc SD RaSD Ra，A ALD ReLD Re，E ELD RfLD Rf，F FDSUB RdDSUB Rd，ReRe，RfRfSD RdSD Rd，D D LD RbLD Rb，B B

79、LD RcLD Rc，C CLD ReLD Re，E E DADD RaDADD Ra，RbRb，RcRcLD RfLD Rf，F FSD RaSD Ra，A A DSUB RdDSUB Rd，ReRe，RfRfSD RdSD Rd，D D p举例：举例： 请为下列表达式生成没有暂停的指令序列请为下列表达式生成没有暂停的指令序列: : ABC ； DEF ； 假设载入延迟为假设载入延迟为1 1个个时钟周期。时钟周期。 题解题解125125/157/1573.4 流水线的相关与冲突3.控制冲突 执行分支指令的结果有两种q分支成功：分支成功：PCPC值改变为分支转移的目标地址。值改变为分支转移的目

80、标地址。 在条件判定和转移地址计算都完成后，才改变在条件判定和转移地址计算都完成后，才改变PCPC值。值。q不成功或者失败：不成功或者失败：PCPC的值保持正常递增，的值保持正常递增， 指向顺序的下一条指令。指向顺序的下一条指令。处理分支指令最简单的方法：“冻结冻结”或者或者“排空排空”流水线流水线 优点：优点：简单简单p前述前述5 5段流水线中，改变段流水线中，改变PCPC值是在值是在MEMMEM段进行的。段进行的。 给流水线带来了给流水线带来了3 3个时钟周期的延迟个时钟周期的延迟126126/157/157分支指令分支指令 IF IF ID ID EX EX MEM MEM WB WB

81、分支目标指令分支目标指令 IFIF stallstall stallstall IF IF ID ID EX EX MEM MEM WB WB 分支目标指令分支目标指令+1 +1 IF IF ID ID EX EX MEM MEM WB WB 分支目标指令分支目标指令+2 +2 IF IF ID ID EX EX MEM MEM 分支目标指令分支目标指令+3 +3 IF IF ID ID EX EX 简单处理分支指令：分支成功的情况简单处理分支指令：分支成功的情况 3.4 流水线的相关与冲突127127/157/1573.4 流水线的相关与冲突把由分支指令引起的延迟称为分支延迟。分支指令在目标

82、代码中出现的频度q每每3 34 4条指令就有一条是分支指令。条指令就有一条是分支指令。 假设：假设：分支指令出现的频度是分支指令出现的频度是3030 流水线理想流水线理想 CPICPI1 1 那么：那么：流水线的实际流水线的实际 CPI CPI 1.91.9可采取两种措施来减少分支延迟。q在流水线中尽早判断出分支转移是否成功；在流水线中尽早判断出分支转移是否成功；q尽早计算出分支目标地址。尽早计算出分支目标地址。128128/157/1573.4 流水线的相关与冲突下面的讨论中，我们假设： 这两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。 12

83、9129/157/1573.4 流水线的相关与冲突3种通过软件（编译器）来减少分支延迟的方法 共同点：n对分支的处理方法在程序的执行过程中始终是对分支的处理方法在程序的执行过程中始终是 不变的，是静态的。不变的，是静态的。n要么总是预测分支成功，要么总是预测分支失败。要么总是预测分支成功，要么总是预测分支失败。q预测分支失败预测分支失败 n允许分支指令后的指令继续在流水线中流动，就允许分支指令后的指令继续在流水线中流动，就 好象什么都没发生似的；好象什么都没发生似的；n若确定分支失败，将分支指令看作是一条普通指若确定分支失败，将分支指令看作是一条普通指 令，流水线正常流动；令，流水线正常流动；

84、130130/157/1573.4 流水线的相关与冲突n若确定分支成功，流水线就把在分支指令之后若确定分支成功，流水线就把在分支指令之后 取出的所有指令转化为空操作，并按分支目地取出的所有指令转化为空操作，并按分支目地 重新取指令执行。重新取指令执行。要保证：要保证：分支结果出来之前不能改变处理机的状态，以分支结果出来之前不能改变处理机的状态，以 便一旦猜错时，处理机能够回退到原先的状态。便一旦猜错时，处理机能够回退到原先的状态。流水线的处理过程流水线的处理过程132132/157/1573.4 流水线的相关与冲突q预测分支成功预测分支成功 假设分支转移成功，并从分支目标地址处取指令执行。假设

85、分支转移成功，并从分支目标地址处取指令执行。起作用的前题：起作用的前题：先知道分支目标地址，后知道分支是否先知道分支目标地址，后知道分支是否 成功。成功。前述前述5 5段流水线中，这种方法没有任何好处。段流水线中，这种方法没有任何好处。q延迟分支延迟分支主要思想：主要思想： 从逻辑上从逻辑上“延长延长”分支指令的执行时间。把延迟分分支指令的执行时间。把延迟分支支看成是由原来的分支指令和若干个延迟槽构成，不管分看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。支是否成功，都要按顺序执行延迟槽中的指令。延迟分支以及指令的执行顺序延迟分支以及指令的执行顺序具有

86、一个分支延迟槽的流水线的执行过程具有一个分支延迟槽的流水线的执行过程分分支支失失败败 分支指令分支指令i i IF IF ID ID EX EX MEM MEM WBWB延迟槽指令延迟槽指令 i+1i+1 IF IF ID ID EX EX MEM MEM WBWB指令指令 i+2 i+2 IF IF ID ID EX EX MEM MEM WBWB指令指令 i+3 i+3 IF IF ID ID EX EX MEMMEMWBWB指令指令 i+4 i+4 IF IF ID ID EX EX MEMMEMWBWB分支延迟槽中的指令分支延迟槽中的指令“掩盖掩盖”了流水线原来必需插入的暂停周期。了流

87、水线原来必需插入的暂停周期。分分支支成成功功 分支指令分支指令i i IF IF ID ID EX EX MEMMEMWBWB 延迟槽指令延迟槽指令 i+1i+1 IF IF ID ID EX EX MEMMEMWBWB分支目标指令分支目标指令j j IF IF ID ID EX EX MEMMEMWBWB分支目标指令分支目标指令j+1 j+1 IF IF ID ID EX EX MEMMEMWBWB分支目标指令分支目标指令j+2j+2IF IF ID ID EX EX MEMMEMWBWB134134/157/1573.4 流水线的相关与冲突 分支延迟指令的调度任务：任务：在延迟槽中放入有用

88、的指令在延迟槽中放入有用的指令由编译器完成。能否带来好处取决于编译器能否把有用由编译器完成。能否带来好处取决于编译器能否把有用的指令调度到延迟槽中。的指令调度到延迟槽中。三种调度方法：三种调度方法： n从前调度从前调度n从目标处调度从目标处调度n从失败处调度从失败处调度调度前和调度后的代码136136/157/1573.4 流水线的相关与冲突三种方法的要求及效果调 度 策 略对调度的要求什么情况下起作用？从从 前前 调调 度度从目标处调度从目标处调度从失败处调度从失败处调度必须保证在分支失败时执行被调度必须保证在分支失败时执行被调度的指令不会导致错误。有可能需要的指令不会导致错误。有可能需要复

89、制指令。复制指令。被调度的指令必须与分支无关被调度的指令必须与分支无关必须保证在分支成功时执行被调度必须保证在分支成功时执行被调度的指令不会导致错误。的指令不会导致错误。任何情况任何情况 分支成功时分支成功时( (但由于复制指令，有但由于复制指令，有可能会增大程序空间可能会增大程序空间) )分支失败时分支失败时137137/157/1573.4 流水线的相关与冲突分支延迟受到两个方面的限制：q可以被放入延迟槽中的指令要满足一定的条件；可以被放入延迟槽中的指令要满足一定的条件；q编译器预测分支转移方向的能力。编译器预测分支转移方向的能力。进一步改进：分支取消机制（取消分支） 当分支的实际执行方向

90、和事先所预测的一样时，当分支的实际执行方向和事先所预测的一样时，执行分支延迟槽中的指令，否则就将分支延迟槽中的执行分支延迟槽中的指令，否则就将分支延迟槽中的指令转化成一个空操作。指令转化成一个空操作。“预测预测成功成功-取消取消”分支的执行过程分支的执行过程分分支支失失败败 分支指令分支指令i i IF IF ID ID EX EX MEM MEM WBWB延迟槽指令延迟槽指令 i+1i+1 IF IF idleidle idle idle idle idle idleidle指令指令 i+2 i+2 IF IF ID ID EX EX MEM MEM WBWB指令指令 i+3 i+3 IF

91、IF ID ID EX EX MEMMEMWBWB指令指令 i+4 i+4 IF IF ID ID EX EX MEMMEMWBWB分分支支成成功功 分支指令分支指令i i IF IF ID ID EX EX MEMMEMWBWB 延迟槽指令延迟槽指令 i+1i+1 IF IF ID ID EX EX MEMMEMWBWB分支目标指令分支目标指令j j IF IF ID ID EX EX MEMMEMWBWB分支目标指令分支目标指令j+1 j+1 IF IF ID ID EX EX MEMMEMWBWB分支目标指令分支目标指令j+2j+2IF IF ID ID EX EX MEMMEMWBWB

92、预测分支成功的情况下，分支取消机制的执行情况预测分支成功的情况下，分支取消机制的执行情况 139139/157/1571.实现MIPS指令子集的一种简单数据通路。该数据通路的操作分成5个时钟周期q取指令取指令q指令译码指令译码/读寄存器读寄存器q执行执行/有效地址计算有效地址计算q存储器访问存储器访问/分支完成分支完成q写回写回 只讨论整数指令的实现（包括：（包括：loadload和和storestore，等于，等于0 0转转移，整数移，整数ALUALU指令等。）指令等。） 3.5 流水线的实现3.5.1 MIPS的一种简单实现141141/157/1573.5 流水线的实现设置了一些临时寄存

93、器。其作用如下：qPC：程序计数器，存放当前指令的地址。：程序计数器，存放当前指令的地址。qNPC：下一条程序计数器，存放下一条指令的地址。：下一条程序计数器，存放下一条指令的地址。qIR：指令寄存器，存放当前正在处理的指令。：指令寄存器，存放当前正在处理的指令。qA：第一操作数寄存器，存放从通用寄存器组读出来：第一操作数寄存器，存放从通用寄存器组读出来的操作数。的操作数。qB：第二操作数寄存器，存放从通用寄存器组读出来的：第二操作数寄存器，存放从通用寄存器组读出来的另一个操作数。另一个操作数。qImm：存放符号扩展后的立即数操作数。：存放符号扩展后的立即数操作数。qCond：存放条件判定的结

94、果。为：存放条件判定的结果。为“真真”表示分支成功。表示分支成功。qALUo：存放：存放ALU的运算结果。的运算结果。qLMD：存放：存放load指令从存储器读出的数据。指令从存储器读出的数据。142142/157/1573.5 流水线的实现2.一条MIPS指令最多需要以下5个时钟周期：取指令周期（IF） 操作pIRIRMemPCMemPCpNPCNPCPC+4PC+4指令译码/读寄存器周期（ID） 操作qA A RegsrsRegsrsqB B RegsrtRegsrtqImm Imm （IRIR1616）1616#IRIR16.3116.31） 指令的译码操作和读寄存器操作是并行进行的。指

95、令的译码操作和读寄存器操作是并行进行的。 原因：在原因：在MIPSMIPS指令格式中，操作码字段以及指令格式中，操作码字段以及rsrs、rtrt 字段都是在固定的位置。字段都是在固定的位置。 这种技术称为这种技术称为固定字段译码固定字段译码技术技术。 143143/157/1573.5 流水线的实现执行/有效地址计算周期（EX） 不同指令所进行的操作不同：qloadload指令和指令和storestore指令指令 操作操作 ALUoALUoA + ImmA + Immq寄存器寄存器寄存器寄存器ALUALU指令指令 操作操作 ALUoALUoA funct BA funct Bq寄存器立即值寄存

96、器立即值ALUALU指令指令 操作操作 ALUoALUoA op ImmA op Immq分支指令分支指令 操作操作 ALUoALUoNPC+NPC+（Imm2Imm2）；）； condcond（A = = 0A = = 0）144144/157/1573.5 流水线的实现 将有效地址计算周期和执行周期合并为一个时将有效地址计算周期和执行周期合并为一个时钟周期，这是因为钟周期，这是因为MIPSMIPS指令集采用指令集采用loadloadstorestore结结构，没有任何指令需要同时进行数据有效地址的计构，没有任何指令需要同时进行数据有效地址的计算、转移目标地址的计算和对数据进行运算。算、转移

97、目标地址的计算和对数据进行运算。存储器访问/分支完成周期（MEM）q所有指令都要在该周期对所有指令都要在该周期对PCPC进行更新。进行更新。 除了分支指令，其它指令都是做：除了分支指令，其它指令都是做：PCPCNPCNPCq在该周期内处理的在该周期内处理的MIPSMIPS指令仅仅有指令仅仅有loadload、storestore和分和分支支三种指令。三种指令。145145/157/1573.5 流水线的实现qloadload指令和指令和storestore指令指令 操作操作 LMD LMDMemALUo MemALUo 或者或者 MemALUoMemALUoB Bq分支指令分支指令 操作操作

98、if if （condcond） PC PC ALUo else PCALUo else PCNPCNPC写回周期（WB）不同的指令在写回周期完成的工作也不一样。不同的指令在写回周期完成的工作也不一样。q寄存器寄存器寄存器寄存器ALUALU指令指令 操作操作 RegsrdRegsrd ALUo ALUoq寄存器立即数寄存器立即数ALUALU指令指令 操作操作 RegsrtRegsrt ALUo ALUoqloadload指令指令 操作操作 RegsrtRegsrt LMD LMD146146/157/1573.5 流水线的实现每一个时钟周期完成的工作看作是流水线的一段，每个时钟周期启动一条新的

99、指令。1.流水实现的数据通路设置了流水寄存器q段与段之间设置流水寄存器段与段之间设置流水寄存器q流水寄存器的名称流水寄存器的名称 用其相邻的两个段的名称拼合而成。用其相邻的两个段的名称拼合而成。 例如：例如：IDID段段与与EXEX段段之间的流水寄存器用之间的流水寄存器用ID/EXID/EX表示表示q每个流水寄存器是由若干个寄存器构成的每个流水寄存器是由若干个寄存器构成的 3.5.2 基本的MIPS流水线147147/157/1573.5 流水线的实现流水实现的数据通路流水实现的数据通路148148/157/1573.5 流水线的实现q寄存器的命名形式为：寄存器的命名形式为：x.yx.yq所包

100、含的字段的命名形式为：所包含的字段的命名形式为：x.ysx.ys 其中：其中：x x：流水寄存器名称流水寄存器名称 y y：具体寄存器名称具体寄存器名称 s s：字段名称字段名称 例如：例如： ID/EX.IRID/EX.IR：流水寄存器流水寄存器ID/EXID/EX中的子寄存器中的子寄存器IRIR IRID/EX.IRop IRID/EX.IRop：该寄存器的该寄存器的opop字段（即操作码字段）字段（即操作码字段）q流水寄存器的作用流水寄存器的作用n将各段的工作隔开，使得它们不会互相干扰。将各段的工作隔开，使得它们不会互相干扰。n保存相应段的处理结果。保存相应段的处理结果。149149/1

101、57/1573.5 流水线的实现例如：例如：EX/MEM.ALUoEX/MEM.ALUo：保存保存EXEX段段ALUALU的运算结果的运算结果MEM/WB.LMDMEM/WB.LMD：保存保存MEMMEM段从数据存储器读出的数据段从数据存储器读出的数据n向后传递后面将要用到的数据或者控制信息向后传递后面将要用到的数据或者控制信息 所有有用的数据和控制信息每个时钟周期所有有用的数据和控制信息每个时钟周期 会随着指令在流水线中的流动往后流动一段。会随着指令在流水线中的流动往后流动一段。 增加了向后传递IR和从MEM/WB.IR回送到通用寄存 器组的连接。 将对PC的修改移到了IF段，以便PC能及时

102、地加 4，为取下一条指令做好准备。 150150/157/1573.5 流水线的实现2.每一个流水段进行的操作qIRrsIRrsIRIR6.106.10qIRrtIRrtIRIR11.1511.15qIRrdIRrdIRIR16.2016.20 流水段流水段流水线的每个流水段的操作所有指令类型所有指令类型ALU ALU 指令指令load/store load/store 指令指令分支指令分支指令IFIFIDIDEXEXIF/ID.IR IF/ID.IR MemPC MemPCIF/ID.NPC, PC IF/ID.NPC, PC （ifif（ EX/MEM.IRop = branch EX/M

103、EM.IRop = branch ）& & EX/MEM.condEX/MEM.cond）EX/MEM.ALUo else PC+4EX/MEM.ALUo else PC+4）；）； ID/EX.A RegsIF/ID.IRrsID/EX.A RegsIF/ID.IRrs；ID/EX.B RegsIF/ID.IRrtID/EX.B RegsIF/ID.IRrt；ID/EX.NPC IF/ID.NPCID/EX.NPC IF/ID.NPC；ID/EX.IR IF/ID.IRID/EX.IR IF/ID.IR；ID/EX.Imm ID/EX.Imm （IF/ID.IRIF/ID.IR1616) )

104、1616#IF/ID.IR#IF/ID.IR16.3116.31； EX/MEM.IR ID/EX.IREX/MEM.IR ID/EX.IR；EX/MEM.ALUo EX/MEM.ALUo ID/EX.A ID/EX.A functfunct ID/EX.B ID/EX.B或或EX/MEM.ALUo EX/MEM.ALUo ID/EX.A ID/EX.A opop ID/EX.Imm ID/EX.Imm； EX/MEM.IR ID/EX.IREX/MEM.IR ID/EX.IR；EX/MEM.ALUo EX/MEM.ALUo ID/EX.A + ID/EX.Imm ID/EX.A + ID/E

105、X.Imm；EX/MEM.BID/EX.BEX/MEM.BID/EX.B； EX/MEM.IR ID/EX.IREX/MEM.IR ID/EX.IR；EX/MEM.ALUo EX/MEM.ALUo ID/EX.NPC + ID/EX.NPC + ID/EX.Imm ID/EX.Imm2 2；EX/MEM.cond EX/MEM.cond （ID/EX.A ID/EX.A =0 0）；）； (动画演示)(动画演示)(动画演示)(动画演示)(动画演示)流水段流水段任何指令类型任何指令类型ALU ALU 指令指令load/store load/store 指令指令分支指令分支指令MEMMEMWBWB

106、MEM/WB.IR EX/MEM.IRMEM/WB.IR EX/MEM.IR；MEM/WB.ALUo MEM/WB.ALUo EX/MEM.ALUo EX/MEM.ALUo； MEM/WB.IR EX/MEM.IRMEM/WB.IR EX/MEM.IR；MEM/WB.LMD MEM/WB.LMD MemEX/MEM.ALUo MemEX/MEM.ALUo；或或MemEX/MEM.ALUo MemEX/MEM.ALUo EX/MEM.B EX/MEM.B； RegsMEM/WB.IRrd RegsMEM/WB.IRrd MEM/WB.ALUo MEM/WB.ALUo；或或RegsMEM/WB.I

107、Rrt RegsMEM/WB.IRrt MEM/WB.ALUo MEM/WB.ALUo； RegsMEM/WB.IRrt RegsMEM/WB.IRrt MEM/WB.LMD MEM/WB.LMD； 流水线的每个流水段的操作(动画演示)(动画演示)(动画演示)(动画演示)153153/157/1573.5 流水线的实现3.流水线的控制主要是如何控制四个多路选择器。qMUX2if （ID/EX.IRop=“分支指令分支指令”） MUX2_outputID/EX.NPC ；else MUX2_outputID/EX.A； /MUX2_output表示表示MUX2的输出的输出qMUX3if （ID/

108、EX.IRop=“寄存器寄存器型寄存器寄存器型ALU指令指令”） MUX3_outputID/EX.B ；else MUX3_outputID/EX.Imm； /MUX3_output表示表示MUX3的输出的输出154154/157/1573.5 流水线的实现qMUX1if （ID/EX.IRop=“分支指令分支指令”）& EX/MEM.cond） MUX1_outputEX/MEM.ALUo ；else MUX1_outputPC+4； /MUX1_output表示表示MUX1的输出的输出qMUX4if （ID/EX.IRop=“load”） MUX4_outputMEM/WB.LMD ；e

109、lse MUX4_outputMEM/WB.ALUo /MUX4_output表示表示MUX4的输出的输出155155/157/1573.5 流水线的实现q第第5 5个多路器：个多路器：从从MEM/WBMEM/WB回传至通用寄存器组的写入回传至通用寄存器组的写入 地址应该是从地址应该是从MEM/WB.IRrdMEM/WB.IRrd和和MEM/WB.IRrtMEM/WB.IRrt中选中选 一个。一个。n寄存器寄存器型寄存器寄存器型ALUALU指令：选择指令：选择MEM/WB.IRrdMEM/WB.IRrd；n寄存器立即数型寄存器立即数型ALUALU指令和指令和loadload指令：选择指令：选择

110、MEM/WB.IRrtMEM/WB.IRrt。解决数据冲突的问题 q所有的数据冲突均可以在所有的数据冲突均可以在IDID段检测到。段检测到。 如果存在数据冲突，就在相应的指令流出如果存在数据冲突，就在相应的指令流出IDID段之段之前将之暂停。前将之暂停。 完成该工作的硬件称为完成该工作的硬件称为流水线的互锁机制。流水线的互锁机制。 156156/157/1573.5 流水线的实现q在在IDID段段确定需要什么样的定向，并设置相应的控制。确定需要什么样的定向，并设置相应的控制。 降低流水线的硬件复杂度。（不必挂起已经改变降低流水线的硬件复杂度。（不必挂起已经改变 了机器状态的指令）了机器状态的指

111、令）q也可以在也可以在使用操作数的那个时钟周期使用操作数的那个时钟周期的开始检测冲突的开始检测冲突 和确定必需的定向。和确定必需的定向。q检测冲突是通过比较寄存器地址是否相等来实现的。检测冲突是通过比较寄存器地址是否相等来实现的。举例：举例： loadload互锁互锁由于使用由于使用loadload的结果而引起的流水线互锁称为的结果而引起的流水线互锁称为loadload互锁。互锁。 157157/157/1573.5 流水线的实现ID/EXID/EX中的操作码中的操作码 （ID/EX.IRopID/EX.IRop） IF/ID IF/ID中的操作码中的操作码 （IF/ID.IRopIF/ID.

112、IRop） 比较的操作数字段比较的操作数字段 load load RR ALU RR ALU ID/EX.IRrt=IF/ID.IRrsID/EX.IRrt=IF/ID.IRrsload load RR ALU RR ALU ID/EX.IRrt=IF/ID.IRrt ID/EX.IRrt=IF/ID.IRrt load load loadload、storestoreALUALU立即数或分支立即数或分支 ID/EX.IRrt=IF/ID.IRrs ID/EX.IRrt=IF/ID.IRrs 在在IDID段检测是否存在段检测是否存在RAWRAW冲突冲突 （这时（这时loadload指令在指令在

113、EXEX段）段） 158158/157/1573.5 流水线的实现q若检测到若检测到RAWRAW冲突，流水线互锁机制必须在流水线中冲突，流水线互锁机制必须在流水线中 插入停顿，并使当前正处于插入停顿，并使当前正处于IFIF段和段和IDID段的指令不再段的指令不再 前进。前进。n将将ID/EX.IRID/EX.IR中的操作码改为全中的操作码改为全0 0 （全（全0 0表示空操作）表示空操作）nIF/IDIF/ID寄存器的内容回送到自己的入口寄存器的内容回送到自己的入口定向逻辑q要考虑的情况更多要考虑的情况更多 q通过比较流水寄存器中的寄存器地址来确定通过比较流水寄存器中的寄存器地址来确定1591

114、59/157/1573.5 流水线的实现例如： p若：若：(ID/EX.IR.op=RR ALU)&(ID/EX.IR.op=RR ALU)&（EX/MEM.IR.op=RR EX/MEM.IR.op=RR ALUALU）& &（ID/EX.IRrt=EX/MEM.IRrdID/EX.IRrt=EX/MEM.IRrd） 则：则：EX/MEM.ALUoEX/MEM.ALUo定向到定向到ALUALU的下面一个输入的下面一个输入p若：若：（ID/EX.IRop=RR ALUID/EX.IRop=RR ALU）& &（MEM/WB.IRop=loadMEM/WB.IRop=load）& & （ID/E

115、X.IRrt=MEM/WB.IRrtID/EX.IRrt=MEM/WB.IRrt） 则：则：把把MEM/WB.LMDMEM/WB.LMD定向到定向到ALUALU的下面一个输入的下面一个输入160160/157/1573.5 流水线的实现4.控制冲突分支指令的条件测试和分支目标地址计算是在EX段完成，对PC的修改是在MEM段完成。它所带来的分支延迟是3个时钟周期。减少分支延迟：作如下改进 （把上述工作提前到（把上述工作提前到IDID段进行）段进行）q在在IDID段段增设一个加法器：增设一个加法器：计算分支目标地址计算分支目标地址q把条件测试把条件测试“=0=0？”的逻辑电路移到的逻辑电路移到ID

116、ID段段q这些结果直接回送到这些结果直接回送到IFIF段的段的MUX1MUX1q改进后的流水线对分支指令的处理改进后的流水线对分支指令的处理161161/157/1573.5 流水线的实现162162/157/1573.5 流水线的实现流流 水水 段段分分 支支 指指 令令 操操 作作IFIFIDIDEXEXIF/ID.IR MemPCIF/ID.IR MemPC；IF/ID.NPC, PC IF/ID.NPC, PC (if( IF/IDop= =branch)&(RegsIF/ID.IRrs = = 0) (if( IF/IDop= =branch)&(RegsIF/ID.IRrs = =

117、 0) IF/ID.NPC + (IF/ID.IR IF/ID.NPC + (IF/ID.IR1616) )1616 # # （IF/ID.IRIF/ID.IR16.3116.31 2 2） else PC+4) else PC+4)； ID/EX.A RegsIF/ID.IRrsID/EX.A RegsIF/ID.IRrs； ID/EX.B RegsIF/ID.IRrtID/EX.B RegsIF/ID.IRrt；ID/EX.IR IF/ID.IRID/EX.IR IF/ID.IR；ID/EX.Imm ID/EX.Imm （ IF/ID.IRIF/ID.IR1616 ）16 16 # IF/ID. # IF/ID. IRIR16.3116.31； MEMMEMWBWB改进后流水线的分支操作改进后流水线的分支操作