第5章标量处理机 流水线冲突MIPS流水线

1、5.4 流水线的相关与冲突流水线的相关与冲突5.4.1 一条经典的一条经典的5段流水线段流水线5.4.2 相关与流水线的冲突相关与流水线的冲突计算机科学与技术系计算机科学与技术系介绍一条经典的5段RISC流水线 首先讨论在非流水情况下是如何实现的w一条指令的执行过程分为以下5个周期：取指令周期（IF）q以程序计数器以程序计数器PC中的内容作为地址，从存储器中取中的内容作为地址，从存储器中取出指令并放入指令寄存器出指令并放入指令寄存器IR；q同时同时PC值加值加4（假设每条指令占（假设每条指令占4个字节），指向顺个字节），指向顺序的下一条指令。序的下一条指令。5.4 流水线的相关与冲突5.4.1

2、 一条经典的5段流水线计算机科学与技术系计算机科学与技术系指令译码/读寄存器周期（ID） 对指令进行译码，并读出寄存器的内容。用对指令进行译码，并读出寄存器的内容。用IR中的寄中的寄存器地址去访问通用寄存器组，读出所需的操作数。由于存器地址去访问通用寄存器组，读出所需的操作数。由于指令的立即数部分也保存在相同的位置，需要扩展立即数指令的立即数部分也保存在相同的位置，需要扩展立即数的操作也在本段完成。的操作也在本段完成。 执行/有效地址计算周期（EX） 不同指令所进行的操作不同：qload和和store指令指令：ALU把指令中所指定的寄存器的内容与把指令中所指定的寄存器的内容与偏移量相加，形成访

3、存有效地址。偏移量相加，形成访存有效地址。q寄存器寄存器寄存器寄存器ALU指令指令：ALU按照操作码指定的操作按照操作码指定的操作对从通用寄存器组中读出的数据进行运算。对从通用寄存器组中读出的数据进行运算。计算机科学与技术系计算机科学与技术系q寄存器立即数寄存器立即数ALU指令指令：ALU按照操作码指定的操作按照操作码指定的操作对从通用寄存器组中读出的操作数和指令中给出的立即对从通用寄存器组中读出的操作数和指令中给出的立即数进行运算。数进行运算。q分支指令分支指令：ALU把指令中给出的偏移量与把指令中给出的偏移量与PC值相加，形值相加，形成转移目标的地址。同时，对在前一个周期读出的操作成转移目

4、标的地址。同时，对在前一个周期读出的操作数进行判断，确定分支是否成功。数进行判断，确定分支是否成功。存储器访问分支完成周期（MEM） 该周期处理的指令只有load、store和分支指令。 其它类型的指令在此周期不做任何操作。计算机科学与技术系计算机科学与技术系qloadload和和storestore指令指令loadload指令：指令：用上一个周期计算出的有效地址从存储器中用上一个周期计算出的有效地址从存储器中 读出相应的数据；读出相应的数据；storestore指令：指令：把指定的数据写入这个有效地址所指出的存把指定的数据写入这个有效地址所指出的存 储器单元。储器单元。q分支指令分支指令 分

5、支分支“成功成功”，就把转移目标地址送入，就把转移目标地址送入PCPC。 分支指令执行完成。分支指令执行完成。计算机科学与技术系计算机科学与技术系写回周期（WB） ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。 ALUALU运算指令：运算指令：结果数据来自结果数据来自ALUALU。 loadload指令：指令：结果数据来自存储器。结果数据来自存储器。 在这个实现方案中：p分支指令需要分支指令需要4 4个时钟个时钟周期（如果把分支指令的执行周期（如果把分支指令的执行 提前到提前到IDID周期，则只需要周期，则只需要2 2个个周期）；周期）；pstorestore指令需要指令需

6、要4 4个个周期；周期；p其它指令需要其它指令需要5 5个个周期才能完成。周期才能完成。w在更先进的实现中，在ID段完成对寄存器的内容进行比较，判断是否为转移指令，若为真，将PC与带符号的位移量相加，生成的转移目标地址写人PC，在ID段完成对转移的处理。计算机科学与技术系计算机科学与技术系w将上述实现方案修改为流水线实现一条经典的5段流水线 q每一个周期作为一个流水段；每一个周期作为一个流水段；q在各段之间加上锁存器（流水寄存器）。在各段之间加上锁存器（流水寄存器）。 IM Reg ALU DM Reg IF 段段 ID 段段 EX 段段 MEM 段段 WB 段段 流流水水寄寄存存器器 计算机

7、科学与技术系计算机科学与技术系w流水寄存器流水寄存器保证了流水线中不同段的指令不会相互影响。每个时钟周期结束之后，该段的所有执行结果都保存在流水段寄存器中，在下一个时钟周期开始作为下一个段的输入。 IM Reg ALU DM Reg IF 段段 ID 段段 EX 段段 MEM 段段 WB 段段 流流水水寄寄存存器器 计算机科学与技术系计算机科学与技术系w第一种描述（类似于时空图）5段流水线的两种描述方式计算机科学与技术系计算机科学与技术系流水线的实现必须关注：w需要确定处理器在每一个时钟周期都进行什么样的动作。w要保证在同一个周期没有两条指令使用相同的数据通路资源。w可以采用流水线方式下简化的

8、RISC数据通路图来表示：计算机科学与技术系计算机科学与技术系第二种描述（按时间错开的数据通路序列）计算机科学与技术系计算机科学与技术系 w采用流水线方式实现时，应解决好以下几个问题：要保证不会在同一时钟周期要求同一个功能段做 两件不同的工作。例如：不能要求例如：不能要求ALUALU同时做有效地址计算和算术运算。同时做有效地址计算和算术运算。避免IF段的访存（取指令）与MEM段的访存（读/写数据）发生冲突。q可以采用分离的指令存储器和数据存储器；可以采用分离的指令存储器和数据存储器；q一般采用分离的指令一般采用分离的指令CacheCache和数据和数据CacheCache。ID段和WB段都要访

9、问同一寄存器文件。 IDID段：读段：读WBWB段：写段：写计算机科学与技术系计算机科学与技术系寄存器堆在寄存器堆在ID段被读，在段被读，在WE段被写，所以在数据通路中出现两段被写，所以在数据通路中出现两次次计算机科学与技术系计算机科学与技术系对于在一个时钟周期内同一寄存器堆进行操作，在时钟的前半部对于在一个时钟周期内同一寄存器堆进行操作，在时钟的前半部分进行写寄存器的操作，后半部分进行读寄存器的操作。分进行写寄存器的操作，后半部分进行读寄存器的操作。计算机科学与技术系计算机科学与技术系如何解决对同一寄存器的访问冲突？ 把写操作安排在时钟周期的前半拍完成，把读操作安排在后半拍完成。边框画实线表

10、示操作，画虚线表示不做任何操作。计算机科学与技术系计算机科学与技术系w考虑考虑PCPC的问题的问题流水线为了能够每个时钟周期启动一条新的指令，流水线为了能够每个时钟周期启动一条新的指令，就必须在每个时钟周期进行就必须在每个时钟周期进行PCPC值的加值的加4 4操作，并保操作，并保留新的留新的PCPC值。这种操作值。这种操作必须在必须在IFIF段完成，段完成，以便为以便为取下一条指令做好准备。取下一条指令做好准备。 （需设置一个专门的加法器）（需设置一个专门的加法器）但分支指令也可能改变但分支指令也可能改变P PC C的值，而且是在的值，而且是在MEMMEM段段进进行，这会导致冲突。行，这会导致

11、冲突。请考虑一下，如何处理分支指令？请考虑一下，如何处理分支指令？计算机科学与技术系计算机科学与技术系w相关：两条指令之间存在某种依赖关系。 如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。5.4.2.1 相关与流水线冲突5.4.2 相关与流水线冲突计算机科学与技术系计算机科学与技术系 流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。 流水线冲突有3种类型：q结构冲突：结构冲突：因硬件资源满足不了指令重叠执行的要因硬件资源满足不了指令重叠执行的要 求而发生的冲突。求而发生的冲突。q数据冲突：数据冲突：当指令在流水

12、线中重叠执行时，因需要当指令在流水线中重叠执行时，因需要 用到前面指令的执行结果而发生的冲突。用到前面指令的执行结果而发生的冲突。q控制冲突：控制冲突：流水线遇到分支指令和其它会改变流水线遇到分支指令和其它会改变PCPC值值 的指令所引起的冲突。的指令所引起的冲突。流水线冲突计算机科学与技术系计算机科学与技术系w导致错误的执行结果。w流水线可能会出现停顿，从而降低流水线的效率和实际的加速比。w我们约定 当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行（否则就永远无法消除冲突）。带来的几个问题：计算机科学与技术系计算机科学与技术系在流水线处理机

13、中，为了能够使各种组合的指令在流水线处理机中，为了能够使各种组合的指令 都能顺利地重叠执行，需要对功能部件进行流水都能顺利地重叠执行，需要对功能部件进行流水 或重复设置资源。或重复设置资源。如果某种指令组合因为资源冲突而不能正常执如果某种指令组合因为资源冲突而不能正常执 行，则称该处理机有行，则称该处理机有结构冲突。结构冲突。常见的导致结构常见的导致结构冲突冲突的原因：的原因：q功能部件不是完全流水功能部件不是完全流水q资源份数不够资源份数不够结构冲突计算机科学与技术系计算机科学与技术系结构冲突举例：访存冲突访存冲突 有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突

14、。q解决办法解决办法：插入暂停周期插入暂停周期 （“流水线气泡流水线气泡”或或“气泡气泡”） 引入暂停后的时空图引入暂停后的时空图q解决方法解决方法： 设置相互独立的指令存储器和数据存储器设置相互独立的指令存储器和数据存储器 或设置相互独立的指令或设置相互独立的指令CacheCache和数据和数据CacheCache。计算机科学与技术系计算机科学与技术系由于访问同一个存储器而引起的结构冲突由于访问同一个存储器而引起的结构冲突 访存冲突返回计算机科学与技术系计算机科学与技术系 时间（时钟周期）时间（时钟周期） 1 2 3 4 5 6 M Reg ALU M Reg M Reg ALU M Reg

15、 M Reg ALU M Reg 7 8 load 指令指令 i+1 指令指令 i+2 暂暂 停停 M Reg ALU M 指令指令 i+3 气泡气泡 气泡气泡 气泡气泡 气泡气泡 气泡气泡 为消除结构冲突而插入的流水线气泡为消除结构冲突而插入的流水线气泡 计算机科学与技术系计算机科学与技术系引入暂停后的时空图引入暂停后的时空图指令编号指令编号 时钟周期时钟周期 1 12 23 34 45 56 67 78 89 91010指令指令i i IF IF ID ID EX EX MEM MEM WB WB 指令指令i+1 i+1 IF IF ID ID EX EX MEM MEM WB WB 指令

16、指令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 计算机科学与技术系计算机科学与技术系w有时流水线设计者允许结构冲突的存在主要原因：减少硬件成本如果把流水线中的所有功能单元完全流水化，或者重复设置足够份数，那么所花费的成本将相当高。 计算机科学与技术系计算机科学与技术系w数据冲突数据冲突 当相关

17、的指令靠得足够近时，它们在流水线中当相关的指令靠得足够近时，它们在流水线中的的重叠执行或者重新排序重叠执行或者重新排序会改变指令读会改变指令读/写操作数写操作数的顺序，使之不同于它们串行执行时的顺序，则发的顺序，使之不同于它们串行执行时的顺序，则发生了生了数据冲突。数据冲突。 计算机科学与技术系计算机科学与技术系举例： 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 R10，R1R1，R11R计算机科学与技术系计算机科学与技术

18、系 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1， R2， R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 IM Reg OR R10，R1，R11 流水线的数据冲突举例流水线的数据冲突举例 ADD在WB段写R1，SUB则在ID段读R1，产生了数据相关。XOR也受到数据相关的影响AND操作由于前半个周期写寄存器对，后半个周期读寄存器堆，可以正确执行。OR操作也能正确执行，此时R1的值已经被正确写人计算机科学与技术系计算机科学

19、与技术系根据指令读访问和写访问的顺序，可以将数据冲 突分为3种类型。 考虑考虑两条指令两条指令i i和和j j ，且，且i i在在j j之前进入流水线，之前进入流水线，可能发生的数据冲突有：可能发生的数据冲突有：q写后读冲突（写后读冲突（RAWRAW） 在在 i i 写入之前，写入之前，j j 先去读。先去读。 j j 读出的内容是错误的。读出的内容是错误的。 这是最常见的一种数据冲突，它对应于真数据相这是最常见的一种数据冲突，它对应于真数据相关。关。 数据冲突的三种类型计算机科学与技术系计算机科学与技术系q写后写冲突（写后写冲突（WAWWAW） 在在 i i 写入之前，写入之前，j j 先写

20、。先写。 最后写入的结果是最后写入的结果是 i i 的。错误！的。错误！ 这种冲突对应于输出相关。这种冲突对应于输出相关。 写后写冲突仅发生在这样的流水线中：n流水线中不只一个段可以进行写操作；流水线中不只一个段可以进行写操作；n指令被重新排序了。指令被重新排序了。 前面介绍的5段流水线不会发生写后写冲突。（只在（只在WBWB段写寄存器）段写寄存器） 计算机科学与技术系计算机科学与技术系q读后写冲突（读后写冲突（WARWAR） 在在 i i 读之前，读之前，j j 先写。先写。 i i 读出的内容是错误的！读出的内容是错误的！ 由反相关引起。由反相关引起。 这种冲突仅发生在这样的情况下：n有些

21、指令的写结果操作提前了，而且有些指令有些指令的写结果操作提前了，而且有些指令 的读操作滞后了；的读操作滞后了；n指令被重新排序了。指令被重新排序了。 计算机科学与技术系计算机科学与技术系w通过通过定向技术定向技术减少数据冲突引起的停顿减少数据冲突引起的停顿 （定向技术也称为旁路或短路）（定向技术也称为旁路或短路）关键思想：关键思想：在计算结果尚未出来之前，后面等待在计算结果尚未出来之前，后面等待使用该结果的指令并不真正立即需要该计算结果，使用该结果的指令并不真正立即需要该计算结果，如果能够将该计算结果从其产生的地方直接送到如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可

22、以避免停顿。其它指令需要它的地方，那么就可以避免停顿。采用定向技术消除上例中的相关采用定向技术消除上例中的相关DSUB操作是在操作是在DADD操作产生了结果之后才使操作产生了结果之后才使用该结果的，考虑将用该结果的，考虑将DADD的结果从的结果从EX/MEM寄寄存器移到存器移到DSUB需要的地方，也就是需要的地方，也就是ALU的输入的输入锁存器，则不需要引入停顿。锁存器，则不需要引入停顿。计算机科学与技术系计算机科学与技术系 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DAD

23、D R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 IM Reg OR R10，R1，R11 采用定向技术后的流水线数据通路采用定向技术后的流水线数据通路 计算机科学与技术系计算机科学与技术系工作过程演示计算机科学与技术系计算机科学与技术系w定向的实现EX段和MEM段之间的流水寄存器中保存的ALU运算结果总是回送到ALU的入口。当定向硬件检测到前一个ALU运算结果写入的寄存器就是当前ALU操作的源寄存器时，那么控制逻辑就选择定向的数据作为ALU的输入，而不采用从通用寄存器组读出的数据。1. 在使用直通时，如果DSUB操作被停顿，那么DADD操作

24、将被完整执行，没有必要激活旁路。当两个操作之间有一个中断也是如此。 计算机科学与技术系计算机科学与技术系直通的实现w直通思想可以一般化：可以将结果直接送到需要它的单元，并不限制在同一个单元的输出到输入。计算机科学与技术系计算机科学与技术系并不是所有的数据冲突都可以用定向技术来解决。 举例: LD LD R1R1，0 0（R2R2）DADD R4DADD R4，R1R1，R5R5AND R6AND R6，R1R1，R7R7XOR R8XOR R8，R1R1，R9R9增加流水线互锁机制，插入“暂停”。 作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。 举例：演示A（资源图表示） 演示B（时空

25、图表示）需要停顿的数据冲突计算机科学与技术系计算机科学与技术系 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU LD R1，0(R2) DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 无法将无法将LDLD指令的结果定向到指令的结果定向到DADDDADD指令指令 采用定向无法解决返回返回计算机科学与技术系计算机科学与技术系w依靠编译器解决数据冲突 让编译器重新组织指令顺序来消除冲突，这种技术称为指令调度或流水线调度。计算机科学与技术系计算机科学与技术

26、系调度前的代码调度前的代码 调度后的代码调度后的代码 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 BLD 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举例

27、：举例： 请为下列表达式生成没有暂停的指令序列请为下列表达式生成没有暂停的指令序列: : ABC ； DEF ； 假设载入延迟为假设载入延迟为1 1个个时钟周期。时钟周期。 题解题解计算机科学与技术系计算机科学与技术系w控制冲突 执行分支指令的结果有两种q分支成功：分支成功：PCPC值改变为分支转移的目标地址。值改变为分支转移的目标地址。 在条件判定和转移地址计算都完成后，才改变在条件判定和转移地址计算都完成后，才改变PCPC值。值。q不成功或者失败：不成功或者失败：PCPC的值保持正常递增，的值保持正常递增， 指向顺序的下一条指令。指向顺序的下一条指令。处理分支指令最简单的方法：“冻结冻结”

28、或者或者“排空排空”流水线流水线 优点：优点：简单简单p前述前述5 5段流水线中，改变段流水线中，改变PCPC值是在值是在MEMMEM段进行的。段进行的。 给流水线带来了给流水线带来了3 3个时钟周期的延迟个时钟周期的延迟控制冲突计算机科学与技术系计算机科学与技术系分支指令分支指令 IF IF ID ID EX EX MEM MEM WBWB 分支目标分支目标指令指令 IFIF stallstall stallstall IFIF ID ID EX EX MEM MEM WB WB 分支目标分支目标指令指令+1 +1 IF IF ID ID EX EX MEMMEM WB WB 分支目标分支目

29、标指令指令+2 +2 IF IF ID ID EX EX MEMMEM 分支目标分支目标指令指令+3 +3 IF IF ID ID EX EX 简单处理分支指令：分支成功的情况简单处理分支指令：分支成功的情况 计算机科学与技术系计算机科学与技术系把由分支指令引起的延迟称为分支延迟。分支指令在目标代码中出现的频度q每每3 34 4条指令就有一条是分支指令。条指令就有一条是分支指令。 假设：假设：分支指令出现的频度是分支指令出现的频度是3030 流水线理想流水线理想 CPICPI1 1 那么：那么：流水线的实际流水线的实际 CPI CPI 1.91.9可采取两种措施来减少分支延迟。q在流水线中尽早

30、判断出分支转移是否成功；在流水线中尽早判断出分支转移是否成功；q尽早计算出分支目标地址。尽早计算出分支目标地址。计算机科学与技术系计算机科学与技术系下面的讨论中，我们假设： 这两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。 计算机科学与技术系计算机科学与技术系3种通过软件（编译器）来减少分支延迟的方法 共同点：n对分支的处理方法在程序的执行过程中始终是对分支的处理方法在程序的执行过程中始终是 不变的，是不变的，是静态静态的。（在整个程序的执行过程中对的。（在整个程序的执行过程中对每个转移的处理都是一样的）每个转移的处理都是一样的）n要么总是预测

31、分支成功，要么总是预测分支失败。要么总是预测分支成功，要么总是预测分支失败。q预测分支失败预测分支失败 n允许分支指令后的指令继续在流水线中流动，就允许分支指令后的指令继续在流水线中流动，就 好象什么都没发生似的；好象什么都没发生似的；n若确定分支失败，将分支指令看作是一条普通指若确定分支失败，将分支指令看作是一条普通指 令，流水线正常流动；令，流水线正常流动；计算机科学与技术系计算机科学与技术系n若确定分支成功，流水线就把在分支指令之后若确定分支成功，流水线就把在分支指令之后 取出的所有指令转化为空操作，并按分支目地取出的所有指令转化为空操作，并按分支目地 重新取指令执行。重新取指令执行。要

32、保证：要保证：分支结果出来之前不能改变处理机的状态，以分支结果出来之前不能改变处理机的状态，以 便一旦猜错时，处理机能够回退到原先的状态。便一旦猜错时，处理机能够回退到原先的状态。流水线的处理过程流水线的处理过程计算机科学与技术系计算机科学与技术系转移不成功和转移成功两种情况下的流水线序列计算机科学与技术系计算机科学与技术系q预测分支成功：预测分支成功：假设分支转移成功，并从分支目假设分支转移成功，并从分支目标地址处取指令执行。标地址处取指令执行。q起作用的前题：起作用的前题：先知道分支目标地址，后知道分先知道分支目标地址，后知道分支是否成功。支是否成功。q前述前述5 5段流水线中，这种方法没

33、有任何好处。段流水线中，这种方法没有任何好处。q无论采用预测不成功还是预测成功，编译器都能无论采用预测不成功还是预测成功，编译器都能通过组织代码来实现与硬件的最佳匹配。通过组织代码来实现与硬件的最佳匹配。计算机科学与技术系计算机科学与技术系 不论采用刚才说的哪种策略，编译器都能通过组织代码来实现与硬件的最佳匹配。q延迟分支延迟分支主要思想：主要思想： 从逻辑上从逻辑上“延长延长”分支指令的执行时间。分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干把延迟分支看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。顺

34、序执行延迟槽中的指令。计算机科学与技术系计算机科学与技术系w有些处理器中也称为延迟转移延迟转移，在早期的RISC处理器中被广泛使用。w在被延迟的转移中，转移延迟为1的执行周期如下：转移指令转移指令后续指令后续指令1（放在延迟槽内）（放在延迟槽内）目标地址的指令（如果转移被选中）目标地址的指令（如果转移被选中） w执行过程w虽然延迟槽的长度可以大于1，实际上，所有带转移延迟的处理器一般只延迟一条指令，并使用其它技术来处理更多有关延迟的开销计算机科学与技术系计算机科学与技术系具有一个分支延迟槽的流水线的执行过程分分支支失失败败 分支指令分支指令i i IF IF ID ID EX EX MEM M

35、EM 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分支延迟槽中的指令分支延迟槽中的指令“掩盖掩盖”了流水线原来必需插入的暂停周期。了流水线原来必需插入的暂停周期。分分支支成成功功 分支指令分支指令i i IF IF ID ID EX EX MEMMEMWBWB 延迟槽指令延迟槽指令 i+1

36、i+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计算机科学与技术系计算机科学与技术系任务：在延迟槽中放入有用的指令由编译器完成。能否带来好处取决于编译器能否把有用的指令调度到延迟槽中。三种调度方法： 解决究竟将什么指令装入延迟槽？从前调度（将转移指令之前的指令装入延迟槽）从目标处调度（将转移目标地址处的指令

37、装入延迟槽）从失败处调度（将延迟槽后的指令装入延迟槽）分支延迟指令的调度计算机科学与技术系计算机科学与技术系从前面调度来自前面：将分支指令之前的一条独立指令调度到延迟槽计算机科学与技术系计算机科学与技术系从目标处调度n来自目标地址：将目标来自目标地址：将目标处的指令拷贝到延迟槽同处的指令拷贝到延迟槽同时修改分支指令的目标地时修改分支指令的目标地址。由于从别的路径可能址。由于从别的路径可能也要执行到该指令，所以也要执行到该指令，所以不能简单的移指令，而是不能简单的移指令，而是复制。采用这种方法实际复制。采用这种方法实际上是猜测分支成功，所以上是猜测分支成功，所以对于循环等分支转移成功对于循环等分

38、支转移成功概率较高的采用此方法较概率较高的采用此方法较好好计算机科学与技术系计算机科学与技术系从失败处调度w将延迟槽后的指令装入延迟槽。计算机科学与技术系计算机科学与技术系调度前和调度后的代码计算机科学与技术系计算机科学与技术系三种方法的要求及效果调 度 策 略对调度的要求什么情况下起作用？从从 前前 调调 度度从目标处调度从目标处调度从失败处调度从失败处调度必须保证在分支失败时执行被调度必须保证在分支失败时执行被调度的指令不会导致错误。有可能需要的指令不会导致错误。有可能需要复制指令。复制指令。被调度的指令必须与分支无关被调度的指令必须与分支无关必须保证在分支成功时执行被调度必须保证在分支成

39、功时执行被调度的指令不会导致错误。的指令不会导致错误。任何情况任何情况 分支成功时分支成功时( (但由于复制指令，有但由于复制指令，有可能会增大程序空间可能会增大程序空间) )分支失败时分支失败时计算机科学与技术系计算机科学与技术系分支延迟受到两个方面的限制：q可以被放入延迟槽中的指令要满足一定的条件；可以被放入延迟槽中的指令要满足一定的条件；q编译器预测分支转移方向的能力。编译器预测分支转移方向的能力。进一步改进：分支取消机制（取消分支） 当分支的实际执行方向和事先所预测的一样时，当分支的实际执行方向和事先所预测的一样时，执行分支延迟槽中的指令，否则就将分支延迟槽中的执行分支延迟槽中的指令，

40、否则就将分支延迟槽中的指令转化成一个空操作。此时，转移指令带有对转移指令转化成一个空操作。此时，转移指令带有对转移能否被选中的预测。预测准确时，延迟槽中的指令像能否被选中的预测。预测准确时，延迟槽中的指令像通常一样执行，否则就将延迟槽中的指令变成空操作。通常一样执行，否则就将延迟槽中的指令变成空操作。计算机科学与技术系计算机科学与技术系分分支支不不跳跳转转分支指令分支指令i i IF IF ID ID EX EX MEM MEM WBWB延迟槽指令延迟槽指令 i+1i+1 IF IF ID ID EX EX MEMMEMWBWB指令指令 i+2 i+2 IF IF ID ID EX EX ME

41、M MEM WBWB指令指令 i+3 i+3 IF 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 idleidle idle idle idle idle idleidle分支目标指令分支目标指令j j IF IF ID ID EX EX MEMMEMWBWB分支目标指令分支目标指令j+1 j+1 IF IF ID ID EX EX MEMMEMWBWB分支目标指令

42、分支目标指令j+2j+2IF IF ID ID EX EX MEMMEMWBWB预测分支不转移的情况下，分支取消机制的执行情况预测分支不转移的情况下，分支取消机制的执行情况 从失败处调度从失败处调度5.5 流水线的实现流水线的实现5.5.1 MIPS的一种简单实现的一种简单实现5.5.2 基本的基本的MIPS流水线流水线计算机科学与技术系计算机科学与技术系w实现MIPS指令子集的一种简单数据通路。该数据通路的操作分成5个时钟周期q取指令取指令q指令译码指令译码/读寄存器读寄存器q执行执行/有效地址计算有效地址计算q存储器访问存储器访问/分支完成分支完成q写回写回 只讨论整数指令整数指令的实现（

43、包括：（包括：loadload和和storestore，等于，等于0 0转转移，整数移，整数ALUALU指令等。）指令等。） 5.5.1 MIPS的一种简单实现5.5 流水线的实现计算机科学与技术系计算机科学与技术系计算机科学与技术系计算机科学与技术系设置了一些临时寄存器。其作用如下：qPC：程序计数器，存放当前指令的地址。：程序计数器，存放当前指令的地址。qNPC：下一条程序计数器，存放下一条指令的地址。：下一条程序计数器，存放下一条指令的地址。qIR：指令寄存器，存放当前正在处理的指令。：指令寄存器，存放当前正在处理的指令。qA：第一操作数寄存器，存放从通用寄存器组读出来：第一操作数寄存器

44、，存放从通用寄存器组读出来的操作数。的操作数。qB：第二操作数寄存器，存放从通用寄存器组读出来：第二操作数寄存器，存放从通用寄存器组读出来的另一个操作数。的另一个操作数。qImm：存放符号扩展后的立即数操作数。：存放符号扩展后的立即数操作数。qCond：存放条件判定的结果。为：存放条件判定的结果。为“真真”表示分支成功。表示分支成功。qALUo：存放：存放ALU的运算结果。的运算结果。qLMD：存放：存放load指令从存储器读出的数据。指令从存储器读出的数据。临时寄存器的作用计算机科学与技术系计算机科学与技术系MIPS指令系统结构w寻址方式编码到操作码中w所有的指令都是32位的w操作码占6位w

45、3种指令格式 3种格式中，同名字段的位置固定不变。种格式中，同名字段的位置固定不变。 MIPS的指令格式计算机科学与技术系计算机科学与技术系MIPS指令系统结构rt rs 立立即即数数（immediate） 操操作作码码 6 5 5 16 0 5 6 10 11 15 16 31 I类指令q包括所有的包括所有的loadload和和storestore指令，立即数指令，分支指令，立即数指令，分支指令，寄存器跳转指令，寄存器链接跳转指令。指令，寄存器跳转指令，寄存器链接跳转指令。q立即数字段为立即数字段为1616位，用于提供立即数或偏移量。位，用于提供立即数或偏移量。计算机科学与技术系计算机科学与

46、技术系MIPS指令系统结构qloadload指令指令 访存有效地址：访存有效地址：RegsrsRegsrsimmediateimmediate 从存储器取来的数据放入寄存器从存储器取来的数据放入寄存器rtrtqstorestore指令指令 访存有效地址：访存有效地址：RegsrsRegsrsimmediateimmediate 要存入存储器的数据放在寄存器要存入存储器的数据放在寄存器rtrt中中q立即数指令立即数指令 Regsrt Regsrs op immediateRegsrt Regsrs op immediateq分支指令分支指令 转移目标地址：转移目标地址：RegsrsRegsrsi

47、mmediateimmediate，rtrt无用无用q寄存器跳转、寄存器跳转并链接寄存器跳转、寄存器跳转并链接 转移目标地址为转移目标地址为RegsrsR计算机科学与技术系计算机科学与技术系MIPS指令系统结构R类指令q包括包括ALUALU指令，专用寄存器读指令，专用寄存器读/ /写指令，写指令，movemove指令等。指令等。qALUALU指令指令 Regsrd Regsrs funct RegsrtRegsrd Regsrs funct Regsrt funct funct为具体的运算操作编码为具体的运算操作编码操操作作码码 rs 6 5 5 6 rt 5 rd funct 0 5 6 1

48、0 11 15 16 31 20 21 sham25 26 5 计算机科学与技术系计算机科学与技术系MIPS指令系统结构J类指令q包括跳转指令，跳转并链接指令，自陷指令，异常返回包括跳转指令，跳转并链接指令，自陷指令，异常返回指令。指令。q在这类指令中，指令字的低在这类指令中，指令字的低2626位是偏移量，它与位是偏移量，它与PCPC值相值相加形成跳转的地址。加形成跳转的地址。26 操作码操作码 6 与与 PC 相加的偏移量相加的偏移量 31 0 5 6 计算机科学与技术系计算机科学与技术系w一条MIPS指令最多需要以下5个时钟周期：取指令周期（IF） 操作pIRIRMemPCMemPCpNP

49、CNPCPC+4PC+4指令译码/读寄存器周期（ID） 操作qA A RegsrsRegsrsqB B RegsrtRegsrtImm IR的立即数字段进行符号扩展 指令的译码操作指令的译码操作和和读寄存器操作读寄存器操作是并行进行的。是并行进行的。 原因：在原因：在MIPSMIPS指令格式中，操作码字段以及指令格式中，操作码字段以及rsrs、rtrt 字段都是在固定的位置。这种技术称为字段都是在固定的位置。这种技术称为固定字段译码固定字段译码技术技术。 由于指令的立即数部分在由于指令的立即数部分在MIPS格式中都有相同的位置，格式中都有相同的位置，所以要是下一个时钟周期需要使用立即数，带符号

50、立即所以要是下一个时钟周期需要使用立即数，带符号立即数的符号扩展操作也在当前时钟周期完成。数的符号扩展操作也在当前时钟周期完成。计算机科学与技术系计算机科学与技术系执行/有效地址计算周期（EX） 不同指令所进行的操作不同：qloadload指令和指令和storestore指令指令 操作操作 ALUoALUoA + ImmA + Immq寄存器寄存器寄存器寄存器ALUALU指令指令 操作操作 ALUoALUoA funct BA funct Bq寄存器立即值寄存器立即值ALUALU指令指令 操作操作 ALUoALUoA op ImmA op Immq分支指令分支指令 操作操作 ALUoALUoN

51、PC+NPC+（Imm2Imm2）；）； condcond（A = = 0A = = 0）计算机科学与技术系计算机科学与技术系 将有效地址计算周期和执行周期合并为一个时将有效地址计算周期和执行周期合并为一个时钟周期，这是因为钟周期，这是因为MIPSMIPS指令集采用指令集采用loadloadstorestore结结构，没有任何指令需要同时进行数据有效地址的计构，没有任何指令需要同时进行数据有效地址的计算、转移目标地址的计算和对数据进行运算。算、转移目标地址的计算和对数据进行运算。存储器访问/分支完成周期（MEM）q所有指令都要在该周期对所有指令都要在该周期对PCPC进行更新。进行更新。 除了分

52、支指令，其它指令都是做：除了分支指令，其它指令都是做：PCPCNPCNPCq在该周期内处理的在该周期内处理的MIPSMIPS指令仅仅有指令仅仅有loadload、storestore和分和分支支三种指令。三种指令。计算机科学与技术系计算机科学与技术系qloadload指令和指令和storestore指令指令 操作操作 LMD LMDMemALUo MemALUo 或者或者 MemALUoMemALUoB Bq分支指令分支指令 操作操作 if if （condcond） PC PC ALUo else PCALUo else PCNPCNPC写回周期（WB）不同的指令在写回周期完成的工作也不一样

53、。不同的指令在写回周期完成的工作也不一样。q寄存器寄存器寄存器寄存器ALUALU指令指令 操作操作 RegsrdRegsrd ALUo ALUoq寄存器立即数寄存器立即数ALUALU指令指令 操作操作 RegsrtRegsrt ALUo ALUoqloadload指令指令 操作操作 RegsrtRegsrt LMD LMD计算机科学与技术系计算机科学与技术系MIPS的数据通路的实现计算机科学与技术系计算机科学与技术系每一个时钟周期完成的工作看作是流水线的一段，每个时钟周期启动一条新的指令，就可以使前面的数据通路流水。w流水实现的数据通路设置了流水寄存器 所有用于在同一条指令的各个时钟周期之间保

54、存临时数据的寄存器都要归入流水寄存器这一类中q段与段之间设置流水寄存器段与段之间设置流水寄存器q流水寄存器的名称流水寄存器的名称 用其相邻的两个段的名称拼合而成。用其相邻的两个段的名称拼合而成。 例如：例如：IDID段段与与EXEX段段之间的流水寄存器用之间的流水寄存器用ID/EXID/EX表示表示q每个流水寄存器是由若干个寄存器构成的每个流水寄存器是由若干个寄存器构成的 5.5.2 基本的MIPS流水线计算机科学与技术系计算机科学与技术系 MEM/WB 数据 存储器 通用寄存器组 符号 位 扩展 ALU PC =0? ADD 16 32 4 存储器 分之 结果 M U X 1 M U X 2

55、 M U X 3 M U X 4 IR A B Imm IRrs IRrt MEM/WB.IR NPC NPC IR cond ALUo B IR LMD ALUo IR EX/MEM ID/EX IF/ID 指令 流水实现的数据通路流水实现的数据通路计算机科学与技术系计算机科学与技术系w寄存器的命名形式为：x.yw所包含的字段的命名形式为：x.ys 其中：x：流水寄存器名称 y：具体寄存器名称 s：字段名称 例如： ID/EX.IR：流水寄存器ID/EX中的子寄存器IR IRID/EX.IRop：该寄存器的op字段（即操作码字段）w流水寄存器的作用 将各段的工作隔开，使得它们不会互相干扰。保

56、存相应段的处理结果。计算机科学与技术系计算机科学与技术系w属于IF/ID部分的指令寄存器IR的各个字段，在用于提供寄存器名时就将其标记。qIRrsIRrsIRIR6.106.10qIRrtIRrtIRIR11.1511.15qIRrdIRrdIRIR16.2016.20w流水线寄存器在两个相邻的流水段之间既传递数据也传递控制信息。后面流水段需要的数据，必须能从一个流水寄存器复制到下一个流水寄存器，直到不再需要为止。w所以流水寄存器与非流水通路中使用的临时寄存器不一样。计算机科学与技术系计算机科学与技术系例如：EX/MEM.ALUo：保存EX段ALU的运算结果MEM/WB.LMD：保存MEM段从

57、数据存储器读出的数据q向后传递后面将要用到的数据或者控制信息向后传递后面将要用到的数据或者控制信息 所有有用的数据和控制信息每个时钟周期 会随着指令在流水线中的流动往后流动一段。w 增加了向后传递IR和从MEM/WB.IR回送到通用寄存 器组的连接。w 将对PC的修改移到了IF段，以便PC能及时地加 4，为取下一条指令做好准备。 计算机科学与技术系计算机科学与技术系 MEM/WB 数据 存储器 通用寄存器组 符号 位 扩展 ALU PC =0? ADD 16 32 4 存储器 分支 结果 M U X 1 M U X 2 M U X 3 M U X 4 IR A B Imm IRrs IRrt

58、MEM/WB.IR NPC NPC IR cond ALUo B IR LMD ALUo IR EX/MEM ID/EX IF/ID 指令 流水实现的数据通路流水实现的数据通路计算机科学与技术系计算机科学与技术系w流水线的控制主要是如何控制四个多路选择器。qMUX2(根据指令类型是否是转移操作来设定根据指令类型是否是转移操作来设定)if （ID/EX.IRop=“分支指令分支指令”） MUX2_outputID/EX.NPC ；else MUX2_outputID/EX.A； /MUX2_output表示表示MUX2的输出的输出qMUX3（根据指令类型是（根据指令类型是R-R的的ALU操作还是

59、其他指令来操作还是其他指令来设定）设定）if （ID/EX.IRop=“寄存器寄存器型寄存器寄存器型ALU指令指令”） MUX3_outputID/EX.B ；else MUX3_outputID/EX.Imm； /MUX3_output表示表示MUX3的输出的输出计算机科学与技术系计算机科学与技术系qMUX1if （ID/EX.IRop=“分支指令分支指令”）& EX/MEM.cond） MUX1_outputEX/MEM.ALUo ；else MUX1_outputPC+4； /MUX1_output表示表示MUX1的输出的输出qMUX4if （ID/EX.IRop=“load”）

60、 MUX4_outputMEM/WB.LMD ；else MUX4_outputMEM/WB.ALUo /MUX4_output表示表示MUX4的输出的输出计算机科学与技术系计算机科学与技术系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指令