从零开始学RISC：第十八篇

分支预测：预见1

一个程序中的指令之间存在相关性，如时间相关性和空间相关性。对于循环语句，一次次的跳转其实是类似的，只有到达极限才会停下来。直接让CPU预测程序下一步干什么，然后运行，而不是傻乎乎的等待，这样子可以显著提高运行效率——大多数情况下是的。

既然如此，我们的分支预测器一定要早于分支结果计算出来就生效。因此，需要将其放在ID级。

静态预测器

静态预测器很傻，但也很老实：它是“一根筋”，只会预测分支要么跳转、要么不跳转，自己不会做出改变。

我们需要留出哪些接口？需要判断当前指令是否为分支指令，以及输出。

module Static_Predictor #(
    parameter int unsigned META_BITS = 8
) (
    input  logic                 clk,
    input  logic                 rst_n,
    input  logic                 valid_i,
    input  logic                 is_branch_instr_i,
    input  logic [          1:0] jump_type_i,
    input  logic [         31:0] branch_target_i,
    output logic                 predict_taken_o,
    output logic [         31:0] predict_target_o,
    output logic [META_BITS-1:0] predict_meta_o
);

    // 静态预测策略：
    // - JAL: 恒预测跳转
    // - JALR: 目标依赖寄存器，不在ID级预测
    // - 条件分支: Backward Taken, Forward Not Taken
    always_comb begin
        predict_taken_o  = 1'b0;
        predict_target_o = branch_target_i;

        if (valid_i) begin
            unique case (jump_type_i)
                `JUMP_JAL:  predict_taken_o = 1'b1;
                `JUMP_JALR: predict_taken_o = 1'b0;
                default: begin
                    if (is_branch_instr_i) begin
                        predict_taken_o = imm_i[31];
                    end
                end
            endcase
        end
    end

endmodule

1-bit分支预测

什么是1-bit分支预测？它会为每条指令保存 1-bit 的信息，来表示这条分支上一次的结果：

• 1：上次跳转了
• 0：上次没跳转

下次再遇到这条分支时，就直接预测它会重复上一次的行为。很显然，它是一种 一级动态分支预测器，只看“这条分支上次怎样”。

它有什么优点？简单，很简单的预测，而且不是傻乎乎的在一棵树上吊死，会改变一次。但它也有一个很显然的缺点：每次循环结束附近会产生两次错误，这是因为一次偶然变化会导致它接下来再错一次：

T T T T N T T T // 实际分支
  // 在前面一直是 T 预测正确
        // 一旦出现 N 就会将分支预测修改为 N
          // 在下一个分支预测又错误一次    

代码也很简单。这里，我们选用PC的前8位字地址作为索引。这个INDEX_BITS越大，索引效果越好。当然，不建议一味拉高，拉太大了会引入额外的电路，损耗面积。

module Dynamic_1bit_Predictor #(
    parameter int unsigned INDEX_BITS = 8,
    parameter int unsigned META_BITS  = 8
) (
    input  logic                 clk,
    input  logic                 rst_n,
    input  logic                 valid_i,
    input  logic [         31:0] pc_i,
    input  logic                 is_branch_instr_i,
    input  logic [          1:0] jump_type_i,
    input  logic [         31:0] branch_target_i,
    input  logic                 update_valid_i,
    input  logic [         31:0] update_pc_i,
    input  logic                 update_is_branch_i,
    input  logic                 update_taken_i,
    output logic                 predict_taken_o,
    output logic [         31:0] predict_target_o,
    output logic [META_BITS-1:0] predict_meta_o
);

    localparam int unsigned BHT_ENTRIES = 1 << INDEX_BITS;

    logic   [BHT_ENTRIES-1:0] bht_table;
    logic   [ INDEX_BITS-1:0] predict_idx;
    logic   [ INDEX_BITS-1:0] update_idx;
    integer                   i;

    assign predict_idx = pc_i[INDEX_BITS+1:2];
    assign update_idx  = update_pc_i[INDEX_BITS+1:2];

    // 预测策略：
    // - JAL: 恒预测跳转
    // - JALR: 不预测
    // - 条件分支: 查询 1-bit BHT，记录该PC上一次实际结果
    always_comb begin
        predict_taken_o  = 1'b0;
        predict_target_o = branch_target_i;
        predict_meta_o   = '0;

        if (valid_i) begin
            unique case (jump_type_i)
                `JUMP_JAL:  predict_taken_o = 1'b1;
                `JUMP_JALR: predict_taken_o = 1'b0;
                default: begin
                    if (is_branch_instr_i) begin
                        predict_taken_o = bht_table[predict_idx];
                    end
                end
            endcase
        end
    end

    always_ff @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            for (i = 0; i < BHT_ENTRIES; i++) begin
                bht_table[i] <= 1'b0;
            end
        end else if (update_valid_i && update_is_branch_i) begin
            bht_table[update_idx] <= update_taken_i;
        end
    end

endmodule

GShare分支预测

GShare是一种 两级动态分支预测器，它不只看“这条分支上次怎样”，还会看最近若干次分支的全局历史。其关键思想是，当前这条分支的结果，往往和前面最近发生过哪些分支有关。

GShare通常包含两部分：

• 全局历史寄存器 GHR（Global History Register）：记录最近 n 次分支的结果，类似 1-bit 的分支预测；
• 模式历史表 PHT（Pattern History Table）：通常是一张 2-bit 的表，代表一个饱和计数器，用来表示“强跳转 / 弱跳转 / 弱不跳转 / 强不跳转”。

这样看来，GShare和 2-bit分支预测很像。但事实上，GShare做了独特的一步：它将索引进行了计算：

索引 = 分支地址低位 XOR 全局历史 GHR

也就是：

• 取分支指令 PC 的低几位
• 和 GHR 做按位异或（XOR）
• 得到最终索引

为什么？只用PC的话，很多分支可能映射冲突；只用 GHR，不同分支又区分不开。把两者 XOR 起来，相当于共享了分支自身的信息和最近历史上下文，这就是Share。

Gshare需要之前的PC传入，以及预测是否正确来更新PHT。因此，需要多几个接口。

module Dynamic_Gshare_Predictor #(
    parameter int unsigned INDEX_BITS = 8,
    parameter int unsigned META_BITS  = 2
) (
    input  logic                 clk,
    input  logic                 rst_n,
    input  logic                 valid_i,
    input  logic [         31:0] pc_i,
    input  logic                 is_branch_instr_i,
    input  logic [          1:0] jump_type_i,
    input  logic [         31:0] imm_i,
    input  logic [         31:0] branch_target_i,
    input  logic                 update_valid_i,
    input  logic [         31:0] update_pc_i,
    input  logic                 update_is_branch_i,
    input  logic                 update_taken_i,
    input  logic [META_BITS-1:0] update_meta_i,
    output logic                 predict_taken_o,
    output logic [         31:0] predict_target_o,
    output logic [META_BITS-1:0] predict_meta_o
);

    localparam int unsigned PHT_ENTRIES = 1 << INDEX_BITS;
    localparam int unsigned HASH_BITS = (INDEX_BITS < META_BITS) ? INDEX_BITS : META_BITS;

    logic   [           1:0] pht_table   [0:PHT_ENTRIES-1];
    logic   [ META_BITS-1:0] ghr_q;
    logic   [INDEX_BITS-1:0] predict_idx;
    logic   [INDEX_BITS-1:0] update_idx;
    integer                  i;

    function automatic logic [INDEX_BITS-1:0] gshare_index(input logic [31:0] pc,
                                                           input logic [META_BITS-1:0] history);
        logic [INDEX_BITS-1:0] pc_idx;
        logic [INDEX_BITS-1:0] history_folded;
        begin
            pc_idx         = pc[INDEX_BITS+1:2];
            history_folded = '0;
            if (HASH_BITS > 0) begin
                history_folded[HASH_BITS-1:0] = history[HASH_BITS-1:0];
            end
            gshare_index = pc_idx ^ history_folded;
        end
    endfunction

    function automatic logic [1:0] next_counter(input logic [1:0] counter, input logic taken);
        begin
            if (taken) begin
                if (counter != 2'b11) begin
                    next_counter = counter + 2'b01;
                end else begin
                    next_counter = counter;
                end
            end else if (counter != 2'b00) begin
                next_counter = counter - 2'b01;
            end else begin
                next_counter = counter;
            end
        end
    endfunction

    assign predict_idx    = gshare_index(pc_i, ghr_q);
    assign update_idx     = gshare_index(update_pc_i, update_meta_i);
    assign predict_meta_o = ghr_q;

    // 非投机式 GShare：
    // - 条件分支在 ID 级使用当前已提交的 GHR 做预测
    // - EX 级更新时使用随流水线带下来的 history snapshot 回写同一项 PHT
    // - GHR 只在分支真实结果产生时更新，避免额外的回滚机制
    always_comb begin
        predict_taken_o  = 1'b0;
        predict_target_o = branch_target_i;

        if (valid_i) begin
            unique case (jump_type_i)
                `JUMP_JAL:  predict_taken_o = 1'b1;
                `JUMP_JALR: predict_taken_o = 1'b0;
                default: begin
                    if (is_branch_instr_i) begin
                        predict_taken_o = pht_table[predict_idx][1];
                    end
                end
            endcase
        end
    end

    always_ff @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            ghr_q <= '0;
            for (i = 0; i < PHT_ENTRIES; i++) begin
                pht_table[i] = 2'b01;
            end
        end else if (update_valid_i && update_is_branch_i) begin
            pht_table[update_idx] <= next_counter(pht_table[update_idx], update_taken_i);
            ghr_q                 <= {ghr_q[META_BITS-2:0], update_taken_i};
        end
    end

    logic unused_imm_bit;
    assign unused_imm_bit = imm_i[0];

endmodule

BPU封装

一个较好的方式是写一个统一的BPU模块，随后使用generate case来实例化对应的分支预测：

`include "include/defines.svh"

module BPU #(
    parameter bpu_type_e   BPU_TYPE   = bpu_type_e'(1),  // STATIC
    parameter int unsigned INDEX_BITS = 8,
    parameter int unsigned META_BITS  = 8
) (
    input  logic                 clk,
    input  logic                 rst_n,
    input  logic                 valid_i,
    input  logic [         31:0] pc_i,
    input  logic                 is_branch_instr_i,
    input  logic [          1:0] jump_type_i,
    input  logic [         31:0] imm_i,
    input  logic [         31:0] branch_target_i,
    input  logic                 update_valid_i,
    input  logic [         31:0] update_pc_i,
    input  logic                 update_is_branch_i,
    input  logic                 update_taken_i,
    input  logic [META_BITS-1:0] update_meta_i,
    output logic                 predict_taken_o,
    output logic [         31:0] predict_target_o,
    output logic [META_BITS-1:0] predict_meta_o
);

    generate
        if (BPU_TYPE == NONE) begin : gen_none
            assign predict_taken_o  = 1'b0;
            assign predict_target_o = branch_target_i;
            assign predict_meta_o   = '0;
        end else if (BPU_TYPE == STATIC) begin : gen_static
            Static_Predictor #(
                .META_BITS(META_BITS)
            ) u_bpu (
                .clk               (clk),
                .rst_n             (rst_n),
                .valid_i           (valid_i),
                .pc_i              (pc_i),
                .is_branch_instr_i (is_branch_instr_i),
                .jump_type_i       (jump_type_i),
                .imm_i             (imm_i),
                .branch_target_i   (branch_target_i),
                .update_valid_i    (update_valid_i),
                .update_pc_i       (update_pc_i),
                .update_is_branch_i(update_is_branch_i),
                .update_taken_i    (update_taken_i),
                .update_meta_i     (update_meta_i),
                .predict_taken_o   (predict_taken_o),
                .predict_target_o  (predict_target_o),
                .predict_meta_o    (predict_meta_o)
            );
        end else if (BPU_TYPE == DYNAMIC_1bit) begin : gen_dynamic_1bit
            Dynamic_1bit_Predictor #(
                .INDEX_BITS(INDEX_BITS),  // 1-bit预测器使用META_BITS作为索引位宽
                .META_BITS (META_BITS)
            ) u_bpu (
                .clk               (clk),
                .rst_n             (rst_n),
                .valid_i           (valid_i),
                .pc_i              (pc_i),
                .is_branch_instr_i (is_branch_instr_i),
                .jump_type_i       (jump_type_i),
                .imm_i             (imm_i),
                .branch_target_i   (branch_target_i),
                .update_valid_i    (update_valid_i),
                .update_pc_i       (update_pc_i),
                .update_is_branch_i(update_is_branch_i),
                .update_taken_i    (update_taken_i),
                .update_meta_i     (update_meta_i),
                .predict_taken_o   (predict_taken_o),
                .predict_target_o  (predict_target_o),
                .predict_meta_o    (predict_meta_o)
            );
        end else if (BPU_TYPE == GSHARE) begin : gen_gshare
            Dynamic_Gshare_Predictor #(
                .INDEX_BITS(INDEX_BITS),
                .META_BITS (META_BITS)
            ) u_bpu (
                .clk               (clk),
                .rst_n             (rst_n),
                .valid_i           (valid_i),
                .pc_i              (pc_i),
                .is_branch_instr_i (is_branch_instr_i),
                .jump_type_i       (jump_type_i),
                .imm_i             (imm_i),
                .branch_target_i   (branch_target_i),
                .update_valid_i    (update_valid_i),
                .update_pc_i       (update_pc_i),
                .update_is_branch_i(update_is_branch_i),
                .update_taken_i    (update_taken_i),
                .update_meta_i     (update_meta_i),
                .predict_taken_o   (predict_taken_o),
                .predict_target_o  (predict_target_o),
                .predict_meta_o    (predict_meta_o)
            );
        end else begin : gen_default
`ifdef YOSYS
            assign predict_taken_o  = 1'b0;
            assign predict_target_o = branch_target_i;
            assign predict_meta_o   = '0;
`else
            initial $fatal(1, "Invalid BPU_TYPE = %0d", BPU_TYPE);
`endif
        end
    endgenerate

endmodule

测试

继续使用CoreMark测试：

分支预测类型	总Tick数	总周期数	错误预测数	基准速度比
无分支预测	5292624	53336415000	/	1.000x
静态分支预测	5011712	50501545000	163426	1.056x
1-bit(4I )动态分支预测	5035325	50730805000	167403	1.051x
1-bit(8I )动态分支预测	4998735	50371755000	142873	1.059x
GShare(8I1M)动态分支预测	4971079	50093755000	120647	1.065x
GShare(8I2M)动态分支预测	4975420	50139215000	124155	1.064x
GShare(8I4M)动态分支预测	4984823	50232025000	130558	1.062x
GShare(8I8M)动态分支预测	4993908	50323525000	138736	1.060x

可以看到，GShare的效果确实很好。