透过 RISC-V 模拟器搞懂指令管线化

本文目标

• 理解处理器在各个 stage 会有何种行为
• Pinpline 的概念
• 现代处理器面临的挑战
• 追踪原始码

进入正题

本篇文章藉由阅读 rv32emu 这个开源的 risc-v emulator 原始码介绍处理器如何执行组合语言，了解其工作原理後再看看如何透过 pinpline 和 branch-prediction 提升处理器效能。

2022/02/06： rv32emu-next 已经重新命名为 rv32emu。

工作流程

1. IO 以及记忆体、虚拟机初始化。
2. run() or run_and_trace()
   根据不同情况决定每个 cycle 要执行多少个指令後再呼叫 rv_step()。
3. rv_step() 拿出指令并判断其类型 (load, jump, store, branch...) 後呼叫 op()，让其做 dispatch 和後续动作。

• rv_step()
  达到 cycle 目标之前重复以下动作:

  1. 将指令从 pc 指向的记忆体位置读取出来。
  2. 读取出来之後，将指令交给 op handler: op() 进行处理。
  • op()
    在 riscv.c 的第 787 行处有预先定义好 RV32I 各类指令的 opcode (前五码)。

  static const opcode_t opcodes[] = {
  //  000        001          010       011          100        101       110   111
      op_load,   op_load_fp,  NULL,     op_misc_mem, op_op_imm, op_auipc, NULL, NULL, // 00
      op_store,  op_store_fp, NULL,     op_amo,      op_op,     op_lui,   NULL, NULL, // 01
      op_madd,   op_msub,     op_nmsub, op_nmadd,    op_fp,     NULL,     NULL, NULL, // 10
      op_branch, op_jalr,     NULL,     op_jal,      op_system, NULL,     NULL, NULL, // 11
  };        
  

  只定义前 5 码是因为 RV32I opcode 的後两码都是固定的 (xxxxx11)，我们也可以在 rv_step() 中看到待执行指令 inst 的预处理:

  // standard uncompressed instruction
      if ((inst & 3) == 3) {
          const uint32_t index = (inst & INST_6_2) >> 2;
  

  简单来说就是判断 inst 是否属於 RV32I 指令 (末两码是否为 11。)，如果是的话我们就将末两码移除并且做 right_shift。

  补充 1 : INST_6_2 定义在 riscv_private.h 中，其值为 0b00000000000000000000000001111100。

  补充 2 : 除了 RVC 指令集外，其他合法 RISC-V 指令集的 OPCODE 末两码都是 11。

  题外话: 在上面的原始码中就有大量的 bitwise 操作，再次凸显它的重要性。

• op()
op 其实只是函式指标，透过 rv_step() 指定指令的 handler 後，再去做相关操作。
  这边以 op_op_imm() 这个关於整数操作的 handler 举例:

      static bool op_op_imm(struct riscv_t *rv, uint32_t inst)
  {
      // i-type decode
      const int32_t imm = dec_itype_imm(inst);
      const uint32_t rd = dec_rd(inst);
      const uint32_t rs1 = dec_rs1(inst);
      const uint32_t funct3 = dec_funct3(inst);
  
      // dispatch operation type
      switch (funct3) {
      case 0:  // ADDI
          rv->X[rd] = (int32_t)(rv->X[rs1]) + imm;
          break;
      case 1:  // SLLI
          rv->X[rd] = rv->X[rs1] << (imm & 0x1f);
          break;
      case 2:  // SLTI
          rv->X[rd] = ((int32_t)(rv->X[rs1]) < imm) ? 1 : 0;
          break;
      case 3:  // SLTIU
          rv->X[rd] = (rv->X[rs1] < (uint32_t) imm) ? 1 : 0;
          break;
      case 4:  // XORI
          rv->X[rd] = rv->X[rs1] ^ imm;
          break;
      case 5:
          if (imm & ~0x1f) {
              // SRAI
              rv->X[rd] = ((int32_t) rv->X[rs1]) >> (imm & 0x1f);
          } else {
              // SRLI
              rv->X[rd] = rv->X[rs1] >> (imm & 0x1f);
          }
          break;
      case 6:  // ORI
          rv->X[rd] = rv->X[rs1] | imm;
          break;
      case 7:  // ANDI
          rv->X[rd] = rv->X[rs1] & imm;
          break;
      default:
          rv_except_illegal_inst(rv);
          return false;
      }
  
      // step over instruction
      rv->PC += 4;
  
      // enforce zero register
      if (rd == rv_reg_zero)
          rv->X[rv_reg_zero] = 0;
      return true;
  }
  

  
  handler 会将传入指令做解码，也就是将传入的 inst 根据上图的 I type 切割成四块:

  1. funct3
  2. imm
  3. rs1
  4. rd
     funct3 会决定要做哪一种操作，如: ADDI, SLLI, ORI...。
     假设现在要做的是 ADDI 操作，模拟器就会按照 RISC-V 中 ADDI 指令所定义的行为执行。

  定义:
  常数部分为 sign-extended 12-bit，会将 12-bit 做 sign-extension 成 32-bit 後，再与 rs1 暂存器做加法运算，将结果写入 rd 暂存器，addi rd, rs1, 0 可被用来当做 mov 指令。

  将结果写回相关暂存器後，handler 会将 Program counter 指到下一个记忆体位置後回传结果。

小结论

上面的工作流程涵盖了处理器的部分行为:

1. Fetch
2. Decode
3. Execute
4. Write-back

恰好呼应到了本文开头提到的 RISC-V Arch 架构图。

什麽是管线?

就 rv32emu 的原始码来看，我们不难知道它会逐步处理 Fetch, Decode, Execute, Write-back，假设每个阶段耗费 1ms，那一个指令需要 4ms 才能完成，若处理十个指令就需要 40ms。由於其中一个阶段在执行时，其他的逻辑电路都是闲置的，这样未免有些浪费。

指令管线化

管线 (pinpline)，又称为指令管线化。被设计来加速指令通过的速度。
如果以指令管线化的技术实现，第一个指令仍会耗费 4ms，之後每 1ms 便能完成一条指令。

上图为一个 5 级管线的示意图，我们可以清楚的看到在 Clock Cycle = 2 时，指令 1 已经进入解码阶段 (ID)，而读取指令的电路也没闲着，已经准备将指令 2 从记忆体读进处理器了。

管线越长越好吗?

使用管线可以有效加速指令的流通速。不过，在现实中还是会遇到一些问题以及缺陷:

• 周期同步问题
  前面假设各个层级的耗费时间都相同。实际上，各层级所耗时间并不是相等的。因此，时钟周期就需要以最慢的 stage 下去做考量，若管线设计过长，反而会因为过长的等待时间造成反效果。

• 电路体积加大
  将一块电路拆成多块电路实现管线，需要在每个阶层都放上大量的暂存器以保存前一层的输出。暂存器在逻辑电路中是用正反器去实现的，越长的管线就会有越多的正反器，这样便会造成电路体积加大以及废热的问题需要解决。

• 指令延迟问题
  利用大量的暂存器去保存前一个阶层的结果也会间接造成指令的延迟问题。

• 分支预测问题

  分支问题可被归类在 Control Hazards。

  以 rv32emu 来看，在一般情况下，当一个指令完成後，程序计数器 (PC, Program Counter) 会读取记忆体中的下一个地址 (PC = PC + 4)。
  实际情况中，还会有分支的可能需要考虑进去，像是常见的无条件转跳指令 jump 和条件转跳指令 branch 都会造成问题，像是，当指令 1 进入执行阶段时发现该指令会进行转跳，那指令 2 和指令 3 已经分别在解码和读取阶段了该怎麽办呢?这时处理器便会将前面的管线清空并将正确的指令放回来。要知道，清除管线是十分浪费效能的(做白工)。因此，随着管线加长，分支预测也是电脑科学家一直一来想去探讨的议题。

  关於 Hazards，在本系列的浅谈分支预测与 Hazards 议题会有更进一步的探讨。

总结

在本篇章中，读者快速的向各位介绍完了处理器的部分行为以及指令管线化的技术，如果对分支预测有兴趣可以参考本篇的延伸阅读。两篇都提到了分支预测的问题并且使用不同的方式解决加快了程序码的执行速度。

延伸阅读

• 浅谈 CPU 分支预测技术
• 2020q3 专题: RISC-V 模拟器
• 优化技巧：提前if判断帮助CPU分支预测