流水线 MIPS 处理器的设计

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Dec.24 2021

本作品由 ZobinHuang 采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

流水线 (Pipeline) 是一种有效的提升系统带宽的技术手段。考虑我们在单周期 MIPS 处理器的设计中设计的单周期 MIPS 处理器，其运行形态如上图 (a) 所示。在本节讨论的流水线技术中，我们通过将单周期处理器的设计分解为 5 个流水线阶段 (pipeline stages)。在同一时刻下，流水线处理器可以同时执行 5 条指令，如上图 (b) 所示。每个指令都处在不同的阶段下。由于每个阶段都只是整个数据通路逻辑的大约 `1/5`，因此流水线处理器的时钟周期大约可以增加 5 倍，所以运行一条指令所需要的时延基本没有发生改变，但是我们却通过流水线技术提升了几乎 5 倍系统运行的吞吐量。

1.2 阶段划分

详细地说，我们会把指令的执行过程分为以下 5 个阶段:

Fetch: 从 Instruction Memory 中读取相关指令;
Decode: 从 Register File 从读取源操作数; 解码获取得到的指令，输出相应的控制信号;
Execute: 利用 ALU 进行相关计算操作;
Memory: 读写 Memory;
Writeback: 如果需要的话，将计算结果写回 Register File

如下图所示，是我们对多条指令在流水线处理器中运行的抽象表示。每一个流水线阶段都由代表该阶段的关键部件表示: Instruction Memory (IM)，Register File (RF) Read，ALU execution，Data Memory (DM) 和 Register File (RF) Write。我们抽取出图中的每一行，看到的将是一条指令穿梭在各个流水线阶段中的运行周期; 我们抽取中图中的每一列，看到的是在一个特定的时钟周期下，各个流水线阶段正在运行的不同指令。

在上述图中，注意到我们使用了阴影来代表某个部件正在被使用。值得注意的是 Register File 在 Decode 阶段会被读取，而在 Writeback 阶段会被进行写入，我们在上图中使用了不同半边的阴影来表示这种区别。可以发现，Register File 在同一个时钟周期内，既可以被读取，又可以被写入。

1.3 冒险

由于流水线处理器允许多条指令在同一段时间内在处理器中运行，因此一个必须解决的问题是冒险 (hazard) 问题 —— 一条后续的指令需要前序指令的运算结果，但是前序指令尚未完成运行。我们在后面将会介绍 forwarding、stalls 和 flushes 三种方法来解决冒险问题。

2. 数据通路

如上图 (a) 所示，是我们在单周期 MIPS 处理器的设计中完成的数据通路。通过在数据通路中插入四个 Pipeline Register，我们即可以将其分解为 5 个阶段，如上图 (b) 所示。然而实际上我们不能简单地向数据通路中添加 Pipeline Register 就草草了事，图 (b) 是一个存在错误的流水线设计。流水线设计中有一个很重要的原则: 与一条指令相关所有信号输出都应该被推送到下一个流水线阶段。因此，观察上图 (b)，错误出现在最后一个对 Register File 的写逻辑，信号 `WriteRegE_{4:0}` 来自于 Execute 阶段，而信号 `Resu l tW` 来自于 Writeback 阶段，这很明显是不匹配且错误的。因此，我们虽然在 Execute 阶段就获得了 `WriteRegE_{4:0}` 信号，但是我们必须将该信号伴随着指令的执行一路推送到 Writeback，然后和 `Resu l tW` 信号一起送上 Register File 的写入端口。修正的数据通路如下图所示:

细心的读者还会发现，PC 的输入端口信号 PC' 的更新逻辑也存在一定的问题: 它既可以在 Fetch 阶段被更新，也可以在 Memory 阶段中被更新。我们会在后面专门针对冒险问题的讨论中解决这个问题。

3. 控制单元

在流水线处理器中，我们使用了和单周期处理器一样的控制信号，如上图所示。Control Unit 根据指令的 opcode 和 funct 字段来输出相应的控制信号。同样地，遵循上述的流水线处理器设计的原则，我们需要将这些控制信号伴随着指令在流水线中的执行，一路推送到后续的各个流水线阶段中。

4. 流水线冒险

4.1 定义

如果一条指令的执行依赖于另一条未完成的指令的运行结果，我们说当前流水线发生了数据冒险 (Data Hazard);
如果在处理器还没有得出下一条要运行的指令的地址的情况下，第一级流水线阶段就读取了可能有误的下一条指令，我们就说当前流水线发生了控制冒险 (Control Hazard);
结构冒险?

我们来看一个数据冒险的例子。如上图所示，当指令 add $s0, $s2, $s2 还没有完成对 s0 的写入操作时，后续指令对 s0 寄存器的引用就都会产生错误的旧的引用结果。我们把这种情况称为写后读 (Read After Write, RAW)。

值得注意的是，上图中最后一条指令 sub $t2, $s0, $s5 的执行并不存在数据冒险问题，原因是因为: 在一个时钟周期内，Register File 在前半个时钟周期完成数据的写入，在后半个时钟周期完成数据的读取。因此在上图的第 5 个时钟周期中，指令 add $s0, $s2, $s2 在前半个时钟周期完成了对 s0 的写入操作，指令 sub $t2, $s0, $s5 在后半个时钟周期读取到了 s0 被更新的值，因此不存在数据冒险问题。

在本节中我们将引入一个 Hazard Unit，用于处理冒险问题。相应地，下面我们将介绍两种种用于解决数据冒险的方法: Forwarding 和 Stall，以及一种用于解决控制冒险的方法: Flush。

4.2 解决数据冒险: Forwarding

Forwarding (转发) 技术用于解决我们在上面看到的 RAW 数据冒险。满足如下条件的数据冒险可以使用转发手段来进行解决:

转发条件

[正在 Execute 阶段的指令的源操作寄存器] 与 [正在 Memory 或 Writeback 阶段的指令的目的操作寄存器] 相同时

转发技术的流程是这样的。如下图所示，在第 4 个时钟周期，指令 add $s0, $s2, $s3 (p.s. 以下简称指令[1]) 位于 Memory 阶段，此时由于下一条指令 and $t0, $s0, $s1 (p.s. 以下简称指令[2]) 需要使用到 s0 寄存器，因此如图所示， s0 寄存器的结果在指令[1] 的 Memory 阶段被转发到了指令 [2] 的 Execution 阶段，此时虽然指令 [1] 还未将更新过的 s0 寄存器的值写入 Register File，但是指令[2] 拿到的是正确的更新好的值。

同理，在第 5 个时钟周期，指令 or $t1, $s4, $s0 (p.s. 以下简称指令[3]) 接受到了来自指令[1] 在其 Writeback 阶段转发过来的 s0 指令的值。而对于最后一条指令 sub $t2, $s0, $s5 (p.s. 以下简称指令[4])，我们在上面已经提及，Register File 在时钟周期前半部分写入，后半部分读取的特性，因此并不需要进行转发。

为了实现转发，我们必须向处理器中加入一个冒险检测单元 (Hazard Detection Unit, HDU)，以及两个用于转发的多路选择器，如下图所示。

HDU 接收运行至 Execution 阶段的指令的 rs (i.e. `Instr_{25:21}`) 和 rt (i.e. `Instr_{20:16}`) 字段，用于明确该指令所需要的源寄存器; 同时它还接收运行至 Memory 和 Writeback 阶段的指令的写入寄存器地址 (p.s. 由 rt (i.e. `Instr_{20:16}`) 或 rd (i.e. `Instr_{15:11}`) 指定，在该指令的 Execution 阶段就已经被获取)，当前指令在 Execution 阶段的 ALU 计算结果 `ALUOutM` 和 `ALUOutW`，以及指示是否需要对 Register File 进行写入的信号 `RegWriteM` 和 `RegWriteW`，用于明确该指令是否需要对相关寄存器进行写入。注意到此处的 `RegWriteM` 和 `RegWriteW` 信号与控制单元的两个同名信号是同样的两个信号。

在数据通路上，两个多路选择器用于选择 ALU 两个输入操作数的来源: (1) 伴随当前指令的 Register File 的寄存器读取值; (2) 先序指令转发值。HDU 会对转发条件 (p.s. 见上面) 进行判断，如果满足条件，则就会通过信号 `Fo rwardAE` 或 `Fo rwardBE`，把由 `ALUOutM` 或 `ALUOutW` 承载的寄存器更新值转发至 Execution 阶段的指令。

值得注意的是，如果 Memory 和 Writeback 阶段的指令都需要进行转发，也即它们都满足转发条件，那么优先转发 Memory 阶段的寄存器更新值，因为它是最新的更新结果。另外，寄存器 $0 是固定被硬件下拉至 0 值的，因此它不会被转发。对于 ALU 的操作数 SrcA 来说，它的转发选择逻辑可以表达如下 Verilog 代码:

// 这样写是否考虑了优先级?
if ((RsE != 0) && (RsE == WriteRegM) && (RegWriteM)) begin
  ForwardAW = 10; 
end
else if ((RsE != 0) && (RsE == WriteRegW) && (RegWriteW)) begin
  ForwardAW = 01; 
end
else begin
  ForwardAW = 00; 
end

4.3 解决数据冒险: Stall

对于 lw 指令来说，它对寄存器的更新值是在 Memory 阶段结束时才能获取到的，而不像我们上面看到的指令那样在 Execute 阶段结束之后就可以拿到，因此我们说这类指令有 Two-cycle Latency。假若这类指令后续有依赖于其目的寄存器的指令，那么单靠我们上面介绍的转发技术是无法解决的。

如下是一个 Two-cycle Latency 的例子。当指令 lw $s0, 40($0) (i.e. 以下简称指令[1]) 需要运行到第 4 个时钟结束时才能够获取到 s0 寄存器的正确更新值，然而指令 and $to, $s0, $s1 (i.e. 以下简称指令[2]) 在第 4 个时钟周期的开始处就需要使用 s0 寄存器的值，因此此时单靠转发并不能解决该冒险问题。

因此，我们在这里讨论一种新的解决上述数据冒险问题的方案: 停顿 (Stall)。如下图所示，指令[2] 会在第 3 个时钟周期，也就是当它运行到 Decode 阶段的时候，产生一次停顿，也就是说到了第 4 个时钟周期，它还是处于 Decode 阶段。相应地，指令 or $t1, $s4, $s0 (i.e. 以下简称指令[3]) 也会被相应地进行一次停顿，在第 3 个和第 4 个时钟周期都停顿在 Fetch 阶段。

注意到在第 4 个时钟周期中，Execute 阶段处于空闲状态; 在第 5 个时钟周期中，Memory 阶段处于空闲状态; 在第 6 个时钟周期中，Fetch 阶段处于空闲状态。我们将这些在流水线中 unused 的阶段成为气泡 (bubble)。气泡的产生原理是在 Execution 阶段清空所有流水线寄存器的值，包括所有的控制信号和存储的数据，以使得 Execution 阶段仿佛是在执行一条 nop，并且这条伪 nop 指令将会随着流水线的推进到达 Memory 和 Writeback 阶段。细心的读者会注意到，在 Execution 阶段的所有流水线寄存器中，只有 RsE, RtE, RdE 和所有控制信号寄存器中存储的值会被用于更新内存单元以及 Architectural State (i.e. 各类寄存器)，因此理论上来说，在停顿发生的时候，我们并不需要清空所有的 Execution 阶段的流水线寄存器，而只清空上面我们提到的这些寄存器就足够了。

停顿条件

我们下面会看到，HDU 会对一条正处于 Execute 阶段的指令进行检查，如果发现是一条 lw 指令，并且它的目的寄存器 (i.e. 由 rt (`Instr_{20:16}`) 字段指定) 与当前正处于 Decode 阶段的指令的任一源寄存器 (i.e. 由 rs (`Instr_{20:16}`) 和 rt (`Instr_{20:16}`) 指定)相同，则这条位于 Decode 阶段的指令会被停顿一个周期，停顿结束后它进入 Execute 阶段时，它就能收到正确的来自 Writeback 阶段的 lw 的转发值。

我们现在来讨论流水线处理器是如何支持停顿设计的。如上图所示，是支持停顿的流水线处理器，我们向 Fetch 和 Decode 阶段的流水线处理器上增加了 EN 使能端口，相应的使能信号是 `StallF` 和 `StallD`;向 Execute 阶段的流水线处理器上增加了 CLR 同步重置端口，相应的重置信号是 `FlushE`。

当 HDU 检测到停顿条件时，它会使能 `StallF` 和 `StallD` 信号来关闭 Fetch 和 Decode 阶段的流水线处理器的更新 (p.s. 注意到这两个流水线寄存器的 EN 使能端口前有两个反相器)，以使得它们保持旧值。同时 HDU 还会使能 `FlushE` 信号，以使在下一个时钟周期开始的时候清空 Execute 阶段的流水线寄存器的输出，以在 Execute 阶段产生一个气泡。另外，我们在 Execute 阶段将控制信号 `Memt oRegE` 送入了 HDU，HDU 凭借这个信号判断得出当前在 Execute 阶段的指令是否是一条 lw 指令。

上述信号的控制逻辑可以使用以下 Verilog 代码进行表示:

wire lwstall = ((RsD==RtE) || (RtD==RtE)) && (MemtoRegE)
StallF = lwstall
StallD = lwstall
FlushE = lwstall

4.4 解决控制冒险: Flush

beq 指令在流水线处理器中会引入这样的一个问题: 只有当 beq 指令运行到 Memory 阶段的时候，才能知悉是否需要对 PC 寄存器进行修改，而此时已经有三条分别位于 Fetch, Decode 和 Execute 阶段的指令进入了流水线，此时必须对在 beq 指令之后的指令进行处理。

一个最简单暴力的办法就是一旦发现一条 beq 指令进入流水线，就停顿三个时钟周期，直到 beq 指令在其 Memory 阶段对 PC 寄存器进行更新，才开始下一条指令的执行。这样的方法无异于降低了处理器的运行效率。

另一种方法是，对分支指令的跳转结果进行预测，然后基于预测结果将相关后序指令送入流水线。当分支指令在其 Memory 阶段知悉跳转结果时，如果预测结果是错误的，那么被送上流水线的三条后续指令就必须被清空 (Flush)，清空的办法是清空相关阶段的流水线寄存器中的值，也就是我们上面提到过的插入气泡。这些被浪费了指令周期被称为分支预测错误惩罚 (Branch Misprediction Penalty)。

下图是清空方案的一个例子。指令 beq $t1, $t2, 40 (i.e. 以下简称指令[1]) 位于 24 地址处，其与后续的三条指令被陆续送上了流水线，也就是说处理器的预测是不会发生跳转行为。在第 4 个时钟周期，位于 Memory 阶段的指令[1] 得到了跳转结果，我们假设跳转条件为真，那么此时后续三条分别位于 Fetch, Decode 和 Execute 阶段的指令的流水线寄存器都将被清空。在第 5 个时钟周期时，位于跳转目的地址的 64 内存单元存储的指令 slt $t3, $s2, $s3 就被送上了流水线。

考虑上面的方案，我们总得等到 beq 指令执行到 Memory 阶段后才能知悉指令跳转的结果。如果预测错误，我们将浪费掉三个时钟周期的运行资源，这对处理器的性能将是一个极大的损失。因此，我们最直接的一个想法就是: 是否可以提前知悉跳转结果?

beq 的跳转预测涉及到对两个寄存器值的判断。当判断到我们读取到的指令是一条 beq 指令时，我们可以在其运行到 Decode 阶段时，提前使用一个额外的比较器，对从 Register File 读取出来的两个源寄存器的值进行比较，并且在 Decode 阶段结束时，将相应的比较结果用于决定下一个 PC 指针值。下图展示了该跳转过程，可以发现，如果我们可以在 Decode 阶段就知悉跳转结果，当遭遇预测失败时，我们只需要清空当前 Fetch 阶段的流水线寄存器就可以了，减少了由于控制冒险产生的气泡的个数。

为了支持对提前清空操作的支持，我们对 HDU 进行了修改，如下图所示。首先，我们在 Decode 阶段增加了一个比较器，在 Decode 阶段就对读取出来的两个寄存器数据进行比较，并且配合控制信号 `BranchD`，形成最终决定是否跳转的信号 `PCSrc`。一旦该信号被使能，首先它会被用于选取 PC 寄存器前的多路选择器，以选择来自 beq 指令计算结果的下一指令地址; 其次它会被用于清空 Decode 阶段的流水线寄存器。

另外，注意到为了在 Decode 阶段就能计算得到相应的跳转地址，我们把用于计算跳转地址的加法器也放置到了 Decode 阶段中，以在需要跳转的时候，在 Decode 阶段中就能得到跳转的具体地址。

然而，单纯的进行上述修改仍然遗留了一个 RAW 的数据冒险问题: 如果 beq 指令的前序指令尚未将相关寄存器的更新值写回 Register File 中，那么比较器获取的两个寄存器值就为旧值，因此我们必须解决该数据冒险问题。

解决办法如下图所示，具体如下:

首先，HDU 根据 `BranchD` 信号检测到位于 Decode 阶段的指令是一条 beq 指令，从 `RsD` 和 `RtD` 获取 beq 指令判断的寄存器，从 `WriteRegE_{4:0}`, `WriteRegM_{4:0}` 和 `WriteRegW_{4:0}` 获取 Execute, Memory 和 Writeback 阶段的指令写入的目标寄存器，然后它会对以下情况进行检查:

如果在 Writeback 阶段的前序指令将新值写入寄存器，那么由于 Register File 在时钟周期前半部分完成写入，在后半部分完成读取，所以没有冒险会产生;
如果在 Memory 阶段的前序指令产生了写入寄存器的新值，它将被转发至 Decode 阶段接在比较器前的两个多路选择器，HDU 分别使用 `Fo rwardAD` 和 `Fo rwardBD` 信号对这两个多路选择器进行控制。HDU 根据 `RegWriteM` 检测到这种情况;
如果在 Memory 阶段的指令是一条 lw 指令，那么位于 Decode 阶段的 beq 就必须等待该 lw 指令到达 Writeback 阶段时，才可能获取更新的寄存器值，因此流水线必须停顿一个时钟周期。HDU 根据 `Memt oRegM` 检测到这种情况;
如果在 Execute 阶段的前序指令产生了写入寄存器的新值，流水线同样需要被暂停一个时钟周期，使得这条指令到达 Memory 阶段，然后根据指令的不同，使用上述 2 或 3 来进行处理。HDU 根据 `RegWriteE` 检测到这种情况。

基于上述修改，转发相关信号的产生逻辑可以使用如下 Verilog 代码来表示:

// Branch Forward Control
wire ForwardAD = ((RsD != 0) && (RsD == WriteRegM) && (RegWriteM))
wire ForwardBD = ((RtD != 0) && (RtD == WriteRegM) && (RegWriteM))

// Normal Forward Control
// 这样写是否考虑了优先级?
if ((RsE != 0) && (RsE == WriteRegM) && (RegWriteM)) begin
  ForwardAW = 10; 
end
else if ((RsE != 0) && (RsE == WriteRegW) && (RegWriteW)) begin
  ForwardAW = 01; 
end
else begin
  ForwardAW = 00; 
end

停顿相关信号的产生逻辑可以使用如下 Verilog 代码来表示:

// Stall Control
wire branchstall =  ( BranchD && (RegWriteE) && ((RsD == WriteRegE)||(RtD == WriteRegE)) ) ||
                    ( BranchD && (Memt oRegM) && ((RsD == WriteRegM)||(RtD == WriteRegM)) )
wire lwstall = ((RsD==RtE) || (RtD==RtE)) && (MemtoRegE)

StallF = (lwstall || branchstall)
StallD = (lwstall || branchstall)
FlushE = (lwstall || branchstall)

4.5 小结

现在我们已经完成了一个 5 阶段的 MIPS 流水线处理器设计了，总体如下所示:

5. 性能分析

5.1 CPI

理想情况下 (i.e. 没有清空和停顿操作)，流水线处理器每一个时钟周期可以接收一条新的指令，因此流水线处理器的 CPI 值为 1。由于每一次清空和每一次停顿操作都需要浪费掉一个时钟周期，所以在实际上流水线处理器会有稍高的 CPI。

5.2 时钟周期

为了确定流水线处理器的运行时钟周期，我们需要取出 5 个阶段运行时间的最大值，也即

`T_c = max((t_{pcq}+t_{mem}+t_{setup}), (2(t_{pcq}+t_{RFRead}+t_{m ux}+t_{eq}+t_{AND}+T_{m ux}+t_{setup})), (t_{pcq}+t_{m ux}+t_{m ux}+t_{ALU}+t_{setup}), (t_{pcq}+t_{memwrite}+t_{setup}), (2(t_{pcq}+t_{m ux}+t_{RFWrite})) ) ((Fetch), (Decode), (Execute), (Memo ry), (Writeback))`

有个值得注意的点是，由于 Register File 在 Writeback 阶段的前半个时钟周期完成写入操作，在 Decode 阶段的后半个时钟周期完成读取操作，因此这两个阶段的时钟周期长度实际上应该是读取/写入操作的两倍长。

Zobin