实现基于 v25.1.0.0 的 Gem5 , github repo: https://github.com/xixi-shredp/gem5/tree/directed-btb

1. 概述

DirectedBTB 是对 gem5 Branch Target Buffer (BTB) 子系统的扩展实现，核心思想是在 BTB entry 中嵌入一个轻量级的方向分类器 (direction classifier)，用于对 conditional branch 提供 coarse-grained 的 taken/not-taken hint。当 BTB 中的饱和计数器 (saturating counter) 积累了足够的 taken 历史后，DirectedBTB 可以绕过 conditional predictor 直接给出 “taken” 的方向预测，从而在流水线早期阶段 (pipeline front-end) 缩短分支预测延迟。

1.1 设计动机

在多周期流水线分支预测器 (PipelinedBPredUnit) 架构下，conditional predictor 的查询可能需要多个周期才能返回最终结果。对于历史上高度倾向于 taken 的 conditional branch（如循环回边 loop back-edge），BTB 本身已经持有目标地址，如果 BTB 同时能判断该分支”几乎总是 taken”，就可以在第一个周期直接给出方向预测，无需等待 conditional predictor 的结果。

1.2 核心设计原则

  • 最小侵入 (minimal intrusion)：通过在 BranchTargetBuffer 基类中添加带有 no-op 默认实现的 virtual method，确保 SimpleBTB 和其他现有 BTB 实现完全不受影响
  • predictor 状态完整性保护：即使 DirectedBTB 覆盖了方向预测结果，仍然通过 branchPlaceholder() 为 conditional predictor 创建 history record，保证后续 commit/squash 路径上的状态恢复正确
  • 可参数化 (parameterizable)：counter 位宽、初始值、阈值均可通过 Python 配置对象灵活调整

2. 文件清单与变更范围

文件 变更类型 描述
src/cpu/pred/directed_btb.hh 新增 DirectedBTBEntry 和 DirectedBTB 类声明
src/cpu/pred/directed_btb.cc 新增 DirectedBTBEntry 和 DirectedBTB 完整实现
src/cpu/pred/btb.hh 修改 基类新增 lookupDirectionHint() 和 updateDirectionInfo() 两个 virtual method
src/cpu/pred/BranchPredictor.py 修改 新增 DirectedBTB SimObject 定义及参数
src/cpu/pred/SConscript 修改 注册 directed_btb.cc 源文件和 DirectedBTB SimObject
src/cpu/pred/bpred_unit.cc 修改 单周期 BPredUnit 集成 direction hint 逻辑
src/cpu/pred/pipelined_bpred_unit.cc 修改 多周期 PipelinedBPredUnit 集成 direction hint 逻辑
tests/pyunit/pred/pyunit_pipelined_bpred_config.py 新增 Python 单元测试，验证 DirectedBTB 参数配置

3. 类层次结构

1
2
3
4
5
6
7
8
ClockedObject
  └── BranchTargetBuffer          (基类, btb.hh)
        ├── SimpleBTB              (原有实现, simple_btb.hh)  ── 无 direction 功能
        └── DirectedBTB            (新增实现, directed_btb.hh) ── 嵌入 direction classifier

ReplaceableEntry
  └── BTBEntry                    (基类, btb_entry.hh)
        └── DirectedBTBEntry      (新增, directed_btb.hh)  ── 增加 SatCounter8 + conditional 标志

3.1 BranchTargetBuffer 基类扩展

在 btb.hh 中新增两个 virtual method，均提供 no-op 默认实现：

1
2
3
4
5
6
7
8
// 查询 direction hint：对于 conditional branch，返回 BTB 是否建议 taken
virtual bool lookupDirectionHint(ThreadID tid, Addr instPC, BranchType type)
{ return false; }

// 更新 direction 信息：在 commit/squash 时将实际结果反馈给 BTB
virtual void updateDirectionInfo(ThreadID tid, Addr inst_pc,
                                 BranchType type, bool actually_taken)
{}

这一设计保证了 SimpleBTB 以及所有未覆写这两个方法的 BTB 子类行为完全不变。

4. DirectedBTBEntry 详细设计

4.1 数据结构

DirectedBTBEntry 继承自 BTBEntry，在基类的 target、inst、valid、tag 之外新增三个字段：

字段 类型 说明
counterBits unsigned 饱和计数器位宽（构造时确定，取值范围 [1, 8]）
takenCounter SatCounter8 饱和计数器，记录该 entry 对应分支 taken 的倾向程度
conditional bool 标记该 entry 是否对应 conditional branch

4.2 关键方法

resetDirectionState(bool is_conditional, unsigned initial_counter)

当一个 entry 被新分配（首次插入或替换旧 entry 后重新使用）时调用。根据分支类型设置 conditional 标志，并将计数器重置为 initialTakenCounter 参数指定的初始值。

1
2
3
4
5
6
void DirectedBTBEntry::resetDirectionState(bool is_conditional,
                                           unsigned initial_counter)
{
    conditional = is_conditional;
    takenCounter = SatCounter8(counterBits, initial_counter);
}

updateDirection(bool taken)

在 commit 或 squash 时由 updateDirectionInfo() 调用。仅对 conditional branch 有效：taken 时递增计数器，not-taken 时递减，由 SatCounter8 保证 saturate 语义（不溢出、不下溢）。

directsTaken(unsigned threshold) → bool

查询接口。当且仅当 entry 有效、是 conditional branch、且计数器值 >= directedTakenThreshold 时返回 true，表示 BTB 建议该分支预测为 taken。

replacementCandidate(unsigned threshold) → bool

替换策略辅助接口。当 entry 无效，或者是 conditional branch 且计数器值 < replacementCandidateThreshold 时返回 true。这些 entry 被认为是”弱”entry，在替换时优先被淘汰。

5. DirectedBTB 核心逻辑

5.1 构造与参数校验

构造函数通过 fatal_if 进行严格的参数校验：

  • numEntries / associativity 必须是 2 的幂（set 数量约束）
  • takenCounterBits 必须在 [1, 8] 范围内
  • initialTakenCounter、directedTakenThreshold、replacementCandidateThreshold 均不得超过计数器最大值 (1 << takenCounterBits) - 1

底层存储使用 gem5 的 AssociativeCache<DirectedBTBEntry> 模板，复用 gem5 现有的 indexing policy 和 replacement policy 框架。

5.2 查找路径 (Lookup Path)

lookup(tid, instPC, type) → PCStateBase*

标准 BTB 查找。通过 btb.accessEntry() 查找 entry（同时更新 replacement policy 的 access 信息），返回目标地址。命中/缺失统计由 stats.lookups[type] 和 stats.misses[type] 记录。

lookupDirectionHint(tid, instPC, type) → bool

DirectedBTB 的核心扩展方法：

1
2
3
4
5
6
7
8
bool DirectedBTB::lookupDirectionHint(ThreadID tid, Addr instPC, BranchType type)
{
    if (!isConditionalBranch(type))
        return false;

    DirectedBTBEntry *entry = findEntry(instPC, tid);
    return entry != nullptr && entry->directsTaken(directedTakenThreshold);
}

注意这里使用 findEntry()（即 btb.findEntry()）而非 btb.accessEntry()，不更新 replacement policy 状态，因为同一分支的 lookup() 已经调用过 accessEntry() 了。

分支类型判定通过 isConditionalBranch() 静态方法完成，覆盖 DirectCond 和 IndirectCond 两种 conditional branch 类型。

5.3 更新路径 (Update Path)

update(tid, instPC, target, type, inst)

在 BTB 目标地址更新时调用（由 BPredUnit::updateBTB() 触发）：

  1. 尝试 findEntry() 查找现有 entry
  2. 若 miss，调用 findVictim() 选择替换目标，插入新 entry，并通过 resetDirectionState() 初始化 direction 状态
  3. 调用 btb.accessEntry() 更新 replacement policy
  4. 调用 entry->update() 写入目标地址和指令指针

关键设计点：只有新分配的 entry 才重置 direction 计数器。已存在的 entry 在更新目标地址时保留其计数器状态，避免目标地址变化时丢失积累的方向统计信息。

updateDirectionInfo(tid, instPC, type, actually_taken)

在 commit 和 squash 路径上均被调用，将分支的实际执行结果反馈给对应 entry 的饱和计数器：

1
2
3
4
5
6
7
8
9
10
void DirectedBTB::updateDirectionInfo(ThreadID tid, Addr instPC,
                                      BranchType type, bool actually_taken)
{
    if (!isConditionalBranch(type))
        return;
    DirectedBTBEntry *entry = findEntry(instPC, tid);
    if (entry == nullptr)
        return;
    entry->updateDirection(actually_taken);
}

仅对 conditional branch 且 BTB 中存在对应 entry 时才更新。不存在的 entry（如 compulsory miss）不做任何操作。

5.4 替换策略 (Replacement Policy)

findVictim() 实现了一种两层优先级的替换策略：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
           ┌─────────────────────────────────┐
           │  getPossibleEntries(key)         │
           │  获取同一 set 中所有 candidate    │
           └──────────┬──────────────────────┘
                      │
           ┌──────────▼──────────────────────┐
           │  对每个 candidate 判断:            │
           │  replacementCandidate(threshold)  │
           │  → invalid 或 counter < threshold │
           └──────────┬──────────────────────┘
                      │
         ┌────────────┴────────────┐
         │                         │
  有 weak candidates?         无 weak candidates
         │                         │
         ▼                         ▼
从 weak_candidates           从 all_replaceable
中由 replPolicy 选择         中由 replPolicy 选择
victim                       victim (LRU 回退)

设计意图：保护”有价值”的 entry（counter 较高、表明该分支频繁 taken 的 entry），优先淘汰无效或 counter 低的 entry。当所有 entry 都是”强” entry 时，退化为标准 replacement policy（如 LRU）选择 victim。

6. 预测器集成 (Predictor Integration)

6.1 对 bpred_unit.cc (BPredUnit) 的修改

6.1.1 BTB 查找前移

原始代码中，BTB lookup 在 direction prediction 之后执行。修改后将 BTB lookup 提前到 direction prediction 之前，因为 lookupDirectionHint() 需要已知 BTB hit/miss 状态：

1
2
3
4
5
6
7
8
9
原始流程:            修改后流程:
┌─────────────┐      ┌─────────────┐
│ direction   │      │ BTB lookup  │  ← 前移
│ prediction  │      ├─────────────┤
├─────────────┤      │ direction   │
│ BTB lookup  │      │ prediction  │  ← 可利用 BTB hint
├─────────────┤      ├─────────────┤
│ RAS/Indirect│      │ RAS/Indirect│
└─────────────┘      └─────────────┘

6.1.2 Direction hint 覆盖逻辑

在 predict() 中插入 direction hint 查询：

1
2
3
const bool directed_taken_hint =
    !hist->uncond && hist->btbHit &&
    btb->lookupDirectionHint(tid, pc.instAddr(), brType);

三个条件缺一不可：

  1. !hist->uncond：必须是 conditional branch（unconditional 已经是 taken，无需 hint）
  2. hist->btbHit：必须 BTB 命中（miss 则无 entry 可查询 counter）
  3. btb->lookupDirectionHint() 返回 true：counter 达到阈值

当 hint 生效时：

1
2
3
4
if (directed_taken_hint) {
    cPred->branchPlaceholder(tid, pc.instAddr(), false, hist->bpHistory);
    hist->condPred = true;
}

关键操作：

  • 调用 branchPlaceholder() 而非 lookup()：创建 conditional predictor 的 history record 但不执行真正的预测查询，不影响 predictor 内部状态（如 GHR 等）。参数 uncond=false 明确告知这是 conditional branch。
  • 将 condPred 强制设为 true（taken）

这确保了当预测错误需要 squash 时，conditional predictor 仍能正确恢复其内部状态。

6.1.3 Commit/Squash 路径更新

在 commitBranch() 和 squash() 中均新增一行：

1
2
3
btb->updateDirectionInfo(tid, hist->pc, hist->type, hist->actuallyTaken);
// 或
btb->updateDirectionInfo(tid, hist->pc, hist->type, actually_taken);

确保无论分支最终是 commit 还是被 squash 修正，direction counter 都能收到实际的 taken/not-taken 反馈。

6.2 对 pipelined_bpred_unit.cc (PipelinedBPredUnit) 的修改

与 BPredUnit 的修改逻辑一致，但需要适配多阶段 (multi-stage) 预测器架构：

  1. BTB lookup 同样前移到 stage prediction 之前
  2. 当 directed_taken_hint 生效时，对每一个 stage predictor 都调用 branchPlaceholder()：
1
2
3
4
5
6
for (size_t stageIndex = 0; stageIndex < stagePredictors.size(); ++stageIndex) {
    void *stage_history = nullptr;
    stagePredictors[stageIndex]->branchPlaceholder(
        tid, pc.instAddr(), false, stage_history);
    // stage_history 记录到 hist->stagedBpHistory
}

这保证了所有 pipeline stage 的 conditional predictor 都生成了正确的 history record，使得后续 squash 能够逐 stage 恢复。

7. Python 配置接口

7.1 SimObject 定义

DirectedBTB 继承自 BranchTargetBuffer，在 BranchPredictor.py 中定义：

参数 类型 默认值 说明
numEntries Unsigned 4096 BTB entry 总数
tagBits Unsigned 16 tag 位宽
instShiftAmt Unsigned 继承 Parent 指令地址右移位数（对齐）
associativity Unsigned 1 组相联度（1 = direct-mapped）
btbReplPolicy BaseReplacementPolicy LRURP 替换策略
btbIndexingPolicy BTBIndexingPolicy BTBSetAssociative 索引策略
takenCounterBits Unsigned 2 饱和计数器位宽
initialTakenCounter Unsigned 0 新 entry 计数器初始值
directedTakenThreshold Unsigned 2 达到此阈值时 hint 为 taken
replacementCandidateThreshold Unsigned 1 低于此阈值的 entry 是优先替换候选

7.2 默认参数分析

以默认 2-bit counter (位宽=2, 取值范围 [0, 3]) 为例：

1
2
3
4
5
6
7
Counter 值:    0      1      2      3
direction:   ─────────┼──────────────
             not-taken │   taken hint
                       │ (threshold=2)
replacement: ──────────┼─────────────
             weak      │  protected
            (threshold=1)
  • 新 entry 从 0 (Strongly Not-Taken) 开始
  • 需要至少连续 2 次 taken 才能达到 threshold 2 开始给出 hint
  • counter 值为 0 的 entry 是 weak replacement candidate（低于 threshold 1）
  • counter 值 1, 2, 3 的 entry 受保护，不优先被替换

7.3 使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from m5.objects import DirectedBTB, PipelinedBPredUnit, LTAGE, LocalBP

system.cpu.branchPred = PipelinedBPredUnit(
    btb = DirectedBTB(
        numEntries = 8192,
        associativity = 4,
        takenCounterBits = 3,          # 8-state counter
        initialTakenCounter = 2,       # 初始偏向中性
        directedTakenThreshold = 5,    # 较高阈值，减少误判
        replacementCandidateThreshold = 2,
    ),
    conditionalBranchPred = LocalBP(),
    stagePredictors = [LocalBP(), LTAGE()],
    stageLatencies = [0, 3],
)

8. 数据流与时序

8.1 Predict 阶段完整数据流

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
27
            ┌──────────────────┐
instPC ───→ │  BTB lookup()    │──→ btb_target (地址)
            │                  │──→ btbHit (命中/缺失)
            └────────┬─────────┘
                     │
       btbHit && conditional?
            ┌────────▼─────────┐
            │ lookupDirection-  │
instPC ───→ │ Hint()           │──→ directed_taken_hint
            └────────┬─────────┘
                     │
        directed_taken_hint == true?
          ┌──────────┴────────────┐
          │ YES                   │ NO
          ▼                       ▼
 ┌────────────────┐    ┌────────────────────┐
 │ branchPlace-   │    │ cPred->lookup()    │
 │ holder()       │    │ (正常方向预测)       │
 │ condPred=true  │    │ condPred=预测结果    │
 └────────────────┘    └────────────────────┘
          │                       │
          └───────────┬───────────┘
                      ▼
          ┌────────────────────────┐
          │  RAS / Indirect 覆盖   │
          │  (与 DirectedBTB 无关)  │
          └────────────────────────┘

8.2 Commit/Squash 阶段反馈

1
2
3
4
5
6
7
8
9
10
11
12
13
commit 路径:                     squash 路径:
┌──────────────────┐            ┌──────────────────────────┐
│ cPred->commit()  │            │ cPred->squash()          │
│ (方向预测器更新) │            │ (方向预测器恢复)         │
├──────────────────┤            ├──────────────────────────┤
│ btb->update()    │            │ btb->update()            │
│ (目标地址更新)   │            │ (目标地址更新, if taken) │
├──────────────────┤            ├──────────────────────────┤
│ btb->update-     │            │ btb->update-             │
│ DirectionInfo()  │ ← NEW      │ DirectionInfo()          │ ← NEW
│ (direction       │            │ (direction               │
│  counter 更新)   │            │  counter 更新)           │
└──────────────────┘            └──────────────────────────┘

9. 与 SimpleBTB 的对比

特性 SimpleBTB DirectedBTB
Entry 类型 BTBEntry DirectedBTBEntry (继承 BTBEntry)
方向信息 无 每 entry 一个 saturating counter
lookupDirectionHint() 基类默认 return false 基于 counter 阈值判断
updateDirectionInfo() 基类默认 no-op 更新 counter
替换策略 标准 LRU 两层优先级 (weak candidate + LRU)
存储开销 (每 entry) target + inst + tag + valid 同上 + counterBits + takenCounter + conditional
额外存储估算 (每 entry) — ~2 bytes (1 byte SatCounter8 + 1 bit conditional + padding)

10. 统计量 (Statistics)

DirectedBTB 复用基类 BranchTargetBufferStats 中已有的统计量：

统计量 类型 说明
stats.lookups[type] Vector 按 BranchType 分类的 BTB 查找次数
stats.misses[type] Vector 按 BranchType 分类的 BTB 缺失次数
stats.updates[type] Vector 按 BranchType 分类的 BTB 更新次数
stats.mispredict[type] Vector 按 BranchType 分类的错误预测次数
stats.evictions Scalar BTB entry 被替换淘汰的次数

注意：当前实现中 DirectedBTB 未新增专门的 direction hint 相关统计量（如 hint 触发次数、hint 准确率等）。这些信息可通过后续扩展添加。

11. 构建集成

11.1 SConscript

  • Source('directed_btb.cc')：注册编译单元
  • SimObject 列表中添加 'DirectedBTB'：注册 Python SimObject

11.2 依赖关系

DirectedBTB 依赖以下 gem5 基础设施：

依赖 头文件 用途
AssociativeCache base/cache/associative_cache.hh 组相联缓存容器
SatCounter8 base/sat_counter.hh 8-bit 饱和计数器
BTBEntry cpu/pred/btb_entry.hh 基础 BTB entry
BranchTargetBuffer cpu/pred/btb.hh BTB 基类
replacement_policy::Base mem/cache/replacement_policies/base.hh 可插拔替换策略
BTBIndexingPolicy mem/cache/tags/indexing_policies/base.hh 可插拔索引策略

12. 架构决策与 Trade-off 分析

12.1 为什么在 BTB 中嵌入 direction classifier 而非独立组件

选择：将 direction counter 作为 BTB entry 的扩展字段。

理由：

  • BTB entry 的生命周期管理（allocation、eviction、invalidation）天然与该分支的”存在”绑定；独立组件需要额外同步
  • 在 BTB lookup 的同一拍内即可获取 direction hint，无额外的延迟开销
  • 利用 BTB entry 的 valid bit 和 tag matching 机制，无需单独的 tag 存储

代价：

  • DirectedBTB entry 的存储开销略大于 SimpleBTB
  • DirectedBTB 与 BTB 容量耦合——高 associativity 的大 BTB 才能充分发挥 direction classifier 的效果

12.2 branchPlaceholder vs. 忽略 conditional predictor

选择：即使 direction hint 覆盖了预测结果，仍调用 branchPlaceholder() 为 conditional predictor 创建 history。

理由：

  • conditional predictor（如 TAGE、Perceptron）通常维护 speculative history（GHR、path history 等）。跳过 history 创建会导致后续 squash 时无法正确恢复
  • branchPlaceholder() 已经是 gem5 中用于”BTB miss 但 pre-decode 检测到分支”场景的既有模式，语义明确
  • 保证了 predictor training 在 commit 路径上仍然正常工作

代价：

  • 每次 direction hint 覆盖时仍有一次 branchPlaceholder() 调用的开销（但该调用本身设计为轻量级）

12.3 两层优先级替换 vs. 纯 LRU

选择：优先淘汰 counter 低于 replacementCandidateThreshold 的 entry。

理由：

  • 高 counter 值的 entry 意味着该分支频繁 taken，direction hint 价值高，应尽量保留
  • 低 counter 值的 entry 贡献的 direction hint 较少，替换它们的损失较小
  • 当所有 entry 的 counter 都高于阈值时，自动退化为标准 replacement policy，不会造成死锁

代价：

  • 替换路径上需要两轮遍历（收集 weak candidates + 选择 victim），略增加 findVictim() 的计算开销
  • 在 set 较大（高 associativity）时，遍历成本线性增长

13. 潜在改进方向

  1. Direction hint 统计量：新增 directionHints、directionHitRate 等统计量，便于性能分析
  2. Hysteresis 初始值策略：考虑根据分支类型（如 loop back-edge vs. if-else）设置不同的 initialTakenCounter
  3. Adaptive threshold：根据运行时 misprediction rate 动态调整 directedTakenThreshold
  4. 与 multi-stage predictor 的深度集成：当前 direction hint 完全绕过所有 stage；可以考虑仅绕过 slow stage 而保留 fast stage 的精确预测
  5. C++ 单元测试补充：为 DirectedBTBEntry 和 DirectedBTB 补充 GTest，覆盖 counter 边界行为和替换策略逻辑