这篇论文提出的是 Bingo Spatial Data Prefetcher (2019 HPCA)：一种基于 Per-Page History (PPH) 的空间数据预取器，用 TAGE 思想把一个 page 的 footprint 同时关联到多个”事件（event）”上，但把所有事件的元数据折叠到同一张 history table 中。

TLDR：

  1. 现有空间预取器（SMS/SFP/AMPM/VLDP/SPP/BOP 等）把 page footprint 只绑定到 单一 event：长事件（如 PC+Address）准确但不常触发，短事件（如 Offset）常触发但不准。鱼和熊掌不可兼得。
  2. Insight：借鉴 TAGE，把每个 footprint 同时关联到多个事件（长+短），查找时先用最长事件，miss 后逐级退到更短事件，从而同时得到高 accuracy 和高 coverage。
  3. 观察到 TAGE 的级联多表存储开销大、冗余高（两级 table 预测相同的情况占 26%–93%）。Bingo 把所有事件的 metadata 合并到 一张 history table：用 短事件的 hash 做 index，长事件的位做 tag，使得同一份 footprint 只存一次即可被长、短事件查到。
  4. 在 ChampSim 上评估，Bingo 相比 no-prefetcher 带来平均 60% 性能提升（最高 285%），比最好的前序空间预取器（SMS）再高 11%（最高 67%），只占 LLC 容量的 6%。

背景和动机

空间数据预取（Spatial Data Prefetcher）

应用访问内存时，数据对象（结构体、数组元素）通常按固定 layout 布置，导致 access pattern 在 page（几 KB 的连续区域）粒度上重复出现。Spatial prefetcher 利用这个 spatial correlation，对每个 page 记录一张位图（footprint）表示该 page 中哪些 block 被访问，再把 footprint 绑定到某个 event，下次同一 event 再现时就直接按 footprint 发起预取。

空间预取器相比 temporal 预取器的几大优点：

  • 存储 offset/delta 即可，不用存整条地址流，metadata 小得多
  • 可预取 compulsory miss（footprint 可迁移到未访问过的新 page）
  • 能把一个 DRAM row 里的 block 一次性取出，减少 DRAM row activation，对能效友好

两类空间预取器

  1. SHared History (SHH): 全局共享的 delta/pattern 表。例：BOP、SPP、VLDP。优点是存储紧凑；缺点是不同 page 的行为被糅到一起，在行为差异大的 workload 上 coverage 低；而且多 degree 预取容易产生大量 overprediction。
  2. Per-Page History (PPH): 为每个 page 记 footprint，page 结束时将 <event, footprint> 存入 history table。例：SFP（PC+Address）、SMS（PC+Offset）、AMPM。优势是一次就能把整张 footprint 发出，timeliness 好、coverage 高。

Bingo 属于 PPH 路线。

核心痛点：单一 event 的两难

作者对比了 5 种 event 的 accuracy 与 match probability（图 2）：

Event (从长到短) Accuracy Match Probability
PC+Address 最高 (~90%) 很低 (~50%)
PC+Offset 高 中
Address 中 中
PC 较低 较高
Offset 最低 (~50%) 最高 (>75%)

长事件 = 多个具体事实同时发生（指令 + 地址），短事件 = 只需一个事实。长事件准但不常；短事件常但不准。只选一个，必定牺牲 coverage 或 accuracy。

Insight

把一个 page 的 footprint 同时关联到”多个长度不同的事件”上（即 TAGE-like 思想在 prefetcher 上的应用）：

  • 预取时先用最长事件查（最准），找不到再退到次长事件、再短事件……
  • 实验证明从 1 个 event 扩到 2 个 event（PC+Address + PC+Offset），coverage 有质的飞跃；扩到 5 个事件收益饱和。因此 Bingo 只用 2 个事件即可。

但原生 TAGE-like 方案需要多张级联 history table，存储开销大，而且这些表的预测存在大量冗余（两表同样预测的情况在 benchmark 上最高达 93%，平均明显）。

核心设计

Bingo 的核心设计一句话：一个 page 的 footprint 被同时绑定到长事件 PC+Address 和短事件 PC+Offset，但只存一份；用一张 history table，通过两次查找覆盖两个事件。

  1. Auxiliary Table（辅助存储，记录正在 active 的 page 的 footprint）
  2. History Table（训练完成后的 footprint 存放处，统一单表）
  3. 核心诀窍：用短事件 PC+Offset 的 hash 作 index，用长事件 PC+Address 的全位作 tag
  4. 查找流程：先按 PC+Address tag 匹配 → 若不中，再比较同 set 中其他表项的 PC+Offset 位是否匹配 → 若多个匹配，取若干 footprint 聚合（某 block 在 ≥20% 匹配项中出现就预取它）

1. Auxiliary Storage（追踪 active pages，实为两级）

论文只笼统地称 “auxiliary storage”，开源实现里它其实被拆成两张表以节省面积并过滤”只访问一次就结束”的 page：

1.1 FilterTable（FT）

  • 规模：64 项，全相联 LRU。
  • 每项存：region_number（key） + 首次访问的 <PC, offset>。
  • 作用：一个 page 第一次被触达时登记在 FT 里；若这个 page 自始至终只被访问过同一个 offset（即”一次性 scan”），它不会被 promote 到 AT，也就不会污染 PHT。

1.2 AccumulationTable（AT）

  • 规模：128 项，全相联 LRU。
  • 每项存：触发访问的 <PC, offset> + 长度为 pattern_len 的位图（vector<bool>）。
  • 进入条件：FT 中的 page 再被访问到一个不同的 offset 时，把 FT 项”升格”到 AT 并开始累积 footprint；FT 中的同一项同时擦除。
  • 退出条件：该 page 被 LLC evict（收到 eviction() 回调）→ 将 <trigger PC+Address, footprint> 写入 PHT。

开源里的 access() 每次 LLC 访问都会调用：先查 AT（命中则仅置位），再查 FT。这与论文正文描述一致，但双表结构在论文图里没有突出体现。

2. History Table（PHT）：单表 + TAGE 风格双查

  • Index：由一个 CRC-式折叠函数从”key”产生。Key 的布局是 base | PC | offset（高位到低位），然后用 tag = PC|offset 反复右移 index_len 位并 XOR 折叠回 key 的低 index_len 位，得到最终 set index。
  • Tag：整条 key（包含 base/PC/offset 全部有效位）在选中 set 后整体做比较。
  • 两种匹配（通过两个 mask 同时检查）：
    • max_tag_mask = (1 << (PC_WIDTH + MAX_ADDR_WIDTH - index_len)) - 1 → 等价于 PC+Address 全匹配（称 max_match）。
    • min_tag_mask = (1 << (PC_WIDTH + MIN_ADDR_WIDTH - index_len)) - 1 → 只比较 PC + offset 部分（称 min_match），即 PC+Offset。
  • 查找优先级：遍历该 set 的所有 way，一旦出现 max_match 就立即采用其 pattern，记 last_event = PC_ADDRESS；否则把所有 min_match 的 pattern 收集起来投票，记 last_event = PC_OFFSET。
  • Pattern 旋转：存入 PHT 前 pattern 会按 -offset 旋转归一（使 trigger offset 在位 0），查出时再按 +offset 还原。这样不同 offset 触发但形状相同的 footprint 可以共享同一条 PHT 表项，显著提升命中率——这是论文正文没强调的一个实现细节。
  • 投票阈值：#define THRESH 0.20。被 ≥20% 的 min-match 条目在同一位置置位的 block 才会进入 prefetch 列表。代码里还提供了 bingo_thresh001…bingo_thresh100 等变体用于灵敏度研究。

存储配置（与源码常量对齐）

开源实现 prefetcher/bingo.llc_pref 末尾的硬编码常量：

常量 值 含义
REGION_SIZE 2048 B page / region 大小（= 32 × 64B block；注意论文正文的”几 KB 的 page”在代码里就是 2KB）
MIN_ADDR_WIDTH 5 bit offset 宽度（对应 32 个 block 需 5 位）
MAX_ADDR_WIDTH 16 bit address 字段使用的总宽度（含 base + offset）
PC_WIDTH 16 bit PC 截取宽度
PHT_SIZE 16 K 项 PHT 总条目（默认 16-way → 1024 set，index_len = 10）
FT_SIZE 64 项 FilterTable
AT_SIZE 128 项 AccumulationTable
THRESH 0.20 min-match 投票阈值

PHT 每项含 valid / LRU / tag(~27 bit) / 32 位 footprint。总大小约 119 KB ≈ LLC 的 6%。灵敏度分析表明 16K 项后 coverage 饱和。

代码解读（基于作者开源 ChampSim 实现）

开源地址: https://github.com/bakhshalipour/Bingo

关键源文件 prefetcher/bingo.llc_pref（795 行，单文件自包含；inc/ 里没有头文件依赖）。仓库还包含 sms.llc_pref / bop.llc_pref / spp.llc_pref / vldp.llc_pref / ampm.llc_pref 以及 bingo_01k … bingo_64k、bingo_thresh001 … bingo_thresh100、bingo_multitable_*（用于 TAGE 级联表对比）、bingo_plus 等变体，正好对应论文的几组灵敏度/消融实验。

1. 模块组织

1
2
3
4
5
6
SetAssociativeCache<T>
  └── LRUSetAssociativeCache<T>
         ├── LRUFullyAssociativeCache<T> ──┬── FilterTable
         │                                  └── AccumulationTable
         └── PatternHistoryTable
Bingo  ─ 持有 FT / AT / PHT 三者，暴露 access() / eviction()

所有表都自带一个 per-set CAM (unordered_map<tag, way>)，使得 find() 不用线性扫描整个 set——这只是模拟器的便利写法，硬件上依然是并行 tag 比较。

2. 主流程 Bingo::access(block_number, pc)

对每一次到达 LLC 的访问执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
region_number = block_number / pattern_len         // pattern_len = 32
region_offset = block_number % pattern_len
if AT.set_pattern(region_number, offset):          // AT 命中 → 仅置位
    return {}                                      // 不发预取、不更新 FT
if FT.find(region_number) == null:                 // ——trigger access——
    FT.insert(region_number, pc, offset)
    pattern = PHT.find(pc, block_number)
    return expand(pattern, region_number)
else if FT 里的 offset != 当前 offset:              // "第二个 offset" 出现
    victim = AT.insert(FT entry)                   // 升格到 AT
    AT.set_pattern(...)
    FT.erase(region_number)
    if victim.valid: PHT.insert(victim)            // AT 满时淘汰者训练 PHT
return {}

要点：

  • 只有 trigger access 会向 LLC 发 prefetch；后续同一 page 的访问只是更新位图。
  • 只”来过一次 offset”的 page 永远不会进入 AT，避免污染 PHT（这是一种隐式过滤）。
  • AT 满时 LRU victim 会立即训练 PHT，不必等待 eviction 回调——对于常驻工作集也能持续更新。

3. 何时训练 PHT：两条路径

  1. AT 满溢出 → 受害 entry 直接 insert_in_phts（在 access() 中触发）。
  2. LLC evict 某 block → Bingo::eviction(block_number) 同时擦除 FT/AT 对应 region；若在 AT 里则同时训练 PHT。

所以文字描述的”page 结束 residency 后训练”其实更精确地是”region 的整张 footprint 从 AT 离开时训练”，无论是被 LRU 挤掉还是被真的 evict。

4. PatternHistoryTable::build_key —— CRC 折叠

1
2
3
4
5
6
7
8
key_raw = (base << (PC_WIDTH + MIN_ADDR_WIDTH))
        | (pc   <<  MIN_ADDR_WIDTH)
        | offset
tag_folded = (pc << MIN_ADDR_WIDTH) | offset
do {
    tag_folded >>= index_len;
    key_raw    ^= tag_folded & (set_mask);
} while (tag_folded > 0);

这段循环把 PC|offset 不断右移 index_len 位并 XOR 进 key 的低 index_len 位；等价于对 PC+Offset 的一次 CRC-like 哈希，只不过与 base 拼接后再按 set_mask 取模选 set。效果：set index 由 hash(PC+Offset) 决定，tag 仍为 PC+Address（隐式包含 PC+Offset）。这完美对应论文”短事件 index + 长事件 tag”的设计。

5. PatternHistoryTable::find —— max/min 匹配与投票

1
2
3
4
5
6
for each valid way in set:
    max_match = (tag & max_tag_mask) == (trigger_tag & max_tag_mask)  // PC+Address
    min_match = (tag & min_tag_mask) == (trigger_tag & min_tag_mask)  // PC+Offset
    if max_match: 立即返回该 pattern，标记 last_event = PC_ADDRESS
    elif min_match: 加入候选集合
若无 max_match：对候选集合按位投票，任一位 ≥THRESH (0.20) 置 1

三个细节与论文图示有出入：

  1. 所有候选 pattern 平权投票，THRESH=0.20 是硬编码，没用 recency 加权（论文脚注 7 说明作者测试过 recency，最终选阈值法）。
  2. max_match 命中后会 set_mru(key)，但 min_match 投票时不更新 LRU——只有成功预测的长事件项会续命，短事件项更易被淘汰。
  3. 因 MAX_ADDR_WIDTH > MIN_ADDR_WIDTH，max_tag_mask ⊇ min_tag_mask，所以 max_match ⇒ min_match；代码用 break 保证 max 优先。

6. Pattern 旋转归一

1
2
3
4
// insert:
pattern = rotate(pattern, -offset)
// find:
pattern = rotate(result, +offset)

trigger offset 总是被归一化到 bit 0 才存入 PHT。论文正文未强调这点，但它对 coverage 很重要：同一个 PC 以不同 offset 触发”相同形状”的 pattern 时（例如扫描 array 时每次从不同元素起步），它们可以共用同一条 PHT 表项。

7. 统计（区分两种事件来源）

代码里 events[region_number] 记录当次预测由 PC_ADDRESS 还是 PC_OFFSET 触发，并在 fill/evict 回调里分别计数 prefetch_cnt / cover_cnt / overpredict_cnt。论文里看不出的经验事实是：作者在开源里还为这两种事件分别统计 coverage 和 overprediction，方便做事后归因（哪部分收益真的来自”短事件兜底”）。

8. 与论文描述的对应关系 / 差异

论文描述 代码实现 备注
“auxiliary storage” FilterTable(64) + AccumulationTable(128) 两级结构，用 FT 过滤 one-shot page
“page 结束时训练 PHT” AT 满溢出 或 LLC evict 时训练 两条路径
“hash(PC+Offset) 索引, PC+Address tag” CRC-style fold；tag 用 max/min 双掩码 完全一致
“20% 阈值” #define THRESH 0.20 硬编码；提供 001…100 变体
“LRU 替换” Super::set_mru / select_victim 只在 max_match 和 insert 时续命
论文未提 pattern 按 offset 旋转归一 提升跨 offset 泛化能力
论文未提 AT 溢出也训练 PHT 常驻 page 也能持续更新

实验 Setup

实验平台：ChampSim（DPC-2 的基础设施）

Workload 选择：

  • 服务器级 big-data workload：Data Serving、SAT Solver、Streaming、Zeus、em3d
  • 5 个 SPEC 混合（Mix 1–Mix 5，每个 4 个内存密集 SPEC program）
  • 服务器负载用 SimFlex 方法，从 warmed checkpoint 跑 200K insns（其中 40K 填 ROB/队列，后续测量），95% 置信、<4% 误差
  • SPEC：每核跑 ≥100M insns，前 20M warmup，之后 80M 测量

系统设置：

  • 14nm、4GHz、4 核（4-wide OoO, 256-entry ROB, 64-entry LSQ）
  • L1 D/I：各 64KB，8-way, 4-cycle，8 MSHR
  • L2（= LLC）：8MB，16-way，4-bank，15 cycle hit
  • 主存：60 ns，37.5 GB/s，2 通道
  • 每核独立 prefetcher（核间不共享 metadata），所有方法触发于 LLC 访问并直接 prefetch 到 LLC

对比对象（均做 sensitivity 调到合理 coverage）：

  • BOP（DPC-2 冠军，256-entry RRT）
  • SPP（256 Signature / 512 Pattern / 1024 Prefetch Filter）
  • VLDP（16 DHB / 64 OPT / 3×64 DPT）
  • AMPM（表扩到 LLC 全容量）
  • SMS（16K-entry, 16-way，Bingo 的基座）
  • Bingo（16K-entry, 16-way）

实验结果

实验 1：存储灵敏度

设计：改变 Bingo 的 history table 大小（1K→64K）观察 miss coverage。

结果：miss coverage 随 size 增加而上升，16K 项后进入平台期。

结论：Bingo 固定 16K 项 / 119KB（LLC 的 6%），在容量和 coverage 间取得最佳平衡。

实验 2：miss coverage & overprediction

设计：比较所有方法 covered / uncovered / overprediction（错预取数 / baseline 的 miss 数）。

结果：

  • Bingo 平均 coverage >63%，比第二名高 8%
  • Overprediction 与其它主流预取器相当，无显著恶化
  • SHH 类（BOP/SPP/VLDP）在服务器负载上 coverage 显著偏低；VLDP 多 degree 预取带来不准
  • PPH 类（AMPM/SMS）coverage 较高但 Bingo 仍领先

结论：多事件关联 + 最长事件优先匹配 的确能同时把 accuracy 和 opportunity 吃满。

实验 3：系统性能

结果：

  • 相对 no-prefetcher，Bingo 平均 +60%，最高 +285%（em3d）
  • 对 SMS 再提升 +11%，最高 +67%
  • Zeus 上提升仅 11%，因该 workload 更偏 temporal correlation，OoO 已覆盖大多数 spatial miss

结论：Bingo 在各种 workload 上一致领先，timeliness（一次性发出整页需要的 block）+ multi-event 匹配 是关键。

实验 4：Performance density（单位面积性能）

设计：计算每种方案”性能提升 / 芯片面积”，衡量硅利用效率。

结果：Bingo 的 performance density 比 baseline 高 59%，比第二名高 10%。面积开销 < LLC 的 6%，导致 density 相对 performance 只掉 <1%。

结论：哪怕把 prefetcher 面积的机会成本计入，Bingo 也是”划算”的设计。

实验 5：ISO-degree 比较

设计：解开 SHH 方法的 degree 限制（BOP/VLDP → 32，SPP 门槛 → 1%），让它们也尝试多发预取以追平 PPH 的 timeliness。

结果：SHH 系方法性能略升但 overprediction 大幅增加（VLDP overpred 从 14% 涨到 31%；SPP 从 25% 涨到 286%！）。Bingo 仍明显领先。

结论：SHH 类方案即使被允许”激进发射”，其数据结构本质不知道一页到底还需要多少块，因此无法在不污染带宽的前提下达到 Bingo 的 timeliness。

Limits

  1. 两事件已够用？ 论文自述 event 数增至 5 时收益饱和，因此仅用 2 个。但这个饱和结论建立在一个选定的事件集合之上（PC+Address / PC+Offset / Address / PC / Offset），未必对其他 workload 成立。
  2. 短事件撞 set 时的融合策略比较简陋：20% 阈值为经验值，作者只对比了 “recency” 等少数替代。当集合内匹配条目的 footprint 差异大时，融合后可能产生 overfetch 或 underfetch。
  3. 仍然是 PPH 范式：每个 page 都需 auxiliary storage 跟踪，对超大 working set 或扫描型 workload 的 active-page 并发量仍有限制（虽然 auxiliary 存储本身不大）。
  4. 依赖 page residency 信号训练：footprint 只在 page 结束 residency 时才被提交到 history table。若 page 长时间驻留，训练样本产生滞后，对新 pattern 的收敛会慢。
  5. 跨核/多线程共享未探索：本文每核独立 prefetcher，未考察服务器多租户场景下 PC 别名与共享数据的干扰。
  6. 相关替代思路未对比：IMP、TEMPO、Domino、B-Fetch 等走 indirect / temporal / 分支-驱动路线，与 Bingo 正交。Bingo 没有与这些做叠加实验。