计组 - Lab 2: 流水线 MIPS CPU

32 位流水线 MIPS 指令集 CPU，使用 SystemVerilog 编写。

Introduction to Computer Systems II (H) @ Fudan University, spring 2020.

1 MIPS 指令集

同单周期，详见 计组 - Lab 1: 单周期 MIPS CPU。

2 部件构成及分析

2.0 总览

图示为流水线 MIPS CPU 的整体构造，与单周期 MIPS CPU 完全一致，区别在于 CPU 核心 mips 的实现。以下我们仅介绍与单周期 CPU 不同的部分，其余请参见单周期 CPU 的实验报告。

2.1 mips

本流水线 CPU 的实现中，将 datapath 按照流水线的 5 个阶段划分为了 5 个模块（Fetch, Decode, Execute, Memory, Writeback），并增加了一个用于处理冲突的冲突单元（Hazard Unit）。其中各模块的作用如下：

方便起见，我们将 Fetch 阶段和 Decode 阶段之间的流水线寄存器命名为 decode_reg，并置于 Fetch 模块中，其余流水线寄存器同理。

具体模块的功能分析将在下文阐述。这里 mips 的作用就是将这些模块连接起来，其中相同名称的端口即连通。除此以外特殊的几条连线如下所示：

• mips 读端口 reset, instr, readdata 分别与 rst, instr_f, read_data_m 连通
• mips 写端口 aluout, memwrite 分别与 alu_out_m, mem_write_m 连通

了解了以上连接规则后，展示 mips 的完整总览图就不那么必要了。比起大而繁乱的连线总览图，直接看代码甚至都更为直观。

代码见 这里。

2.2 fetch

Fetch 阶段，通过 pc_f 输出指令地址 pc 到 imem，通过 instr_f 从 imem 读入指令 instr，存储到流水线寄存器 decode_reg 中，在下一个时钟上升沿到达时从 instr_d 输出。

此外，本阶段还需要完成 PC 的更新。pc_next（新的 PC 值）的选择逻辑同单周期的 2.8 节，这里不再赘述。需要注意的是 Fetch 阶段需要用到一些 Decode 阶段的数据，也就是上一条指令计算得到的相对寻址地址 pc_branch_d、用于指令 jr 跳转的地址 src_a_d 和指令解析得到的 pc_src_d, jump_d 信号，用来确定 pc_next 的值。

在需要解决冲突的情况下，通过 stall_f, stall_d, flush_d 信号决定是否保持（stall）或清空（flush）对应流水线寄存器保存的数据，其中 stall_f 为 1 时保持当前 PC 值不更新，stall_d 为 1 时保持当前 decode_reg 的数据不更新，flush_d 为 1 时清空 decode_reg 的数据。具体这些信号在何时为何值，将在 2.7 节详细阐述。

代码见 这里。

2.2.1 fetch_reg

Fetch 阶段流水线寄存器。结构很简单，就是将 PC 寄存器 pc_reg 封装了一下。但相较于单周期版本的 flip_flop，流水线版本做了一些调整。

代码见 这里。

2.2.1.1 flip_flop

这里只说与单周期版本的区别，其余请参见单周期的 2.10 节。

首先增加了一个清零信号 \(\textrm{CLR}\)，当 \(\textrm{CLR}\) 为 \(1\) 时，将保存的数据同步清零（\(\textrm{RST}\) 为异步清零），用于 flush 信号。尽管这里 fetch_reg 用不到，但其他流水线寄存器可能会需要，这里是出于部件复用的考虑。其次增加了一个低电平有效的保持信号 \(\textrm{EN}\)，当 \(\textrm{EN}\) 为 \(0\) 时，保持数据不变。对于 fetch_reg 来说，其值即 ~stall_f。

代码见 这里。

2.2.2 decode_reg

Fetch 阶段和 Decode 阶段之间的流水线寄存器，中转一下 instr 和 pc_plus_4。为什么需要用触发器中转数据？因为流水线上需要同时跑多条指令（这里是 5 条），需要控制每个阶段各自只在执行一条指令。

这里 instr_reg 的 \(\textrm{CLR}\) 信号为 ~stall_d & flush_d，是为了使 stall_d 和 flush_d 信号互斥，且强制 stall_d 的优先级更高（当 stall_d 为 1 时，flush_d 无效，不允许清零），否则当两者同时为 1 时会导致错误（因为在触发器的实现中，flush 的优先级更高，这将导致指令丢失）。pc_plus_4_reg 不需要清零，因此 \(\textrm{CLR}\) 信号恒为 \(0\)。

代码见 这里。

2.3 decode

Decode 阶段，读入指令 instr_d，由控制单元 control_unit 解析，决定各个控制信号。此外，本阶段还需要完成相对寻址地址 pc_branch_d 的计算，然后交给下一条指令的 Fetch 阶段。

作为静态分支预测，本阶段新增了比较器 equal_cmp，用来比较从寄存器中读出的两个数 src_a, src_b 是否相等，其作用是将指令 beq, bne 的比较过程提前到 Decode 阶段，提前得到 pc_src 信号，从而提高效率。这里需要用到 Memory 阶段的数据 alu_out_m 以应对数据冒险，src_a, src_b 取值的选择由 forward_a_d, forward_b_d 信号控制。

在实现中，将寄存器文件 reg_file 放在了 decode 模块里，因此 Writeback 阶段的寄存器写入操作也将在这里完成。所以这里需要用到一些 Writeback 阶段的数据，也就是 reg_write_w 信号、目标寄存器 write_reg_w、写入数据 result_w。

在需要解决冲突的情况下，通过 stall_e, flush_e 信号决定是否保持或清空 execute_reg 保存的数据。

代码见 这里。

2.3.1 control_unit

流水线版本中，control_unit 新增了一个控制信号 \(\textrm{SIGN}\)，用于控制对立即数进行符号扩展还是无符号扩展，解决了新增测试样例 I-type 中遇到的一些问题。此外为了调试方便，本实现中将控制信号中的无关项 \(\textrm{x}\) 都改成了 \(0\)，其余同单周期版本。主译码器中，新增信号的真值表如下：

代码见 这里。

2.3.2 equal_cmp

32 位比较器，用于比较两个数是否相等。

使用时读入 \(\textrm{A}\) 和 \(\textrm{B}\)，若 \(\textrm{A}\) 和 \(\textrm{B}\) 相等则从 \(\textrm{EQUAL}\) 输出 \(1\)。

代码见 这里。

2.3.3 extend

扩展模块的作用是将 16 位的立即数扩展至 32 位。单周期版本中默认使用符号扩展，流水线版本中可以自行选择。

使用时从 \(\textrm{A}\) 读入待扩展的数据，从 \(\textrm{RESULT}\) 输出扩展后的数据。当 \(\textrm{SIGN}\) 为 \(1\) 时使用符号扩展，为 \(0\) 时使用无符号扩展。

代码见 这里。

2.3.4 reg_file

流水线版本中，寄存器文件调整为在时钟下降沿将数据写入，其余同单周期版本。

代码见 这里。

2.3.5 execute_reg

Decode 阶段和 Execute 阶段之间的流水线寄存器，中转一下 control, pc_plus_4, reg_data_1, reg_data_2, rs, rt, rd, shamt, ext_imm，其中：

• control 是控制信号 reg_write, reg_dst, alu_src, alu_control, jump, mem_write, mem_to_reg 的集合¹。
• pc_plus_4 是 PC + 4 的值。由于指令 jal 在之后还要用到这个值，因此继续传到 Execute 阶段。
• reg_data_1, reg_data_2 是 reg_file 读出的两个值。
• rs, rt, rd, shamt 分别是 instr_d 的 [25:21], [20:16], [15:11], [10:6]。
• ext_imm 是 32 位扩展后的 instr_d[15:0]。

结构及原理同 decode_reg，不再赘述。

代码见 这里。

2.4 execute

Execute 阶段，对操作数 src_a, src_b 使用 ALU 执行计算。在单周期版本的基础上，新增了两个 mux4 用于转发逻辑。这里需要用到 Memory 阶段的数据 alu_out_m 和 Writeback 阶段的数据 result_w 以应对数据冒险，read_reg_data, write_data（分别为通常情况下的 src_a, src_b）取值的选择由 forward_a_e, forward_b_e 信号控制。

代码见 这里。

2.4.1 memory_reg

Execute 阶段和 Memory 阶段之间的流水线寄存器，中转一下 control, alu_out, write_data, write_reg，其中：

• control 是控制信号 reg_write, mem_write, mem_to_reg 的集合。
• alu_out 通常是 ALU 的计算结果，可能作为写入 dmem 的目标地址，也可能作为之后需要写入 reg_file 的数据，之后由传给 Memory 阶段的控制信号控制。对于指令 jal，则是之前传下来的 pc_plus_4，因为和 alu_out 要走的路径一致，这里借路继续传到 Memory 阶段。
• write_data 是需要写入 dmem 的数据。
• write_reg 是之后写入 reg_file 的目标寄存器。对于指令 jal，则为 $ra 寄存器。

代码见 这里。

2.5 memory

Memory 阶段，当 mem_write 为 1 时，在 dmem 的目标地址 alu_out 存储需要写入的数据 write_data。不过实际上这件事情并不是在 memory 模块内完成的，因为 dmem 在 mips 外面。因此实现中是在 execute 模块通过 mem_write_m, alu_out_m, write_data_m 将 mem_write, alu_out, write_data 直接输出到 dmem，在下一个时钟上升沿到达时（即 Memory 阶段）写入 dmem。memory 模块内则是通过 read_data_m 从 dmem 读入数据 read_data。

代码见 这里。

2.5.1 writeback_reg

Memory 阶段和 Writeback 阶段之间的流水线寄存器，中转一下 control, alu_out, read_data, write_reg，其中：

• control 是控制信号 reg_write, mem_to_reg 的集合。
• read_data 是可能需要写入 reg_file 的数据。

代码见 这里。

2.6 writeback

Writeback 阶段，由 mem_to_reg 信号控制 result_mux2 选择写入 reg_file 的数据为 alu_out 还是 read_data。写入逻辑放在了 decode 模块，参见 2.3 节。

代码见 这里。

2.7 hazard_unit

冲突单元根据传入的各阶段寄存器和控制信号，检查是否存在数据冲突或控制冲突，并输出相应的控制信号（forward, stall, flush）以处理冲突。

代码见 这里。

2.7.1 数据冲突

当一条指令依赖于另一条指令的结果，而此结果还未写入寄存器文件时，将发生写后读（Read After Write, RAW）数据冲突。解决 RAW 冲突的方法如下：

• 如果此时这个结果已经在某个阶段被计算出来，那么使用重定向（forward）将数据转发过来；
• 否则，阻塞（stall）流水线直到结果可用。

需注意，$0 寄存器硬连接为 \(0\)，因此源寄存器为 $0 时不需要进行转发或阻塞。以下将阐述这两种方法的具体实现。

2.7.1.1 使用重定向解决冲突

当 Execute 阶段的源寄存器 $rs 或 $rt 与 Memory 阶段或 Writeback 阶段（即前两条指令）的写入目标寄存器 write_reg 相同，且其 reg_write 信号为 1 时（即需要写入目标寄存器），重定向对应的 src_a 或 src_b。

以 $rs 的情况为例（$rt 同理），重定向逻辑如下：

1
2
3
4
5
6
7

if (rs_e_i && rs_e_i == write_reg_m_i && reg_write_m_i) begin
  forward_a_e_o = 2'b10;
end else if (rs_e_i && rs_e_i == write_reg_w_i && reg_write_w_i) begin
  forward_a_e_o = 2'b01;
end else begin
  forward_a_e_o = 2'b00;
end

其中当 forward_a_e 为 10 时，Memory 阶段转发的数据是 alu_out_m；当 forward_a_e 为 01 时，Writeback 阶段转发的数据是 result_w。

需注意这里 Memory 阶段的优先级高于 Writeback 阶段，因为 Memory 阶段的指令后执行，阶段中的数据更新。

2.7.1.2 使用阻塞解决冲突

对于指令 lw，因为它有两个周期的延迟，意味着其他指令至少要到两个周期后才能使用它的结果。如果指令 lw 后紧接着一个使用其结果的指令，则使用重定向无法解决这种冲突，此时需要阻塞流水线。现实中，编译器可能会针对这种情况做一定的优化，通过调整指令顺序，在发生数据冲突的两条指令间插入一条无关指令，从而避免这种冲突。

当 Execute 阶段正在执行的指令是 lw（此时 mem_to_reg 信号为 1），且 Decode 阶段的任一源操作数 $rs 或 $rt 与 Execute 阶段的目的寄存器 $rt 相同时，阻塞 Decode 阶段直到源操作数准备好。

阻塞逻辑如下：

1
2
3
4
5

assign lw_stall = (rs_d_i == rt_e_i || rt_d_i == rt_e_i) && mem_to_reg_e_i;

assign flush_e_o = lw_stall;
assign stall_d_o = flush_e_o;
assign stall_f_o = stall_d_o;

这里阻塞 Decode 阶段的同时也要阻塞 Fetch 阶段，并且刷新（flush）Execute 阶段，产生气泡（bubble）。

2.7.2 控制冲突

当取下一条指令的时候还不能确定指令地址时，将发生控制冲突，此时 CPU 不知道应该取哪条指令。解决控制冲突的方法如下：

• 尝试预测下一条指令地址，先按预测的分支走；
• 如果预测错误，则刷新（flush）流水线。

目前的实现中使用的是静态分支预测，之后我们将实现动态分支预测以获得更好的性能。

不幸的是，引入静态分支预测将导致新的 RAW 冲突，因此需要再次用到 2.7.1 节里解决数据冲突的两种方法。

2.7.2.1 使用重定向解决冲突

如果指令的结果在 Writeback 阶段，则它将在前半周期写入寄存器，在后半周期进行读操作，此时不会产生冲突。如果指令的结果在 Memory 阶段，则可以将它重定向回 Decode 阶段的 equal_cmp。

类似 2.7.1.1 节，以 $rs 的情况为例，重定向逻辑如下：

1

assign forward_a_d_o = rs_d_i && rs_d_i == write_reg_m_i && reg_write_m_i;

2.7.2.2 使用阻塞解决冲突

如果指令的结果在 Execute 阶段，或者指令 lw 的结果在 Memory 阶段，则需要阻塞流水线。

类似 2.7.1.2 节，阻塞逻辑如下：

1
2
3
4
5
6
7

assign branch_stall = (branch_d_i || jump_d_i[1])
    && (reg_write_e_i && (rs_d_i == write_reg_e_i || rt_d_i == write_reg_e_i)
    || mem_to_reg_m_i && (rs_d_i == write_reg_m_i || rt_d_i == write_reg_m_i));

assign stall_d_o = lw_stall || branch_stall;
assign flush_e_o = stall_d_o;
assign stall_f_o = stall_d_o;

其中，jump_d[1] 信号为 1 时表示当前指令为 jr。

2.7.2.3 清除无效数据

当发生跳转时，需要清除跳转指令之后多读的一条无效指令，即刷新 Decode 阶段，产生气泡。

刷新逻辑如下：

1

assign flush_d_o = pc_src_d_i || jump_d_i;

3 样例测试

3.1 测试结果

3.2 测试环境

• Windows 10 Version 2004 (OS Build 19041.207)
• Vivado v2019.1

3.3 结果分析

可以看到本实现的 CPI 偏高，经观察发现主要是 bubble sort 的样例 CPI 比较高（达到了 \(1.8\)），其余样例的 CPI 普遍在 \(1.2\) 左右。分析原因可能是因为 bubble sort 的循环较多，而静态分支预测对循环不太友好，跳转指令的 CPI 通常为 \(2\)。如果引入动态分支预测，则跳转指令的 CPI 将更接近 \(1\)，从而改善整体的 CPI。

由于时间有限，目前暂未实现动态分支预测，因此这里仅进行理论上的分析。

参考资料

1. David Money Harris, Sarah L. Harris: Digital Design and Computer Architecture Second Edition