Patents	Inc.	Title
US12190114B2	Intel	Segmented branch target buffer based on branch instruction type

问题

高代码覆盖工作负载中，BTB misses 会导致前端停滞和重定向，严重影响性能
传统 BTB 未针对不同类型分支指令的行为特征进行优化，导致存储效率低和预测准确性不足

解法：分段 BTB 结构

专利提出将 BTB 分为多个独立缓存部分，根据分支指令类型、出现频率、目标地址与分支地址的空间关系等信息进行访问

Segmented BTB

Hot Cache：存储频繁出现的直接分支指令的目标信息
- Delta Cache：存储 BIA 和 BTA 在同一内存页内的 Direct Branch（只需要存储 BTA 到 BIA 的偏移）
- Page/Offset Cache：存储 BIA 和 BTA 在不同页的 Direct Call 指令，分为：
  - Page Cache：存储 BTA 的页面信息
  - Offset Cache：存储 BTA 在页面内的偏移量
Target Cache：存储 Indirect Branch 以及不频繁出现的 Direct Branch
BTB Monitor：记录哪些分支指令存储在 Hot Cache 中，并指示访问哪个子缓存
BTB Entry Meta-Data
Usefulness / Confidence：预测正确++，预测错误则大幅降低或重置
- 当一个 Direct Branch 在 TargetCache 中的 Usefulness / Confidence 大于某个阈值，则可以从 Target Cache 迁移到 Hot Cache
- 当一个 Direct Branch 在 HotCache 中的 Usefulness / Confidence 大于某个阈值，则可以从 Target Cache 移出
Age / Recency：某个 Cache 内部进行替换时的决策依据（LRU）

Example Cache Size

Component	Entry bits	Entries	Storage(KB)
BTB Monitor	36	8192	36
Page Cache	56	512	3.5
Offset Cache	16	768	1.5
Delta Cache	16	580	1.13
Target Cache	88	4096	44
APT-BTB(Total Storage)			86.13
Conventional BTB	88	8192	88

                BTB Monitor Entry
         +-+---------+---------+------+
         |v|   Tag   | EntryID | Flag |
         +-+---------+---------+------+
bits(36): 1    16        18        1

            Page Cache Entry
         +---------+------------+---+
         | PageID  | Usefulness |age|
         +---------+------------+---+
bits(56):    52

           Offset Cache Entry
         +---------+------------+---+
         | Offset  | Usefulness |age|
         +---------+------------+---+
bits(16):    12

           Delta Cache Entry
         +---------+------------+---+
         | Delta   | Usefulness |age|
         +---------+------------+---+
bits(16):    12

                Target Cache Entry
         +-+-----+--------+------------+---+
         |v| Tag | Target | Usefulness |age|
         +-+-----+--------+------------+---+
bits(88): 1  16      64

DeltaCache 的容量为什么偏偏是 580？

EntryID 的分配问题:

方案 1: 全相联 Cache
1. 更新复杂：每次更新需要全相联式比较 page cache 的 page id 和 bta 所在 page 是否匹配
2. 一致性问题，多个分支共享一个 page ，更新一个分支会影响到 PageID, 其他分支难以感知到变化从而受到影响
方案 2: 组相联 Cache
1. 更新问题：以 BTA 的 Page 和 Offset 作为 index 和 tag 实现为组相联 cache ，并将对应的 index 存到 EntryID 中
2. 一致性问题:
  - 预测：有条目就预测(选择置信度高的条目预测)，预测正确则提高置信度，预测错误不降低置信度
  - 训练：置信度低时才替换，置信度低的 page 被替换后原本使用该 page 的分支预测会出错（但原本 page 置信度低已说明预测正确性不高且有大量对该 page 的竞争，这个因素不好分析，需要评估）
3. 根据专利，Cache 里面存储的是完整的 PageID 和 PageOffset (而且对于 Offset 而言，似乎直接把 Offset 存 EntryID 更合理)
方案 3: EntryID 以 FreeList 的方式分配
- 相比于 HotCache, BTB Monitor 的容量太大
- PageCache 和 OffsetCache 容量似乎应当保持一致，不需要拆分为 2 个 Cache
- 可以避免某个分支对 PageCache 和 OffsetCache 的更新对其他分支产生影响

lookup logic

graph TD
  a[Incoming PC] --> b{{Direct Branch?}};
  b --no-->    tc[lookup TargetCache]
  tc --miss--> miss[miss in BTB]
  tc --hit-->  tcret[target]
  b --yes--> hc[lookup HotCache]
  hc --> iscall{{Direct Call?}}
  iscall --no-->  dc[lookup DeltaCache]
  iscall --yes--> oc[lookup Page/OffsetCache]
  dc --miss--> tc
  dc --hit-->  dcret[target = pc + delta]
  oc --miss--> tc
  oc --hit-->  ocret[target = page + offset]

BTB 结构变体

offset cache 和 delta cache 合并到一起，通过 BM 中的一个分支类型域区分 offset/delta cache entry
target cache 的结构也可以类似于 hot cache 结构以降低存储开销

软件 Hint

专利还提出在分支指令中嵌入 Hint 字段，指导 BTB 的分配与更新策略：

Page 指示位：指示 BIA 和 BTA 是否在同一页面
流式代码指示位：标识流式代码，避免 BTB 分配污染 (没有时间局部性)
Hot Target 指示位：指示应优先存入 Hot Cache
阶段指示位：标识程序进入新阶段，可重置旧 Entry 或降低旧 Entry 的 Usefulness/Confidence
覆盖指示位：指示是否采用软件 Hint 指导的 BTB 分配