前言

关于Rocket Chip中的BTB模块，已经有前辈整理得很清楚了，可以参照开源处理器Rocket的分支预测机制研究与性能评估这一系列文章，本文仅仅稍微补充一点点代码上的实现细节，并配上一些图片供大家食用。

Rocket中分支预测模块概要

Rocket Core 中，BTB主要分为三个部分

1. BTB：Branch Target Buffer
2. BHT：Branch History Table
3. RAS：Return Address Stack

其中，
BTB与BHT都是针对branch指令进行分支预测(很多设计中将两者整合，作为一个模块)

• BTB主要记录分支指令跳转目标地址(即：往哪里跳? branch target)
• BHT则决定是否采用BTB的目标地址跳转(即：跳不跳?taken or not taken)

RAS相对独立，是针对与函数调用有关的JAL和JALR指令进行预测执行。

Rocket Core中将这三者整合成一个模块，模块名称就叫BTB，为了不引起歧义，下面所说的BTB都是指其中的子模块，而不是Rocket Core中整合成的大模块。

1. BTB

在课上讲解得BTB基本原理大概都如下图所示那样，与Cache设计思路类似，BTB取PC其中k位作为buffer的entry，读出Entry PC与当前PC比对，若相等则可取出目标地址来预测。

BTB基本原理

基本原理比较清晰易懂，但是存在一个较大的问题，Buffer太大，会浪费相当多的存储资源，体现在两个方面：

1. Buffer 每一项位宽太宽：Enrty PC和target PC位宽都是32。
2. Buffer中的PC高位存在冗余：对于branch指令，跳转范围有限，地址高位(页号部分)通常不会改变

为了解决这个问题，Rocket Chip中重新设计了下面这种方案：

BTB Register Model

与基本原理图最明显的区别在于：

1. idx不作为buffer的入口地址，而是与全相联的idxs逐一比对形成独热码idxHit
2. BTB 与页号(图中pages即页号)分离存储，BTB中通过指针指向对应页号(图中红色弧线：idxPages、tgtPages为指向pages的指针)

1.1 PC划分

在Rocket Core中，PC切分方式如下：

Rocket Core中PC划分方式

根据Rocket Generator配置不同，PC位宽为32或39，主要分为了三部分

1. coreInstBytes:指令字节，由于使用压缩指令(2字节), 对齐位1bit
2. idx(tgt)，idx不作为入口地址!!!(代码中tgt、target也对应此字段)
3. page，即页号

1.2 命中检测(hit or miss)

虽然页号(pages)与buffer独立管理维护，但是两者都采用全相联的命中检测方法：逐一比对，生成独热码。
BTB中定义了idxMatch 与 pageMatch两个方法，可以检查一个pc地址page字段与idx字段是否命中。

idxMatch 与 pageMatch

  private def page(addr: UInt) = addr >> matchBits
  private def pageMatch(addr: UInt) = {
    val p = page(addr)
    pageValid & pages.map(_ === p).asUInt
  }
  private def idxMatch(addr: UInt) = {
    val idx = addr(matchBits-1, log2Up(coreInstBytes))
    idxs.map(_ === idx).asUInt & isValid
  }

  val pageHit = pageMatch(io.req.bits.addr)
  val idxHit = idxMatch(io.req.bits.addr)

若命中，则直接读出BTB对应项target，返回给Frontend

  io.resp.valid := (pageHit << 1)(Mux1H(idxHit, idxPages))
  io.resp.bits.target := Cat(pages(Mux1H(idxHit, tgtPages)), Mux1H(idxHit, tgts) << log2Up(coreInstBytes))
  io.resp.bits.entry := OHToUInt(idxHit) // 若idxHit不命中，entry为0

1.3 替换策略

页号(pages)和BTB buffer也有不同的替换策略。

1.3.1 替换时机

首先介绍一下替换时机，BTB的更新与流水线两个阶段相关：

1. IF Stage：Predication
2. WB Stage ：BTB Updating

取指令阶段只读不写，若BTB不命中，不会改变BTB。
写回阶段才会更新BTB和独立管理的页号(pages)。

读源码小技巧：IF Stage 与WB Stage信号名区别，主要看有没有update
IF Stage相关信号名：

• pc相关：io.req.bits.addr(update_target)
• pages相关：pageHit、usePageHit
• idx相关： idxHit

WB Stage相关信号名：

• pc相关：r_btb_update.bits.pc
• pages相关：updatePageHit、useUpdatePageHit
• idx相关：updateHitAddr
• entry相关：waddr

1.3.2 BTB buffer替换策略：PseudoLRU

Rocket Chip中采用一个伪LRU的算法，不展开。

  val repl = new PseudoLRU(entries)
  val waddr = Mux(updateHit, updateHitAddr, repl.replace)
  val r_resp = Pipe(io.resp)
  when (r_resp.valid && r_resp.bits.taken || r_btb_update.valid) {
    repl.access(Mux(r_btb_update.valid, waddr, r_resp.bits.entry))
  }

1.3.2 pages替换策略：nextPageRepl + Rotation Method

pages替换策略分为两部分：

1. 当idxMatch 不命中时，使用一个nextPageRepl指针
2. 当idxMatch 命中时，采用Rotation Method

nextPageRepl是一个寄存器，指向下一次替换的位置，由于idx和target都有指向pages的指针，可能都需要更新：

1. 若两者只更新一个，指针加1
2. 若两者都更新，指针加2

相关代码：

  // pages指针nextPageRepl更新策略
  when (r_btb_update.valid && (doIdxPageRepl || doTgtPageRepl)) {
    val both = doIdxPageRepl && doTgtPageRepl
    val next = nextPageRepl + Mux[UInt](both, 2, 1)
    nextPageRepl := Mux(next >= nPages, next(0), next)
  }

另外还有一个这部分我也没完全理解透orz，大体上类似下图这个

Replacement Policy: Rotation Method
比较迷惑的是中间的一个Rotator循环移位，参考论文：An Optimal CAM-based Separated BTB for a Superscalar Processor
对应代码

  // 这里采用了Rotation Method
  val idxPageRepl = Cat(pageHit(nPages-2,0), pageHit(nPages-1)) | Mux(usePageHit, UInt(0), UIntToOH(nextPageRepl))
  val idxPageUpdateOH = Mux(useUpdatePageHit, updatePageHit, idxPageRepl)
  val idxPageUpdate = OHToUInt(idxPageUpdateOH)
  val idxPageReplEn = Mux(doIdxPageRepl, idxPageRepl, UInt(0))

  val samePage = page(r_btb_update.bits.pc) === page(update_target)
  val doTgtPageRepl = !samePage && !usePageHit
  val tgtPageRepl = Mux(samePage, idxPageUpdateOH, Cat(idxPageUpdateOH(nPages-2,0), idxPageUpdateOH(nPages-1)))
  val tgtPageUpdate = OHToUInt(pageHit | Mux(usePageHit, UInt(0), tgtPageRepl))
  val tgtPageReplEn = Mux(doTgtPageRepl, tgtPageRepl, UInt(0))

2. BHT

BHT模块比较简单，Rocket Chip中封装成一个class，定义了接口。BHT大致结构如下：

BHT示意图

• history是历史预测结果的pattern，采用比特串表示，如history为b'1110,则历史预测结果为taken、taken、taken、not taken
• counter table是一组counter ,用计数器表示本次分支是否预测跳转

2.1 BHT大致原理

BHT基于历史预测结果(history)和当前pc值，读取counter table预测当前分支是否采用BTB的预测结果。

1. 为了使history和addr都对预测结果有影响，Rocket Chip中index方法采用hash函数，是两者起作用。
2. index函数得到入口地址后，再用get函数打包成BHTResp处理

2.2 counter table 更新策略

Rocket Chip中BHT内置了两种counter (1-bit 和 2-bit)，可通过参数params.counterLength配置，参考代码：

  // 根据分支预测的结果更新表
  def updateTable(addr: UInt, d: BHTResp, taken: Bool): Unit = {
    // 通过match case模式匹配来选择使用预测器
    table(index(addr, d.history)) := (params.counterLength match {
      // 1-bit:Last-Time Prediction
      case 1 => taken
      // 2-bit counter (这里不是饱和计算)
      case 2 => Cat(taken ^ d.value(0), d.value === 1 || d.value(1) && taken)
    })
  }

2.3 history 更新策略

由于分支指令需要到EX Stage才能真正resolve，history 更新策略采用speculative的方式

1. 当分支指令流入指令Buffer时，就提前更新history(advanceHistory),同时将旧的history随流水线传递下去
2. 若预测结果正确，则采用更新后的history(即不变化)
3. 若预测失败，则用随流水线传递的旧history恢复原样

RAS

前面已经写了相关文章，参考Rocket Core : RAS(Return Address Stack)