计组学习笔记4

流水线技术

流水线技术的基本思想是：

把一个重复执行的过程分解为若干个子过程，每个子过程由专门的功能部件完成，多个任务在时间上错开，依次经过各个功能段。这样不同任务的不同阶段就可以并行执行

流水线中的每个子过程称为流水线的级或段

流水线的段数称为流水线的深度

指令流水线就是把指令执行过程分成若干段，使多条指令重叠执行

比如 MIPS 经典五段流水线：

IF：取指令
ID：译码和读寄存器
EX：执行或地址计算
MEM：访问数据存储器
WB：写回寄存器

流水线并不能减少单条指令的执行时间

但流水线提高了吞吐率，即单位时间完成的指令数

流水线特点

流水线有几个基本特点：

各段时间应尽量相等，否则最慢的段会成为瓶颈
每个功能部件后面需要流水段寄存器，用于保存本段输出，并隔离相邻阶段
流水线适合大量重复任务
流水线需要建立时间和排空时间

第一个任务从进入流水线到输出结果的时间称为通过时间
最后一个任务进入流水线后，直到流水线完全空掉的时间称为排空时间

如果任务数量很少，流水线建立和排空开销占比大，效果不明显

只有任务源源不断进入时，流水线才能接近理想吞吐率

流水线分类

按功能可以分为：

单功能流水线：只完成一种功能
多功能流水线：能完成多种功能

按同一时刻是否能处理多种功能：

静态流水线：同一时刻只能完成一种功能
动态流水线：同一时刻可处理多种功能

按连接方式：

线性流水线：各段按固定顺序连接
非线性流水线：段之间有反馈回路

按输出顺序：

顺序流水线：输出顺序和输入顺序一致
乱序流水线：输出顺序可能和输入顺序不同

流水线性能

流水线常用性能指标包括吞吐率、加速比和效率

吞吐率

吞吐率表示单位时间内流水线完成的任务数： \[ TP=\frac{n}{T_k} \]

其中 $n$ 是任务数，$T_k$ 是完成 $n$ 个任务所花的总时间

如果流水线有 $k$ 段，每段时间相等，为 $\Delta t$，完成 $n$ 个任务需要： \[ T_k=(k+n-1)\Delta t \]

当 $n$ 很大时，理想情况下流水线每个周期完成一个任务，则当 $n \gg k$ 时： \[ TP\approx\frac{1}{\Delta t} \] 如果每段时间不相等，时钟周期由最长段决定：

如果各段时间不相等，时钟周期必须由最长段决定： \[ \Delta t=\max(\Delta t_i) \]

\[ TP = \frac{n}{\Sigma_{i=1}^k \Delta t_i + (n-1)\max(\Delta t_i)} \approx \frac{1}{\max(\Delta t_i)} \]

加速比

加速比为： \[ S=\frac{T_s}{T_k} \]

其中 $T_s$ 是不使用流水线完成同样任务的时间，$T_k$ 是使用流水线后的时间

如果非流水方式执行 $n$ 个任务，每个任务经过 $k$ 段，每段 $\Delta t$，则： \[ T_s=nk\Delta t \]

所以： \[ S=\frac{nk\Delta t}{(k+n-1)\Delta t}=\frac{nk}{k+n-1} \]

当 $n\gg k$ 时： \[ S\approx k \]

也就是说，理想加速比接近流水线段数

当个段时间不相等时，非流水时间为： \[ S = \frac{n\Sigma_{i=1}^k \Delta t_i}{\Sigma_{i=1}^k \Delta t_i + (n-1)\max(\Delta t_i)} \approx \frac{\Sigma_{i=1}^k \Delta t_i}{\max(\Delta t_i)} \]

效率

效率表示流水线设备的利用率： \[ E=\frac{T_s}{kT_k} \]

对于各段时间相等的理想流水线： \[ E=\frac{n}{k+n-1} \]

当 $n\gg k$ 时，效率接近 1

此时短段会等待长段，流水线效率下降： \[ E=\frac{n\Sigma_{i=1}^k \Delta t_i}{k(\Sigma_{i=1}^k \Delta t_i + (n-1)\max(\Delta t_i))} \approx \frac{\Sigma_{i=1}^k \Delta t_i}{k\max(\Delta t_i)} \]

瓶颈处理

流水线瓶颈来自时间最长的阶段。

常见处理方式：

细分瓶颈段
重复设置瓶颈段

细分瓶颈段是把慢阶段拆成多个更短阶段

重复设置瓶颈段是增加多个同类功能部件，让多个任务并行通过瓶颈资源

但流水线不能无限加深，因为流水段寄存器有额外开销，包括：

建立时间
时钟到输出延迟
时钟偏移

当时钟周期短到主要由这些额外开销组成时，继续加深流水线就没有意义了

流水线提高吞吐率，但通常不会缩短单个任务的响应时间
一条 lw 在五段流水线中仍然要经过 IF、ID、EX、MEM、WB 五个周期
如果考虑流水段寄存器开销，单条指令延迟甚至可能比非流水实现更长
流水线真正带来的好处是多条指令重叠执行
稳定状态下，第 $i$ 条指令在 EX 阶段时，第 $i+1$ 条可能在 ID 阶段，第 $i+2$ 条可能在 IF 阶段
所以平均看，每个周期可以完成一条指令

适合流水线的指令集

规整、简单、一致的指令集更适合流水线

MIPS 适合流水线，原因包括：

指令长度固定，都是 32 位
指令格式少，字段位置规整
源寄存器 rs 和 rt 位置固定
只有 load/store 指令访问内存
内存数据按边界对齐

固定长度指令使取指简单

字段位置固定使译码阶段在不知道具体指令功能前，就能先读寄存器

load-store 结构使普通 ALU 指令不需要访存，执行阶段更规整

相比之下，x86 指令长度可变，操作数可能来自内存，寻址方式复杂，所以流水线前端和译码会复杂得多。

五段 MIPS 流水线

经典 MIPS 五段流水线为：

阶段	名称	功能
IF	Ifetch	取指令，计算 PC+4
ID	Reg/Dec	指令译码，读寄存器
EX	Exec	ALU 运算，地址计算，分支比较
MEM	Mem	数据存储器读写
WB	Wr	写回寄存器

为了使流水线规整，所有指令都按五个阶段流动

某些指令不需要某一阶段，就在该阶段执行 NOP

比如 R 型指令实际上不需要 MEM 阶段，但仍然保留一个空的 MEM 阶段，使写回都统一在 WB 阶段

为什么要统一为五段

如果 R 型指令在第 4 阶段写回，而 lw 在第 5 阶段写回，那么连续指令可能在同一个周期争用寄存器堆写口

为了避免这种结构冒险，规定所有会写寄存器的指令都在 WB 阶段写回

所以 R 型指令的 MEM 阶段是空操作

类似地，sw 不需要 WB，也保留一个空的 WB 阶段

流水线设计中，“规整”比单条指令少走一个阶段更重要

Load 指令

1	lw rt, imm(rs)

五段为：

IF：取指令，计算 PC+4
ID：读 rs，读 rt，立即数扩展
EX：计算地址 R[rs]+SignExt(imm16)
MEM：读数据存储器
WB：把数据写回 rt

每条 lw 本身仍然需要五个周期完成

但流水线稳定后，每个周期都可以有一条指令进入流水线，也可以有一条指令完成

R 型指令

R 型指令如：

1	add rd, rs, rt

阶段如下：

IF：取指令
ID：读 rs、rt
EX：ALU 运算
MEM：空操作
WB：写回 rd

R 型指令本来只需要四个有效阶段

但为了避免它和 lw 在不同阶段竞争寄存器写口，把写回统一安排在第 5 阶段

Store 指令

1	sw rt, imm(rs)

IF：取指令
ID：读 rs、rt
EX：计算存储器地址
MEM：把 rt 的值写入数据存储器
WB：空操作

sw 不写寄存器，所以 WB 阶段为空

Branch 指令

1	beq rs, rt, label

IF：取指令
ID：读 rs、rt
EX：比较两个寄存器，并计算分支目标
MEM：根据分支结果更新 PC
WB：空操作

如果把分支判断和目标地址计算提前到 ID 阶段，可以减少控制冒险代价

但这样会增加 ID 阶段硬件，并可能引入新的数据相关处理

五段中每段的硬件使用

按功能部件看：

IF 使用指令存储器和 PC+4 加法器
ID 使用寄存器堆读口和主控制器
EX 使用 ALU、扩展器和分支目标加法器
MEM 使用数据存储器
WB 使用寄存器堆写口

为了避免结构冒险，每个部件应只在固定阶段使用

比如 ALU 总在 EX 阶段使用，数据存储器总在 MEM 阶段使用

这也是 MIPS load-store 结构适合流水线的重要原因

流水线五个阶段

Ifetch(IF) 段

IF 阶段的主要功能是取指和计算 PC+4，这个步骤由取指部件完成：

假设当前 PC 为 12，当时钟 CLK 的下降沿来时，PC 输入端经过 clk-to-Q 时延后，送到 IM 地址的输入端 Ad，并同时送到加法器 Adder，Adder 另一个输入端为 4

加法器的结果保存到 IF/ID 寄存器中，并且 IM 截取的部分指令字也保存到 IF/ID 寄存器中：

IM 截取指令字：PC 高四位 PC[31:28] 计算无条件跳转目标地址(Jtarg)
加法器结果：PC 用来后续计算分支跳转目标地址(Btarg)

Adder 结果 PC+4 会和后续的分支/跳转指令的目标一起汇入一个多路选择器 MUX，最终送到 PC 输入端

Reg/Dec(ID) 段

ID 阶段的主要功能是指令译码和寄存器读操作：

上一步 IF 阶段的输出保存在 IF/ID 寄存器中，ID 阶段从 IF/ID 寄存器读取指令字，并根据指令格式解析出对应的 Rs 和 Rt 字段，送到寄存器堆 RFile 的输入端 Ra 和 Rb，读取出寄存器中的值 R[Rs] 和 R[Rt]，送到 ID/EX 寄存器中

此外，针对 I 型指令，还需要保存 Rt 字段，针对 R 型指令，还需要保存 Rd 字段，此外，解析 func 和 imm16，送到 ID/EX 寄存器中

保存 PC+4，以便后续分支指令计算分支目标地址

针对跳转指令，还需要保存 Jtarg，此处可以对 Jtarg 进行计算，PC[31:28]||target||00

把这些信息保存到 ID/EX 寄存器中，供后续 EX、MEM、WB 阶段使用

Exec(EX) 段

EX 阶段的主要功能是 ALU 运算、地址计算和分支比较：

针对不同的指令类型，这一段的功能不同：

R-型指令的执行

add，sub，subu，slt，sltu 都是 R 型指令，通过控制信号 ALUctr 控制执行运算，该控制信号来自局部 ALU 控制器通过先前解析的 func 字段产生，并取出先前解析的 R 型指令目的寄存器 Rd

ALU 运算的输入端来自 bus A 和一个复用器，对于该复用器的控制信号为 ALUSrc，实际输入为 bus B

ALU 运算的结果 ALUout 和 Overflow，Zero 一起送到寄存器 Ex/Mem

这种情况控制信号：

RegDst = 1
ExtOp = x
ALUSrc = 0
ALUop = xxx
R-type = 1

I-型指令的执行

ori 和 addiu 时 I 型指令，通过控制信号 ALUctr 控制执行运算，该控制信号由主控制器根据指令操作码 OP 字段产生，并取出 I 型指令的目的寄存器 Rt

ALU 运算的输入端来自 bus A 和一个复用器，对于该复用器的控制信号为 ALUSrc，实际输入为 imm 16 通过扩展器进行零扩展或者符号扩展后的结果

ALU 运算的结果 ALUout 和 Overflow，Zero 一起送到寄存器 Ex/Mem

这种情况控制信号：

RegDst = 0
ExtOp = 0
ALUSrc = 1
ALUop = or
R-type = 0

lw 指令的执行

在 ALU 中进行地址计算，操作数来自 busA 和扩展器输出，采用符号扩展

ALU 中由 ALUctr 控制执行 addu 运算，目的寄存器 Rt

ALU 运算的结果 ALUout 和 Overflow，Zero 一起送到寄存器 Ex/Mem

这种情况控制信号：

RegDst = 0
ExtOp = 1
ALUSrc = 1
ALUop = addu
R-type = 0

sw 指令的执行

在 ALU 中进行地址计算，操作数来自 busA 和扩展器输出，采用符号扩展

ALU 中由 ALUctr 控制执行 addu 运算，无目的寄存器

ALU 运算的结果 ALUout 和 Overflow，Zero 一起送到寄存器 Ex/Mem

这种情况控制信号：

RegDst = x
ExtOp = 1
ALUSrc = 1
ALUop = addu
R-type = 0

beq 指令的执行

为了比较寄存器 Rs 和 Rt 的值，在 ALU 中做减法生成 Zero 标志实现比较

ALU 操作数来源为 busA 和 busB

ALU 中由 ALUctr 控制执行 subu 运算，

同时讲 imm16 送到扩展器在 ExtOp 控制下执行符号扩展，将结果左移两位，和 PC+4 相加，生成目的地址（Btarg）

将 Zero 标志和 Btarg 送到寄存器 Ex/Mem

这种情况控制信号：

RegDst = x
ExtOp = 1
ALUSrc = 0
ALUop = subu
R-type = 0

j 指令的执行

之前已计算过 Jtarg，直接送到寄存器 Ex/Mem

这种情况控制信号：

RegDst = x
ExtOp = x
ALUSrc = x
ALUop = xxx
R-type = x

Mem 段

Mem 段功能主要是访问数据存储单元：

针对不同的指令类型，这一段的功能不同：

R-型指令的执行和 I-型指令的执行

Mem 段为空，把信息传到下一段

控制信号：

Branch = 0
Jump = 0
MemWr = 0

lw 指令的执行

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

控制信号：

Branch = 0
Jump = 0
MemWr = 0

sw 指令的执行

进行存数操作，Ex 段得到的地址被送到数据存储器 DM 写地址端 WA，同时把 Ex/Mem 寄存器送来的要存的数据R[Rt]送 DM的输入端 Di，经过一段存取时间后，数据被存入 DM

控制信号：

Branch = 0
Jump = 0
MemWr = 1

beq 指令的执行

当 Ex 段生成的 Zero 为 1，则控制多路选择器选择将转移目标地址 Btarg 送 PC 输入端

控制信号：

Branch = 1
Jump = 0
MemWr = 0

j 指令的执行

则控制将 Ex/Mem 流水段寄存器传送过来的转移目标地址 Jtarg 送 PC 的输入端

控制信号：

Branch = 0
Jump = 1
MemWr = 0

Wr 段

Wr 的主要功能时写地址

RFile 写地址端口 Rw 来自 Mem/Wr 寄存器的目的寄存器输出，写数据端口 Di 来源于多路选择器输出

写使能新号 WE 由 Overwrite 和 RegWr 共同决定

如果是 R 型或者 I 型运算指令，将 ALU 输出结果送到寄存器堆的输入端 DI，目的寄存器松写地址端 Rw

控制信号：

MemtoReg = 0
RegWr = 1

如果是 lw 指令，将数据存储器读出的值送到寄存器堆的输入端 DI，目的寄存器松写地址端 Rw

控制信号：

MemtoReg = 1
RegWr = 1

如果是 sw、beq、j 等指令，不写寄存器堆

控制信号：

MemtoReg = x
RegWr = 0

流水段寄存器

五段流水线需要在相邻阶段之间放流水段寄存器：

IF/ID
ID/EX
EX/MEM
MEM/WB

流水段寄存器保存两类信息：

后续阶段需要的数据
后续阶段需要的控制信号

IF/ID 要保存：

指令字
PC+4

ID/EX 要保存：

Reg[rs]
Reg[rt]
扩展后的立即数
rt
rd
PC+4
EX、MEM、WB 阶段需要的控制信号

EX/MEM 要保存：

ALU 结果
Zero 标志
分支目标地址
写入内存的数据
目的寄存器编号
MEM、WB 阶段控制信号

MEM/WB 要保存：

数据存储器读出的值
ALU 结果
目的寄存器编号
WB 阶段控制信号

流水段寄存器对程序员透明，不属于体系结构可见状态

数据必须跟着指令走

流水线中一个常见错误是只传数据，不传目的寄存器编号

例如 lw 的目的寄存器是 rt 字段

这个字段在 ID 阶段就能取出，但真正写回发生在 WB 阶段

如果不把 rt 从 ID/EX 传到 EX/MEM，再传到 MEM/WB，WB 阶段就不知道该写哪个寄存器

因此流水段寄存器不只是保存计算结果，也要保存后续阶段需要的“身份信息”

类似地，控制信号也必须跟着对应指令走

否则某条指令的 RegWrite 可能误控制另一条指令的写回

流水线控制信号

IF 和 ID 阶段对所有指令基本相同，所以通常不需要根据指令产生特殊控制信号

主要控制信号集中在 EX、MEM、WB 三个阶段

EX 阶段信号：

ExtOp：立即数符号扩展还是 0 扩展
ALUSrc：ALU 第二操作数来自寄存器还是立即数
ALUOp：ALU 操作类型
RegDst：目的寄存器选 rd 还是 rt
R-type：是否为 R 型指令

MEM 阶段信号：

MemWr：是否写数据存储器
Branch：是否为分支指令

WB 阶段信号：

MemtoReg：写回数据来自内存还是 ALU
RegWr：是否写寄存器堆

控制信号的传递

流水线中，控制信号在 ID 阶段统一产生

但不同信号在后续不同阶段才会使用

例如 lw：

EX 控制信号在 1 个周期后使用
MEM 控制信号在 2 个周期后使用
WB 控制信号在 3 个周期后使用

所以控制信号也必须像数据一样，保存在流水段寄存器中逐段传递

这点和单周期处理器不同

单周期中一条指令的控制信号在整个周期内使用完；流水线中同一时刻有多条指令，不同阶段使用的是不同指令的控制信号

分段控制表

可以把控制信号按使用阶段分成三组：

阶段	控制信号	用途
EX	`ExtOp`	控制立即数扩展方式
EX	`ALUSrc`	选择 ALU 第二操作数
EX	`ALUOp`	决定 ALU 运算类型
EX	`RegDst`	选择目的寄存器编号
MEM	`MemWr`	控制数据存储器写
MEM	`Branch`	控制分支 PC 选择
WB	`MemtoReg`	选择写回数据来源
WB	`RegWr`	控制寄存器堆写

ID 阶段产生全部控制信号后，可以把它们打包送入 ID/EX

之后每过一个时钟，剩余控制信号继续向后传递。

例如进入 EX/MEM 时，EX 阶段控制信号已经使用完，只需要继续携带 MEM 和 WB 控制信号

进入 MEM/WB 时，只剩 WB 控制信号还要用

流水线冒险

冒险是指流水线中出现无法正确执行后续指令，或者执行了不该执行的指令的情况

常见三类：

结构冒险
数据冒险
控制冒险

结构冒险

结构冒险是硬件资源冲突

也就是说，同一个功能部件在同一个周期被多条指令同时使用

例子：

指令取指和 lw 数据读取共用一个存储器
寄存器堆读口和写口没有分开
R 型指令和 lw 在不同阶段同时写寄存器

解决方法：

指令存储器和数据存储器分开
寄存器堆设置独立读口和写口
规定每类功能部件只在固定阶段使用
必要时增加功能部件

MIPS 五段流水线中，ALU 总在 EX 阶段使用，数据存储器总在 MEM 阶段使用，寄存器写回总在 WB 阶段使用

这样结构比较规整，容易避免结构冒险

指令存储器和数据存储器分开的原因

如果只有一个统一存储器，则某个周期内：

一条指令在 IF 阶段要取指
另一条 lw/sw 在 MEM 阶段要访存

这两者会同时访问同一个存储器，产生结构冒险

把指令存储器 IM 和数据存储器 DM 分开，就能让 IF 和 MEM 同时进行

实际现代处理器中，这通常对应分离的 I-cache 和 D-cache

读写寄存器分开

如果寄存器堆只有一个读写口，那么同一周期内：

一条指令在 ID 阶段要读寄存器
另一条指令在 WB 阶段要写寄存器

这两者会同时访问寄存器堆，产生结构冒险

这个时候采取在时钟上升沿和下降沿两次触发，使得前半周期使用写口进行寄存器写，后半段使用读口进行寄存器读

数据冒险

数据冒险是后面指令需要前面指令的结果，但前面指令结果尚未产生或尚未写回

最常见的是 RAW：

Read After Write，写后读

例子：

add r1, r2, r3
sub r4, r1, r3
or  r8, r1, r9
add r6, r1, r7
xor r3, r1, r5

sub 要读 r1，但 add 的结果还没写回

三种名字相关经常一起出现：
RAW：写后读，后面指令读前面指令将要写的值
WAR：读后写，后面指令写前面指令尚未读取的位置
WAW：写后写，两条指令写同一位置，写回顺序不能乱
五段顺序流水线中，指令按序发射、按序经过各阶段，读总在 ID，写总在 WB，因此 WAR 和 WAW 不会发生
但在乱序执行中，后面的指令可能先写回，WAR 和 WAW 就必须通过寄存器重命名、ROB 等机制处理

硬件阻塞

可以通过阻塞解决数据冒险，延迟到有新值之后执行

阻塞也叫插入气泡 Bubble

硬件保持 PC 和 IF/ID 不变，同时把后续控制信号清 0

软件插入无关指令

让某个阶段执行 NOP，编译器插入三条 NOP 指令

软件也可以插入 nop 指令

这是最差的做法，浪费了三条指令的空间和时间

好处：数据通路简单

寄存器堆先写后读

如果寄存器堆在一个周期前半段写，后半段读，那么同一周期内前面指令写回的数据可以被后面指令直接读出

这能解决一部分数据冒险，但不能解决紧邻指令之间的相关

转发也叫旁路

思想是：前面指令的结果虽然还没写入寄存器堆，但已经存在于流水段寄存器 EX/MEM 中

因此可以直接从流水段寄存器把结果送到 ALU 输入端

需要在 ALU 输入端增加多路选择器，并增加转发检测逻辑：

常见转发来源：

EX/MEM 流水段寄存器
MEM/WB 流水段寄存器

转发目标：

ID/EX 中当前指令的 rs
ID/EX 中当前指令的 rt

转发对执行部件的改动

原始流水线中，ALU A 输入只来自 ID/EX 中保存的 busA

加转发后，ALU A 输入至少需要三选一：

00：来自 ID/EX 的 busA
10：来自 EX/MEM 的 ALU 结果
01：来自 MEM/WB 的写回结果

ALU B 输入更复杂，因为它本来还要在寄存器 busB 和立即数之间选择

因此可以把原来的二选一 MUX 扩展为四选一：

来自 ID/EX 的 busB
来自 EX/MEM 的 ALU 结果
来自 MEM/WB 的写回结果
来自扩展立即数

这就是 ALUSrcA 和 ALUSrcB 的位数增加的原因

转发条件

设当前进入 EX 阶段的指令源寄存器为：

ID/EX.RegisterRs
ID/EX.RegisterRt

前一条指令的目的寄存器在：

EX/MEM.RegisterRd

前两条指令的目的寄存器在：

MEM/WB.RegisterRd

如果前一条指令要写寄存器，并且目的寄存器不是 $0，且目的寄存器等于当前指令源寄存器，则需要从 EX/MEM 转发。

条件为： \[ EX/MEM.RegWrite \land (EX/MEM.RegisterRd\ne 0) \land (EX/MEM.RegisterRd=ID/EX.RegisterRs) \]

对应 ForwardA=10

对 rt 类似： \[ EX/MEM.RegWrite \land (EX/MEM.RegisterRd\ne 0) \land (EX/MEM.RegisterRd=ID/EX.RegisterRt) \]

对应 ForwardB=10

如果相关来自 MEM/WB，则条件为： \[ MEM/WB.RegWrite \land (MEM/WB.RegisterRd\ne 0) \land (MEM/WB.RegisterRd=ID/EX.RegisterRs) \]

对应 ForwardA=01

对 rt 类似

还要注意：如果 EX/MEM 和 MEM/WB 同时满足，应优先转发 EX/MEM 的结果

例如：

1
2
3

add $1, $1, $2
add $1, $1, $3
add $1, $1, $4

第三条指令要使用第二条指令的结果，而不是第一条指令的结果

所以 MEM/WB 转发条件还要加一个限制：如果 EX/MEM 已经能给出更新的结果，则不要使用 MEM/WB 的旧结果

对 rs 可写成： \[ MEM/WB.RegWrite \land (MEM/WB.RegisterRd\ne0) \] \[ \land\ \neg(EX/MEM.RegWrite \land (EX/MEM.RegisterRd\ne0)\land(EX/MEM.RegisterRd=ID/EX.RegisterRs)) \] \[ \land\ (MEM/WB.RegisterRd=ID/EX.RegisterRs) \]

直观说，就是“近的优先”

距离当前 EX 阶段越近的流水段，结果越新

Load-use 冒险

并非所有 RAW 冒险都能单靠转发解决

考虑 lw 指令后续跟着 R 或者 I 型指令

lw  r1, 0(r2)
sub r4, r1, r3
or  r8, r1, r9
add r6, r1, r7

lw 读出的数据要到 MEM 阶段末尾才有效，而紧随其后的 sub 在下一周期 EX 阶段开头就需要这个数据：

数据来不及转发

这种情况称为装入-使用数据冒险，也就是 load-use hazard

解决方法是阻塞一个周期，再配合转发：

阻塞检测条件为： \[ ID/EX.MemRead \land ((ID/EX.RegisterRt=IF/ID.RegisterRs)\lor(ID/EX.RegisterRt=IF/ID.RegisterRt)) \]

含义是：

当前在 EX 阶段的是 load 指令
load 的目的寄存器是下一条指令的源寄存器

阻塞时：

PC 不变
IF/ID 不变
ID/EX 的控制信号清 0，插入一个气泡
load 指令继续向后执行

硬件处理数据冒险的常用方案就是：

转发 + load-use 阻塞

编译器调度例子

编译器还可以通过调整指令顺序减少阻塞

比如把无关的 lw 或 ALU 指令插入到 load 和使用它的指令之间

假设有两条独立赋值：

1 2	a = b + c; d = e - f;

一种较差的机器码顺序可能是：

lw  $2, b
lw  $3, c
add $1, $2, $3
sw  $1, a
lw  $5, e
lw  $6, f
sub $4, $5, $6
sw  $4, d

lw $3, c 后面紧跟 add，出现 load-use 阻塞

可以调整为：

lw  $2, b
lw  $3, c
lw  $5, e
add $1, $2, $3
lw  $6, f
sw  $1, a
sub $4, $5, $6
sw  $4, d

通过更改指令执行顺序，在不影响功能性的前提下，给前面的 load 留出时间

这说明编译器理解流水线结构后，可以通过指令调度减少硬件阻塞

控制冒险

控制冒险来自分支、跳转、异常和中断

分支指令改变 PC，但流水线在分支结果产生前已经取了后续指令

例如 beq 在 MEM 阶段才确定是否转移，则它后面可能已有 3 条指令被取出

如果分支实际发生，这些指令就是取错的，需要清除

硬件阻塞和软件 NOP

硬件阻塞分支后的若干条指令
或编译器插入若干条 nop

这种方法简单但效率低

静态分支预测

静态预测的简单策略是：

总是预测 not taken

也就是默认继续执行顺序后继指令：

如果分支实际 taken，则预测失败，需要冲刷流水线

也可以加启发式规则：

循环底部分支通常预测 taken
向后跳转通常预测 taken
向前跳转通常预测 not taken

这类规则可达到约 65% 到 85% 的准确率

缩短分支延迟

可以把分支目标地址计算和条件判断提前到 ID 阶段

分支目标地址计算提前是可行的，因为 IF/ID 中已经有：

PC+4
imm16

条件判断也可以提前，用简单逻辑比较 rs 和 rt

比如先按位异或，再对结果各位求或，就可以判断两个寄存器是否相等

这样如果预测 not taken，而实际 taken，只需要清除 IF 阶段已经取出的那条指令

控制信号可写为： \[ IF.Flush=Branch\land Zero \]

IF.Flush=1 时，把 IF/ID 中的指令清 0，使它变成 nop

分支提前到 ID 的新问题

把分支比较提前到 ID 阶段能减少控制冒险损失，但会带来新的数据冒险

例如：

1 2	add $1, $5, $2 beq $1, $3, label

beq 在 ID 阶段就需要 $1，但前一条 add 的结果还没到可以正常转发的位置

如果是上上条 ALU 指令，可能可以从后面阶段转发到 ID 比较逻辑

如果是紧邻上一条 ALU 指令，往往来不及，需要阻塞

所以缩短控制冒险代价，可能会增加数据冒险处理复杂度

动态分支预测

动态预测利用分支历史来预测未来

常见结构：

BHT：Branch History Table，分支历史表
BPB：Branch Prediction Buffer，分支预测缓冲
BTB：Branch Target Buffer，分支目标缓冲

这些表通常用分支指令地址的低位索引，因此在 IF 阶段就能得到预测信息

如果命中，则根据预测位决定取顺序地址还是分支目标地址

如果未命中，则说明这个分支以前可能没执行过，需要加入新项：

一位预测

一位预测记录上一次分支结果，定义：

1：上次 taken，下次预测 taken
0：上次 not taken，下次预测 not taken

预测错则翻转该位，预测对则保持

缺点是循环分支会在在第一次和最后一次出错

比如循环中大多数时候 taken，最后一次 not taken

最后一次会把预测位改成 not taken，下次再次进入循环时第一次又会错

两位预测

两位预测用四个状态表示强弱倾向：

强预测 not taken
弱预测 not taken
弱预测 taken
强预测 taken

基本思想是：

连续两次预测错误才改变预测方向

这样对循环分支更稳定

循环中间一直 taken，最后一次 not taken 时，只会从强 taken 变为弱 taken，下次仍预测 taken

所以两位预测通常比一位预测更好

BHT 表项别名

BHT 常用分支指令地址低位索引

这意味着不同分支指令可能映射到同一个表项

这种情况称为别名冲突

因为 BHT 只是预测结构，不属于体系结构状态，所以即使取到的是另一个分支留下的预测位，也不会影响程序正确性

最坏情况只是预测错误，随后冲刷流水线并修正预测表

BTB 的作用

如果只知道分支方向，还不够

预测 taken 时，还需要尽快知道目标地址

BTB 会缓存分支指令地址和转移目标地址

IF 阶段查到 BTB 命中后，可以直接从预测目标地址取指，而不必等到后续阶段计算目标地址

因此 BTB 同时解决“是否跳”和“跳到哪里”的问题

延迟分支

延迟分支由编译器重排指令实现

基本思想是：把分支前面与分支无关的指令移动到分支后面的延迟槽中执行

如果找不到合适指令，就填 nop

这属于静态调度技术

调度时要小心，不能改变程序语义，也不能引入新的 load-use 冒险

分支延迟槽中的指令无论分支是否发生都要执行

因此能放入延迟槽的指令必须满足：

与分支判断无关
不会破坏 taken 和 not taken 两条路径的语义
不依赖分支之后才确定的数据

如果找不到合适指令，只能填 nop，性能收益就会下降

例子：

lw	r1, 0(r2)
lw	r3, 0(r2)
sub r6, r4, r2
beq r3, r5, 2
add r3, r3, r2
sw  r1, 0(r2)

调度后变为：

lw  r3, 0(r2)
sub r6, r4, r2
beq r3, r5, 2
lw  r1, 0(r2)  
nop
add r3, r3, r2
sw  r1, 0(r2)

延迟分支在简单流水线中有效，但在深流水线、动态预测、乱序执行中会增加恢复和异常处理复杂度，所以现代体系结构中较少再依赖它

异常和中断

异常和中断也会改变程序执行流，所以也是控制冒险

流水线处理异常比单周期和多周期更复杂，因为同一时刻有多条指令处于不同阶段

例如一条 add 在 EX 阶段发现溢出时，它后面可能已经有两条指令进入流水线

处理思路：

清除发生异常的指令及其后面的指令
关中断
保存断点到 EPC
把异常处理入口地址送 PC

MIPS 异常处理入口常见为： \[ 0x80000180 \]

如果 add 发生溢出，需要保证它不会在 WB 阶段把错误结果写入寄存器

所以异常时要清除对应阶段的控制信号，尤其是 RegWr

精确异常

流水线中要回答一个问题：到底是哪条指令发生异常？

不同异常发生在不同阶段：

无效指令地址：IF 阶段
无效指令：ID 阶段
除数为 0：ID 或 EX 阶段
溢出：EX 阶段
无效数据地址：load/store 的 EX 或 MEM 阶段

为了实现精确异常，需要把指令地址跟随指令一起保存在流水段寄存器中

异常发生时，把对应指令的地址写入 EPC

如果无法准确给出断点，就称为非精确异常，这会增加操作系统处理复杂度

外部中断与某条具体指令无关，通常在指令边界处理，保证前面的指令正确完成，再跳转到中断处理程序，也就是放在第一个流水段 IF 或者最后一个流水段 WR 中进行

多异常优先级

一个周期内可能有多条指令同时发生异常

例如：

IF 阶段发现取指地址异常
ID 阶段发现非法指令
EX 阶段发现 ALU 溢出
MEM 阶段发现数据缺页

为了实现精确异常，应该优先处理程序顺序中最早的那条异常指令

即：Wr > Mem > Ex > ID > IF

一种做法是让异常原因随指令在流水段中继续向后传递，到合适阶段统一提交

这样前面的指令先到达提交点，后面的异常不会越过前面的异常

每个时钟周期内，在多个流水段发生的异常的原因和断点只是被记录到特定的寄存器中，并将发生异常的标记同时记录到流水段寄存器，发生异常的指令继续在流水线中执行，直到执行到最后一个阶段，由最后阶段内的硬件检测本指令是否发生过异常或此时是否有外部中断发生，若有，则清除流水线中后面所有阶段正在执行的指令，然后转到相应的异常处理程序执行

Flush 的含义

异常或分支预测失败时，需要把某些流水段中的指令变成 nop

这通常不是把所有数据位都清 0，而是把控制信号清 0

只要：

RegWr=0
MemWr=0
PCWrite

不被错误触发，这条被冲刷的指令就不会改变体系结构状态

因此冲刷本质上是禁止错误路径上的指令产生副作用

性能比较

CPU 执行时间仍然是： \[ CPU时间=指令条数\times CPI\times 时钟周期 \]

存储器：200ps
ALU 和加法器：100ps
寄存器堆读写：50ps
MUX、控制、传输延迟忽略

指令比例：

lw：25%
sw：10%
ALU：52%
branch：11%
jump：2%

单周期

单周期时钟周期由 lw 决定，为 600ps

执行 $n$ 条指令： \[ T=600n \]

多周期

多周期时钟周期取最长功能部件时间，为 200ps

各类指令周期数：

lw：5
sw：4
ALU：4
branch：3
jump：3

平均 CPI： \[ 5\times25\%+4\times10\%+4\times52\%+3\times11\%+3\times2\%=4.12 \]

执行时间： \[ T=4.12\times200n=824n \]

流水线

流水线时钟周期也取最长阶段，为 200ps

考虑：

load-use 相关时 lw 平均 1.5 个周期
sw 和 ALU 指令平均 1 个周期
branch 预测成功 1 个周期，预测失败 2 个周期，准确率 75%
jump 平均 2 个周期

平均 CPI： \[ 1.5\times25\%+1\times10\%+1\times52\%+1.25\times11\%+2\times2\%=1.17 \]

执行时间： \[ T=1.17\times200n=234n \]

所以在这个模型下，流水线明显快于单周期和多周期

不过这依赖于理想化假设

真实机器还要考虑：

Cache 缺失
分支预测错误
数据相关
结构冲突
异常和中断

访存瓶颈

教材例子中多周期反而比单周期慢，一个重要原因是访存时间太长，且多周期没有把访存再细分

如果把访存拆成更均匀的两个阶段，时钟周期可以继续缩短，多周期和流水线都会受益

这正是超流水线的思路：把长阶段拆细，使各段延迟更均衡

但拆分访存也会增加流水段寄存器和控制复杂度，所以需要综合权衡

高级流水线技术

进一步提高性能的核心是指令级并行 ILP

常见技术包括：

超流水线
多发射流水线
静态多发射
动态多发射
推测执行
动态调度

超流水线

超流水线是把原来的流水段进一步细分，使时钟周期更短

如果原来五段流水线变成更多段，则同一时刻能有更多指令处于执行中

但流水线越深，分支错误代价越高，流水段寄存器开销也越大

多发射流水线

多发射流水线在一个周期内发射多条指令

如果每周期最多发射 $m$ 条指令，则理想情况下： \[ IPC=m \]

这里 IPC 是每周期完成指令数

它和 CPI 互为倒数关系： \[ IPC=\frac{1}{CPI} \]

如果能做到每周期完成 2 条指令，则： \[ CPI=0.5 \]

但实际很难达到理想 IPC，因为指令之间有依赖关系

多发射流水线的性能上限可以从 CPI 改用 IPC 来描述

单发射理想流水线： \[ IPC=1,\quad CPI=1 \]

2 发射理想流水线： \[ IPC=2,\quad CPI=0.5 \]

实际中 IPC 往往明显低于发射宽度

限制因素包括：

指令之间真实数据依赖
分支预测错误
访存缺失
功能部件数量不足
编译器或硬件找不到足够无关指令

推测执行

推测技术是指编译器或处理器猜测后续执行路径或指令结果，并据此提前调度指令

如果猜对，性能提高

如果猜错，需要回滚，产生额外开销

推测分为：

软件推测：编译器静态完成
硬件推测：处理器运行时动态完成

分支预测就是一种典型硬件推测

推测执行必须配套恢复机制

如果推测错误，处理器要撤销错误路径上的结果，恢复到正确 PC 继续执行

所以推测结果在确认安全之前，通常不能直接写入体系结构寄存器或存储器

这也是 ROB 的重要作用之一

静态多发射和 VLIW

静态多发射由编译器在编译时完成相关性分析、指令调度和指令打包

把同一周期内发射的多条指令合并为一个长指令，称为发射包

这种技术也称 VLIW：

Very Long Instruction Word，超长指令字

VLIW 的特点：

编译器负责发现并行性
编译器负责消除包内冒险
硬件控制相对简单
对编译器要求很高
二进制代码和具体机器结构关系紧密

以 2 发射 MIPS 为例：

一条 ALU 或分支指令
一条 load 或 store 指令

两条指令打包成 64 位长指令

如果找不到可配对指令，就用 nop 填充

为了支持 2 发射，数据通路需要：

同时取两条指令
同时译码两条指令
增加寄存器堆读口和写口
增加 ALU 或地址计算部件
扩宽流水段寄存器
分别传递两条指令的控制信号

潜在性能接近 2 倍，但实际达不到

原因是：

结构硬件成本增加
指令难以总是配对
数据冒险更复杂
分支冒险代价更大

循环展开

循环展开是编译器提高指令级并行的重要方法

基本思想是把循环体复制多份，减少分支次数，并在展开后的多条指令之间重新调度

好处：

提供更多无关指令给调度器
减少循环分支开销
减少 load-use 阻塞

代价：

代码体积增加
需要更多寄存器
需要处理循环次数不是展开倍数的情况

循环展开 4 次后使用更多临时寄存器，消除了部分名字依赖，使 14 条指令在 8 个周期内完成： \[ CPI=\frac{8}{14}\approx 0.57 \]

名字依赖和寄存器重命名

循环展开后，多个循环体副本会使用相似的临时变量

如果都使用同一个寄存器名，就会产生名字依赖

名字依赖不是真实数据依赖，只是寄存器名重复造成的限制

例如两个独立计算都写 $t0，它们并不需要彼此结果，但因为名字相同，调度时必须保持顺序

解决方法是寄存器重命名

编译器可以把不同副本中的临时变量分配到 $t1、$t2、$t3 等不同寄存器

动态处理器也可以在硬件中把体系结构寄存器映射到更多物理寄存器

IA-64 和 EPIC

IA-64 类似 RISC 风格，但要求编译器显式给出指令级并行性

Intel 称其为 EPIC：

Explicitly Parallel Instruction Computer，显式并行指令计算机

特点：

更多通用寄存器和浮点寄存器
指令以 bundle 形式组织
使用模板字段说明并行执行方式
支持谓词化执行
支持推测执行

谓词化可以减少分支。

例如：

if (p) {
    Statement1;
} else {
    Statement2;
}

可以转成：

1 2	(p) Statement1 (~p) Statement2

条件为真时执行对应指令，否则该指令变成 nop

这样可以把控制相关转化为数据相关，减少分支冒险

IA-64 的设计目标是把并行性显式暴露给硬件

它提供大量寄存器、谓词寄存器、指令包和模板字段，希望编译器告诉硬件哪些指令可以并行

这种思路对编译器要求极高

如果编译器不能准确发现足够并行性，硬件资源就会空闲

而且二进制代码和具体机器组织关系更紧，迁移到不同实现时不如动态超标量灵活

动态多发射

动态多发射由硬件在运行时决定哪些指令可以并行发射

这类处理器通常称为超标量处理器

和 VLIW 不同：

VLIW 由编译器打包指令
超标量由硬件动态选择和发射指令

因此超标量能更好地屏蔽不同处理器实现细节，同一份二进制代码能在不同实现上运行

为什么还需要动态调度

编译器可以静态调度，但它无法预知所有运行时事件

不可预知事件包括：

Cache 缺失
TLB 缺失
分支真实方向
不同输入数据造成的依赖变化

动态调度能在某条指令等待时，从后面的指令窗口中找已经准备好的无关指令执行。

这能提高功能部件利用率

动态调度

动态调度的思想是：

当前面指令阻塞时，到后面找无关指令提前执行

结构包括：

指令预取和译码单元
指令窗口
多个功能单元
保留站
重排序缓冲 ROB
提交单元

指令可以乱序执行，但通常要按序提交

按序提交可以简化异常处理，并保证程序员看到的机器状态仍然像顺序执行一样

保留站和 ROB

保留站保存：

操作数
操作类型
等待的依赖信息

当操作数和功能部件都准备好时，指令就可以发射执行

ROB 保存已经执行完但还不能立即提交的结果

只有当一条指令前面的所有指令都已经安全完成，并且推测没有错误时，才能提交

ROB 也用于实现：

精确异常
回滚
结果转发
按序提交

有序发射和乱序执行

很多动态调度处理器仍然保持取指和译码按程序顺序进行

指令进入指令窗口后，硬件根据以下条件决定能否发射：

源操作数是否可用
功能部件是否可用
是否存在必须保持顺序的相关
推测路径是否仍然有效

如果条件满足，即使它在程序顺序上位于某些阻塞指令之后，也可以先执行

但提交通常仍按程序顺序进行

这样可以让异常表现为精确异常，程序员看到的结果仍像顺序执行

执行模式

动态流水线可以分为：

按序发射、按序完成
按序发射、乱序完成
乱序发射、乱序完成

按序完成最保守，控制简单，但性能受限

乱序完成能提高功能部件利用率，但需要解决 WAW、WAR、异常精确性等问题

乱序发射乱序完成性能潜力最高，但硬件复杂度最大

现代高性能处理器通常结合：

动态分支预测
指令窗口
寄存器重命名
保留站
ROB
多功能部件
多级 Cache

功能部件的两个指标

功能部件性能通常用两个周期数描述

执行周期数 latency：完成一次操作需要多少周期
发射间隔 issue time：连续发射两个独立操作之间至少隔多少周期

一个部件可以 latency 很长，但 issue time 很短

这说明它是流水化的

例如浮点加法可能需要 3 个周期完成，但每个周期都能接收一个新的浮点加法

而除法通常 latency 长且 issue time 也长，说明它难以流水化

这解释了为什么处理器会给常用操作配置更多、更深的流水功能部件，而对除法这类不常用操作使用较慢实现

Pentium 4

教材用 Pentium 4 说明复杂动态超标量流水线

它的特点包括：

深流水线
指令先翻译成微操作
使用 trace cache 保存微操作序列
动态分支预测
寄存器重命名
多个整数、访存、浮点和 SIMD 功能部件
乱序调度和执行

CISC 指令复杂、长度不固定，不适合直接进入统一流水线

因此复杂 x86 指令通常会先被译码成更规整的微操作

后端真正调度和执行的是微操作，而不是原始 x86 指令

这也说明现代处理器内部实现和表面 ISA 可以差别很大

小结

流水线的核心收益是提高吞吐率，而不是缩短单条指令延迟

MIPS 这类规整 ISA 很适合五段流水线：

流水线实现必须处理三类冒险：

结构冒险：靠资源分离和规整阶段解决
数据冒险：靠转发和 load-use 阻塞解决
控制冒险：靠预测、延迟分支和冲刷解决

更高性能的处理器继续扩大指令级并行：

更深流水线
多发射
动态调度
推测执行
乱序执行

但并行性不是无限的

数据依赖、分支预测错误、Cache 缺失和异常处理都会限制真实性能

#计组学习笔记4

流水线技术

流水线特点

流水线分类

流水线性能

吞吐率

加速比

效率

瓶颈处理

适合流水线的指令集

五段 MIPS 流水线

为什么要统一为五段

Load 指令

R 型指令

Store 指令

Branch 指令

五段中每段的硬件使用

流水线五个阶段

Ifetch(IF) 段

Reg/Dec(ID) 段

Exec(EX) 段

Mem 段

Wr 段

流水段寄存器

数据必须跟着指令走

流水线控制信号

控制信号的传递

分段控制表

流水线冒险

结构冒险

指令存储器和数据存储器分开的原因

读写寄存器分开

数据冒险

硬件阻塞

软件插入无关指令

寄存器堆先写后读

转发

转发对执行部件的改动

转发条件

Load-use 冒险

编译器调度例子

控制冒险

硬件阻塞和软件 NOP

静态分支预测

缩短分支延迟

分支提前到 ID 的新问题

动态分支预测

一位预测

两位预测

BHT 表项别名

BTB 的作用

延迟分支

异常和中断

精确异常

多异常优先级

Flush 的含义

性能比较

单周期

多周期

流水线

访存瓶颈

高级流水线技术

超流水线

多发射流水线

推测执行

静态多发射和 VLIW

循环展开

名字依赖和寄存器重命名

IA-64 和 EPIC

动态多发射

为什么还需要动态调度

动态调度

保留站和 ROB

有序发射和乱序执行

执行模式

功能部件的两个指标

Pentium 4

小结

计组学习笔记4

同分类文章 4 related_posts_unit