gem5分支预测──LocalBP

LocalBP 是 gem5 中最简单的分支预测算法，代码在 src/cpu/pred/2bit_local.cc

主要组件

1. 计数器表 (localCtrs)

一个数组，每个元素是一个 2-bit 饱和计数器（可配置）。默认 1024 个表项（可配置），每个表项对应一个或多个分支指令（可能存在 hash 冲突）。这里以默认举例。

2. 2-bit 饱和计数器

状态值	二进制	含义	预测结果
0	00	Strongly Not Taken	不跳转
1	01	Weakly Not Taken	不跳转
2	10	Weakly Taken	跳转
3	11	Strongly Taken	跳转

判断规则：看最高位 (MSB)

MSB = 0 (值 0,1) → 预测不跳转
MSB = 1 (值 2,3) → 预测跳转

状态转换也很简单，跳转就 +1，没有跳转就 -1：

    +1 (taken)      +1 (taken)      +1 (taken)
00 ───────────> 01 ───────────> 10 ───────────> 11
↑               ↑               ↑               │
│   -1          │   -1          │   -1          │ 饱和
└───────────────┴───────────────┴───────────────┘
  (not taken)     (not taken)     (not taken)

3. 索引计算

1 2	const unsigned instShiftAmt; // 指令右移位数 (x86=0, ARM/RISC-V=2) const unsigned indexMask; // 掩码，取低 N 位 (默认 0x3FF = 1023)

索引计算公式：

1	index = (PC >> instShiftAmt) & indexMask

这就是它的 hash 计算函数，PC 是跳转指令的地址，PC 右移 instShiftAmt，按位与 0x3FF，计算出这条指令在 localCtrs 中的计数器索引，然后按照计数器中的值的最高位，拿到预测结果。

动画演示

以下是一个 LocalBP 的具体例子：

👉 点击查看 LocalBP 分支预测器动画演示

运行测试

测试代码：

int main() {
    volatile int sum = 0;
    for (volatile int i = 0; i < 4; i++) {
        sum += i;
    }
    return sum;
}

配置使用 LocalBP 进行分支预测：

1	system.cpu.branchPred = LocalBP()

配置输出分支预测日志：

1	--debug-flags=Branch

生成了 46 万行日志，主要是初始化中产生的：

1	464492 /home/test/builds/gem5/test/branch_output.log

在汇编中找到跳转语句的地址：

汇编日志

进一步筛选，提取出日志如下（时间戳一样的是一次）：

========== 第 1 次循环 (计数器: 0→1) ==========
10010036000: system.cpu.branchPred: [tid:0, sn:0] Branch predictor predicted 0 for PC:0x401817 DirectCond
    # 预测结果: 0 (不跳转)
10010036000: system.cpu.branchPred: [tid:0, sn:0] PC:0x401817 BTB:miss
    # BTB 未命中，第一次遇到这个分支
10010036000: system.cpu.branchPred: predict(tid:0, sn:0, PC:0x401817, DirectCond) -> taken:0, target:(0x401819=>0x401821).(0=>1) provider:NoTarget
    # 预测不跳转，目标地址未知
10010036000: system.cpu.branchPred: [tid:0] [squash sn:0] Mispredicted: DirectCond, PC:0x401817
    # 预测错误！需要冲刷流水线
10010036000: system.cpu.branchPred: Commit branch: sn:0, PC:0x401817 DirectCond, pred:0, taken:1, target:0x4017fd
    # 提交: 预测=0(不跳), 实际=1(跳了), 跳转目标=0x4017fd

========== 第 2 次循环 (计数器: 1→2) ==========
10010862000: system.cpu.branchPred: [tid:0, sn:0] Branch predictor predicted 0 for PC:0x401817 DirectCond
    # 预测结果: 0 (不跳转)
10010862000: system.cpu.branchPred: [tid:0, sn:0] PC:0x401817 BTB:hit
    # BTB 命中，已经记录过这个分支
10010862000: system.cpu.branchPred: predict(tid:0, sn:0, PC:0x401817, DirectCond) -> taken:0, target:(0x401819=>0x401821).(0=>1) provider:NoTarget
    # 预测不跳转
10010862000: system.cpu.branchPred: [tid:0] [squash sn:0] Mispredicted: DirectCond, PC:0x401817
    # 预测错误！
10010862000: system.cpu.branchPred: Commit branch: sn:0, PC:0x401817 DirectCond, pred:0, taken:1, target:0x4017fd
    # 提交: 预测=0, 实际=1, 又错了

========== 第 3 次循环 (计数器: 2→3) ==========
10011702000: system.cpu.branchPred: [tid:0, sn:0] Branch predictor predicted 1 for PC:0x401817 DirectCond
    # 预测结果: 1 (跳转) ← 计数器终于到 2 了，开始预测跳转
10011702000: system.cpu.branchPred: [tid:0, sn:0] PC:0x401817 BTB:hit
    # BTB 命中
10011702000: system.cpu.branchPred: predict(tid:0, sn:0, PC:0x401817, DirectCond) -> taken:1, target:(0x4017fd=>0x401805).(0=>1) provider:BTB
    # 预测跳转，目标地址由 BTB 提供
10011702000: system.cpu.branchPred: Commit branch: sn:0, PC:0x401817 DirectCond, pred:1, taken:1, target:0x4017fd
    # 提交: 预测=1, 实际=1, 预测正确！(没有 Mispredicted)

========== 第 4 次循环 (计数器: 3→3 饱和) ==========
10012556000: system.cpu.branchPred: [tid:0, sn:0] Branch predictor predicted 1 for PC:0x401817 DirectCond
    # 预测结果: 1 (跳转)
10012556000: system.cpu.branchPred: [tid:0, sn:0] PC:0x401817 BTB:hit
    # BTB 命中
10012556000: system.cpu.branchPred: predict(tid:0, sn:0, PC:0x401817, DirectCond) -> taken:1, target:(0x4017fd=>0x401805).(0=>1) provider:BTB
    # 预测跳转
10012556000: system.cpu.branchPred: Commit branch: sn:0, PC:0x401817 DirectCond, pred:1, taken:1, target:0x4017fd
    # 提交: 预测=1, 实际=1, 预测正确！

========== 第 5 次循环 - 退出 (计数器: 3→2) ==========
10013664000: system.cpu.branchPred: [tid:0, sn:0] Branch predictor predicted 1 for PC:0x401817 DirectCond
    # 预测结果: 1 (跳转)
10013664000: system.cpu.branchPred: [tid:0, sn:0] PC:0x401817 BTB:hit
    # BTB 命中
10013664000: system.cpu.branchPred: predict(tid:0, sn:0, PC:0x401817, DirectCond) -> taken:1, target:(0x4017fd=>0x401805).(0=>1) provider:BTB
    # 预测跳转
10013664000: system.cpu.branchPred: [tid:0] [squash sn:0] Mispredicted: DirectCond, PC:0x401817
    # 预测错误！循环退出了
10013664000: system.cpu.branchPred: Commit branch: sn:0, PC:0x401817 DirectCond, pred:1, taken:0, target:0x401819
    # 提交: 预测=1(跳), 实际=0(不跳), 退出循环，跳转到下一条指令 0x401819

总结：5 次预测，2 次正确，3 次错误，准确率 40%

运行结果和动画演示完全一样：

预测结果

优缺点

优点：逻辑简单，适合硬件资源受限的环境

缺点：

冷启动问题：需要进行多次执行才能”学会”分支模式
循环退出大概率预测错误：因为循环执行多次后，计数器已经偏向跳转状态，退出时预测跳转但实际不跳转，导致错误
hash 冲突：不同地址经过 index = (PC >> instShiftAmt) & indexMask 计算出相同的索引，会造成两个跳转指令的计数器冲突
无法利用分支间的相关性：LocalBP 是通过 PC 来计算出它对应的计数器，这导致它只能看到当前分支的历史，不考虑其他分支的影响。比如两个 if (x > 0) 分支结果完全相同，但 LocalBP 无法利用这种关联