问题起源: 性能反常

Intel SegmentedBTB 是一种根据 branch hotness 将 BTB 分为 Hot Cache, Target Cache 两个 Segments 的设计，针对 Hot Cache 按照 BIA 和 BTA 之间的页面关系进行存储空间的优化，使得相同存储预算下, Hot Cache 可以存储更多的 branch targets.

InfinitBTB 是一种无限容量的全相联 BTB ，主要用于探索 BTB 优化设计的性能上限。

在研究 Intel SegmentedBTB (有限容量 BTB) 和 InfinitBTB 的性能对比时发现，SegmentedBTB 比 InfinitBTB 在某些 workloads 上的 ipc 更高。

最终分析得到的原因为：

方向预测器并不是理想的: InfinitBTB 对于方向预测器预测错误的 not-taken branch (预测为 taken)，依旧会提供 target，导致这些分支直到后端计算完目标地址之后才能 squash，而原本这些 not-taken branch 在 SegmentedBTB 中由于 hotness 不足很可能导致 BTB miss ，进而预测为 not-taken
BTB miss 导致的 misprediction 的代价（not taken, 在 decode 阶段就可以 resteer）比方向预测器导致的 misprediction （taken 预测错误，流水线走完才能修正）代价更低
有限容量的 SegmentedBTB 充当了”taken 预测的门控器“, 自然过滤掉了那些很少 taken 的分支——对这些分支，由于容量不足导致的 “默认 not taken” 比让 TAGE 来预测反而更准

这个性能反常现象进一步说明了：盲目地加大 BTB 容量不可取，反而可能会使性能倒退

除此之外，这个现象还引发了如下的思考：

将部分 BDP 的功能转移到 BTB：
SegmentedBTB 根据 hotness 可以对 BDP 预测为 taken 的分支起到一定的过滤作用，是否可以让 BTB 承担更多 BDP 的功能？
BTB 和 BDP 的功能在 Not Taken Prediction 上存在重合，是否可以将二者结合在一起，减少冗余？

超出 BTB 容量视为 not taken 本身可以理解为一种 not taken 预测
SegmentedBTB 对 hot branch 的过滤本身也是一种方向预测，相当于将 cold branch 预测为 not taken
所以有限容量的 BTB 天然就是一种 Not Taken Predictor
虽然 BDP 和 SegmentedBTB 内部都有 counter 来记录 hotness，BDP 索引需要 pc + history ，而 SegmentedBTB 只需要 pc 相当于 TAGE 的 base table ，二者是否可以考虑融合在一起?

核心思想: branch 分类

Class 1: easy not-taken / cold-taken

特征：

taken 率低, (即使 taken，将 target 驻留在 BTB 中的收益也不高)
历史相关性弱
不值得占用 BTB / target resources

这种分支最适合直接由 BTB miss 来处理

Class 2: easy taken / hot target branches

特征：

taken率高
target 稳定
值得常驻 BTB

这种分支可以让 BTB 直接承担：

target 提供
默认方向 taken
不必访问方向预测器

Class 3: hard branches / context-sensitive branches

特征：

单看 PC 不够
需要 global history / path history
phase-sensitive
aliasing 敏感

由复杂的 BDP 处理

总的设计思路是：把 Class 1 和 Class 2 从传统 BDP 中剥离出去，只把 Class 3 留给 history-based predictor

收益来源：将方向预测器的资源更多的留给 Class 3

可能的设计方案: DirectedBTB

设计方式 1: BTB Entry 增加 fields

BTB Entry 增加 fields:

taken counter: 记录 taken 概率。 branch taken 一次，counter +1；not-taken 一次，counter -1；counter 实现为饱和计数器

分配策略：不做改变

替换策略: taken counter 低于一定阈值的 target 都被视为替换候选项，替换候选项之间采用 LRU 替换策略

lookup 时，如果找到的 BTB entry taken counter 大于一定阈值，则方向判断绕过方向预测器

update 时如果对应分支的 PC 在 BTB 中得到的 Entry Bits 中 taken counter 很高，被视为 Hot-Taken branch ，则不去更新方向预测器中和局部历史相关的结构(包括预测更新和 commit 更新)

在 Gem5 上的个人实现：

设计方式 2: Directed Segmented BTB

将 BTB 分为如下的 2 个 Segments:

Hot-Taken Segment：强 taken，BTB 提供 target，其方向预测直接绕过方向预测器
Uncertain Segment：提供 target，但需方向预测器判定方向

分配策略：一个新的分支先进入 Uncertain Segment 进行训练，其 hotness 应当设置为最低值，当其 hotness 训练达到一定阈值之后，将其移动到 Hot-Taken Segment

替换策略: Uncertain Segment 中所有 hotness 低于一定阈值的 target 都被视为替换候选项，替换候选项之间采用 LRU 替换策略; Hot-Taken Segment 内部只需要使用基本的 LRU 替换策略即可

lookup 时 Hot-Taken Segment 和 Uncertain Segment 并行查找（理论上最多只会有一个 hit）

update 时如果对应分支的 PC 在 Hot-Taken Segment 中，则不去更新方向预测器中和局部历史相关的结构(包括预测更新和 commit 更新)