流水线处理器

我们已经通过icache提升了NPC的指令供给能力, 虽然面积预算很有限, 但添加icache还是明显提升了NPC的总体性能表现. 剩下的优化方向包括提升数据供给能力和提升计算效率.

评估dcache的理想收益

提升数据供给能力的有效方法是添加dcache. 我们在上一节已经要求你通过性能计数器来估算dcache的理想收益了, 在对icache进行优化后, dcache在理想情况下带来的加速比可能会发生变化. 尝试重新评估dcache的理想收益.

通过cachesim评估dcache的预期性能表现

尝试改进你的cachesim, 让其可以读入mtrace, 然后评估一定大小的dcache的预期性能表现.

你应该会发现, 在剩余的面积预算下, 我们很难通过dcache来有效提升NPC的数据供给能力. 因此, 把剩余的面积用在提升计算效率, 是更科学的决策. 目前的NPC是多周期的, 这意味着NPC每经过若干个周期才能执行一条指令. 如果能提升NPC执行指令的吞吐, 就可以提升其计算效率. 流水线作为一种指令级并行技术, 可以有效提升NPC执行指令的吞吐.

评估提升计算效率的理想收益

我们还没有介绍流水线的具体实现, 但你已经可以根据性能计数器来估算流水线技术的理想收益了. 假设除访存指令之外, NPC每个周期都可以执行一条指令, 尝试估算在当前icache缺失情况的条件下, 此时NPC的理想加速比能到多少?

从全系统角度评估性能收益

这个估算结果可能会出乎你的意料.

还记得Amdahl's law那个加速5000倍的例子吗? 只看一项技术自身带来的性能收益, 和放到全系统场景下带来的性能收益, 可能是完全不同的. 如果你实现了乱序多发射, 但指令供给和数据供给跟不上, 在真实芯片中它们只是一堆占面积占功耗但对程序的运行性能提升不大的门电路.

流水线的基本原理

工厂流水线

在我们的生活中也存在流水线的思想, 最常见的就是工厂中的流水线. 例如, 某工厂生产产品需要经过组装, 贴纸, 装入包装袋, 装入包装盒, 外检这5道工序. 如果分别用1~5来标识这些工序, 用A, B, C......标识不同的产品, 那么, 不采用流水线方式的时空图如下:

          ----> 时间
 | 产品
 | +---+---+---+---+---+
 V |A.1|A.2|A.3|A.4|A.5|
   +---+---+---+---+---+
                       +---+---+---+---+---+
                       |B.1|B.2|B.3|B.4|B.5|
                       +---+---+---+---+---+
                                           +---+---+---+---+---+
                                           |C.1|C.2|C.3|C.4|C.5|
                                           +---+---+---+---+---+
================================================================
          ----> 时间
 | 员工
 | +---+               +---+                +---+
 V |A.1|               |B.1|                |C.1|
   +---+               +---+                +---+
       +---+               +---+                +---+
       |A.2|               |B.2|                |C.2|
       +---+               +---+                +---+
           +---+               +---+                +---+
           |A.3|               |B.3|                |C.3|
           +---+               +---+                +---+
               +---+               +---+                +---+
               |A.4|               |B.4|                |C.4|
               +---+               +---+                +---+
                   +---+                +---+                +---+
                   |A.5|                |B.5|                |C.5|
                   +---+                +---+                +---+

而采用流水线方式的时空图如下:

          ----> 时间
 | 产品
 | +---+---+---+---+---+
 V |A.1|A.2|A.3|A.4|A.5|
   +---+---+---+---+---+
       +---+---+---+---+---+
       |B.1|B.2|B.3|B.4|B.5|
       +---+---+---+---+---+
           +---+---+---+---+---+
           |C.1|C.2|C.3|C.4|C.5|
           +---+---+---+---+---+
               +---+---+---+---+---+
               |D.1|D.2|D.3|D.4|D.5|
               +---+---+---+---+---+
                   +---+---+---+---+---+
                   |E.1|E.2|E.3|E.4|E.5|
                   +---+---+---+---+---+
================================================================
          ----> 时间
 | 员工
 | +---+---+---+---+---+
 V |A.1|B.1|C.1|D.1|E.1|
   +---+---+---+---+---+
       +---+---+---+---+---+
       |A.2|B.2|C.2|D.2|E.2|
       +---+---+---+---+---+
           +---+---+---+---+---+
           |A.3|B.3|C.3|D.3|E.3|
           +---+---+---+---+---+
               +---+---+---+---+---+
               |A.4|B.4|C.4|D.4|E.4|
               +---+---+---+---+---+
                   +---+---+---+---+---+
                   |A.5|B.5|C.5|D.5|E.5|
                   +---+---+---+---+---+

可以看到, 在流水线方式中, 虽然每个产品的生产时间没有减少, 但由于每位员工都一直保持工作状态, 它们能连续处理不同产品的同一道工序, 使得从总体上来看, 每一时刻都有一件产品完成生产, 从而提升产线的吞吐.

指令流水线

类比工厂流水线, 处理器也可以用流水线方式来执行指令. 我们把指令执行的过程分为若干个阶段, 让每个部件处理其中一个阶段, 并让这些部件保持工作状态, 可以连续处理不同指令的同一个阶段, 使得从总体上来看, 每个周期都有一条指令完成执行, 从而提升处理器的吞吐.

在学习总线的时候, 我们已经要求大家把NPC升级成一个分布式控制的多周期处理器. 多周期处理器已经有阶段的概念了, 其工作过程和上述工厂场景中的非流水线方式非常类似. 因此, 指令流水线的工作方式也不难理解了.

我们可以对几种处理器的性能进行简单的分析评估. 假设将处理器的工作分为取指, 译码, 执行, 访存, 写回这5个阶段, 它们的逻辑延迟都是1ns, 且先不考虑取指和访存的延迟.

单周期处理器: 阶段间无寄存器, 因此关键路径为5ns, 频率为200MHz. 其中, 一条指令需要执行1周期, 即5ns; 每1周期执行1条指令, 即IPC = 1.
多周期处理器: 阶段间有寄存器, 因此关键路径为1ns, 频率为1000MHz. 其中, 一条指令需要执行5周期, 即5ns; 每5周期执行1条指令, 即IPC = 0.2.
流水线处理器: 阶段间有寄存器, 因此关键路径为1ns, 频率为1000MHz. 其中, 一条指令需要执行5周期, 即5ns; 每1周期执行1条指令, 即IPC = 1.

处理器	频率	指令执行延迟	IPC
单周期	200MHz	5ns	1
多周期	1000MHz	5ns	0.2
流水线	1000MHz	5ns	1

可以看到, 虽然指令执行的延迟仍然是5ns, 但流水线具有频率高和IPC高的优势, 这些优势本质上是由指令级并行技术带来的: 流水线处理器的每个周期都在处理5条不同的指令.

当然, 上面只是从理想情况下分析得到的数据. 如果考虑SoC中的访存, IPC就远远没有这么高了; 此外流水线处理器也并不是总能在每个周期都执行5条指令, 我们会在下文进一步分析.

更长的流水线

上面的例子只将流水线划分成5个阶段. 事实上, 我们可以将流水线划分成更多的阶段, 使得每一个阶段的逻辑更简单, 从而提升处理器整体的频率. 这种流水线称为"超流水"(superpipeline). 例如, 如果能将流水线划分成30级, 按照上面的估算, 理论上频率可以达到6GHz.

但目前的主流高性能处理器一般只会将流水线划分成15级左右, 你认为有可能是哪些因素导致不宜将流水线划分成过多的阶段?

流水线的简单实现

基于握手机制的多周期处理器来实现流水线并不困难, 对于每个阶段的输入in和输出out, 我们只需要正确处理以下信号 (bits指代阶段之间需要传输的负载):

out.bits, 由当前阶段生成
out.valid, 由当前阶段生成, 通常还与in.valid有关
in.ready, 由当前阶段生成, 忙碌时置为无效, 处理完当前指令时置为有效
out.ready, 与下一阶段的in.ready相同
in.bits, 当前阶段的in.ready和上一阶段的out.valid同时有效时, 更新成上一阶段的out.bits
in.valid, 作为作业留给大家

根据上述内容, 我们可以将后三个信号的处理包装成一个函数, 然后用它来连接各个阶段即可:

def pipelineConnect[T <: Data, T2 <: Data](prevOut: DecoupledIO[T],
  thisIn: DecoupledIO[T], thisOut: DecoupledIO[T2]) = {
    prevOut.ready := thisIn.ready
    thisIn.bits := RegEnable(prevOut.bits, prevOut.valid && thisIn.ready)
    thisIn.valid := ???
  }

pipelineConnect(ifu.io.out, idu.io.in, idu.io.out)
pipelineConnect(idu.io.out, exu.io.in, exu.io.out)
pipelineConnect(exu.io.out, lsu.io.in, lsu.io.out)
// ...

特别地, IFU无需等待当前指令执行结束, 即可马上取出下一条指令. 上述的RegEnable起到了传统教科书中"流水段寄存器"的作用, 但我们也可以从总线的视角将它理解为下游模块接收消息的缓冲区: 上下游握手成功后, 上游模块认为下游模块已经成功接收到消息, 因此它不再保存该消息, 故下游模块需要将收到的消息记录到缓冲区中, 防止消息丢失. 而对于前三个信号, 由于其具体逻辑与当前阶段的行为有关, 因此需要在当前阶段对应的模块中实现.

特别地, 流水线处理器中会存在一些无法继续执行当前指令的情况, 称为"冒险"(Hazard). 冒险主要分为3类: 结构冒险, 数据冒险和控制冒险. 如果无视冒险强行执行, 将会导致CPU状态机的转移结果与ISA状态机不一致, 表现为指令的执行结果不符合其语义. 因此在流水线设计中, 我们需要检测出冒险, 要么通过硬件设计消除它们, 要么从时间上等待冒险不再发生. 对于后者, 可以通过对in.ready和out.valid添加等待条件来实现.

结构冒险

结构冒险是指流水线中的不同阶段需要同时访问同一个部件, 但该部件无法支持被多个阶段同时访问. 例如, 在下图所示的指令序列中, 在T4时刻, I1正在LSU中读数据, I4正在IFU中取指令, 两者都需要读内存; 在T5时刻, I1正在WBU中写寄存器, I4正在IDU中读寄存器, 两者都需要访问寄存器堆.

           T1   T2   T3   T4   T5   T6   T7   T8
         +----+----+----+----+----+
I1: lw   | IF | ID | EX | LS | WB |
         +----+----+----+----+----+
              +----+----+----+----+----+
I2: add       | IF | ID | EX | LS | WB |
              +----+----+----+----+----+
                   +----+----+----+----+----+
I3: sub            | IF | ID | EX | LS | WB |
                   +----+----+----+----+----+
                        +----+----+----+----+----+
I4: xor                 | IF | ID | EX | LS | WB |
                        +----+----+----+----+----+

部分结构冒险可以从硬件设计上完全避免, 使其不会在CPU执行过程中发生: 我们只需要在硬件设计上让这些部件支持同时被多个阶段访问即可. 具体地:

对于寄存器堆, 我们只需要独立实现其读口和写口, 让IDU通过读口访问寄存器堆, 让WBU通过写口访问寄存器堆
对于内存, 则有多种解决方案
- 像寄存器堆那样将读口和写口分开, 实现真双口的内存
- 将内存分为指令存储器和数据存储器, 两者独立工作
- 引入cache, 如果在cache中命中, 则无需访问内存

教科书和真实系统的差异

教科书上的解决方案大多基于一些简化过的假设, 这些假设在真实的处理器中很可能不再成立, 因此它们不一定适合在"一生一芯"的场景中使用.

例如, SDRAM的存储颗粒无法将读口跟写口分开, 无论是READ命令还是WRITE命令, 都是通过SDRAM的存储器总线传递给SDRAM颗粒. 而将内存分为指令存储器和数据存储器, 将会使得指令和数据位于不同的地址空间, 这违反了ISA规范对指令和数据采用统一地址空间的内存模型. 一方面, 现代编译器无法编译出适应上述方案的程序; 另一方面, 即使采用汇编语言来开发程序, 类似bootloader的加载程序功能也无法正确运行.

事实上, "一生一芯"对大家提出了更高的要求: 学会从全系统的角度评价一个方案. 教科书上的简化假设能帮助大家聚焦到当前知识点的学习中, 但你将来要面对的是真实的项目, 只有学会将系统中的各个因素关联起来, 你才能在将来的工作中做出合理有效的决策.

还有一些结构冒险还是无法完全避免, 例如:

cache缺失时, IFU和LSU还是要同时访问内存
SDRAM控制器的队列满了, 无法继续接收请求
除法器的计算需要花数十个周期, 在一次计算结束之前无法开始另一次

为了应对上述情况, 一种简单的处理方式是等待: 如果IFU和LSU同时访存, 就让一个等待另一个; 等SDRAM控制器的队列有空闲位置; 等除法器完成当前计算. 一个好消息是, 总线天生就具备等待的功能, 因此只要从设备, 下游模块或仲裁器把ready置为无效, 就能把结构冒险的检测和处理归约到总线状态机, 从而无需实现专门的结构冒险检测和处理逻辑.

谁等谁?

在等待的时候, 是让IFU等待LSU, 还是让LSU等待IFU? 还是两种方案都可以? 为什么?

数据冒险

数据冒险是指不同阶段的指令依赖同一个寄存器数据, 且至少有一条指令写入该寄存器. 例如, 在下图所示的指令序列中, I1要写a0寄存器, 但要在T5时刻结束时才完成写入, 在这之前, I2在T3时刻读到a0的旧值, I3在T4时刻读到a0的旧值, I4在T5时刻读到a0的旧值, I5在T6时刻才能读到a0的新值.

                    T1   T2   T3   T4   T5   T6   T7   T8   T9
                  +----+----+----+----+----+
I1: add a0,t0,s0  | IF | ID | EX | LS | WB |
                  +----+----+----+----+----+
                       +----+----+----+----+----+
I2: sub a1,a0,t0       | IF | ID | EX | LS | WB |
                       +----+----+----+----+----+
                            +----+----+----+----+----+
I3: and a2,a0,s0            | IF | ID | EX | LS | WB |
                            +----+----+----+----+----+
                                 +----+----+----+----+----+
I4: xor a3,a0,t1                 | IF | ID | EX | LS | WB |
                                 +----+----+----+----+----+
                                      +----+----+----+----+----+
I5: sll a4,a0,1                       | IF | ID | EX | LS | WB |
                                      +----+----+----+----+----+

上述数据冒险称为写后读(Read After Write, RAW)冒险, RAW冒险的特征是, 一条指令需要写入某寄存器, 而另一条更年轻的指令需要读出该寄存器. 显然, 如果不处理这种数据冒险, 指令I2, I3和I4将会因为读到a0的旧值而计算出错误的结果, 违反指令执行的语义.

指令之间的顺序关系

中文的"前"和"后"存在歧义, 可以指代"以前"/"前方"/"以后"/"后方", 在动态指令序列中一般采用"年老"和"年轻"来描述不同指令之间的先后关系. 例如, "I1比I2年老"(I1 is older than I2), 表示I1在时间上比I2先执行; "I2比I1年轻"(I2 is yonger than I1), 表示I2在时间上比I1后执行.

解决RAW冒险有多种方式. 从软件上来看, 指令是由编译器生成的, 因此一种方式是让编译器来检测RAW冒险, 并插入空指令, 来等待写入寄存器的指令完成写入, 如下图所示:

                    T1   T2   T3   T4   T5   T6   T7   T8   T9   T10  T11  T12
                  +----+----+----+----+----+
I1: add a0,t0,s0  | IF | ID | EX | LS | WB |
                  +----+----+----+----+----+
                       +----+----+----+----+----+
    nop                | IF | ID | EX | LS | WB |
                       +----+----+----+----+----+
                            +----+----+----+----+----+
    nop                     | IF | ID | EX | LS | WB |
                            +----+----+----+----+----+
                                 +----+----+----+----+----+
    nop                          | IF | ID | EX | LS | WB |
                                 +----+----+----+----+----+
                                      +----+----+----+----+----+
I2: sub a1,a0,t0                      | IF | ID | EX | LS | WB |
                                      +----+----+----+----+----+
                                           +----+----+----+----+----+
I3: and a2,a0,s0                           | IF | ID | EX | LS | WB |
                                           +----+----+----+----+----+
                                                +----+----+----+----+----+
I4: xor a3,a0,t1                                | IF | ID | EX | LS | WB |
                                                +----+----+----+----+----+
                                                     +----+----+----+----+----+
I5: sll a4,a0,1                                      | IF | ID | EX | LS | WB |
                                                     +----+----+----+----+----+

插入空指令的本质还是等待, 但其实编译器还可以做得更好: 与其等待, 还不如执行一些有意义的指令. 这可以通过让编译器进行指令调度的工作来实现, 编译器可以尝试寻找一些没有数据依赖关系的指令, 在不影响程序行为的情况下调整其顺序. 一个例子如下, 其中I6, I7和I8均与I1无数据依赖关系, 因此可以调度到I1之后执行:

I1: add a0,t0,s0          I1: add a0,t0,s0
I2: sub a1,a0,t0          I6: add t5,t4,t3
I3: and a2,a0,s0          I7: add s5,s4,s3
I4: xor a3,a0,t1   --->   I8: sub s6,t4,t2
I5: sll a4,a0,1           I2: sub a1,a0,t0
I6: add t5,t4,t3          I3: and a2,a0,s0
I7: add s5,s4,s3          I4: xor a3,a0,t1
I8: sub s6,t4,t2          I5: sll a4,a0,1

编译器和乱序执行处理器

如果把编译器的指令调度工作下放到硬件来完成, 我们就得到了一个乱序执行处理器. 当然, 为了在硬件上完成指令调度的工作, 我们还需要额外添加不少硬件模块. 但从本质上来说, 这两项技术都是为了提升处理器执行指令的效率.

不过对于指令调度的工作, 编译器只能尽力而为, 并非总能找到合适的指令. 例如, 除法指令需要执行数十个周期, 编译器通常很难找到这么多合适的指令. 在这些情况下, 如果要让编译器来处理RAW冒险, 还是只能插入空指令.

一个更糟糕的消息是, 有的RAW光靠编译器是无法解决的. 考虑被依赖的指令是一条load指令, 这种RAW冒险称为load-use冒险:

                    T1   T2   T3  ....  T?   T?   T?   T?   T?   T?   T?
                  +----+----+----+--------------+----+
I1: lw  a0,t0,s0  | IF | ID | EX |      LS      | WB |
                  +----+----+----+--------------+----+
                       +----+----+----+----+----+
    nop X ?            | IF | ID | EX | LS | WB |
                       +----+----+----+----+----+
                                                +----+----+----+----+----+
I2: sub a1,a0,t0                                | IF | ID | EX | LS | WB |
                                                +----+----+----+----+----+

事实上, 在真实的SoC中, 软件几乎无法预测一条访存指令在将来执行时的延迟:

如果cache命中, 数据可能3个周期后返回
如果cache缺失, 要访问SDRAM, 数据可能30个周期后返回
如果正好碰上SDRAM充电刷新, 数据可能30+?个周期后返回
如果CPU频率从500MHz提升到600MHz, 数据返回所需的周期数更多

也因为这样, 现代处理器几乎都采用硬件检测并处理RAW冒险的方案. 由于寄存器的写入操作发生在WBU中, 因此需要写入的寄存器编号会也会随着流水线传播到WBU, 也即, 我们可以从每个阶段中找到相应指令将要写入哪一个寄存器. 如果位于IDU的指令要读出的寄存器与后续某阶段中将要写入的寄存器相同, 则发生RAW冒险:

def conflict(rs: UInt, rd: UInt) = (rs === rd)
def conflictWithStage[T <: Stage](rs1: UInt, rs2: UInt, stage: T) = {
  conflict(rs1, stage.rd) || conflict(rs2, stage.rd)
}
val isRAW = conflictWithStage(IDU.rs1, IDU.rs2, EXU) ||
            conflictWithStage(IDU.rs1, IDU.rs2, LSU) ||
            conflictWithStage(IDU.rs1, IDU.rs2, WBU)

上面的伪代码只是一个大致的思路, 实际上你还需要考虑更多的问题: 并非所有指令都需要写入寄存器, 并非所有阶段都正在执行指令, 并非所有指令都需要读出rs2(如U型指令), 零寄存器的值恒为0等. 如何写出正确的RAW检测代码, 就交给你来思考了.

检测到RAW冒险后, 最简单的处理方式还是等待: 只要把in.ready和out.valid置为无效即可. 可见, 这种硬件检测和处理RAW冒险的方案, 无需提前得知指令执行何时结束, 这是因为指令执行过程中的各种等待都会通过总线的握手信号传递到流水线当中, 因此适用性比上述的软件方案更强.

                    T1   T2   T3   T4   T5   T6   T7   T8   T9   T10  T11  T12
                  +----+----+----+----+----+
I1: add a0,t0,s0  | IF | ID | EX | LS | WB |
                  +----+----+----+----+----+
                       +----+-------------------+----+----+----+
I2: sub a1,a0,t0       | IF |         ID        | EX | LS | WB |
                       +----+-------------------+----+----+----+
                            +-------------------+----+----+----+----+
I3: and a2,a0,s0            |         IF        | ID | EX | LS | WB |
                            +-------------------+----+----+----+----+
                                                +----+----+----+----+----+
I4  xor a3,a0,t1                                | IF | ID | EX | LS | WB |
                                                +----+----+----+----+----+
                                                     +----+----+----+----+----+
I5: sll a4,a0,1                                      | IF | ID | EX | LS | WB |
                                                     +----+----+----+----+----+

控制冒险

控制冒险是指跳转指令会改变指令执行顺序, 导致IFU可能会取到不该执行的指令. 例如, 在下图所示的指令序列中, T4的IFU具体应该取出哪条指令, 需要等到I3在T5时刻计算出跳转结果后才能得知.

                 T1   T2   T3   T4   T5   T6   T7   T8
               +----+----+----+----+----+
I1: 100   add  | IF | ID | EX | LS | WB |
               +----+----+----+----+----+
                    +----+----+----+----+----+
I2: 104   lw        | IF | ID | EX | LS | WB |
                    +----+----+----+----+----+
                         +----+----+----+----+----+
I3: 108   beq 200        | IF | ID | EX | LS | WB |
                         +----+----+----+----+----+
                              +----+----+----+----+----+
I4: ???   ???                 | IF | ID | EX | LS | WB |
                              +----+----+----+----+----+

除了上述分支指令, jal和jalr也会造成类似问题. 假设上图的I3为跳转指令, 我们期望在T4时刻就取出跳转目标处的指令, 而在T4时刻IDU正好在对I3进行译码, 按道理是可以赶上的, 但现代处理器一般会认为还是赶不上, 从而将其作为控制冒险来处理.

为什么现代处理器要这样处理?

事实上, 有一些教科书确实会通过上述方式来处理控制冒险. 你认为有哪些因素使得上述的教科书方案无法在真实的处理器设计中采用?

甚至CPU抛出异常也会导致控制冒险. 抛出异常时, 需要马上从mtvec所指的内存位置重新取指, 但通常来说, 处理器无法在取指时刻就得知这条指令的执行是否会发生异常.

上述问题都是因为在取指阶段无法确定接下来真正需要取出哪条指令. 如果选择等待, 就要等待上一条指令几乎执行完成, 才能得知下一条指令的真正地址. 例如, 访存指令要等到访存结束后, 通过总线的resp信号才能确定访存过程没有抛出异常. 显然, 这个方案会使得指令流水线流不起来, 大幅降低处理器执行指令的吞吐. 而如果选择不等待, 就有可能取出了一部分不该执行的指令, 如果不采取进一步的处理措施, 处理器的状态转移就会与ISA状态机不一致, 从而导致执行结果不正确.

为了应对控制冒险, 现代处理器通常采用"推测执行"(speculative execution)的技术. 推测执行本质上是一种预测技术, 其基本思想是, 在等待的同时尝试推测一个选择, 如果猜对了, 就相当于提前做出了正确的选择, 从而节省了等待的开销. 推测执行具体由三部分组成:

选择策略 - 得到正确结果之前, 通过一定的策略推测一个选择
检查机制 - 得到正确结果时, 检查之前推测的选择是否与正确结果一致
错误恢复 - 如果检查后发现不一致, 则需要回滚到选择策略时的状态, 并根据得到的正确结果做出正确的选择

针对控制冒险, 一种最简单的推测执行策略是"总是推测接下来执行下一条静态指令". 从上述三部分考虑这种策略的实现, 具体如下:

选择策略 - 非常简单, 只需要让IFU一直取出PC + 4处的指令即可.
检查机制 - 根据指令的语义, 只有在执行分支和跳转指令, 以及抛出异常时, CPU才有可能改变执行流, 其他情况下都是顺序执行. 因而在其他情况下, 上述推测的选择总是正确的, 无需额外检查. 故只需要在执行分支和跳转指令, 以及抛出异常时, 才需要检查跳转结果与推测的选择是否一致, 也即, 检查跳转结果是否为PC + 4.
错误恢复 - 如果发现上述跳转结果不为PC + 4, 则说明之前的推测是错误的, 基于这一推测所取出的指令都不应该被执行, 应该将其从流水线上消除, 这一动作称为"冲刷"; 同时还需要让IFU从正确的跳转结果处取指.

推测执行所带来的性能提升与推测的准确率有关, 如果推测的准确率高, 则IFU能以高概率提前取到正确的指令, 从而节省等待的开销; 如果推测的准确率低, 则IFU经常取到不该执行的指令, 这些指令后续又被冲刷, 在这段时间内, 流水线的行为等价于未执行任何有效指令, 从而降低了执行指令的吞吐. 具体地:

由于异常属于处理器执行过程中的小概率事件, 绝大部分指令的执行都不会抛出异常, 因此针对异常, 上述策略的准确率接近100%
分支指令的执行结果只有"跳转"(taken)和"不跳转"(not taken), 上述策略相当于总是预测"不跳转", 因此从概率上来说, 针对分支指令, 上述策略的准确率接近50%
跳转指令的行为是无条件跳转到目标地址, 但目标地址的可能有很多, 正好跳转到PC + 4的概率非常低, 因此针对跳转指令, 上述策略的准确率接近0%

根据上述分析, 推测执行一方面可以正确处理控制冒险, 另一方面, 相对于消极等待的方式, 推测执行还可以带来一定的性能提升. 但针对分支指令和跳转指令, 上述的推测执行方案还有较大的提升空间, 我们会在下文继续讨论.

关于推测执行的实现, 还有一些需要注意的细节:

从需求的角度来看, 冲刷是为了将处理器的状态恢复成发生控制冒险之前的时刻, 因此, 我们可以从状态机的视角推导出应该如何处理相关的实现细节. 状态机视角告诉我们, 处理器的状态由时序逻辑电路决定, 而处理器的状态更新又受到控制信号的控制, 因此, 要实现冲刷的效果, 我们只需要考虑将相关的控制信号置为无效即可. 例如, 通过将valid置为无效, 可以将大部分部件正在执行的指令直接冲刷掉.
但如果部件中还存在一些影响控制信号的状态, 你还需要进行额外的考量, 例如icache中的状态机, 尤其是发出的AXI请求无法撤回, 因此需要等待请求完成.
推测执行意味着当前执行的操作不一定是将来真正需要的, 如果推测错误, 就应该取消相关操作. 但有一些操作很难取消, 包括更新寄存器堆, 更新CSR, 写内存, 访问外设等, 这些模块的状态一旦发生改变, 就很难恢复到旧状态. 因此, 需要在确认推测正确后, 才能更新这些模块的状态.

实现简单的流水线处理器

用最简单的方式处理各种冒险, 从而实现最基本的流水线结构. 实现后, 尝试运行microbench, 从而检查你的实现是否正确.

Hint:

为了让DiffTest正确工作, 你可能需要修改向仿真环境传递的信号
目前你可以先忽略异常处理相关的实现, 我们接下来再实现它

嵌套的推测执行

思考一下, 如果遇到了连续的分支指令或者跳转指令, 你的设计还能正确工作吗?

对于流水线处理器中异常的实现, 我们还需要考虑如下细节:

抛出异常时, 需要将mepc设置为发生异常的指令的PC值, 这种特性称为"精确异常". 如果不满足这一特性, 从异常处理通过mret返回时, 就无法精确返回到之前发生异常的指令处, 从而使得发生异常前后的状态不一致. 这可能会导致系统软件无法利用异常机制实现现代操作系统的某些关键机制, 例如进程切换, 请页调度等. 但在流水线处理器中, IFU的PC会不断变化, 等到某条指令在执行过程中抛出异常时, IFU的PC已经与这条指令不匹配了. 为了获取与该指令匹配的PC, 我们需要在IFU取指时将相应的PC一同传递到下游.
指令可能会在推测执行时抛出异常, 但如果推测错误, 那实际上这条指令不应该被执行, 所抛出的异常也不应该被处理. 因此, 在异常处理过程中需要更新处理器状态的操作, 都需要等到确认推测正确后, 才能真正进行, 包括写入mepc, mcause, 跳转到mtvec所指示的位置等.
mcause的更新取决于异常的类型, 在RISC-V处理器中, 不同的异常号由不同的部件产生. 产生的异常号也需要传递到流水线的下游, 等到确认推测正确后, 才能真正写入mcause.

异常号	异常描述	最早产生的部件
0	Instruction address misaligned	IFU
1	Instruction access fault	IFU
2	Illegal Instruction	IDU
3	Breakpoint	IDU
4	Load address misaligned	LSU
5	Load access fault	LSU
6	Store/AMO address misaligned	LSU
7	Store/AMO access fault	LSU
8	Environment call from U-mode	IDU
9	Environment call from S-mode	IDU
11	Environment call from M-mode	IDU
12	Instruction page fault	IFU
13	Load page fault	LSU
15	Store/AMO page fault	LSU

实现支持异常处理的流水线

按照上述内容, 实现支持异常处理的流水线. 实现后, 运行一些异常处理相关的测试, 来检查你的实现是否正确.

发生多个异常

在流水线处理器中, 不同阶段会执行不同的指令, 这意味着不同阶段可能会同时产生不同的异常. 例如, 在IFU发现指令地址不对齐的同时, IDU发现非法指令, LSU发现读访存错误. 这时应该如何处理?

尽管目前我们不要求你实现所有异常, 但你仍然可以思考, 你的设计可以正确处理这一情况吗?

Intel的超流水架构

在2005年之前的一段时间, Intel曾经使用超流水技术追求极致的主频. 在2004年2月, Intel发布了一款架构代号为Prescott在新窗口中打开的处理器, 其流水线深度达到前所未有的31级, 即使在当时的90nm工艺节点上, 主频也达到了3.8GHz. 但在实测时发现, 和上一代20级流水线的Northwood相比, 这款处理器的性能并没有得到太大提升在新窗口中打开, 反而成为了x86史上运行最烫和功耗最高的单核处理器. 事实上, 在如果不是散热和功耗问题, 这款处理器的主频还能比3.8GHz更高: 在发布的一年前, Intel宣称这款处理器的主频最高可以达到5GHz在新窗口中打开.

从微结构层面来看, 31级流水线的执行效率也并不尽如人意. 一方面, 流水线中的指令充斥着数据冒险, 很多指令因为RAW冒险, 只能在流水线中等待. 另一方面, 分支指令因推测执行错误而冲刷流水线的代价却很高. 假设处理器在第26级计算出分支指令是否跳转, 在推测执行错误的情况下, 前面的25个周期所取出的指令需要全部冲刷. 特别地, Prescott是一个多发射处理器, 每周期可进行4次简单ALU操作在新窗口中打开, 估算其为4发射, 因此在推测执行错误的情况下, 需要冲刷25 * 4 = 100条指令! 尽管Prescott采用了一些先进的技术提升推测的准确率, 但根据实测结果, 仍然有不少程序的性能因为过长的流水线而下降在新窗口中打开.

后来, Intel放弃了这种激进超流水的技术路线, 后续架构的流水线深度普遍在15级左右, 最多不超过20级在新窗口中打开.

流水线处理器的测试验证

流水线的处理对象是指令, 这意味着, 不同的指令序列将对流水线的行为产生不同的影响. 因此, 流水线的验证过程应将指令序列作为测试输入, 并尽可能覆盖各种不同的情况. 根据指令在流水线中的行为, 可粗略分为以下10个种类:

加/减/逻辑/移位等ALU可在一周期内完成计算的指令
控制流转移指令, 分3种: 条件分支, jal, jalr
访存指令, 分2种: load, store
CSR指令
ecall, mret
fence.i

仅仅考虑上述10类指令在传统5级流水线中的组合情况, 就已经有种可能. 事实上, 还需要考虑上文提到的各种冒险: 访存可能需要等待, 指令之间存在数据依赖, 控制流转移指令会导致流水线冲刷...... 总得来说, 不同情况组合而成的指令序列实在太多, 即使是开发一个指令生成器, 也很难保证覆盖上述所有情况, 如果是人工设计那么多测试用例, 就更困难了.

通过传统的指令测试集无法证明处理器的正确性

如果你了解类似riscv-tests的指令测试集, 你需要明白, 通过riscv-tests并不代表流水线NPC是正确的. 事实上, riscv-tests中提供的测试用例数量远远没到上文粗略计算的100000, 这就已经说明了, 必定存在某些指令序列, 是riscv-tests无法覆盖的. 更本质地, riscv-tests测试的是单条指令的行为, 而充分测试流水线处理器, 需要的是遍历各种指令序列. 因此, 如果你的流水线NPC仅仅通过了riscv-tests这些传统的指令测试集, 你不应该对你的NPC实现感到100%放心.

既然人工参与测试用例的设计很困难, 那就想办法交给工具吧! 回顾我们在验证缓存的时候用到的形式化验证工具, 它可以自动帮助我们找到违反assert的测试用例, 如果找不到, 就证明了设计的正确性. 如果能够将形式化验证应用到流水线NPC, 就可以让工具帮助我们自动寻找错误的指令序列了!

要使用形式化验证, 我们还需要一个REF, 以及编写合适的验证条件(即assert). 对于REF, 我们需要可以正确执行指令序列的另一个实现. 由于我们使用的形式化验证工具只能在RTL层次进行验证, 因此暂时无法接入类似NEMU和Spike的指令集模拟器. 不过我们可以考虑之前开发的单周期NPC, 它同样作为RISC-V ISA的微结构实现, 必然能正确执行指令序列.

至于验证条件, 一个想法是像DiffTest那样, 在DUT和REF执行完相同的指令后, 检查两者GPR的状态是否一致. 在C代码中, 检查所有GPR是否一致只是一次memcmp()的调用, 开销并不大; 但在形式化验证中, 检查所有GPR是否一致却是作为"解方程"的约束条件, 会对BMC的求解过程带来不小的开销. 为此, 我们有必要寻找一种较为简单的对比方法.

回顾状态机模型, 新状态取决于当前状态以及状态的转移. 因此, 除了直接对比新状态, 我们还可以从另一个角度来进行对比: 在当前状态一致的情况下, 如果状态的转移也一致, 那么新状态也应当一致. 通常来首, 描述一次状态转移比描述状态本身(即状态空间)要小很多, 因此对比状态的转移是否一致, 通常是一种更简单的对比方式. 以上述GPR的状态为例, 虽然GPR的状态空间有位, 但一条RISC-V指令最多写入一个GPR, 我们只需要记录这条指令将哪个GPR更新成哪个值, 并对比DUT和REF的这条记录是否一致, 就不必直接对比512位的GPR状态空间是否一致, 从而大幅简化对比的开销.

根据上文的分析, 我们很容易编写出验证顶层模块的伪代码. 这里我们用Chisel作为伪代码, 如果你使用Verilog开发, 你仍然可以借鉴相关思路来编写验证顶层模块.

class PipelineTest extends Module {
  val io = IO(new Bundle {
    val inst = Input(UInt(32.W))
    val rdata = Input(UInt(XLEN.W))
  })

  val dut = Module(new PipelineNPC)
  val ref = Module(new SingleCycleNPC)

  dut.io.imem.inst  := io.inst
  dut.io.imem.valid := ...
  dut.io.dmem.rdata := io.rdata
  dut.io.dmem.valid := ...
  // ...

  ref.io.imem.inst := dut.io.wb.inst
  // ...

  when (dut.io.wb.valid) {
    assert(dut.io.wb.rd  === ref.io.wb.rd)
    assert(dut.io.wb.res === ref.io.wb.res)
  }
}

上述伪代码只给出了大致的框架, 还有不少细节需要你注意并补充:

为了减小BMC的求解空间, DUT只包含流水线本身, 而不包含缓存和各种外设模块, 但可以通过握手信号实现缓存缺失带来的访存延迟
指令是验证顶层模块的输入之一, 这意味着BMC将会遍历各种指令, 在界的作用下, BMC将会遍历各种指令在不同周期下的组合, 也即实现了在给定长度下所有指令序列的遍历.
生成的指令序列将会依次输入DUT的IFU, 但由于对一条指令来说, 在流水线NPC中需要等待若干周期才能完成执行, 而在单周期NPC中只需要1周期即可完成执行, 因此需要在DUT和REF之间进行同步, 使得DUT执行完一条指令后, 才将该指令输入到REF中, 故需要在DUT的WBU中获得当前完成执行的指令.
除了对比写入的GPR编号rd及其值res外, 还需要对比PC, 以检查控制流的转移是否正确. 不过我们可以选择对比PC的新值, 这样能提早一个周期捕捉PC不一致的错误.
有的指令不写入GPR, 对于这些指令, 我们无需对比rd和res.
对于load指令, 其访存结果也作为流水线的输入之一, 故需要在验证顶层模块的端口处体现. 为了保证DUT和REF在执行同一条load指令后状态一致, 还需要保证它们读出相同的数据.
对于store指令的执行结果, 我们不进行专门的对比, 主要有两点考虑:
1. 写数据和写地址都来源于GPR, 如果它们有错, 那么一定存在一条比store指令年老的指令向GPR写入了错误的值, 这种情况可以通过上述机制检查出来.
2. 如果写数据和写地址没错, 但AXI写通道的信号错了, 这个问题属于AXI总线实现的范畴, 不属于流水线的验证范畴. 原则上也可以在流水线的验证框架中加入对AXI信号的检查, 但这将会增加BMC的约束条件, 从而增加求解的开销.
需要正确处理IFU和LSU的握手信号.
对于CSR的写入, 我们也不进行专门的对比, 因为若对某CSR的写入实现错误, 则可以通过额外一条指令将该CSR的值读入GPR中, 将错误的值暴露出来, 从而将CSR写入的对比归约为GPR写入的对比.
还需要令GPR和CSR在DUT和REF中都有相同的初始状态, 因此需要对GPR和CSR初始化. 注意, 这只是形式化验证的要求, 在仿真和流片时, 并非所有GPR和CSR都需要初始化.
由于指令序列是BMC由生成的, 如果不加任何限制, 生成的指令序列中可能会包含非法指令. 如果NPC不支持非法指令异常的处理, 则NPC执行非法指令的行为是未定义的, 这将不利于对比指令序列的执行结果. 为了解决这个问题, 一种思路是只允许BMC生成合法的指令, 这可以通过Chisel和SystemVerilog皆提供的assume语句来实现, 它用于表示验证的前提条件. 例如, 若isIllegal表示"指令译码结果为非法指令", 则assume(!isIllegal)表示将"指令译码结果不为非法指令"作为验证的前提条件, 此时, BMC将在此前提条件下进行求解, 从而排除指令序列中的非法指令.
CSR指令中的CSR寄存器地址也需要考虑, 同样可以通过assume语句, 将CSR指令中的CSR寄存器地址限制在已实现的CSR范围内.
另一个需要考虑的是不对齐访存, 如果不加任何限制, 生成的访存指令中计算得到的地址可能是不对齐的. 这个问题同样可以通过assume语句来解决.

更换效率更高的模型检测工具

我们在2024/08/20 02:30:00修改了调用形式化验证工具的方式, 将对Z3求解器的调用更换成对BtorMC模型检测器的调用, 以此提升形式化验证的效率. 如果你使用Chisel进行开发, 请重新参考缓存部分"形式化验证的简单示例"小节的内容.

通过形式化验证测试流水线的实现

尽管这不是必须的, 我们还是强烈建议你通过形式化验证来测试你的流水线. 不过你需要仔细思考assert和assume这些验证条件如何编写, 如果它们的编写不恰当, 可能会导致误报或漏报: 误报可以在调试时发现并修复相应的验证条件, 但漏报就难以发现了. 因此, 这个任务本质上也是考察大家对流水线细节的理解是否有足够深入.

此外, 关于BMC的界, 你可以挑选一个合适的参数, 使形式化验证工具能遍历足够多的指令序列, 并覆盖各种冒险组合的情况. 通常来说, 界可能需要达到10以上, 不过这要求求解过程花费数小时甚至数十小时的时间, 但从工具的便利性来说, 这还是非常值得的, 因为如果通过人工方式编写测试用例, 即使花费数天的时间, 也不一定能够编写出可以覆盖一些极端情况的测试用例. 不过为了快速找到一些反例, 你可以从一个小的界开始测试, 然后逐渐测试更大的界.

用形式化验证测试更复杂的处理器

中科院软件所的研究团队开发了一套基于形式化验证的RISC-V处理器测试框架, 通过它甚至找到了可启动Linux的NutShell处理器在新窗口中打开中一些非常隐蔽的bug, 具体可参考他们研发的nutshell-fv项目在新窗口中打开. 这个案例也反应出形式化验证技术的优势. 不过由于目前NPC的功能经过了诸多简化, 为了接入到这个测试框架中, 你可能需要对你的代码和测试框架的代码进行一些调整. 如果你感兴趣, 可以阅读项目中的README来了解其使用方法, 并通过阅读相关代码了解测试框架的相关细节.

让流水线流起来

实现简单的流水线处理器后, 我们来讨论如何提升流水线的效率.

评估简单流水线的性能

在优化之前, 你需要先评估一下上述简单流水线的性能. 和实现流水线之前的多周期相比, 你发现实现流水线后性能有多少提升? 如果你发现性能反而倒退了, 我们建议你通过性能计数器深入理解其原因.

流水线的理想情况是每周期都可以完成一条指令的执行, 但一般情况下流水线的吞吐无法达到理想情况, 主要原因如下:

指令供给能力不足, 无法向流水线提供足够的指令
数据供给能力不足, 访存指令的执行被阻塞
计算效率不足, 由于上述三种冒险的存在, 流水线需要阻塞

定位性能瓶颈

要提升流水线的效率, 我们首先要定位性能瓶颈. 尝试在流水线处理器中添加更多性能计数器, 从各种阻塞原因中分析出当前的性能瓶颈.

根据你的设计自行决定是否采用以下优化方案

下面介绍一些可能有用的优化方案, 具体是否在RTL设计中采用, 取决于很多因素, 包括你之前的设计, 对当前性能计数器的分析, 以及剩余的可用面积等. 但我们还是要求你在进行RTL实现之前对相应技术的预期性能收益进行评估, 这对体系结构设计能力来说是非常重要的训练: 你可以选择不实现某个优化技术, 但你需要用量化分析方法得出的数据佐证你的决策.

不过"减少数据冒险的阻塞"对应优化方案是一个重要的知识点, 我们将其作为必做题.

总之, 如果之前的面积优化工作做得比较好, 现在你就有更多的机会来进行优化了.

提升指令供给能力

在之前的多周期处理器中, 假设每条指令执行5个周期, 这时, 只要指令供给能力达到0.2条指令/周期, 就能满足多周期处理器的指令消费需求. 但在流水线处理器中, 理想情况下的指令消费需求提升到了1条指令/周期, 如果指令供给能力无法达到相应水平, 就无法发挥流水线的优势. 不过对于icache来说, 缺失时需要访问内存, 此时必定无法达到上述的指令供给能力, 因此我们重点考虑icache在命中时的指令供给能力. 根据icache设计的不同, 是否需要在此处对icache进行优化, 也会有不同的决策.

具体地, 如果你的icache可以在1周期内判断是否命中, 并在命中的情况下向IFU返回指令, 则icache的指令供给能力已经接近1条指令/周期, 基本满足流水线处理器的指令消费需求. 这种情况下, 你基本上无需进一步提升指令供给能力, 但你可能需要付出频率不高的代价, 毕竟icache需要在一个周期内完成较多的操作, 这也会导致流水线无法在较高频率下工作.

如果你的icache在命中的情况下也需要多个周期才能向IFU返回指令, 则icache的指令供给能力最大为0.5条指令/周期, 甚至更低. 在这样的指令供给能力之下, 流水线的性能会受到明显的约束. 假设icache在命中的情况下需要3个周期才能向IFU返回指令, 则有以下的指令时空图. 由于cache的发音和cash相同, 因此一些英文文献也用$来指代cache, 下图为了简化, 也采用I$来指代icache, 替换之前的IF, 因为此时IF需要等待的时间与icache的访问时间一致:

       T1   T2   T3   T4   T5   T6   T7   T8   T9   T10  T11  T12  T13
     +--------------+----+----+----+----+
 I1  |      I$      | ID | EX | LS | WB |
     +--------------+----+----+----+----+
                    +--------------+----+----+----+----+
 I2                 |      I$      | ID | EX | LS | WB |
                    +--------------+----+----+----+----+
                                   +--------------+----+----+----+----+
 I3                                |      I$      | ID | EX | LS | WB |
                                   +--------------+----+----+----+----+

要提升icache的指令供给能力, 某种程度上也是要提升icache的吞吐. 这个需求和上文中提到的"提升指令执行的吞吐"非常类似, 很自然地, 我们也可以尝试将icache的访问流水化!

       T1   T2   T3   T4   T5   T6   T7   T8   T9
     +----+----+----+----+----+----+----+
 I1  | I$1| I$2| I$3| ID | EX | LS | WB |
     +----+----+----+----+----+----+----+
          +----+----+----+----+----+----+----+
 I2       | I$1| I$2| I$3| ID | EX | LS | WB |
          +----+----+----+----+----+----+----+
               +----+----+----+----+----+----+----+
 I3            | I$1| I$2| I$3| ID | EX | LS | WB |
               +----+----+----+----+----+----+----+

估算icache流水化带来的性能收益

尝试根据性能计数器, 粗略估算icache流水化带来的性能收益.

上图将icache的访问进一步划分成3个阶段, 并通过流水线技术将这3个阶段在时间上重叠起来, 从而让icache在命中时的吞吐接近1条指令/周期. 为了实现icache的流水化, 你可以根据icache命中时的状态转移过程来设计上述阶段, 这和我们将处理器改成流水线是非常类似的, 甚至比处理器流水线更简单, 因为icache的工作过程不存在控制冒险的概念. 当然, 如果icache发成缺失, 则还是需要阻塞icache流水线, 并通过状态机控制内存的访问和icache的更新. 由于缺失会导致icache的更新, 这可能会导致类似数据冒险的问题, 因此你需要考虑如何正确相应的情况, 具体如何解决, 还是取决于你的实现.

实现icache的流水化

如果你的icache在命中时需要多个周期才能向IFU返回指令, 尝试借鉴指令流水线的思想, 将icache的访问流水化, 从而提升其指令供给能力. 实现后, 尝试通过性能计数器和benchmark, 分别评估指令供给能力的提升是否符合预期.

上文将icache的访问划分成3个阶段, 仅仅是一个示例, 你应该根据你的具体设计决定阶段如何划分. 如果你之前使用了类似PipelineConnect()的方式来实现流水线, 你会发现icache的流水化是很容易实现的: 你只需要定义好阶段之间需要传递的信息, 就已经实现了接近90%的内容了.

实现后, 尝试与之前估算的性能提升进行对比, 来检查你的实现是否符合预期.

减少数据冒险的阻塞

在上述的简单流水线中, 我们是通过阻塞等待的方式来处理RAW数据冒险的, 这一方案需要等待被依赖的寄存器写入新值后, 被阻塞的指令才能继续执行, 显然这样的等待会降低流水线的吞吐.

一个观察是, 被依赖寄存器的新值是在WB阶段写入, 但其实这个值最早在EX阶段就已经被计算出来了, 并会随着流水线传递给LS阶段和WB阶段. 因此, 我们可以考虑提前从这些阶段中将计算出的新值拿过来给后续指令使用, 让它们不必等待被依赖寄存器完成更新, 即可拿到正确的源操作数开始执行, 这种技术称为"转发"(forward)或"旁路"(bypass).

                    T1   T2   T3   T4   T5   T6   T7   T8
                  +----+----+----+----+----+
I1: add a0,t0,s0  | IF | ID | EX | LS | WB |
                  +----+----+----+----+----+
                                |    |    |
                                V    |    |
                       +----+----+----+----+----+
I2: sub a1,a0,t0       | IF | ID | EX | LS | WB |
                       +----+----+----+----+----+
                                     |    |
                                     V    |
                            +----+----+----+----+----+
I3: and a2,a0,s0            | IF | ID | EX | LS | WB |
                            +----+----+----+----+----+
                                          |
                                          V
                                 +----+----+----+----+----+
I4  xor a3,a0,t1                 | IF | ID | EX | LS | WB |
                                 +----+----+----+----+----+

估算转发技术的理想性能提升

可以看到, 转发技术可以很好地消除load-use冒险以外的RAW阻塞. 至于load-use冒险, 因为load指令需要等待数据读出后才能转发, 在此之前仍然需要阻塞流水线.

尝试根据性能计数器, 估算转发技术能带来的理想性能提升.

我们先来讨论转发技术对数据通路的修改. 在上述流水线中, 转发源有3个, 分别是EX阶段, LS阶段和WB阶段, 它们都有可能携带可以转发的数据. 但转发并不能无条件进行, 需要转发源满足以下条件: 将要写入寄存器, 待写入的寄存器编号和被依赖寄存器编号一致, 并且数据已经就绪. 前两个条件和上文提到的RAW冒险检测条件一致, 因此可以复用RAW冒险的检测逻辑; 最后一个条件和指令的行为有关, 大部分计算类指令都可以在EX阶段计算出结果, 因此在EX阶段得到的结果即可转发到ID阶段; 但load指令在EX阶段只能计算出访存地址, 因此不应该在EX阶段进行转发, 而且在LS阶段也需要在总线的R通道握手后才能得到返回的数据, 在这之前也不应该进行转发.

除了数据通路的变化, 我们还需要考虑控制通路的修改. 之前在简单流水线处理器中, 一旦检测到RAW冒险, 就会阻塞流水线. 而使用转发技术后, 阻塞流水线的条件将有所变化:

如果ID阶段未检测到RAW冒险, 则无需阻塞流水线, 这与上文的简单流水线一致
如果ID阶段检测到了RAW冒险, 并且存在某个阶段满足转发条件, 则无需阻塞流水线, 同时将转发的数据作为ID阶段的输出
如果ID阶段检测到了RAW冒险, 但不存在满足转发条件的阶段, 则需要阻塞流水线

特别地, 如果存在多条指令同时满足转发条件, 则需要仔细考量. 考虑以下指令序列:

                      T1   T2   T3   T4   T5   T6   T7   T8
                    +----+----+----+----+----+
I1: add a0, a0, a1  | IF | ID | EX | LS | WB |
                    +----+----+----+----+----+
                         +----+----+----+----+----+
I2: add a0, a0, a1       | IF | ID | EX | LS | WB |
                         +----+----+----+----+----+
                              +----+----+----+----+----+
I3: add a0, a0, a1            | IF | ID | EX | LS | WB |
                              +----+----+----+----+----+
                                   +----+----+----+----+----+
I4: add a0, a0, a1                 | IF | ID | EX | LS | WB |
                                   +----+----+----+----+----+

假设I1不依赖于比它更老的指令, 则不必阻塞I1的执行; 对于I2, 它依赖于I1的结果, 但通过转发技术, 可以在T3时刻将I1在EX阶段的结果转发给位于ID阶段的I2, 因此也不必阻塞I2的执行; 对于I3, 在T4时刻发现, 位于EX阶段的I2和位于LS阶段的I1均满足转发条件, 但从ISA状态机的视角考虑, 指令是串行执行的, 因此I3读出的a0应该是最近一次写入a0的结果, 因此应该选择由位于EX阶段的I2进行转发; 同理, 对于I4, 在T5时刻, 位于EX阶段的I3, 位于LS阶段的I2和位于WB阶段的I1均满足转发条件, 但从ISA状态机的视角考虑, 应该选择由位于EX阶段的I3进行转发. 也即, 存在多条指令同时满足转发条件时, 应该选择最年轻的指令进行转发.

实现转发技术

根据上述内容, 在流水线中实现转发技术, 从而消除大部分RAW冒险. 实现后, 尝试与之前估算的性能提升进行对比, 来检查你的实现是否符合预期.

教科书上的转发方案

上述转发方案是将其他阶段的计算结果转发到ID阶段后, 再选出正确的操作数送入流水段寄存器, 而大部分教科书上的转发方案则是转发到EX和LS阶段, 然后在计算之前选出正确的操作数.

尝试对比这两种方案, 如果你想不清楚, 可以分别实现这两种方案, 然后从IPC, 频率, 面积等各个方面对比它们.

减少控制冒险的阻塞

在上述简单流水线中, 我们用推测执行来应对控制冒险. 具体地, 我们推测"接下来总是执行下一条静态指令", 如果推测正确, 就能消除控制冒险带来的阻塞. 但事实上, 上述推测并非总是正确, 此时需要冲刷流水线, 从而浪费了若干周期. 要提升流水线的执行效率, 一个角度是降低冲刷流水线带来的负面影响.

估算优化控制冒险相关阻塞带来的性能收益

尝试根据性能计数器, 粗略估算完全消除控制冒险相关阻塞时的性能, 从而相应优化技术的理想性能收益.

要降低冲刷流水线对处理器执行效率带来的负面影响, 可以从以下两个方向考虑:

降低单次冲刷流水线的代价. 这需要尽快计算出分支指令的结果. 有的教科书中介绍了在ID阶段计算分支结果的方案, 这显然可以提升流水线的IPC, 但还需要从频率和面积的角度综合评估这一方案.
降低冲刷流水线的次数. 这需要提升推测的准确率. 根据上文的分析, "推测异常不发生"的准确率已经接近100%, 因此主要考虑分支指令和跳转指令的推测准确率.

通常通过"分支预测"(branch prediction)技术来提升分支指令的推测准确率, 进行分支预测的模块称为分支预测器(branch predictor). 分支指令的执行结果只有"跳转"(taken)和"不跳转"(not taken), 因此分支预测技术只需要在两个选择中预测一个即可, 具体如何给出一个预测结果, 称为分支预测算法. 考虑是否参考运行时刻的信息, 分支预测算法分为静态预测和动态预测两种. 这里我们先介绍静态预测算法, 我们将在A阶段介绍动态预测算法.

体会现代处理器中分支预测器的重要性

尝试统计动态指令数中分支指令的占比, 即, 假设平均每x条指令中包含一条分支指令, 求x.

假设在某理想的五级流水线处理器中, 指令供给能力为1条/周期, 无结构冒险和数据冒险, 访存延迟均为0周期, 跳转指令总能预测正确, 但分支指令可能会预测错误, 且分支指令在EX阶段计算出跳转结果. 根据上文求得的x, 分别计算处理器在不同分支预测准确率下的IPC: 100%, 99.5%, 99%, 95%, 90%, 80%.

将上述处理器改进为乱序单发射15级流水, 其中分支指令在第13级计算出跳转结果, 其他假设不变, 重新计算处理器在不同分支预测准确率下的IPC.

继续将处理器改进为乱序四发射15级流水, 其他假设不变, 重新计算处理器在不同分支预测准确率下的IPC.

静态预测只根据分支指令本身来进行预测. 由于分支指令本身在程序执行过程中不会发生变化, 因此对于给定的一条分支指令和给定的一种静态预测算法, 其预测结果总是相同的. 上文的"总是推测接下来执行下一条静态指令", 站在分支预测技术的角度, 就是"总是不跳转", 是一种静态预测算法. 另一种静态预测算法是"总是跳转".

事实上, 根据分支跳转方向的不同, 分支指令的执行结果是否跳转, 是有偏向性的(bias). 这其实和程序中循环的行为有关, 例如, 当分支的跳转目标位于前方(年轻指令)时, 可能是一个循环的出口, 因此偏向不跳转; 而当分支的跳转目标位于后方(年老指令)时, 可能是要重新执行循环体, 因此偏向跳转. 一种利用这一特性的静态预测算法称为BTFN(Backward Taken, Forward Not-taken): 若分支的跳转目标位于后方, 则预测跳转, 反之则预测不跳转. 实现时, 只需要根据B型指令offset的符号位, 即可得到预测结果. 事实上, RISC-V手册也建议编译器按照BTFN的模式生成代码:

Software should also assume that backward branches will be predicted taken and
forward branches as not taken, at least the first time they are encountered.

评价一个分支预测算法的重要指标就是预测准确率. 和之前的icache类似, 对于给定的程序, 需要执行哪些分支指令, 以及每条分支指令的执行结果, 都是固定的. 只要获得程序运行的itrace, 我们就能快速统计一个分支预测算法的准确率, 没有必要进行RTL层次的仿真. 更进一步地, itrace已经包含了完整的指令流, 除分支以外其他指令的trace, 对分支指令的执行结果没有影响, 因此我们真正需要的, 只有分支指令的trace, 我们称为btrace(branch trace).

根据上述分析, 我们只需要实现一个分支预测器的功能模拟器, 我们称它为branchsim. branchsim接收btrace, 并根据分支预测算法预测出每一条分支指令是否跳转, 然后与btrace中记录的执行结果进行对比, 统计该算法的预测准确率. 至于btrace, 我们可以通过NEMU来快速生成.

实现branchsim

根据上文的介绍, 实现一个简单的分支预测模拟器branchsim, 然后分别评估上述静态预测算法的准确率, 并根据预测准确略评估该预测算法带来的性能收益.

如果你对动态预测算法感兴趣, 可以先学习相关资料, 然后在branchsim中实现相应的算法并评估其准确率.

和cachesim类似, branchsim也可以作为分支预测性能表现的REF. 例如, 上文的简单流水线中采用了"总是不跳转"的静态预测算法, 相关的性能计数器应该与branchsim给出的统计结果完全一致.

通过branchsim选出一个表现较好的分支预测算法后, 就可以考虑如何在处理器中实现一个分支预测器了. 通常来说, 分支预测器的预测结果需要提供给IFU使用: 如果预测跳转, 则让IFU从分支指令的跳转目标处取指, 否则, 则让IFU从PC + 4处取指. 但实际上, 我们在ID阶段才能得知一条指令是否为分支指令, 如果为分支指令, 也需要在ID阶段才能得知其跳转目标. 而在IF阶段中, 我们只有PC值, 难以获得上述信息来进行分支预测.

解决上述问题的方法是通过一张表来维护PC和分支跳转目标的对应关系, 这张表称为BTB(Branch Target Buffer). BTB可以看作一个特殊的cache, 它通过PC值进行索引, 若命中, 表示该PC对应一条分支指令, 可从中读出跳转目标; 若缺失, 表示该PC对应的指令不是分支指令, 此时让IFU从PC + 4处取指即可. 此外, BTB需要在处理器执行过程中进行填充更新, 原则上最早可以在ID阶段中译码出分支指令时更新BTB. 通常BTB的项数有限, 若更新时发现无空闲表项, 根据局部性原理, 此时应该覆盖旧表项. 特别地, 处理器复位时, BTB中的表项均无效, 此时无法读出正确的跳转目标. 但由于分支预测属于推测执行技术, 预测错误也不影响处理器执行程序的正确性, 等到往BTB中写入正确的表项后, 即可进行有效的预测.

              tag     target
           +-------+----------+   Branch Target Buffer
+----+     +-------+----------+
| PC |---> +-------+----------+
+-+--+     +-------+----------+
  |        +-------+----------+
  |            |         | branch               predicted
  |            v         | target +-----------+  next PC  +-----+
  |          +----+      +------->|  branch   |---------->| IFU |
  +--------->| == |-------------->| predictor |           +-----+
             +----+    is branch  +-----------+

实现分支预测器

由于不同分支的信息可能会在项数有限的BTB中互相替换, 因此在进行分支预测时, 当前PC对应的分支指令的跳转目标并非总是可获得的. 这种情况将会影响分支预测的准确率, 因此你需要在branchsim中添加一个BTB, 来校准其预测准确率.

具体地, 先在RTL中实现一个简单的BTB, 组织方式不限, 你可以根据需要选择采用直接映射, 全相联还是组相联. 你也可以根据你的需要, 在BTB中添加新的字段. 实现后, 评估其面积, 根据剩余的面积选择合适的BTB项数, 然后根据这一项数调整branchsim, 重新评估分支预测算法的准确率.

重新评估后, 再综合所有因素决定如何实现分支预测器. 实现后, 将RTL的分支预测准确率与branchsim中统计的分支预测准确率进行对比.

上文介绍的是分支指令的预测, 对于跳转指令, 也需要进行推测执行. 跳转指令都是无条件的, 但跳转结果有多种, 因此对跳转指令的预测主要是预期其跳转目标. 跳转指令又分直接跳转jal和间接跳转jalr. 对于给定的jal指令, 其跳转目标是确定的, 因此只要将jal指令的跳转目标记录到BTB中, 只要相应表项未被替换, 下次遇到该jal指令时就能以100%的准确率取到正确的跳转目标处的指令. 至于jalr指令, 其跳转目标由执行该指令时的源寄存器的值决定, 仅靠静态预测算法难以预测成功, 需要考虑相应的动态预测算法. 为简单起见, 目前可对jalr指令采用"总是不跳转"的预测算法.

估算跳转指令推测执行正确的性能收益

尝试根据性能计数器, 分别估算jal指令和jalr指令推测执行正确时的理想性能收益.

如果要对jal指令的跳转目标进行预测, 你可以让jal指令与分支指令共享同一个BTB, 也可以让jal指令单独使用另一个BTB. 前者可以节约面积, 但指令之间的表项可能会互相覆盖, 从而影响预测准确率; 后者则相反. 你可以根据branchsim的评估情况决定如何设计.

实现jal指令的跳转目标预测

根据上述方案, 实现jal指令的跳转目标预测.

实现ret指令的跳转目标预测

一般来说, jalr指令的跳转目标比较难预测正确, 但作为一类特殊的jalr指令, ret指令是比较容易预测正确的. 如果你感兴趣, 并且有较为充足的剩余面积, 可以查阅"返回地址栈"(Return Address Stack)的相关资料, 并在处理器中实现ret指令的跳转目标预测.

优化流水线

根据分析出的性能瓶颈, 在满足面积约束的前提下, 尝试将有限的面积资源投入到最值得投入的优化技术中, 尽可能提升处理器的性能.

重新审视处理器的性能优化

我们能预料到, 在完成这一部分内容的时候, 你并不会感到十分愉快: 要么可用面积非常紧张, 难以添加优化技术; 要么添加优化技术后处理器频率有所下降, 抵消了该技术对IPC带来的提升; 要么投入很大精力之后, 终于使得面积和频率的表现都不错, 但发现IPC的提升很小......

更重要的是, 你应该会在心中隐隐感觉到一种无奈: 流水线作为组成原理教科书上的技术巅峰, 它的性能表现就这? 事实上, 这种技术巅峰的幻觉来源于教科书上对指令供给和数据供给的大幅削弱, 让你误以为计算效率就是处理器设计的一切, 让你觉得乱序多发射就是处理器设计的终极追求. 你需要从"学会流水线, 就具备了体系结构设计能力"的幻想中清醒过来, 认识到性能计数器, Amdahl's law, 模拟器等等对体系结构设计的意义, 学会在面积, 主频和IPC之间作出合理的取舍, 甚至能找到一个各方面表现都不错的方案, 这才是一名合格的架构师需要具备的能力.

而上述的这些能力, 是无法仅仅通过将书上的架构图翻译成RTL代码来获得的. 如果你只是参考一些书籍的代码, 就更别想了. 相反, 我们之所以按照当前的顺序来组织讲义内容, 就是希望大家早日从上面的幻觉中醒悟过来, 在SoC中面对残酷的现实, 然后学会用科学的方法一点一点探索出合理的处理器优化方案.

从结果上看, 你设计的处理器性能可能还很弱, 但如果你完成了我们设置的训练, 你就已经锻炼出真正的体系结构设计能力: 你学会分析性能瓶颈, 学会从中思考出新方案, 学会去估算其性能收益, 学会在各种约束下将这个方案实现出来, 学会去评测你的实现是否符合预期...... 这些比你学会用RTL写一个流水线处理器重要得多.

因此, 你也可以通过以下方法检验自己是否具备体系结构设计能力: 如果你脱离了参考书就不知道应该做什么, 或者需要询问他人才知道一个方案的优劣, 那就是不具备体系结构设计能力.

`fence.i`的处理

最后, 我们还需要对fence.i指令在流水线中的执行进行额外的处理. 回顾fence.i的语义, 其行为是让在其之后的取指操作都能看到在其之前的store指令修改的数据. 我们已经在实现icache的时候, 通过对icache进行特殊处理, 来保证后续取指操作不会通过icache取到过时的指令.

在流水线处理器中, 过时的指令可能会存在于流水线中. 考虑如下示例: 假设fence.i在EX阶段生效, 但作为比fence.i年轻的指令, I3和I4已经取出并在流水线中, 它们有可能是过时的, 继续执行它们可能会导致CPU状态机的转移结果与ISA状态机不一致, 从而造成错误.

                 T1   T2   T3   T4   T5   T6   T7
               +----+----+----+----+----+
I1: add        | IF | ID | EX | LS | WB |
               +----+----+----+----+----+
                    +----+----+----+----+----+
I2: fence.i         | IF | ID | EX | LS | WB |
                    +----+----+----+----+----+
                         +----+----+
I3: ??? may be stale     | IF | ID |
                         +----+----+
                              +----+
I4: ??? may be stale          | IF |
                              +----+
                                   +----+----+----+----+----+
I5: sub                            | IF | ID | EX | LS | WB |
                                   +----+----+----+----+----+

设计反例

根据上述分析, 设计一个fence.i相关的测试用例, 使得该测试用例在之前的多周期处理器中运行正确, 但在流水线处理器中运行出错.

解决上述问题的方案也很简单: 既然上述指令是不应该被执行的, 将其冲刷掉即可. 实现时, 可以复用推测执行错误时的冲刷逻辑.

在流水线中正确实现fence.i

在执行fence.i时冲刷流水线, 然后重新运行上述测试用例. 如果你的实现正确, 测试用例将运行成功.

# 流水线处理器