Branch History Table

Posted on | In , ,

“I don’t make mistakes. I make prophecies which immediately turn out to be wrong.”

简介

Branch history table(BHT)是前端预测器的一种，可以根据当前跳转指令和全局或局部分支历史，预测出跳转指令的结果（跳转或不跳转），再配合branch target buffer中保存的跳转目标地址，实现无空泡的执行流。本文将针对XuanTie C910的BHT进行总结。

玄铁BHT结构及关键模块

玄铁的BHT模块框图如下

BPU

BHT中关键的模块、功能及具体结构如下：

模块名 功能 structure
x_ct_ifu_bht_pre_array BHT predict array SRAM 可以划分为两个entry为32bits的表，分别记录大概率跳转与不跳转的分支预测信息

关键IO Bundle

Input

信号名 功能 来源
pcgen_bht_ifpc 待预测pc
bht_pred_array_din predict array 更新 bht_wr_buf_pred_updt_val
bht_sel_array_din select array 输入 bht_wr_buf_sel_updt_val
bht_pred_array_index predict array index bht_pred_array_rd_index // read
bht_wr_buf_pred_updt_index // update

Output

玄铁BHT中重要的Output信号包括：

模块 信号名 功能 来源
bht_sel_data select array 被选中的entry
sel_array_val_cur select array entry最终筛选的饱和计数器
predict array
bht_pre_data_out predict array SRAM输出，拆分为了bht_pre_taken_data/bht_pre_ntaken_data两部分
pre_array_pipe_taken\_data predict array结果保留至IP阶段

关键逻辑

BHT中的一些关键逻辑包括：

  • Bypass 逻辑
  • Predict array index 计算逻辑
  • Select array 输出逻辑

  • BHT更新逻辑

    • Predict array 更新逻辑
    • Select array更新逻辑

  • GHR 更新逻辑

    • VGHR(全局历史寄存器)
    • RTU GHR

Predict array index 计算逻辑

点击显/隐内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
always @( vghr_reg[20:14]
       or after_bju_mispred
       or rtughr_reg[21:16]
       or iu_ifu_bht_check_vld
       or after_rtu_ifu_flush
       or vghr_reg[12:2]
       or rtu_ifu_flush
       or bju_ghr[13:3]
       or rtughr_reg[13:4]
       or bju_mispred
       or bju_ghr[21:15])
begin
    if(rtu_ifu_flush)    // RTU冲刷IFU
        bht_pred_array_rd_index[9:0] = {rtughr_reg[13:10],{rtughr_reg[9:4]^rtughr_reg[21:16]}};  
    else if(bju_mispred && !iu_ifu_bht_check_vld)   // 误预测，不检查bht是否vld
        bht_pred_array_rd_index[9:0] = {bju_ghr[13:10],{bju_ghr[9:4]^bju_ghr[21:16]}};
    else if(bju_mispred && iu_ifu_bht_check_vld)    // 误预测，检查bht是否vld
        bht_pred_array_rd_index[9:0] = {bju_ghr[12:9],{bju_ghr[8:3]^bju_ghr[20:15]}};
    else if(after_bju_mispred || after_rtu_ifu_flush)    // ????
        bht_pred_array_rd_index[9:0] = {vghr_reg[12:9],{vghr_reg[8:3]^vghr_reg[20:15]}};//
    else //ipctrl_bht_con_br_vld
        bht_pred_array_rd_index[9:0] = {vghr_reg[11:8],{vghr_reg[7:2]^vghr_reg[19:14]}};
// &CombEnd; @162
end

Predict array更新逻辑

点击显/隐内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
always @( vghr_reg[20:14]
       or after_bju_mispred
       or rtughr_reg[21:16]
       or iu_ifu_bht_check_vld
       or after_rtu_ifu_flush
       or vghr_reg[12:2]
       or rtu_ifu_flush
       or bju_ghr[13:3]
       or rtughr_reg[13:4]
       or bju_mispred
       or bju_ghr[21:15])
begin
if(rtu_ifu_flush)
  bht_pred_array_rd_index[9:0] = {rtughr_reg[13:10],{rtughr_reg[9:4]^rtughr_reg[21:16]}};
else if(bju_mispred && !iu_ifu_bht_check_vld)
  bht_pred_array_rd_index[9:0] = {bju_ghr[13:10],{bju_ghr[9:4]^bju_ghr[21:16]}};
else if(bju_mispred && iu_ifu_bht_check_vld)
  bht_pred_array_rd_index[9:0] = {bju_ghr[12:9],{bju_ghr[8:3]^bju_ghr[20:15]}};
else if(after_bju_mispred || after_rtu_ifu_flush)
  bht_pred_array_rd_index[9:0] = {vghr_reg[12:9],{vghr_reg[8:3]^vghr_reg[20:15]}};
else //ipctrl_bht_con_br_vld
  bht_pred_array_rd_index[9:0] = {vghr_reg[11:8],{vghr_reg[7:2]^vghr_reg[19:14]}};
// &CombEnd; @162
end

Select array 输出逻辑

Select array 一个entry包含了8个分支预测器，由pc[5:3]生成一个独热码if_pc_onehot进行选择

1
2
3
4
5
6
7
8
always @( pcgen_bht_ifpc[5:3])
begin
case(pcgen_bht_ifpc[5:3])
  3'b000  : if_pc_onehot[7:0] = 8'b0000_0001; 
  3'b001  : if_pc_onehot[7:0] = 8'b0000_0010; 
  ...
  default : if_pc_onehot[7:0] = 8'b0000_0001;
endcase

GHR更新逻辑

VGHR

VGHR是BHT中的全局历史寄存器，用于记录ifu中条件分支执行情况，根据分支执行状态，VGHR有不同的更新来源：

  • RTU冲刷时，VGHR来自RTU
  • 分支跳转单元(BJU)检测到条件分支预测错误时，VGHR来自BJU
  • 短循环被加载到loop buffer中时，来自短循环加速器
  • 以上情况均未发生，VGHR从BHT中获取更新信息
点击显/隐内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
always @(posedge bht_ghr_updt_clk or negedge cpurst_b)
begin
  if(!cpurst_b)
    vghr_reg[21:0] <= 22'b0;
  else if(bht_inv_on_reg)
    vghr_reg[21:0] <= 22'b0;
    else if(rtu_ifu_flush && cp0_ifu_bht_en)          // RTU冲刷，说明在RTU阶段发现预测错误
    vghr_reg[21:0] <= rtughr_reg[21:0];
  else if(ghr_updt_vld && iu_ifu_bht_check_vld)
    vghr_reg[21:0] <= {bju_ghr[20:0], iu_ifu_bht_condbr_taken};
  else if(ghr_updt_vld && !iu_ifu_bht_check_vld)
    vghr_reg[21:0] <= bju_ghr[21:0];
  else if(vghr_lbuf_updt_vld)
    vghr_reg[21:0] <= {vghr_reg[20:0], lbuf_bht_con_br_taken};
  else if(vghr_ip_updt_vld  && !lbuf_bht_active_state)
    vghr_reg[21:0] <= {vghr_reg[20:0], ipctrl_bht_con_br_taken};
  else
    vghr_reg[21:0] <= vghr_reg[21:0];
end

RTU GHR

在乱序执行处理器中，需要一个指令退休单元，当指令离开退休单元时，意味着该指令最终成功执行，并且其结果在架构状态中是正确且可见的。但是如果在RTU阶段发现一条跳转指令方向错误了，那么需要由RTU更新一下GHR（否则如果一条分支指令从RTU正常退休，说明跳转方向正确，即BHT和RTU的结果是一致的，直接使用BHT即可）。玄铁中包含三个RTU：

点击显/隐内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
always @( rtu_ifu_retire2_condbr_taken
       or rtu_ifu_retire1_condbr
       or rtu_ifu_retire0_condbr_taken
       or rtughr_reg[21:0]
       or rtu_ifu_retire1_condbr_taken
       or rtu_ifu_retire2_condbr
       or rtu_ifu_retire0_condbr)
begin
case({rtu_ifu_retire0_condbr, rtu_ifu_retire1_condbr, rtu_ifu_retire2_condbr})
  3'b000  : rtughr_pre[21:0] =  rtughr_reg[21:0];
  3'b001  : rtughr_pre[21:0] = {rtughr_reg[20:0], rtu_ifu_retire2_condbr_taken};
  3'b010  : rtughr_pre[21:0] = {rtughr_reg[20:0], rtu_ifu_retire1_condbr_taken};
  3'b100  : rtughr_pre[21:0] = {rtughr_reg[20:0], rtu_ifu_retire0_condbr_taken};
  3'b101  : rtughr_pre[21:0] = {rtughr_reg[19:0], rtu_ifu_retire0_condbr_taken, 
                                                  rtu_ifu_retire2_condbr_taken};
  3'b110  : rtughr_pre[21:0] = {rtughr_reg[19:0], rtu_ifu_retire0_condbr_taken, 
                                                  rtu_ifu_retire1_condbr_taken};
  3'b011  : rtughr_pre[21:0] = {rtughr_reg[19:0], rtu_ifu_retire1_condbr_taken, 
                                                  rtu_ifu_retire2_condbr_taken};
  3'b111  : rtughr_pre[21:0] = {rtughr_reg[18:0], rtu_ifu_retire0_condbr_taken, 
                                                  rtu_ifu_retire1_condbr_taken,
                                                  rtu_ifu_retire2_condbr_taken};
  default : rtughr_pre[21:0] =  rtughr_reg[21:0];
endcase
// &CombEnd; @295
end

参考文献

0%