这篇论文提出的是 Micro-Armed Bandit（MICRO 2023）：

TLDR：

发现微架构决策问题中动作空间具有时间同质性（temporal homogeneity）——在较长时间窗口内，最优动作基本不变
基于这一性质，用最简单的 RL 形式——Multi-Armed Bandit (MAB) 替代复杂的 MDP-RL，大幅降低复杂度和存储开销
采用 Discounted Upper Confidence Bound (DUCB) 算法，存储开销仅约 100 字节
在 data prefetching 和 SMT instruction fetch 两个用例上验证了有效性和可复用性

背景和动机

背景： 在线强化学习（Online RL）因其高适应性和无需离线训练的特点，被广泛用于微架构决策，如 prefetching、cache replacement、资源管理等。

现有问题：

复杂度和存储开销高： 现有硬件 RL agent（如 Pythia 基于 SARSA）将环境建模为 MDP，需要维护大量状态-动作值，存储开销大（Pythia 需 24KB）
不可复用： 大多数 RL agent 为特定问题定制，每个新用例都需要重新设计和验证

Insight: Temporal Homogeneity

微架构决策问题的动作空间具有时间同质性（temporal homogeneity）：在给定时间窗口内，最优动作基本保持不变

论文将 RL 问题分为 3 类:

MDP-RL：状态多, 复杂度最高
Contextual Bandit：比 MDP 简化，但保留上下文状态
Multi-Armed Bandit：直接把环境压成单状态，只学“哪个动作总体最好”

通常认为 MAB 不适合复杂硬件控制，但作者发现：在一些微体系结构问题里，某一段时间窗口内真正“有用”的动作只占很小一部分，而且最优动作在该时间段内相对稳定。

这意味着不一定非要精确建模状态转移，只要动作空间在时间上有“局部稳定性”，就可以把问题粗略建模为单状态 RL，用 MAB 来逼近最优决策
而且可以直接把 RL 的硬件复杂度从“状态数 × 动作数”降到了“动作数”

在预取场景中，如果直接把动作定义成“offset + degree”的组合，那么不同 degree/offset 在不同程序阶段确实有不同效果。

论文通过观察一个强 RL 预取器 Pythia 的动作分布，发现：

Pythia 支持 16 个 offset × 4 个 degree = 64 个动作；
在 SPEC 的 1B 指令轨迹上，平均最常选动作占 60%；
第二常选动作再占 15%；
即：整个动作空间的约 3% 就覆盖了 75% 的动作选择

这说明预取动作空间具有明显的时间同质性。

但论文也指出 MAB 无法区分 cache line 地址, PC 等细粒度状态，因此不能直接用来给“每一次访问”决定统一的最佳 offset/degree；否则会过度粗化

但是对于多预取器的管理而言，不存在上述问题，MAB 非常适合此类粗粒度动作：

细粒度模式识别仍由传统预取器完成
Bandit 只做预取器的管理

核心设计

Micro-Armed Bandit（简称 Bandit）是一个轻量级硬件 RL agent，基于 DUCB 算法：

DUCB 算法替代简单的 UCB/ε-Greedy，通过折扣因子 γ 适应非平稳环境（程序阶段变化）
两个微架构适配修改：奖励归一化 + 随机重启机制，解决跨 benchmark IPC 差异和多核干扰问题
两个应用场景：prefetching coordinator（协调多个轻量级预取器的 degree/type）和 SMT fetch PG policy（同时控制 fetch priority 和 fetch gating）

1. DUCB 算法

三种 MAB 算法对比：

ε-Greedy：
- 以概率 1−ϵ 选当前平均 reward 最高的动作，以概率 ϵ 随机探索
- 探索是随机的
- 探索不随时间自然衰减
- 探索效率较低
UCB(Upper Confidence Bound)：
- 选择公式：平均 reward + 探索边界 $r_i + c\sqrt{\frac{\ln(n_{total})}{n_i}}$
- 如果某个动作很少被选过，它的 $n_i$ 小，探索项就大，因此更容易再次被尝试
- 随着时间推移，探索项自然衰减
- 不遗忘历史，无法适应阶段变化
DUCB(Discounted Upper Confidence Bound)：
- 在 UCB 基础上引入折扣因子 γ（<1）
- 在 updSels 中对所有 arm 的选择次数 $n_i$ 乘以 γ 进行衰减，使得 agent 能”遗忘”旧行为，适应程序阶段变化

论文认为微体系结构场景中 workload 行为随时间变化，DUCB 比 UCB 更合适，也更不容易长期困在次优动作。

	ε-Greedy	Upper Confidence Bound	Discounted Upper Confidence Bound
nextArm	$arm \leftarrow \begin{cases} \arg\max{r_i} & \text{with prob. } 1-\epsilon \ \text{random arm} & \text{with prob. } \epsilon \end{cases}$	$arm \leftarrow \arg\max\left{r_i + c\sqrt{\frac{\ln(n_{total})}{n_i}}\right}$	$arm \leftarrow \arg\max\left{r_i + c\sqrt{\frac{\ln(n_{total})}{n_i}}\right}$
updSels	$n_{arm} \leftarrow n_{arm}+1$ $n_{total} \leftarrow n_{total}+1$	$n_{arm} \leftarrow n_{arm}+1$ $n_{total} \leftarrow n_{total}+1$	$n_i \leftarrow \gamma \times n_i,\ \forall i \in [1,M]$ $n_{arm} \leftarrow n_{arm}+1$ $n_{total} \leftarrow \gamma \times n_{total}+1$
updRew	$r_{arm} \leftarrow \dfrac{r_{arm} \ast (n_{arm}-1) + r_{step}}{n_{arm}}$	$r_{arm} \leftarrow \dfrac{r_{arm} \ast (n_{arm}-1) + r_{step}}{n_{arm}}$	$r_{arm} \leftarrow \dfrac{r_{arm} \ast (n_{arm}-1) + r_{step}}{n_{arm}}$

MAB 算法框架：

Input: M arms
Variables:
- $r_i$ : arm i 的平均 reward
- $n_i$ : arm i 被选过的次数

Initial Round Robin Phase
- ntotal ← 0
- 依次对所有的 arm:
  - $n_i += 1$
  - $n_{total} += 1$
  - 接收到 reward 反馈后 $r_i = r_{step}$
Main Loop
- arm = nextArm()
- updSels(arm)
- 接收到 reward 反馈后 $r_{arm}$ = updRew($r_{step}$)

2. 微架构环境适配

Reward 归一化

问题：如果统一使用 IPC 作为 reward，不同 benchmark 的 IPC 量级差异很大，那么同一个探索常数 c 对低 IPC 程序会显得过强，对高 IPC 程序会显得过弱。
结果导致低 IPC 程序被过度探索。

解决方案：在初始 round-robin 试完所有动作后，计算一个初始平均奖励 $r_{avg}$，用它去归一化后续 reward，这样不同 benchmark 上的探索强度更一致

多核随机重启

问题：多个核都在跑 MAB 时，核间干扰会污染 reward。比如某个核选了非常激进的预取动作，把 DRAM 带宽抢走，其他核 IPC 下降，这些核可能误以为“自己当前在尝试的动作不好”，从而错误学习

解决方案：加入一个小概率 $rr_restart_prob$ 的重新执行 initial round-robin phase 机制，但不清空已有统计($r_i$ 和 $n_i$)。这样每个核有机会在更稳定的环境中重新评估所有动作
(但这并不是完美解法，只是一种缓解手段)

Bandit 在多核场景下的根本问题：独立代理 + 局部 reward 会导致竞争与误归因

2025 MICRO µMama 正是顺着这条线继续做的

3. 硬件结构

Bandit 的硬件主要由三部分构成：

nTable：记录每个 arm 被选过多少次 $n_i$
rTable：记录每个 arm 当前平均奖励 $r_i$
算术单元 + 控制逻辑：计算 potential, 更新计数和 reward, 把所选动作通知子预取器

Bandit 的工作流程：

顺序读出所有 arm 的 $n_i$ 和 $r_i$
计算出每个 arm 的 potential
选出最大的 arm
把该 arm 配置发给预取器或 SMT fetch 控制逻辑
bandit step 结束后，根据硬件计数器算出此次 step reward
更新 rTable/nTable

4. 两个应用场景

多预取器管理

Bandit 作为 coordinator 控制一组轻量预取器（next-line、stream、stride）的开关和 degree

共 11 个 arm
每个 arm 编码:
- next-line 开/关
- stream prefetcher 的 degree
- stride prefetcher 的 degree
Bandit step 定义：1000 次 L2 demand access

SMT Instruction Fetch

Bandit 控制 fetch Priority & Gating (PG) policy:

fetch priority policy：优先从哪个线程 fetch
fetch gating policy：是否因为某个线程过度占用 IQ/ROB/IRF/LSQ 而暂时停止 fetch instruction

论文将这两个决策合成 fetch Priority & Gating (PG) policy，扩展了 Choi & Yeung 的 Hill Climbing 方案：

4 种 fetch priority policy（BrC, IC, LSQC, RR）× 16 种 fetch gating 配置 = 64 种 PG policy
从中裁剪出 6 个高效 arm
Bandit step = 32 个 Hill Climbing epoch（每 epoch = 64k cycles）
Hill Climbing 在 Bandit 选定的 arm 下运行，负责调优 occupancy threshold

利用 temporal homogeneity：一段时间内，某种 PG policy 往往持续有效

5. 硬件开销

Bandit 的开销随 arm 数线性增长；
若 r 用 float, n 用 unsigned int，每个 arm 只要 8B
预取场景中 11 个 arm 时总存储 < 100 字节，面积 0.00044 mm²，功耗 0.11 mW（10nm），相对 server 级 CPU 开销 < 0.003%

关键路径延迟: < 500 cycle，小于 bandit step 持续时间（128k cycle for prefetching）

在 step 切换的 500 个 cycle 内存在滞后

实验 Setup

Prefetching：

实验平台：ChampSim（trace-driven）
workload：SPEC06, SPEC17, PARSEC, Ligra, CloudSuite, DPC-3 traces
系统设置：类 Intel Skylake 核，L2=256KB 8-way，LLC=2MB 16-way；也测试了 L2=1MB, LLC=1.5MB 配置
单核跑 1B instructions，4 核跑 250M/core

SMT Instruction Fetch：

实验平台：Gem5 v20 + SecSMT（支持 2-thread SMT）
workload：22 个 SPEC17 应用，226 个 2-thread mix
系统设置：类 Intel Skylake 核，ROB=224, IQ=97, 16B fetch width

Prefetch 场景：

参数	值
Bandit Algorithm	DUCB
γ	0.999
c	0.04
# Arms	11
Bandit Step	1000 L2 acc
# Trackers in Streamer	64
# Trackers in Stride	64
rr_restart_prob (4 cores)	0.001

SMT 场景：

参数	值
Bandit Algorithm	DUCB
γ	0.975
c	0.01
# Arms	6
Bandit Step-RR	32 HillClimb Epochs
Bandit Step	2 HillClimb Epochs
Hill Climbing Epoch	64k cycles
Hill Climbing δ	2

实验结果

实验 1: MAB 算法对比（Tune Set）

设计：在 tune set 上比较 Best Static arm、Single（探索后固定）、Periodic、ε-Greedy、UCB、DUCB。

结果（prefetching，相对 best static arm 的 IPC 百分比）：

DUCB gmean = 99.1%，最佳
UCB gmean = 98.8%
Pythia gmean = 98.4%
DUCB max = 101.6%（超越 best static，因能适应阶段变化）

结论：DUCB 是最优 MAB 算法，其折扣机制使其能捕捉程序阶段变化，甚至超越静态最优 arm。

实验 2: Prefetching 单核性能

设计：比较 Stride、Bingo、MLOP、Pythia、Bandit 在所有 trace 上的 geomean IPC。

结果（Figure 8，IPC normalized to no-L2-prefetcher）：

Bandit 超过 Stride 9%、Bingo 2.6%、MLOP 2.3%
Bandit 与 Pythia 仅差 0.2%（Pythia 存储 24KB vs Bandit < 100B）

结论：Bandit 以极低存储实现了接近 SOTA 的预取性能。

实验 3: 带宽受限场景

设计：扫描 DRAM 带宽从 150 MTPS 到 9600 MTPS，对比 Bandit 和 Pythia。

结果：在最受限配置（150 MTPS）下，Bandit 超过 Pythia 2.5%。因为 Bandit 直接以 IPC 为奖励，能自动学会在带宽受限时选择保守配置。

结论：Bandit 在带宽受限场景下优于 Pythia，无需显式带宽感知。

实验 4: 4 核多核性能

设计：4 核各跑相同或不同应用，对比各预取器。

结果：Bandit 超过 Stride 6%、MLOP 2.4%、Bingo 4.0%，但略低于 Pythia 1.0%（因多核并行探索时奖励更噪声）。

结论：多核性能良好，但核间干扰导致的噪声奖励是未来改进方向。

实验 5: SMT Fetch Policy

设计：226 个 2-thread mix，比较 Bandit 相对 Choi policy 的 IPC。

结果：

Bandit 在 36 个 mix 中超过 Choi 4% 以上（最高 36%），仅 6 个 mix 中 Choi 更好
总体 geomean speedup = 2.2% over Choi，7% over plain ICount
Bandit 减少 rename stall，增加 rename running cycle 2.6%（因能感知 SQ 等结构，减少保守的 fetch gating）

结论：Bandit 作为通用 RL agent 可以有效替代手工设计的 SMT 资源管理策略。

Limits

时间同质性是前提假设：对于动作空间变化极快的问题（temporal heterogeneous），MAB 将无法有效工作
无法区分环境状态：Bandit 将所有状态坍缩为单状态，无法为不同 PC 或 cache line 选择不同动作
多核干扰：多核并行探索时，一个核的激进选择导致其他核的奖励噪声化。随机重启只是部分缓解，不是根本解决方案
超参数需要 tune set 调优：γ、c、bandit step 等参数对不同用例需要不同取值，且最优值因应用而异
延迟较长: 在 step 切换的 500 个 cycle 内存在滞后

Micro-Armed Bandit (2023 MICRO): Lightweight & Reusable Reinforcement Learning for Microarchitecture Decision-Making