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中关键的模块、功能及具体结构如下：

模块名 功能 structure
x_ct_ifu_bht_pre_array BHT predict array SRAM 可以划分为两个entry为32bits的表，分别记录大概率跳转与不跳转的分支预测信息
x_ct_ifu_bht_sel_array BHT select array SRAM 一个entry为16bits的表，根据PC高位记录分支可能的跳转方向，做一个一级预测

关键IO及Signal Bundle

Input

信号名 功能 来源模块或信号
bht_pred_array_index predict array 更新index bht_pred_array_rd_index rd index
bht_wr_buf_pred_updt_index wr index, cur_ghr拼接成
bht_pred_array_din predict array 更新data bht_wr_buf_pred_updt_val
bht_sel_array_index select array rd index pcgen_bht_pcindex rd index，读来自pcgen
bht_wr_buf_sel_updt_index wr index
bht_sel_array_din select array 输入 bht_wr_buf_sel_updt_val
bht_sel_data select array data bht_sel_data_out // 直接从内存中输出
bht_sel_data_reg // 从寄存器中输出(防止写内存改变输出值)

Input from BJU

BJU从PCFIFO中获得预测信息后，会在EX2阶段将实际的分支信息反馈给FrontEnd，作为BHT更新时的依据

信号名 功能 来源模块或信号
bju_mispred 是否发生误预测 iu_ifu_chgflw_vld
bju_pred_rst BHT进行分支预测时提供的pred result {iu_ifu_bht_pred, iu_ifu_chk_idx[24]}
bju_sel_rst BHT进行分支预测时提供的sel result iu_ifu_chk_idx[23:22]
bju_ghr 来自BJU的GHR iu_ifu_chk_idx

Output

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

模块 信号名 功能 来源
IPDP bht_ipdp_pre_array_data_ntake; pred 预测结果
bht_ipdp_pre_array_data_taken;
bht_ipdp_pre_offset_onehot; pred 位选
bht_ipdp_sel_array_result; sel 预测结果
bht_ipdp_vghr vghr

外部模块关系

方向 模块名 信号 功能
Output
Indirect BTB bht_ind_btb_rtu_ghr
bht_ind_btb_vghr		 为Ind BTB提供rtu ghr和ghr
Loop Buff bht_lbuf_pre_taken\_result
bht_lbuf_vghr		 为loop buff提供predict 预测结果和ghr
Input
pcgen pcgen_bht_ifpc 待预测pc
pcgen_bht_pcindex [9:3]作为SA读时的index
BJU bju_mispred(iu_ifu_chgflw_vld) 是否误预测
bju_pred_rst predict result
bju_sel_rst select result
bju_ghr(iu_ifu_chk_idx[21:0]) 来自BJU的ghr
RTU rtu_ifu_flush 来自RTU的前端冲刷信号(RTU状态机)
rtu_ifu_retire0\<1 2\>_condbr_taken 来自RTU单元的br实际执行情况，用于更新rtughr
ipctrl

关键逻辑

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

  • Bypass 逻辑
  • 前端流水线逻辑
    • IP级逻辑
  • Select/Predict array index 计算逻辑
  • 多分支处理
  • Select/Predict array
  • 输出逻辑
  • BHT更新逻辑
    • Predict array 更新逻辑
    • Select array更新逻辑
  • GHR 更新逻辑
    • VGHR(全局历史寄存器)
    • RTU GHR
  • BHT write buffer逻辑
  • 失效逻辑

此外，在BHT部分逻辑还位于ipdp中(根据select array的结果选择predict array的结果)，实际上BHT中完成了对SA和PA的读取，进一步的筛选在ipdp中完成

前端流水线逻辑

前端流水线由bht_pipe_clk进行驱动

IP级逻辑

在IF到IP的逻辑中，需要将BHT的data发射到IP级，具体包括

  • PA result: bht_ipdp_pre_array_data_taken\
  • SA result: bht_ipdp_sel_array_result
  • predict array offset
  • vghr
  • pre array offset

Select & Predict array index 计算逻辑

根据不同操作，predict array的index有不同来源（w/r），而对于rd_index，又可以根据分支执行状态从不同来源中得到

点击显/隐内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
always @( ... )
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

// write buff index 更新
assign bht_wr_buf_pred_updt_index[9:0] = {cur_ghr[13:10],{cur_ghr[9:4]^cur_ghr[21:16]}};

位选逻辑：在IF和IP阶段会分别给出pred array offset值

1
2
3
4
5
6
7
8
9
10
assign pre_offset_onehot[15:0]    = (ipctrl_bht_more_br || ipdp_bht_h0_con_br)
                                    ? pre_offset_onehot_ip[15:0]
                                    : pre_offset_onehot_if[15:0];

assign pre_offset_onehot_ip[15:0] = (ipctrl_bht_con_br_vld)
                                    ? pre_offset_onehot_ip_1[15:0]
                                    : pre_offset_onehot_ip_0[15:0];
assign pre_offset_onehot_if[15:0] = (ipctrl_bht_con_br_vld)
                                    ? pre_offset_onehot_if_1[15:0]
                                    : pre_offset_onehot_if_0[15:0];

多分支处理

前端在进行指令fetch时一次会取出128bits的指令block，（RISCV支持32位的标准指令与16位压缩指令，因此128位的block块可能包含4到8条指令），pcgen模块提供给BHT的用于索引的PC实际是block PC，由于一个块中可能包含多条分支指令，因此在设计过程中需要对多条分支的情况进行处理。

如何判断是否存在多条分支

在IF到IP的阶段，我们会进行pre-decode（该部分逻辑位于）

BHT 更新逻辑（重要）

Write Buffer结构

在介绍BHT更新逻辑之前，我们先介绍一下BHT的write buffer，玄铁BHT的预测表使用的是single port的SRAM，这意味着会发生RW的conflict，读的优先级要高于写，因此需要设置一个write buffer，对写进行缓冲。从结构上讲，write buffer就是一个FIFO队列，通过指针进行实现。关于FIFO的维护不做过多介绍，这里直接给出代码：

点击显/隐内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//Entry 1
always @(posedge wr_buf_clk or negedge cpurst_b)
begin
  if(!cpurst_b)
    entry1_vld <= 1'b0;
  else if(bht_inv_on_reg)
    entry1_vld <= 1'b0;
  // 创建与销毁
  else if(entry_create[1])
    entry1_vld <= 1'b1;
  else if(entry_retire[1])
    entry1_vld <= 1'b0;
  else
    entry1_vld <= entry1_vld;
end

从哪里获取更新

BHT的更新信息来源为Write Buffer或者BJU data，对于write buffer的entry data，会根据retire_ptr[3:0]进行选择。BHT会利用这些信息，对pred/sel的index以及content进行update。（Overflow 如何处理）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 从iu_ifu_chk_idx中解析
// pcfifo_bju_chk_idx -> iu_ifu_bht_pred

// If buffer entry valid
cur_condbr_taken  = buf_condbr_taken;    // 分支实际执行情况

cur_sel_rst[1:0]  = buf_sel_rst[1:0];    // 进行预测时sel的result
cur_pred_rst[1:0] = buf_pred_rst[1:0];   // 进行预测时pred的result

cur_ghr[21:0]     = buf_ghr[21:0];       // 进行预测时的分支历史
cur_cur_pc[9:0]   = buf_cur_pc[9:0];     // 进行预测时的PC

// else，直接利用BJU的info，不做入队处理
cur_condbr_taken  = iu_ifu_bht_condbr_taken;
cur_sel_rst[1:0]  = bju_sel_rst[1:0];
cur_pred_rst[1:0] = bju_pred_rst[1:0];
cur_ghr[21:0]     = bju_ghr[21:0];
cur_cur_pc[9:0]   = iu_ifu_cur_pc[12:3];

何时可以更新（wr）

在发生BHT无效化或允许update的时候，可以进行更新：

1
2
3
// wr enable
assign bht_pred_array_wr     = bht_inv_on_reg ||    
                               bht_wr_buf_updt_vld;    //

而update vld更新逻辑为，或者BJU检查发现可以更新，或者在wr_buf不为空且满足一系列条件时，可以更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
assign bht_wr_buf_updt_vld       = (bju_check_updt_vld ||         // BJU允许更新
                           bht_wr_buf_not_empty) && 
                           !(
                           after_inv_reg || 
                           ipctrl_bht_con_br_vld ||   // 为何没有bju_mispred
                           after_bju_mispred || 
                           rtu_ifu_flush || 
                           after_rtu_ifu_flush || 
                           pcgen_bht_chgflw && !lbuf_bht_active_state ||
                           pcgen_bht_seq_read  // When read, do not write
                           );

// BJU 检查，pred和sel vld,且分支vld
assign bju_check_updt_vld        = (pred_array_check_updt_vld || 
                                   sel_array_check_updt_vld) && 
                                   iu_ifu_bht_check_vld;

往哪里更新

(更新表选择)

1
2
3
assign bht_wr_buf_pred_updt_index[9:0] = {cur_ghr[13:10],{cur_ghr[9:4]^cur_ghr[21:16]}};

assign bht_wr_buf_sel_updt_index[6:0] = cur_cur_pc[9:3];

如何更新（两位饱和计数器）

Predict与select array更新时，需要根据现有的info，对表中的两位饱和计数器进行update，比较简单。而index和位选信号则是根据进行预测时的分支历史及PC进行计算。

点击显/隐内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 更新时表索引的计算
assign bht_wr_buf_sel_updt_index[6:0] = cur_cur_pc[9:3];
assign bht_wr_buf_pred_updt_index[9:0] = {cur_ghr[13:10],{cur_ghr[9:4]^cur_ghr[21:16]}};

// 表内容update
always @( cur_pred_rst[1:0]
       or cur_condbr_taken)
begin
case({cur_pred_rst[1:0],cur_condbr_taken})
  3'b001  : pred_array_updt_data[1:0] = 2'b01;
  3'b011  : pred_array_updt_data[1:0] = 2'b10;
  ...
  default : pred_array_updt_data[1:0] = 2'b00;
endcase
end

在更新数据pred_array_updt_data准备好后，扩展为bht_wr_buf_pred_updt_val，作为SRAM的输入

1
2
3
assign bht_pred_array_din[63:0] = bht_inv_on_reg 
                                ? 64'h3333_3333_3333_3333 
                                : bht_wr_buf_pred_updt_val[63:0];

Select array & predict array输出逻辑

rd enable

读使能信号是sel/pred中的一个关键信号，控制BHT在正确的时机输出预测结果。pred和sel的读使能信号分别如下：

pred array读使能信号

1
2
3
4
5
6
7
assign bht_pred_array_rd     = after_inv_reg ||
                               ipctrl_bht_con_br_vld && !lbuf_bht_active_state ||   // condition branch happen in IP stage
                               lbuf_bht_con_br_vld && lbuf_bht_active_state || 
                               bju_mispred || 
                               after_bju_mispred || 
                               rtu_ifu_flush || 
                               after_rtu_ifu_flush;

IP阶段会进行predecode，判断一条指令是否为一个分支指令，因此pred需要在IP阶段输出一个预测结果，同时在该阶段根据sel的结果，对taken/ntaken两张表中的内容进行选择。但是这里有一个不太明白的点，为何在mispred和flush的时候也要对pred array进行读操作，从原理上来讲，当发生mispred和flush时，需要更新pred array，更新操作需要进行read。但是由于在更新时我们并不依赖预测表中的内容，而是直接根据BJU反馈的发生错误的预测结果对表进行更新，因此从实际来讲，不需要对pred array进行读。

sel array读使能信号如下：

1
2
3
assign bht_sel_array_rd    = after_inv_reg || 
                             pcgen_bht_chgflw ||
                             pcgen_bht_seq_read;

从sel array的读使能信号我们可以看到，在发生chgflw以及顺序执行的情况下，我们都要对sel array进行读操作，这个也合理，因为读sel时在IF阶段，此时尚无法知道指令是否为分支指令，所以我们必须每条指令都读sel array，并在IP阶段根据是否为分支指令，对pred array进行处理。

位选

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

1
2
3
4
5
6
7
8
9
10
11
12
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

// 输出
assign sel_array_val_cur[1:0] = ({2{if_pc_onehot[ 0]}} & bht_sel_data[ 1: 0]) | 
                                ({2{if_pc_onehot[ 1]}} & bht_sel_data[ 3: 2]) |

Predict array 类似，一个entry包含16个分支预测器，同样使用独热码进行选择

GHR更新逻辑

VGHR（Foldered History）

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
20
21
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
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};
  ... // rtu状态机
  default : rtughr_pre[21:0] =  rtughr_reg[21:0];
endcase
// &CombEnd; @295
end

write buffer

BHT使用了一套write buffer的机制，对来自BJU的更新信息进行缓存。write buffer包含两个移位寄存器：create_ptr和retire_ptr，每次更新实际是从valid的buffer中选择一个，此处的逻辑涉及entry的create和retire

饱和更新

pre/sel array在饱和的情况下不再更新，其中sel array更复杂一些

1
2
3
4
5
6
7
8
9
10
11
assign sel_array_check_updt_vld  = !( ( 饱和不更新
                                      // sel 表示不更新，但是实际结果是更新，且ifu chgflw not valid???
                                      ( (bju_sel_rst[1] == 1'b0) && //bi-mode logic  
                                        iu_ifu_bht_condbr_taken && 
                                        !iu_ifu_chgflw_vld
                                      ) || 
                                      ( (bju_sel_rst[1] == 1'b1) && //bi-mode logic
                                        !iu_ifu_bht_condbr_taken && 
                                        !iu_ifu_chgflw_vld
                                      )
                                    );

失效逻辑

BHT中使用一个counter，定期对BHT进行失效

逻辑筛选

  • predict/select array w/r及模块enable，时钟enable，write bit enable，两者基本上是对称的
  • predict/select array index
  • GHR更新（GHR时钟及其使能）
  • select array最终输出逻辑
  • 根据RTU的信号知道怎么了解是哪条指令mispred

问题

BHT在IF阶段就开始进行预测，但是在IP阶段才能知道指令是否为分支指令

1
2
assign bht_pred_array_rd     = after_inv_reg ||
                               ipctrl_bht_con_br_vld && !lbuf_bht_active_state ||  // ip阶段 decode后发现是分支指令，需要更新BHT，所以需要读pred array

BHT使用了Single Port SRAM，如何解决RW conflict

Most Important: RW confilct

SRAM Single port：每个cycle 固定做RW，内部有仲裁，怎么做这个仲裁（worst case怎么搞，一定是考虑Worst case，RW请求连续到达该如何仲裁，Write buffer能进行写缓存，缓存该有多大，满了之后该怎么处理，停止后端？）。Multi bank，

参考文献

0%