开源处理器Rocket的分支预测机制研究与性能评估（二）

geren2014

3 Rocket处理器分支预测机制分析

3.1 分支预测机制设计分析
Rocket处理器除了实现BTB、BHT，还实现了RAS，都在BTB Module中实现，BTB Module的接口以及与Rocket Core的连接如图3所示。

Rocket处理器主要在流水线的取指、访存两个阶段使用到BTB Module。

3.1.1 取指阶段

将取指阶段的指令地址通过Req送到BTB Module，后者进行如下判断：

（1）查询BTB，是否有对应的指令地址，如果有，那么进行下一步骤；

（2）如果是返回指令，那么将RAS堆栈顶部的数据返回，作为目标地址；反之，进行下一步骤；

（3）如果是jal、jalr这两条绝对转移指令，那么设置taken为true，表示转移发生，目标地址是BTB查询的结果；反之，进行下一步骤；

（4）按照图1进行查询，依据BHT的查询结果，判断是否发生转移，如果转移，那么设置taken为true，转移目标地址为BTB查询的结果，反之，设置taken为false。无论是否转移，均更新BHT中的BHSR。

（5）将上述判断结果通过resp返回给Rocket Core，后者据此决定下一条指令的地址。

上述处理过程如图4所示。


3.1.2 访存阶段

当分支指令进入访存阶段后，Rocket Core可以判断出前期的分支预测是否正确，从而更新BTB Module中相应的内容，更新消息是通过btb_update、bht_update、ras_update送入BTB Module的，分别代表更新BTB、BHT、RAS。假设分支指令是B，跳转指令是J、返回指令是R，那么可以分为如下几种情况。
（1）B在取指阶段没有在BTB查询命中，并且实际分支结果是not taken

此时不更新BTB，仅仅更新BHT，即图1中的BHSR，以及对应的模式历史表中的表项，按照图2的2 bit饱和计数器的状态机进行更新。

（2）B在取指阶段没有在BTB查询命中，并且实际分支结果是taken
此时更新BTB、BHT，其中BHT的更新内容同（1），对于BTB而言，需要在其中新增一个表项，其中存储指令B的地址与分支目标地址。

（3）B在取指阶段在BTB查询命中，实际分支结果与预测结果不一致
此时更新BTB、BHT，其中BHT的更新内容同（1），对于BTB而言，需要更新其中存储的指令B对应的目标地址。

（4）B在取指阶段在BTB查询命中，实际分支结果与预测结果一致
此时不更新BTB，仅仅更新BHT，更新内容同（1）。

（5）J在取指阶段没有在BTB查询命中
此时将更新BTB，在其中新增一个表项，将指令J的地址及跳转的目标地址写入该表项，同时将当前指令地址加4，结果存入RAS堆栈顶部。

（6）J在取指阶段在BTB查询命中，并且目标地址预测正确
此时将当前指令地址加4，结果存入RAS堆栈顶部。

（7）J在取指阶段在BTB查询命中，但是目标地址预测错误
此时将更新BTB，将其中存储的指令J对应的目标地址更新为新的地址，同时，将当前指令地址加4，结果存入RAS堆栈顶部。

（8）R在取指阶段没有在BTB查询命中
此时将更新BTB，在其中新增一个表项，将指令R的地址及跳转的目标地址写入该表项。

（9）R在取指阶段在BTB查询命中，并且目标地址预测正确
此时将RAS堆栈顶部的数据出栈。

（10）R在取指阶段在BTB查询命中，但是目标地址预测错误
此时将更新BTB，将其中存储的指令R对应的目标地址更新为新的地址。

3.2 BTB Module分析
在BTB Module中实现了BTB、BHT、RAS，其中RAS就是一个简单的堆栈，本文不再单独分析，重点分析BTB、BHT。

3.2.1 BHT分析
通过BHT类实现了BHT，其实现的就是图1所示的GShare分支预测算法，其中重点的方法是get，通过get方法返回预测结果，通过以下片段可以理解GShare的基本过程。

1. def get(addr: UInt, update: Bool): BHTResp = {
   
2.     val res = Wire(new BHTResp)
   
3.     val index = addr(nbhtbits+1, log2Up(coreInstBytes)) ^ history  // 指令地址的低位与BHSR进行异或
   
4.     res.value := table(index)                                // 异或的结果作为查询模式历史表的索引
   
5.     res.history := history
   
6.     val taken = res.value(0)                                 // 依据查询结果，判断分支是否taken
   
7.     when (update) { history := Cat(taken, history(nbhtbits-1,1)) }
   
8.     res
   
9.   }
   

复制代码

3.2.2 BTB分析
Rocket通过一系列数组实现了BTB，为了便于分析，假设BTB的表项是64，此时会有如图5所示的一系列数组。以idx开始的数组表示是与分支指令有关，以tgt开始的数组表示是与分支目标地址有关，其含义如下。

• idxs：64项，存储的是分支指令地址的第2-11bit，实际应该是低12bit，但是指令是4字节的，所以最低2bit可以忽略。
• idxPages：64项，与idxs一一对应，每一项是3bit，是一个索引，指向pages数组，后者存储的是分支指令地址的高27bit。
• idxPagesOH：64项，与idxPages一一对应，每一项是6bit，实际就是idxPages中对应数据的one-hot编码，是为了加快查询pages数组的速度而设计的。
• idxValid：64项，与idxs一一对应，每一项是1bit，表示对应的idxs是否有效。
• tgts：64项，存储的是分支目标地址的第2-11bit，实际应该是低12bit，但是指令是4字节的，所以最低2bit可以忽略。
• tgtPages：64项，与tgts一一对应，每一项是3bit，是一个索引，指向pages数组，其中存储的是分支目标地址的高27bit。
• tgtPagesOH：64项，与tgtPages一一对应，每一项是6bit，实际就是tgtPages中对应数据的one-hot编码，是为了加快查询pages数组的速度而设计的。
• pages：6项，存储的是分支指令地址或者分支目标地址的高27bit，RISC-V中定义虚拟地址是39bit，在idxs中已经有了低位的10bit，此外最低2bit忽略，所以就是27bit。
• pagesValid：6项，与pages一一对应，表示对应的pages是否有效。
  

图5 实现BTB的一系列数组

从图5可以发现，Rocket将地址分为两部分：低位、高位，其中高位存储在pages中，并且pages的表项显著小于idxs、tgts，从而减少BTB占用的芯片资源。每次进行BTB查询的时候，首先将分支指令地址的低位与idxs中的表项一一比较，如果有相等项，再通过对应的idxPages表项检索pages数组，进行地址高位的比较，如果也相等，那么表示BTB查询命中，反之，BTB查询没有命中。当BTB查询命中的时候，就可以通过tgts数组得到分支目标地址。


作者：leishangwen
来源：CSDN

相关阅读：
开源处理器Rocket的分支预测机制研究与性能评估（一）
开源处理器Rocket的分支预测机制研究与性能评估（二）
开源处理器Rocket的分支预测机制研究与性能评估（三）