论文笔记：AnImitation Learning Approach for Cache Replacement-EW帮帮网

ICML 2020

代码：kato1628/cache_replacement: A transformer-based cache replacement model for CDNs using imitation learning technique with Belady's optimal policy

google-research/cache_replacement at master · google-research/google-research

1 INTRO

大致而言，提升缓存命中率的手段主要有两种
- 通过预取（prefetching）机制主动将未来需要的数据提前加载到缓存中，避免未来的未命中
- 在缓存需要为新数据腾出空间时，策略性地选择要从缓存中移除哪些数据（即缓存替换）
本研究专注于单层缓存替换
- 当由于缓存未命中而需要向缓存中添加一个新的数据块（称为 line）时，必须从缓存中移除一个已有的缓存行以腾出空间
- 在缓存未命中时，缓存替换策略会接收当前访问的数据行以及当前缓存中的所有数据行作为输入，并输出应当被移除的缓存行
- 、
已有的研究经常依赖人工设计的启发式规则，以捕捉最常见的缓存访问模式
- 这些启发式方法在它们针对的简单访问模式上表现良好，但它们只能覆盖所有可能访问模式中的一小部分，因此在面对更加多样和复杂的访问模式时效果不佳。
论文提出一种新的方法PARROT，通过模仿学习（Imitation Learning, IL）框架借助 Belady 最优策略来学习缓存替换策略
- Belady 的最优策略（简称 Belady 策略）是一种理想的“预知未来”的策略，能基于未来的访问序列做出最优的替换决策
- 论文提出用只依赖历史访问数据的策略去近似它
  - 首次将缓存替换问题表述为一个模仿学习问题
  - 设计了一种用于端到端缓存替换的神经网络结构，并引入了若干监督学习任务以进一步提升其在标准模仿学习上的表现

2 将缓存替换建模为模仿学习（Imitation Learning）

将缓存替换问题建模为一个带有终止状态的马尔可夫决策过程上的策略学习任务
- 在第 t个时间步中，状态由三个部分组成
  - $s^a_t = (m_t, pc_t)$ ：当前的缓存访问，包含当前访问的缓存行地址 mt以及该访问对应的唯一程序计数器 pct。
  - $s^c_t = \{l_1, \dots, l_W\}$ ：表示当前缓存组中的 W 个缓存行地址组成的集合，替换策略将根据当前访问 $s^a_t$ 决定驱逐哪个行
  - $s^h_t = (\{m_1, \dots, m_{t-1}\}, \{pc_1, \dots, pc_{t-1}\})$ ：所有过去的缓存访问的历史。实际上，我们仅在过去的 H 次访问上进行条件建模。
动作集合 $\mathcal{A}_{s_t}$ 是针对状态 $s_t = (s^c_t, s^a_t, s^h_t)$ 可选的动作定义：
- 如果发生缓存未命中，即 $m_t \notin s^c_t$ ，则动作集合 $\mathcal{A}_{s_t}$ 是整数集合 $\{1, \dots, W\}$ ，其中 w表示驱逐缓存行 lw。
- 如果发生缓存命中，则动作集合 $\mathcal{A}_{s_t}$ 仅包含一个空操作动作 $a_{\text{no-op}}$ ，因为没有行需要被替换。
状态转移函数 $\mathcal{P}(s_{t+1} \mid a_t, s_t)$ 由状态中三个部分的动态变化决定：
- 下一步的访问 $s^a_{t+1} = (m_{t+1}, pc_{t+1})$ 是程序所访问的下一个地址及其对应的 PC；
- 访问历史更新为 $s^h_{t+1} = (\{m_1, \dots, m_t\}, \{pc_1, \dots, pc_t\})$ ；
- 缓存状态的转移由替换策略决定：
  - 若缓存命中，则 $s^c_{t+1} = s^c_t$ ，因为访问的数据已经在缓存中；
  - 若缓存未命中，动作 $a_t = w$ 表示驱逐第 w 个缓存行，新的缓存状态为：
    - $s^c_{t+1} = \{l_1, \dots, l_{w-1}, m_t, l_{w+1}, \dots, l_W\}$
奖励函数 $R(s_t)$ 定义如下：
- 如果缓存未命中（即 mt∉st），则 R(st)=0；
- 如果缓存命中，则 R(st)=1。
目标是学习一个策略 $\pi_\theta(a_t \mid s_t)$ 。对于一个长度为 T 的缓存访问序列 $(m_1, pc_1), \dots, (m_T, pc_T)$ ，最大化整个访问序列的累计命中次数，即 $\sum_{t=0}^{T} R(s_t)$
在训练阶段，可以利用未来访问信息是已知的这一事实，计算出最优策略（即 Belady 策略）：
- π∗(at∣st,(mt+1,pct+1),…,(mT,pcT))
  
  然后，我们学习一个策略 $\pi_\theta(a_t \mid s_t)$ 来逼近这个最优策略，而不依赖未来访问信息，因为在测试阶段未来访问是未知的。
为了展示该问题的难度，在图 2 中展示了：要达到 Belady 策略性能所需的未来信息量
-