技术杂谈：对于SMT的Hill-Climbing算法与Off-Line Exhaustive Learning的简单记录

发表于 分类于 阅读次数：

Off-Line Exhaustive Learning

如果我们能在每个 epoch 都“试遍所有资源划分方案”，并且总能选到表现最好的那个，那么 SMT 资源分配最多能好到什么程度？

方法核心

论文把 SMT 的执行划分成一连串固定长度的 epoch。在每个 epoch 里，资源分配机制会给同时运行的线程分配共享硬件资源的份额；线程只能使用自己分到的那部分资源，因此这是按 epoch 进行的资源分区。

  • Offline Exhaustive Learning：直接利用当前这个 epoch 的性能反馈来选当前 epoch 最优方案。

具体步骤

对每个 epoch，它会这样做：

  1. 在 epoch 开始时保存机器状态（checkpoint）。论文实现里会保存寄存器文件、流水线寄存器、分支预测器、cache、主存等状态。

  2. 把所有可能的资源划分方案都跑一遍。也就是从同一个 checkpoint 出发，对当前 epoch 逐个尝试不同 partition。

  3. 测量每种划分的性能，然后选出性能最高的那一种。论文这里用的是 average weighted IPC 作为选优指标。

  4. 只把最佳试验对应的执行时间计入真实运行时间，其他所有“试错”的开销全部忽略；然后进入下一个 epoch，重复这个过程。

所以它其实不是一个现实可部署的硬件算法，而是一个“带上帝视角的理想最优近似”，专门用来评估学习型资源分配的潜力。论文也明确说了，这种离线学习在真实机器上并不实际。

它分配的是什么资源

论文并不是对所有共享资源独立穷举，因为那样搜索空间太大。它做了两个简化：

  • 重点分配 整数 IQ、整数重命名寄存器、ROB 这几个关键共享结构；

  • 假设一个线程在这些资源上的占用是成比例相关的，所以只显式划分一种资源，再按比例映射到其他资源上。

这样搜索空间才降下来。即便如此，穷举依然非常贵，所以论文的离线穷举实验只研究了 2 hardware contexts 的 SMT。

参数设置

这部分实验里：

  • epoch 大小用的是 64K cycles；

  • 实际穷举的是 256 个整数重命名寄存器在 2 个线程之间的划分；

  • 为了省仿真时间，只尝试“每隔一个”的划分方案，所以每个 epoch 一共跑 127 次试验。

这个方法的意义

它的作用不是“可实现”，而是作为性能上限基准：

  • 理想离线学习相对 ICOUNT 平均提升 19.2%

  • 相对 FLUSH 提升 18.0%

  • 相对 DCRA 提升 7.6%

这说明：如果能学到每个 epoch 的最佳资源划分，SMT 资源分配确实还有明显优化空间。

一句话总结

Offline Exhaustive Learning = 把执行按 epoch 切开，在每个 epoch 开头从同一检查点出发穷举所有资源划分，测完性能后选当前 epoch 最优方案执行，并且忽略穷举试错成本，用它来估计学习型 SMT 资源分配的理论上限。

Hill-Climbing Algorithm

它是论文提出的一个在线学习资源划分方法。核心思想是：

不像 Offline Exhaustive Learning 那样每个 epoch 把所有划分都试完，
Hill-climbing 只在“当前最好划分”附近做少量试探，然后沿着性能上升最快的方向继续走，逐步逼近最优划分。类似于梯度下降法。

有一个核心假设：各种资源之间的分配是成比例的 ## 它维护的核心量

1. anchor_partition

当前认为最好的资源划分。
可以理解成“当前爬山所在的位置”。

一开始，anchor_partition 默认是均分。

2. trial_partition

本轮为了试探坡度而临时采用的划分。
就是在 anchor_partition 附近，分别偏向某一个线程一点点，看性能变好还是变差。

3. Delta

每次试探时移动的步长。
论文里取 Delta = 4，这里指的是整数重命名寄存器移动 4 个；IQ 和 ROB 按比例一起调整。

它怎么运行

论文把算法分成两个部分：

  • sampling sequence / round：采样阶段

  • partition selection：选方向、更新 anchor 的阶段

第一步：按 epoch 收集性能

系统还是按固定 epoch 运行，epoch 大小是 64K cycles。

每个 epoch 结束时，记录这一个 epoch 在当前 trial_partition 下的性能。这个性能就是学习反馈。

第二步：一轮 round 内，依次试探每个方向

假设有 N 个线程。

从当前 anchor_partition 出发，算法不会试所有可能划分，而是只试 N 个相邻方向：

  • 第 1 个 epoch：多给线程 0 一点资源，其他线程各减一点

  • 第 2 个 epoch：多给线程 1 一点资源，其他线程各减一点

  • …

  • 第 N 个 epoch：多给线程 N-1 一点资源，其他线程各减一点

也就是说：

一轮 round = 连续用 N 个 epoch，分别测试“如果把资源稍微偏向某一个线程，性能会怎样”。

论文伪代码里写得很清楚：
每个 sample 都是“让一个线程从其他 T-1 个线程那里各拿走 Delta 的资源”。因此被偏向的线程一共增加 Delta*(N-1)，其他每个线程减少 Delta。

第三步：一轮结束后，选最好方向

当这 N 个方向都试完后，算法比较这 N 次 sample 的性能：

  • 哪个 sample 性能最高

  • 就说明“把资源往哪个线程偏一点”是当前的正梯度方向

然后把 anchor_partition 朝这个方向移动一步。

也就是：

  • 若偏向线程 k 的那个 sample 最好

  • 下一轮的 anchor_partition 就更新为：

    • 线程 k 多拿一点

    • 其他线程各少一点

这一步就是“沿着坡往上爬”。

第四步：继续下一轮

更新完 anchor_partition 后，再围绕新的 anchor 继续试：

  • 再做一轮 N 个 epoch 的局部采样

  • 再选最好方向

  • 再移动一步

如此反复，直到逼近性能峰值。

它的优点

1. 采样少

不需要像离线穷举那样试遍所有资源划分，只需要每轮试 N 个方向，所以学习时间低很多。

2. 直接优化性能指标

学习反馈可以选 weighted IPC、average IPC、harmonic mean of weighted IPC。
论文指出：用什么指标学习，就最擅长优化什么指标。

3. 很接近理想上界

论文里，2-thread 情况下 hill-climbing 达到了 OFF-LINE 理想性能的 96.6%。

它的缺点

1. 有学习时间

它不是一开始就知道最优点，所以学习过程中会用到一些非最优划分，损失部分性能。

2. 可能卡在局部最优

如果性能曲线有多个峰，hill-climbing 可能爬到一个次优峰后停住。

3. 会受 inter-epoch jitter 干扰

论文特别提到，跨 epoch 的抖动会制造“假的梯度方向”，让 hill-climber 有时走错方向。

论文中的机制分两步

1️⃣ 先判断线程是否被获取门控（fetch-lock）

系统会检查每个线程在 IQ、IRF、ROB 中的占用：

  • 如果某线程 超过其 partition limit

  • 就对该线程 fetch-lock（获取门控）

  • 该线程在这一周期 不能再取指

这一步是 资源分区机制控制的。

2️⃣ 在“没有被门控的线程”之间决定谁先取指

如果有多个线程 仍然允许 fetch，就需要一个 fetch policy 决定优先级。

论文这里直接沿用 ICOUNT：

在未被 fetch-lock 的线程中，使用 ICOUNT fetch policy 决定取指优先级。

ICOUNT 的规则是：

  • 比较各线程 in-flight instruction 数量

  • 谁在流水线里的指令更少，就优先 fetch 谁

因此完整流程是

每个 cycle：

  1. 检查每个线程是否超过
    IQ / IRF / ROB partition limit

  2. 如果超过 → fetch-lock

  3. 在剩余 未被门控的线程 中

  4. 用 ICOUNT 决定 fetch 顺序

总结

Hill-climbing algorithm 是一种基于 epoch 的在线 SMT 资源划分学习方法。它维护当前最优划分 anchor_partition，并在每一轮中围绕该划分对每个线程分别做一次小幅资源倾斜试探，收集这 N 个相邻方向的性能反馈。轮结束后，选择性能提升最大的方向作为正梯度方向，并将 anchor_partition 朝该方向移动一步。通过反复执行“局部采样—梯度判断—更新划分”，算法逐步逼近 epoch 资源划分空间中的性能峰值。相比离线穷举，它采样更少、开销更低，但可能受学习时间、局部最优和 epoch 间抖动影响。