这篇论文提出的是 ReSemble（Reinforced Ensemble Framework for Data Prefetching）：

TLDR：

已有的多预取器管理策略（分类法、SBP）存在离线训练不适应在线变化、response lag 等问题
提出用 Q-learning 训练一个感知机（MLP），从多个预取器的建议中动态选择最佳预取地址，通过 hash and norm 解决地址空间爆炸, lazy sampling 解决反馈延迟问题
采用的是 $\epsilon$-greedy 算法（随机探索）

背景和动机

背景： 内存延迟是性能瓶颈，硬件预取通过提前加载数据来隐藏延迟。现有预取器（spatial / temporal / spatio-temporal）各自擅长不同的访存模式：

Spatial prefetcher（BO, SPP, VLDP）：利用空间局部性，预测固定 region 内的访问，但无法追踪长距离跨页依赖
Temporal prefetcher（ISB, STMS, Domino）：利用时间局部性，记录并回放历史访问序列，但依赖重复出现的模式，无法处理 compulsory miss
Spatio-temporal prefetcher（STeMS）：结合两者，但 coverage 低、启动延迟高

动机： 不同应用甚至同一应用的不同阶段，适合不同的预取器。论文通过自相关分析展示了 4 个 benchmark 的不同访存特征：

433.milc、621.wrf 有强空间自相关 → 适合 BO 等空间预取器
471.omnetpp、623.xalancbmk 按 PC 分组后才显示出自相关 → 适合 ISB 等 temporal 预取器

已有多预取器管理方法的问题：

分类法：离线训练，训练/测试 trace 不一致时 accuracy 下降；对动态 cache 行为适应性差
- Ensemble prefetching through classification using support vector machine (2016 Intelligent Systems Technologies and Applications)
- Maximizing hardware prefetch effectiveness with machine learning (2015 ICHPC, ISCSS, ICESS)
- DOL/TPC: Division of labor: A more effective approach to prefetching (2018 ISCA)
性能评估法：在线评估，但有 response lag——次优预取器要工作一段时间才会被替换(比较平均表现)，导致性能损失(尤其是短 phase)
- SBP: Sandbox prefetching: Safe run-time evaluation of aggressive prefetchers (2014 ISCA)
- Ensemble adaptive tile prefetching using fuzzy logic (2016 IJGIS)

Insight

将多预取器管理建模为强化学习问题：

Environment：硬件架构 + 多个预取器 + cache 层次
Agent：集成控制器
State：各预取器当前的预测地址（经预处理）
Action：选择哪个预取器的建议（或不预取 NP）
Reward：预取命中 +1，过期未命中 -1，NP 则 0

RL 的优势：无需离线训练、可以从 cache 反馈中在线学习、基于当前状态而非历史性能做决策（避免 response lag）

核心设计

ReSemble 的核心是用一个轻量级 MLP 作为 Q-network 来做集成预取控制，解决三个关键挑战：

Hash and Norm 预处理：解决地址空间爆炸（class explosion）问题
MLP Q-network：紧凑的模型做在线推理和学习
Lazy Sampling：解决 cache 反馈延迟问题

整体流程：

多个 prefetcher 各自给出预测地址
这些预测地址先经过预处理，组成状态向量
MLP 控制器根据状态向量输出每个 action 的 Q 值
选择一个 action：选某个 prefetcher 的预测，或选择 NP（no prefetch）
之后根据未来这条 prefetch 是否命中，回填 reward
用这些带 reward 的 transition 在线训练控制器

1. 预处理：Hash and Norm

预取器的预测分为两类，分别处理：

Spatial predictions $p_n^S(t)$：计算与当前地址的 delta 并归一化
$$s_n^S(t) = \frac{p_n^S(t) - Addr(t)}{2^{PAGE_BITS}}$$

Temporal predictions $p_n^T(t)$：用 hash 函数折叠压缩绝对地址并归一化
$$s_n^T(t) = \frac{hash(p_n^T(t))}{2^{HASH_BITS}}$$

其中，$p_n^S(t)$ 和 $p_n^T(t)$ 表示预取器给出的预取地址，Addr(t) 是 demand address

这样将百万级地址空间压缩到紧凑的 state vector:
$$s_t = f_{prep}(O_t) = [s_1^S(t),s_2^S(t),…,s_X^T(t),s_1^T(t),s_2^T(t),…,s_Y^T(t)]$$

避免 tokenization 所需的额外存储开销。

2. MLP Q-Network

使用只有一个隐藏层的 MLP 近似 Q 函数：
$$Q(s_t, a_t) = MLP(s_t, a_t; \theta)$$

输入：
- state vector $s_t$（维度 $S = N$，预取器数量）
- action $a_t \in \Alpha = {1,2,…,n,…,N,NP}$:
  $$
  a_t = \begin{cases}
  \text{Random selection from A if } P < \epsilon \
  argmax_{a \in A}\ MLP(s_t, a_t; \theta) \text{ otherwise}
  \end{cases}
  $$
  - P is a probability
  - $\epsilon = \epsilon_{start} + (\epsilon_{start} - \epsilon_{end}e^{-\frac{step}{decay}})$
输出：每个 action 的 Q-value（维度 $A = N + 1$，包含 NP）
使用 decaying $\epsilon$-greedy 策略平衡探索与利用

双网络设计：

policy net $MLP_p$（频繁更新，每 $I_p$ 步更新一次）
target net $MLP_t$（较少更新，每 $I_t$ 步）

$I_t > T_p$
通过 role switch 机制避免模型更新带来的推理停顿:

每经过 $I_p$ 步，更新 $MLP_p$:
- 下一步的 reward: $y_j \leftarrow r_j + \gamma\ max_{a’} MLP_t(s_{j+1},a’;\theta’)$
- 权重：$\theta \leftarrow \theta + \alpha (y_j - MLP_p(\cdot;\theta))\nabla_\theta MLP_p(\cdot;\theta)$
每经过 $I_t$ 步，更新 $MLP_t$:
- $Swap(MLP_t, MLP_p)$
- $\theta’ \leftarrow \theta$

损失函数定义: $L(\theta) = \Epsilon_{s,a\sim \rho(s,a)} [(y_i - MLP_p(s,a;\theta))^2]$

$\rho(s,a)$ 为 sequence s 和 action a 下的概率分布

3. Lazy Sampling

cache 反馈有延迟——预取发出后需要等待一段时间才能知道是否命中。

ReSemble 的解决方案：

每个时间步立即存储 $(s_t, a_t, p_t)$ 到 replay memory，reward 留空
后续访存命中历史预取时，回填 reward（$r_i = 1$）
超出 window $W$ 仍未命中的标记为 $r_i = -1$
选择的 action 为 NP 时，$r_i = 0$
只从已有有效 reward 的 transition 中采样训练

4. 一种使用 Q-value table 的变体

除了使用 MLP 直接计算 action 之外，还可以使用 Q-value table 查表得到 action:

Q-value 更新：$Q(s,a) \leftarrow Q(s,a) + \alpha[r + \gamma\ max Q’(s’,\cdot) - Q(s,a)]$

r: reward for action a
s’: next state

为硬件友好实现，提供 Q-table 变体：

$$
S_n^S(t) = hash(p_n^S(t) - Addr(t))
$$
$$
S_n^T(t) = hash(p_n^T(t)
$$

用 hash 函数压缩地址空间
用 tokenization 进一步压缩——只为出现过的 unique state 分配 token
8-bit hash 下 token 化后仅需 592K entries（vs 直接 21.5G）

Model	Size Expression	Configuration	param/Entries
MLP	SH + HA + H + A	H = 100	1.05K
Table (direct)	$2^{BS}A$	B = 4	328K
Table (direct)	$2^{BS}A$	B = 8	21.5G
Table (token)	$2A$(#unique states)	B = 4	37.3K
Table (token)	$2A$(#unique states)	B = 8	592K

(H: hidden layer dimension of MLP, B: hash bits)

即使优化后，Q-value Table 面积依然很大（相比于 MLP），因此该方案不可行，最终还是采用了 MLP

实验 Setup

实验平台：ChampSim 模拟器

workload 选择：SPEC CPU 2006、SPEC CPU 2017、GAP benchmark suite。每个应用模拟 100M 指令（20M warmup + 80M 测量）

系统设置：

CPU: 4 GHz, 4 cores, 4-wide OoO, 256-entry ROB
L1I/D: 64KB, L2: 1MB, LLC: 8MB 16-way, LRU
MLP: hidden dim=100, 1.05K parameters; Replay memory: 2K entries
Baseline: 各单一预取器 + SBP(E)（SBP 的扩展版本）

4 个输入预取器：BO (spatial), SPP (spatial), ISB (temporal), Domino (temporal)

Prefetchers	Configuration	Budget
BO	1K entry RR table, 1Kb prefetch bits	4KB
SPP	256 entry ST, 512 entry PT, 1024 entry PF, 8 entry GHR	5.3KB
ISB	2K entries for SP-AMC and PS-AMC	8KB
Domino	2KB prefetch buffer, 256B PointBuf, 128B LogMiss, 64B FetchBuf	2.4KB

ReSemble Setup: (面向 L2 Cache)

Configuration(env)	Info
Address bits	64
Block offset	6
Page offset	12
State dimension	4
Action dimension	5
Hash bit (for MLP)	16

Configuration(agent)	Info
Replay memory R	2000
Prefetch window size W	256
Batch size for training	256
$\epsilon_{start}$	0.95
$\epsilon_{end}$	0.005
$decay$	80
$I_p$	1
$I_t$	20

实验结果

实验 1: Model Learning Performance

设计：比较 MLP 和 tabular variants 在 1K access window 内的平均 reward，探究 PC 信息和 hash bit 数的影响

结果：

MLP（无 PC）在所有 benchmark 上获得最高平均 reward
8-bit hash tabular 优于 4-bit（更小 hash 损失信息）
PC 信息对 SPEC06 的 MLP 模型反而有害，对 tabular 模型有帮助
MLP 模型切换预取器更频繁、适应更快（Fig. 7）

结论：MLP 模型因更好的泛化能力和更快的响应速度，整体优于 tabular 模型

实验 2: Ensemble Prefetch Performance

设计：在全部 benchmark 上比较 ReSemble（MLP）、ReSemble-T（8-bit tabular）与 4 个单一预取器及 SBP(E)

结果：(平均)

Accuracy: ReSemble 85.27%, ReSemble-T 83.94%, SBP(E) 82.05%, 最佳单一（BO）60.51%
Coverage: ReSemble 44.22%, ReSemble-T 42.16%, SBP(E) 37.67%, 最佳单一（SPP）31.14%
IPC 提升: ReSemble 31.02%, ReSemble-T 29.26%, SBP(E) 25.33%, 最佳单一（SPP）22.67%

结论：ReSemble 在三个指标上全面优于所有 baseline。IPC 提升超最佳单一预取器 8.35%，超 SBP(E) 5.69%

实验 3: Latency Sensitivity Analysis

设计：引入 0-40 cycle 的推理延迟，评估 high TP（1 inference/cycle）和 low TP（1/T inference/cycle）

结果：

High TP 下 20 cycle 延迟：83.66% accuracy, 29.19% IPC 提升（仍优于 SBP 4.2%）
High TP 下 40 cycle：78.64% accuracy, 26.02% IPC（略优于 SBP）
Low TP 下延迟 >20 cycle 时性能低于 SBP

结论：高吞吐实现下，ReSemble 在 40 cycle 内仍可优于 SBP

ReSemble Inference Latency

Phase	Description	Cycle
Prepossessing	- $T_h = \lceil \log_2 \lceil \frac{\text{Addr bit}}{\text{Hash bit}} \rceil \rceil$ - $T_n$: constant multiplication	2 1
MLP	- $T_{mm_h} = \lceil 1 + \log_2 S \rceil$ - $T_{mm_o} = \lceil 1 + \log_2 H \rceil$ - $T_{av} \times 2$: look up table	5 9 2
Action	- $T_{qv} = \lceil \log_2 A \rceil$	3
Total		22

实验 4: 集成 NN-based Prefetcher (Voyager)

设计：用 Voyager（LSTM-based）替换 Domino 作为输入预取器之一

结果：ReSemble + Voyager 达到 36.22% IPC 提升，比单独 Voyager 高 4.71%，比无 Voyager 版本高 5.10%

结论：ReSemble 框架兼容 NN-based 预取器，且能进一步提升其性能

硬件开销

Structure	Description	Size
MLP	- # MLP = 2 - # parameters = 1.05K - 16-bit fixed point - Stored on chip	4.2KB
Replay Memory	- # entries of transitions = 2K - Each entry: $(s_t, a_t, r_t, s_{t+1})$ - $2 \times s_t (4 \times 16b) + a_t (3b) + r_t (1b)$ - Prefetch window: $256 \times p_t (58b)$ - Stored off chip in main memory	34.8KB

MLP 模型存储：4.2KB（on-chip），1.05K 参数
Replay Memory：34.8KB（off-chip main memory）

Limits

地址信息损失：hash and norm 不可避免地丢失信息，特别是 temporal prediction 的哈希折叠可能导致不同地址被混淆
单一选择模型：每个时间步只从 N 个预取器中选一个建议，不能同时发出多个预取请求（现实中多数系统支持多发射预取）
reward 设计过于简单：+1/-1 的 binary reward 没有考虑预取的时效性（太早/太晚的预取价值不同）和 cache pollution 的代价差异
MLP 推理延迟：22 cycle 的推理延迟在时间关键路径上，high latency 时性能优势减弱
Replay memory 在主存：34.8KB 虽然不大，但每次训练需要访问主存读取 transition，可能产生额外带宽压力
MLP 面积评估没有考虑乘法器的面积