计算机体系结构：6、指令流水线

6.指令流水线

6.1 流水线概述

6.1.1 流水线的执行效率

一条指令的执行过程可被分为若干阶段，每个阶段由相应的功能部件完成。一般而言，一条指令的流水线由如下5个流水段组成：

取指令(IF):从存储器取指令
指令译码(ID):产生指令执行所需的控制信号
取操作数(OF):读取操作数
执行(EX):对操作数完成指定操作
写回(WB):将结果写回

进入流水线的指令流，由于后一条指令的第 $i$ 步与前一步指令的第 $i + 1$ 步同时进行，从而使一串指令总的完成时间大为缩短。

在这里插入图片描述

图1 五段指令流水线

通常流水线设计的原则是：指令流水段个数以最复杂指令所用的功能段个数为准;流水段的长度以最复杂的操作所花时间为准。容易发现，流水线方式不能缩短一条指令的执行时间，但是对于整个程序来说，流水线方式可以大大增加指令执行的吞吐率。

6.1.2 适合流水线的指令集特征

指令长度尽量一致，有利于简化取指令和指令译码操作。

例如MIPS架构中指令都是32位，每条指令占4个存储单元。
指令格式尽量规整，尽量保证源寄存器的位置相同，这样有利于在按指令未译码时就可取寄存器操作数。

例如MIPS指令格式中，源操作数寄存器Rs和Rt的位置总是固定在 $I R < 25 : 21 >, I R < 20 : 16 >$ ，
采用装入/存储型指令风格，可以保证除 $l o a d / s t ore$ 指令外的其他指令(如运算指令)都不访问存储器。这样可以把 $l o a d / s t ore$ 指令的地址运算和运算指令的执行步骤规整在同一个周期中，有利于减少操作步骤。

6.2 流水线的实现

也是实现之前的11条MIPS指令，用流水线实现

6.2.1 每条指令的流水段分析

每条指令前两个功能段都是一样的

Ifetch:取指并计算PC+4

Reg/Dec:寄存器取数并译码

后面的功能段有所差异

1.R-型指令功能段划分

R-型指令都涉及在ALU中对Rs和Rt内容进行运算，最终把ALU的运算结果送目的寄存器Rd(不溢出)。

那么容易得出R-型指令的功能段划分：

在这里插入图片描述

图2 R-型指令的功能段划分

其中，

Exec：用于在ALU中计算

Write：用于将ALU中的计算结果写回寄存器

2.I-型运算类指令功能段划分

I-型带立即数的运算类指令都涉及对16位立即数进行符号扩展或零扩展，然后和Rs的内容进行运算，最终把ALU的运算结果送目的寄存器Rt，那么功能段划分与R-型相同

3. lw指令功能段划分

lw指令的功能为 $R[Rt]\leftarrow M[R[RS]+SEXT(imm16)]$ ,功能段划分为：

在这里插入图片描述

图3 lw指令的功能段划分

其中，

Exec：用于在ALU中计算地址

Mem：用于从存储期中读数据

Write：用于将数据写入寄存器

4. sw指令功能段划分

sw指令的功能为 $M[R[RS]+SEXT(imm16)]\leftarrow R[Rt]$ ,即把寄存器内容写入存储期中，与lw指令想必，少了一步写寄存器的工作，功能段划分为：

在这里插入图片描述

图4 sw指令的功能段划分

其中，

Exec：用于在ALU中计算

Write：用于将ALU中的计算结果写回寄存器

5. beq指令功能段划分

beq指令的功能为 $if(R[Rs]=R[Rt])then\ PC\leftarrow PC+4+(SEXT(imm16)\times 4)else\ PC\leftarrow PC+4$

除了前面的两个公共功能段(Ifetch,Reg/Dec)外，其后各功能段可以划分为:Exec用于在ALU中做减法以比较是否相等，同时用一个加法器计算转移地址;WrPC功能段用于在比较相等的情况下将转移目标地址写到PC中，因为写入PC的操作(WrPC)比存储期访问操作(Mem)的时间段，所以可以将功能段WrPC向功能段Mem靠，即最后的功能段用Mem表示，在Mem功能段时间内完成PC写入操作，则beq的功能段划分类似sw指令。

6. j指令功能段划分

j指令是无条件转移指令，其功能是直接将目标地址送入PC中，所以，其功能段划分很简单，除了两个公共的功能段外，就只有一个功能段WrPC，其操作时间比Exec段时间短，因而可合并到Exec段。

由以上分析可以看出，最复杂的是lw指令，有5个功能段，其他指令都可以通过加入"空"功能段来向lw指令靠齐。

在插入"空"短时，应遵循两个原则：

每个功能部件每条指令只能使用一次(如寄存器写口不能用两次或以上)
每个功能部件必须在相同的阶段被使用(如寄存器写口总是在第5阶段被使用)

综上，对各个指令做出以下调整：

R-型，I-型，需在Write之前加一个空的Mem段，使得其Write和lw指令的Write对齐
sw,beq指令在第4个功能段后加一个空的Write段
j指令则在后面添加两个空段Mem和Write

这样，该处理器的指令流水线可以设计成5个流水段。

6.2.2 流水线数据通路的设计

基本框架：

在这里插入图片描述

图5 5段流水线数据通路基本框架

在如图所示的数据通路中，每条指令的执行都经历5个流水段：IF、ID、Ex、Mem和Wr，每个流水段都在不同的功能部件中执行。流水段之间有一个流水段寄存器，例如，IF/ID寄存器是介于IF段和ID段之间的寄存器。每个流水段寄存器用来存放从当前流水段传到后面所有流水段的信息(控制信号之类的)。

图5中列出了所有的控制信号，注意到PC和各个流水段寄存器都没有写使能信号，这是因为每个时钟都会改变PC和流水段寄存器的值，所以不需要。此外，前两个流水段的功能每条指令都相同，是公共流水段，因此，也不需要控制信号。其余段的控制信号如下:

Exec段：

ExtOp(扩展器操作):1-符号扩展;0-零扩展
ALUSrc(ALU的B口来源):1-来源于扩展器；0-来源于busB
ALUop(用于辅助局部ALU控制逻辑来决定ALUctr的操作信号):3位编码
RegDst(指定目的寄存器)：1-Rd;0-Rt
R-type(区分是否为R-型指令)：1-R型指令;0-非R型指令

Mem段：

MemWr(数据存储期DM的写信号):sw指令时为1，其他指令为0
Branch(分支指令信号):分支指令时为1，其他指令为0
Jump(是否为无条件转移指令):无条件转移指令为1，其他指令为0

Wr段：

MemtoReg(寄存器的写入源):1-DM输出;0-ALU输出
RegWr(寄存器堆写信号):写寄存器的指令为1，其他为0

1. Ifetch(IF)段

IF流水段的功能是：将PC的值作为地址到指令存储器IM(instruction memory)中取指令，并计算PC+4，送PC输入端。这些功能由取指部件(IUnit)来完成，具体实现如图：

在这里插入图片描述

图6 取指令部件IUnit的内部实现

取指令的通路是容易的，对于PC的更新，在该部件实现加4的操作后进入一个多路选择器，根据控制信号来决定是否要转移。

IF段执行的结果被送到IF/ID寄存器的输入端，下个时钟到来时，在IF/ID寄存器输入端的信息开始送到ID段继续被处理。

IF/ID寄存器中需要保存的：

IM中取出的指令
PC+4(分支指令在后续计算目标地址时会用到)
PC[31:28] (J指令需要使用)

此外，该段的多路选择器的控制信号由Mem段产生的Branch信号和Zero标志，以及Jump信号来控制。

2. Reg/Dec(ID)段

ID流水段的功能是:根据指令中的Rs和Rt的值到寄存器堆中取出相应寄存器的值，同时对指令中的操作码OP字段进行译码，生成相应的控制信号。寄存器堆有写口和读口。

该阶段可以将IF/ID寄存器中传递过来的PC[31:28]与指令中的低26位(J-型指令中的target字段)进行拼接，最后再添两个0，得到无条件转移目标地址Jtarg。

ID段执行结果被送到ID/EX寄存器的输入端，下个时钟到来时，在输入端的信息开始送到Ex段继续被处理。这些信息包括PC+4、Jtarg、func、imm16、R[Rs]、R[Rt]、Rt、Rd，指令包含的信息均已被保存，故不需要保存指令

3. Exec(Ex)段

执行部件的示意图:

在这里插入图片描述

图7 执行部件exec unit的内部实现

Ex流水段每条指令的执行流程及其控制信号取值如下：

R-型指令的执行

在ALU中由ALUctr控制分别执行对应运算，ALUctr是由局部ALU控制器根据func字段产生，R-型指令的目的寄存器是Rd，ALU的操作数来自busA和busB，不需要扩展操作，最终将ALU得到的结果ALUout以及Overflow标志和Zero标志输出到Ex/Mem的输入端

综上，控制信号为RegDst=1，ExtOp=x，ALUsrc=0，ALUop=xxx，R-type=1
I-型指令的执行

ALUctr控制信号是由ALUop产生的，I-型指令的目的寄存器是Rt，ALU的操作数来自busA和扩展器的输出，逻辑运算进行零扩展，算术运算则为符号扩展。输出与R-型类似

综上

ori控制信号为RgeDst=0，ExtOp=0，ALUSrc=1，ALUop=or，R-type=0

addiu指令控制信号为RegDst=0,ExtOp=1,ALUSrc=1,ALUop=addu,R-type=0
lw指令的执行

首先要在ALU中进行地址计算，ALU的操作数来自busA和扩展器输出，采用符号扩展，在ALU中由ALUctr控制执行addu运算，目的寄存器是Rt，输出同样的信号

综上，控制信号为RegDst=0，ExtOp=1，ALUSrc=1，ALUop=addu，R-type=0
sw指令的执行

同lw指令一样，需要进行地址计算并送到下一级流水线寄存器，因为该指令不会写结果到寄存器，所以RegDst是任意的

综上，控制信号为RegDst=x，ExtOp=1,ALUSrc=1,ALUop=addu,R-type=0
beq指令的执行

beq需要做减法生成Zero标志来实现比较，则ALU的操作数是busA和busB，ALUctr为subu;同时，将imm16送到扩展器，然后再ExtOp的控制下进行符号扩展，扩展结果左移两位，再和PC+4相加(使用Adder)，生成分支转移目标地址(Btarg)。与sw类似，不会更改寄存器的值，所以RegDst是任意的

综上，控制信号为RegDst=x，ExtOp=1，ALUSrc=0，ALUop=subu，R-type=0
j指令的执行

只需要将转移地址 $J t a r g = PC < 31 : 28 > ∣∣ t a r g e t < 25 : 0 > ∣∣00$ ，直接传送到EX/Mem寄存器的输入端即可，控制信号为RegDst=x,ExtOp=x,ALUSrc=x,ALUop=xxx,R-type=x

4. Mem段

控制信号取决于具体指令：

R-型或I-型指令

则在Mem段是空操作，只需要把相应信息继续传递到下一个流水段即可

控制信号为Branch=Jump=MemWr=0
lw指令

进行取数操作，在EX段得到的地址被送到DM的读地址端RA，经过一段存储时间，数据从DM的输出端Do送到Mem/Wr寄存器的输入端

控制信号为Branch=Jump=MemWr=0
sw指令

进行存数操作，在Ex段得到的地址被送到DM的写地址端WA，同时把要存的数据R[Rt]送DM的输入端Di，经过一段存取时间后，数据被存入DM中。控制信号取值为Branch=Jump=0，MemWr=1。
beq指令

若Ex段生成的Zero为1，则将Btarg送PC输入端，控制信号为Branch=1，Jump=MemWr=0
j指令

将Jtarg送PC输入端，控制信号为Branch=0，Jump=1，MemWr=0

5.Wr段

寄存器写地址端Rw来源于Mem/Wr寄存器的目的寄存器输出，写数据端口Di来源于一个多路选择器的输出，写使能信号WE=!Overflow&RegWr,

R-型、I-型指令

选择将ALU的输出结果送入Di，目的寄存器送入Rw

控制信号为MemtoReg=0，RegWr=1
lw指令

将DM读出结果送入Di，目的寄存器送入Rw

控制信号为MemtoReg=1，RegWr=1
sw、beq、j指令

任何寄存器的值都不改变

控制信号为MemtoReg=x,RegWr=0

6.2.3 流水线控制器的设计

由于流水线的形式，则控制信号在每一段中都可能不一样，传递过程如图所示：

在这里插入图片描述

图8 控制信号在流水线中的传递

则每个流水段寄存器中保存的信息包括两类：

一类是后面阶段需要用到的所有数据信息，包括PC+4、立即数、目的寄存器等
另一类是前面传递过来的后面各阶段要用到的所有控制信号

流水线中的控制信号一旦在Reg/Dec(ID)阶段由控制器生成，就不会改变，并和数据信息同步地一次传递到后面的流水段中。

6.3 流水线冒险及其处理

一些指令的组合可能会导致流水线无法正确执行后续指令而引起流水线阻塞或停顿(stall)，这种现象称为流水线冒险(hazard)。

根据导致冒险的原因不同，有结构冒险，数据冒险，控制冒险3种

6.3.1 结构冒险

结构冒险也称为硬件资源冲突，引起结构冒险的原因在于同一个部件同时被不同指令所用，也就是说它是由硬件资源竞争造成的。

例如，若不区分指令存储期和数据存储期而只使用一个存储器时，在load指令取数据的同时，随后的第三条指令instr3正好在取指令，冲突了。类似地，如果不对寄存器堆的写口和读口独立设置的话，load和instr3也会发生寄存器访问冲突

在这里插入图片描述

图9 有寄存器和存储期访问冲突的流水线

解决策略：

遵循功能段划分原则：一个部件每条指令只能使用一次，且只能在特定时钟周期使用，可以避免一部分结构冒险。
通过设置多个独立的部件来避免硬件资源冲突。例如：对于寄存器访问冲突，可将读口和写口独立开来，利用同一个时钟周期的上升沿和下降沿两次除法，使得前半周期用写口写，后半周期用读口读；对于存储器访问冲突，可将存储器分为IM和DM。

6.3.2 数据冒险

数据冒险也称为数据相关。引起数据冒险的原因在于后面指令用到前面指令的结果时前面指令结果还没产生。

例如：

在这里插入图片描述

图10 存在数据冒险的流水线

在图10中，第一条指令的结果在Wr时才存到$1中，但紧接着的sub、or、add在Reg后半段就要读出来。我们发现，一条指令是可能与紧随着它的后三条指令相关的，且所有的数据冒险都是由于前面指令写结果之前后面的指令就需要读而造成的，这种数据冒险称为写后读(read after write,RAW),在非乱序执行的基本流水线中，所有数据冒险都属于RAW数据冒险。

可采用以下措施：

1.插入空操作指令

在编译时预先插入空操作指令nop，好处是硬件控制简单，但浪费了指令存储空间和指令执行时间。

2.插入气泡

在硬件上采取措施，使相关指令延迟执行，通过硬件阻塞(stall)方式组织后续指令执行。这种硬件阻塞的方式称为插入气泡(bubble)。不增加指令条数，但有额外时间开销

3.转发技术

将数据通路中生成的中间数据直接转发到ALU的输入端，实际上，add指令在Ex段结束时就已经得到$1的新值，被存放在Ex/Mem流水段寄存器，因此，可以直接从该流水段寄存器中取出数据送到ALU的输入端。

在这里插入图片描述

图11 用转发技术解决数据冒险

采用转发技术必须在硬件上进行相应改动，通过在ALU的输入端加多路选择器，使Ex段之后的流水段寄存器的值能返送到ALU输入端。

ALU的A口原来只有ID/Ex寄存器来的busA，B口原来只有从ID/Ex寄存器来的busB和扩展器的值，采用转发技术后，都增加了3个可能的输入，他们分别来自前1条，前2条，前3条的ALU输出。

在这里插入图片描述

通过在ALU加入多路选择器，可以解决相邻两条ALU运算、相隔一条的两个ALU运算之间，以及相隔一条的load和ALU运算指令间的数据冒险都可以解决了。

若前面指令的目的寄存器和随后sw指令的源寄存器发生数据相关，例如，相邻两条指令为"add $3,$2,$1"和"sw $3,0($1)"，则转发线路不能解决问题，可以类似的，在DM的数据输入端Di处增加一个多路选择器，当出现这种数据冒险是，选择上条指令(即较早的一次存)执行阶段产生的ALU结果作为Di的输入值。

P179(pdf194) ALU的控制信号具体讲解

4. load-use 数据冒险

在这里插入图片描述

图12 load-use数据冒险

lw指令只有在Mem段结束时才能得到DM中的结果，然后送Mem/Wr寄存器，在Wr段前半周期才将新值存入$1,但随后的sub在Ex阶段就要取$1的值。但根据之前的ALU的更改，输入端要么来自上条指令在Ex段生成且存在Ex/Mem寄存器中的值，要么来自上上条指令的执行结果，因此用转发线路无法解决这个数据相关问题。通常把这种情况称为load-use数据冒险

一般我们是在编译时进行优化，通过调整指令顺序避免出现load-use现象。可将至少一条无关指令插入load和R-型指令间来优化代码。

使用硬件来处理load-use冒险：必须在数据通路中增加load-use冒险检测部件(p182)