Introduction to Computer Systems II @ Fudan University, spring 2020.
Pipeline MIPS CPU
32 位流水线 MIPS 指令集 CPU,使用 SystemVerilog 编写。[^1]
1. MIPS 指令集
同单周期,详见单周期实验报告。
2. 部件构成及分析
2.0 总览
如图所示为流水线 MIPS CPU 的整体概览,与单周期 MIPS CPU 是一样的,区别在于 CPU 核心 mips 的实现。以下将仅介绍与单周期不同的部分,其余请参见单周期实验报告。
2.1 mips
本流水线 CPU 的实现中,将 datapath 按照流水线的 5 个阶段划分为了 5 个模块(Fetch, Decode, Execute, Memory, Writeback),并增加了一个用于处理冲突的冲突单元(Hazard Unit)。其中各模块的作用如下 [^1]:
- Fetch:取指令阶段,从指令存储器中读取指令
- Decode:译码阶段,从寄存器文件中读取源操作数,并对指令译码以产生控制信号
- Execute:执行阶段,使用 ALU 执行计算
- 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 的数据。具体这些信号在何时为何值,将在 hazard_unit 章节详细阐述,下同。
代码见这里。
2.2.1 fetch_reg
Fetch 阶段流水线寄存器。结构很简单,就是将 PC 寄存器 pc_reg 封装了一下。但相较于单周期版本的 flip_flop,流水线版本做了一些调整。
代码见这里。
2.2.1.1 flip_flop
这里只说与单周期版本的区别,其余请参见单周期实验报告第 2.10 节。
首先增加了一个清零信号 CLR,当 CLR 为 1
时,将保存的数据同步清零(RST 为异步清零),用于 flush
信号。尽管这里 fetch_reg 并不需要用到,但其他流水线寄存器可能会需要,这里是出于部件复用的考虑。其次增加了一个低电平有效的保持信号 EN,当 EN 为 0
时,保持数据不变。对于 fetch_reg 来说,其值即 ~stall_f
。
代码见这里。
2.2.2 decode_reg
Fetch 阶段和 Decode 阶段之间的流水线寄存器。中转一下 instr
和 pc_plus_4
。为什么需要用触发器中转数据?因为流水线上需要同时跑多条指令(这里是 5 条),需要控制每个阶段各自只在执行一条指令。
这里 instr_reg 的 CLR 信号为 ~stall_d & flush_d
,是为了使 stall_d
和 flush_d
信号互斥,且强制 stall_d
的优先级更高(当 stall_d
为 1
时,flush_d
无效,不允许清零),否则当两者同时为 1
时会导致错误(因为在触发器的实现中,flush
的优先级更高,这将导致指令丢失)。pc_plus_4_reg 不需要清零,因此 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 新增了一个控制信号 sign
,用于控制对立即数进行符号扩展还是无符号扩展,解决了新增测试样例 i-type 中遇到的一些问题。此外为了调试方便,本实现中将控制信号中的无关项 x
都改成了 0
,其余同单周期版本。主译码器中,新增信号的真值表如下:
指令 | opcode | sign |
---|---|---|
R-type | 000000 | 0 |
addi | 001000 | 1 |
andi | 001100 | 0 |
ori | 001101 | 0 |
slti | 001010 | 1 |
lw | 100011 | 1 |
sw | 101011 | 1 |
j | 000010 | 0 |
jal | 000011 | 1 |
jr | 001000 | 0 |
beq | 000100 | 1 |
bne | 000101 | 1 |
代码见这里。
2.3.2 equal_cmp
32 位比较器,用于比较两个数是否相等。
使用时读入 A 和 B,若 A 和 B 相等则从 EQUAL 输出 1
。
代码见这里。
2.3.3 extend
扩展模块的作用是将 16 位的立即数扩展至 32 位。单周期版本中默认使用符号扩展,流水线版本中可以自行选择。
使用时从 A 读入待扩展的数据,从 RESULT 输出扩展后的数据。当 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]
,instr_d[20:16]
,instr_d[15:11]
,instr_d[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 冲突的方法:如果此时这个结果已经在某个阶段被计算出来,那么可以使用重定向(forwarding)将数据转发过来;否则需要阻塞(stall)流水线直到结果可用。需注意,$0
寄存器硬连接为 0
,因此源寄存器为 $0
时不需要进行转发或阻塞。以下将阐述这两种方法的具体实现。
2.7.1.1 使用重定向解决冲突
当 Execute 阶段的源寄存器 $rs
或 $rt
与 Memory 阶段或 Writeback 阶段(即前两条指令)的写入目标寄存器 write_reg
相同,且其 reg_write
信号为 1
时(即需要写入目标寄存器),重定向对应的 src_a
或 src_b
。以 $rs
的情况为例($rt
同理),重定向逻辑如下:
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 阶段直到源操作数准备好。阻塞逻辑如下:
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 阶段,产生气泡。
2.7.2 控制冲突
在取下一条指令时还不能确定指令地址时,将发生控制冲突,即处理器不知道应该取哪条指令。解决控制冲突的方法:预测下一条指令地址,如果预测错误则刷新流水线。目前的实现中使用的是静态分支预测,事实上动态分支预测可以获得更高的性能。
然而,静态分支预测将导致新的 RAW 冲突,因此需要再次使用第 2.7.1 节解决数据冲突时的两种方法。
2.7.2.1 使用重定向解决冲突
如果指令的结果在 Writeback 阶段,则它将在前半周期写入寄存器,而在后半周期进行读操作,此时不会产生冲突。如果指令的结果在 Memory 阶段,则可以将它重定向回 Decode 阶段的 equal_cmp。类似第 2.7.1.1 节,以 $rs
的情况为例($rt
同理),重定向逻辑如下:
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 节,阻塞逻辑如下:
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 阶段,产生气泡。刷新逻辑如下:
assign flush_d_o = pc_src_d_i || jump_d_i;
3. 样例测试
3.1 测试结果
3.2 测试环境
- OS: Windows 10 Version 2004 (OS Build 19041.207)
- Using Vivado v2019.1 (64-bit)
3.3 测试分析
可以看到本实现的 CPI 偏高,经观察发现主要是 bubble sort 的样例 CPI 较高(达到了 1.8
),其余样例的 CPI 普遍在 1.2
级别。分析原因可能在于其中的循环较多,而静态分支预测对循环并不友好,跳转指令的 CPI 通常为 2
。如果引入动态分支预测,则跳转指令的 CPI 将更接近 1
,从而大幅降低整体 CPI。
由于时间有限,未能有机会实现动态分支预测,因此仅在此做理论上的分析。
4. 贡献者
- Hakula Chen<[email protected]> - Fudan University
5. 许可协议
This project is licensed under the GNU General Public License v3.0 - see the LICENSE file for details.
6. 参考资料
[^1]: David Money Harris, Sarah L. Harris: Digital Design and Computer Architecture Second Edition
版权声明:本文为原创文章,版权归 Hakula 所有。
本文链接:https://hakula.xyz/comp_arch/pipeline_mips.html
本文采用 CC BY-NC-SA 4.0 许可协议 进行许可。