处理器¶

单周期 CPU¶

处理器由控制单元和数据通路组成，其中数据通路包括多路选择器、ALU、寄存器等元件，控制单元负责根据指令的机器码选择不同的数据通路。

在单周期 CPU 中，每条指令都只在一个周期内完成，指令逐条执行。其中，每个指令都需要做的操作是：

从内存获得指令的机器码
得到下一条指令的地址

根据指令的类型，还可能进行的操作有：

使用 ALU 进行运算
向内存写入数据
从寄存器读取数据
向寄存器写入数据

获得机器码和读取寄存器的操作对每个指令来说都是一样的，可以共享相同的数据通路，而其他的操作则需要通过控制单元选择不同的数据通路来完成。

这里给出一个 Datapath 的示例：

Single Datapath

立即数处理¶

由 RISC-V 指令格式易得，不同类型的指令的立即数如下：

I-type: $signed({inst[31:20]})
S-type: $signed({inst[31:25], inst[11:7]})
B-type: $signed({inst[31], inst[7], inst[30:25], inst[11:8], 1'b0})
J-type: $signed({inst[31], inst[19:12], inst[20], inst[30:21], 1'b0})
U-type: {inst[31:12], 12'b0}

控制单元需要根据指令的 opcode 获得对应的控制信号，来生成各种指令的立即数。

ALU 运算¶

在 ALU 运算之前，要先根据指令的机器码，从寄存器中读取相应的 rs1 和 rs2，并生成相应的立即数。这里的实现是以 rs1 为第一个操作数，rs2 或 imm 为第二个操作数。

不同指令需要进行的运算操作为：

add 等指令需要以 rs1 和 rs2 为操作数进行某些运算
addi 等指令需要以 rs1 和 imm 为操作数进行某些运算
lw sw 等指令需要以 rs1 和 imm 为操作数计算内存地址
beq blt 等指令需要以 rs1 和 rs2 为操作数比较结果
jalr 指令需要以 rs1 和 imm 为操作数计算跳转地址

可以看到，这些指令的运算只涉及 rs1, rs2 和 imm，因此我们只需做完简单连接，然后让控制单元根据指令机器码选择第二个操作数和 ALU 运算类型即可。

lui 和 auipc 的运算的操作数并不涉及寄存器，所以一般不在 ALU 中进行。需要注意的是，beq blt 等分支指令的运算也可以不在 ALU 中进行，直接在数据通路中构建电路，得到对应的分支跳转信号即可。

指令跳转¶

指令的跳转有四种可能：

跳转到顺序执行的下一条指令：是大多数指令的情况，也在分支指令失败时发生，需要计算 PC + 4
跳转到 PC 相对地址：在执行 jal 指令或分支指令成功时发生，需要计算 PC + imm
跳转到寄存器相对地址：在执行 jalr 指令时发生，需要计算 rs1 + imm

因此，可以使用一个四路选择器，根据指令的类型选择不同的跳转地址：

若为 jal 指令，则选择 PC + imm
若为分支指令，则根据比较结果选择 PC + 4 或 PC + imm
若为 jalr 指令，则选择 ALU 运算结果
若为其余指令，则选择 PC + 4

在运算出了跳转地址之后，我们在上升沿将 PC 更新为跳转地址，这样就实现了单周期 CPU 的指令跳转。

内存写入¶

sb sh sw 等指令都是写入 rs2，因此我们需要输出 rs2 作为写入数据。写入的数据可能不是四字节宽的，但是我们这里的 RAM 却是四字节写入，因此先将写入的数据左移到正确的位置，然后再写入。

例如，若要写入 0xF8 至地址 0x0002，则需要先将其左移变为 0x00F80000，再写入 RAM 中。需要移动的位数为 addr % 4 * 8，最终的表达式为 data << (addr[1:0] << 3)。

控制单元也需要相应地控制 RAM 的写入使能信号 wea。因为我们这里的 RAM 是四字节写入的，所以 wea 是四位的，每一位分别代表对应字节的读写信号。我们需要使得其每一位仅在需要被写入时为 1，其余任何时候都为 0。

需要注意的是，我们必须等到数据和地址都准备好之后再写入 RAM，否则若数据变化而地址未变，则会向之前的地址写入错误的数据。为此，可以将 RAM 的时钟置为 CPU 时钟的反，使得 RAM 在 CPU 时钟的下降沿写入数据，给 CPU 足够的时间准备。

内存读取¶

lb lh lw lbu 等指令读入的数据位宽不同，位宽不足时的扩展方式也不同。对于读入位宽小于 32 位的指令，我们可以先将读入数据右移，使得我们要读取的数据位于低位，然后再取低位对应宽度的数据进行扩展：

lw 直接读入内存数据
lb 读入 $signed(shifted_data[7:0])
lh 读入 $signed(shifted_data[15:0])
lbu 读入 shifted_data[7:0]
lhu 读入 shifted_data[15:0]

右移数据的方式与写入内存时类似，需要右移 addr[1:0] << 3 位。

寄存器读写¶

寄存器可能会写入五种数据：

add addi 等指令会写入 ALU 运算的结果
lb lw 等指令会写入内存读取的数据
jal 和 jalr 指令写入 PC + 4
lui 指令会写入 imm
auipc 指令会写入 PC + imm

控制单元在遇到上述指令时需要将寄存器写入使能信号 we 设置为 1，其余情况下为 0，同时在写入时，根据指令类型选择不同的写入数据。

获取寄存器的读写地址较为简单，直接将 inst[19:15] 作为 rs1 地址，inst[24:20] 作为 rs2 地址，inst[11:7] 作为 rd 地址输入即可。

流水线 CPU¶

概览¶

我们可以将所有指令分为五个阶段依次执行：

IF (Instruction Fetch): 从内存读取指令
ID (Instruction Decode): 译码指令并读取寄存器
EX (Execute Operation): 进行 ALU 运算
MEM (Memory): 读写内存
WB (Write Back): 写回寄存器

在流水线中，数据通路会被分为五个部分，每个部分对应一个阶段，每个阶段的操作都是独立的，可以同时进行。数据通路的每个部分都有自己对应的流水线寄存器，存储着处于当前阶段的指令的相关信息。每过一个时钟周期，数据通路的每个部分就会根据输出，更新下一个阶段的流水线寄存器。这样，当一条指令进入流水线的下一个阶段后，后续的指令可以立即进入前一个阶段，实现指令的并行执行。

Pipeline Datapath

流水线虽然不能改善单个指令的延迟，但是可以提高 CPU 的吞吐量，以及内存、CPU 等资源的利用效率。

将流水线划分为几个阶段需要权衡：一方面，阶段越多，指令之间的并行度就越高，有利于缩短运行时间；另一方面，许多计算无法被分为更小的阶段，每个阶段之间的 latch 也会带来延迟，反而会增加运行时间。

冒险¶

在流水线中，指令的并行会带来冒险 (Hazard) 的问题：

数据冒险 (Data Hazard)：后面的指令需要使用前面的指令的结果，但是前面的指令还没有执行完毕
控制冒险 (Control Hazard)：分支指令的执行会改变程序的执行流程，但是无法立即得知下一条指令的地址
结构冒险 (Structural Hazard)：多个指令需要同时访问同一个硬件资源，导致资源冲突

所有冒险都可以通过 stall 来解决，但是这会极大地降低流水线的效率。流水线 CPU 的 CPI 几乎总是 1，但是加上 stall 后，就变成了：

\[\text{CPI pipelined} = 1 + \text{Pipeline stall clk cycles per instruction}\]

提升的速度就变成了：

\[ \begin{aligned} \text{Speedup} &= \frac{1}{1 + \text{Pipeline stall per instruction}} \times \frac{\text{Clock cycle unpipelined}}{\text{Clock cycle pipelined}} \\ &= \frac{\text{Pipeline depth}}{1 + \text{Pipeline stall per instruction}} \end{aligned} \]

结构冒险¶

结构冒险可能会发生在内存和寄存器这两个硬件资源上：

内存会在 IF 和 MEM 这两个阶段被访问，可能因为读取地址不同发生竞争，可以通过将指令和数据分别存储在 ROM 和 RAM 来解决
寄存器会在 ID 和 WB 这两个阶段被访问，可能因为同时读写发生竞争，可以通过双重触发 (double bump) 来解决，即先在在时钟周期中间的触发沿执行写操作，再执行读操作

除了内存和寄存器以外，还有一些未完全流水线化的功能单元可能导致结构冒险，如浮点数乘法器等。它们的单次执行时间超过一个时钟周期，因此可能会有多条指令同时使用它们，导致流水线暂停等待。尽管如此，大多数机器仍会使用未流水线化的元件，因为流水线化既会提高成本，又会增加该元件的延迟。

结构竞争的影响

假设浮点数乘法器的执行时间为 6 个时钟周期，在 SPECfp 基准测试中，浮点数乘法的频率为 14%。

在最好的情况下，刚好每隔七个时钟周期就发生一次浮点数乘法，这时不会发生结构竞争，CPI 不变。

在最坏的情况下，所有的浮点数乘法在一起执行，每条浮点数乘法指令都需要 stall 五次，CPI 会变为 $1 + 14\% \times 5 = 1.7$

最终的实验结果是，结构冒险只让执行时间增加了不到 3%。

数据冒险¶

在一个周期结束后，我们需要将读到的寄存器传输给 EX 阶段的流水线寄存器，用以 ALU 计算。但是我们读的寄存器可能是之前指令的目标寄存器，若之前的指令还没有写回，则我们读到的数据可能是错误的。

此时，前面的三条指令刚执行完 EX、MEM 和 WB 阶段，根据之前提到的双重触发，前面第三条指令不会发生数据冒险，但是前两条指令可能会发生。我们可以通过检测 EX 阶段和 MEM 阶段的流水线寄存器，来判断处于该阶段的指令是否会写回目标寄存器，从而得知是否会发生数据冒险：

RegWrite_ex && rd_addr_ex != 0 && rd_addr_ex == rsX_addr 表示位于 EX 阶段的指令会写回目标寄存器
RegWrite_mem && rd_addr_mem != 0 && rd_addr_mem == rsX_addr 表示位于 MEM 阶段的指令会写回目标寄存器
MemRead_ex && rd_addr_ex != 0 && rd_addr_ex == rsX_addr 表示位于 EX 阶段的指令会写回目标寄存器，且原因是 load memory
MemRead_mem && rd_addr_mem != 0 && rd_addr_mem == rsX_addr 表示位于 MEM 阶段的指令会写回目标寄存器，且原因是 load memory

当检测到会发生数据冒险时，我们可以将流水线暂停，直到数据准备好。stall 的方法是：

让 IF 和 ID 阶段的流水线寄存器保持不变，维持刚读取到该指令的状态
将 EX 阶段的流水线寄存器置为 nop 的状态，这样当前指令在后续阶段就不会产生任何影响

另一种方法解决数据冒险的方法是前推 (Forwarding)，即将要写回的数据直接传递给需要的地方，而不是等待写回。我们可以将要写回的数据一个阶段接一个阶段地传递下去，这样就可以在需要的时候直接使用。需要注意的是，在使用前推时，如果 EX 阶段和 MEM 阶段的指令同时写回，我们需要选择 EX 阶段的数据，因为 EX 阶段的数据是最新的。

然而，前推并不能解决所有的数据冒险。当 EX 阶段的指令是 load 时，要写回的数据还没有产生，需要再等待一个周期才能从内存中取出。此时，我们需要将流水线 stall 一次，做法如上所述。

load stall 的影响

假设 30% 的指令是 load，这其中又有一半的 load 指令后面紧跟着使用其结果的指令。

根据前推的实现，我们可以将 15% 的 load stall 通过前推解决，剩下的 15% 需要 stall 一个周期。

因此，结果是 CPI 变为 $1 + 30\% \times 50\% \times 1 = 1.15$。

控制冒险¶

当遇到跳转指令时，我们无法立即得知下一条指令的地址：

jal 指令需要用到立即数，最早在 ID 阶段才能计算得到
jalr 指令需要用到 rs1 和立即数，最早在 ID 阶段才能计算得到
分支指令需要比较 rs1 和 rs2，要等到 EX 阶段执行完毕才能得知是否跳转，即使提前知道是否要跳转，跳转地址最早也需要等到 ID 阶段结束才能得知

jal 和 jalr 较为简单，我们只需等到跳转地址计算出来之后把后续的指令 flush 掉，再用计算结果更新 PC 即可。flush 就是将对应的流水线寄存器置为 nop 的状态，例如将后续指令的机器码置为 0x00000013、写信号置为零等。

分支指令则有多种处理方法，最简单的是 stall，即等到跳转地址计算出来之后再执行。另一种方法是分支预测 (branch prediction)，常见的分支预测算法有：

predict-untaken: 预测总是不跳转。一种可能的做法是，在 IF 和 ID 阶段不做任何操作，在 EX 阶段结束时，若发现预测错误，则 flush 到 pc + imm
predict-taken: 预测总是跳转。一种可能的做法是，在 ID 阶段结束时 flush 到 pc + imm，在 EX 阶段结束时若发现预测错误，则 flush 到 pc + 4
2-bit predict: 两位预测器，根据历史记录预测是否跳转。一种可能的做法是，在 ID 阶段结束时，根据预测器决定是否 flush 到 pc + imm，在 EX 阶段结束时若发现预测错误，则更新预测器，并 flush 到另一个分支