TL;DR:利用轻量级协程来优化访存引起的停顿

1 Introduction

针对高访存延迟引起的停顿
SMT是不满足的，首先，众所周知，SMT 可能会导致延迟显着增加，因为它只专注于复用指令流以最好地利用核心资源，此外，SMT 不允许对主延迟和辅助任务的吞吐量之间的权衡进行细粒度控制，而这是在延迟服务水平目标下最大化 CPU 利用率所必需的。
SMT最多支持两个线程也是不够的

轻量级的协程：允许主协程和辅助协程交错，其切换开销比传统执行线程（进程和内核线程）小得多
基于采样的分析：可以通过分析减少缓存未命中率

面临的困难

  1. 为了提高任务切换的效率（或者说资源的有效利用），我们需要减少每次“yield”操作中寄存器状态的保存和恢复开销，并且保证程序的正确性
  2. 为了引入最小的延迟开销，辅助程序需要在消耗足够的停顿周期后立即让出核心
  3. 为了充分利用停顿周期，我们需要检测何时需要更高程度的并发，并正确交错多个辅助程序的执行
  4. 将辅助程序执行与具有内部线程结构的主二进制文件透明地交错是一项挑战。

提出Memory Stall Software Harvester (MSH)
要使用 MSH，用户只需提供未修改的主二进制文件和一个清理程序线程池，MSH 会负责运行清理程序线程以及主二进制文件的停顿周期。

主要贡献

  1. 一种透明且高效的方法来获取软件中受内存限制的 CPU 停顿周期
  2. 基于此方法的系统 (MSH) 的详细设计和实现，其中涉及分析、程序分析、二进制检测和运行时调度的协同设计；
  3. 实际应用的评估

2 Background and Motivation

SMT的缺陷：延迟高、配置不灵活、只能2线程

基于样本的分析：通过在现代 CPU 中使用硬件性能计数器，例如英特尔的 PEBS [3] 和 LBR [47]，人们可以分析二进制文件，无需特殊构建，运行时间开销可以忽略不计。由于这些优点，基于样本的分析已广泛应用于生产中的分析引导优化 (PGO)

轻量级协程：协程的上下文切换比传统的执行线程便宜几个数量级。这是因为作为单个进程内的用户空间机制，协程上下文切换不需要系统调用，也不需要更改虚拟内存映射。

3 MSH Overview

  • Binary instrumentation:MSH 对主要任务（primaries）和辅助任务（scavengers）进行监控和管理，使其能够有效地利用处理器中的停滞周期（stall cycles）。通过在 二进制级别 操作，MSH 可以访问详细的低级信息，比如寄存器使用和基本块的控制流。
  • Profiling：通过基于样本的分析，MSH 可以决定收获停滞周期的位置，
  • Program analysis：通过减少寄存器保存和恢复操作的开销，MSH 提高了任务切换的效率；MSH 通过将接近的 yield 操作协调到另一个 scavenger，以确保 CPU 中的空闲周期得到充分利用。；MSH 控制相邻 yield 操作之间的延迟，确保任务调度中的延迟在可接受范围内，以满足实时性要求。
  • Runtime scheduling：在主节点的内部线程结构之上安排清理程序执行。它使 MSH 能够利用可用的清除程序充分收获停顿周期，方法是将多个清除程序分配给主线程以扩大并发性，并将清除程序从阻塞的主线程迁移到活动的主线程

MSH 如何通过以下步骤来优化程序的资源利用：

  1. 分析：首先，MSH 对程序的二进制文件进行分析，收集有关缓存未命中、基本块延迟、执行次数和分支概率的信息。
  2. 深入分析：在收集到数据后，MSH 进行详细的分析，以确定每个 yield 操作的最佳位置和最小寄存器保存恢复操作量，并为辅助任务决定额外的 yield 位置，以控制延迟。
  3. 过程内分析：大多数分析工作是在单个过程内部完成的，这使得分析的复杂度随着程序大小的增加而以次线性方式增长。
  4. 仪器化：基于分析结果，MSH 将相应的代码插入到程序的二进制文件中，从而实现资源的优化利用和性能的提升。

主任务：在主任务的代码中，插入 yield 操作以在加载指令之前让出 CPU 控制权，并预取缓存行，以减少因缓存未命中导致的延迟。特别地，当主任务中的 yield 操作非常接近时，这些操作会转移到其他辅助任务上，从而增加并发性。

辅助任务：在辅助任务的代码中，同样插入 yield 操作，确保辅助任务能够及时释放 CPU 核心。此外，辅助任务也有专门的 scavenger yields，以便在适当的时候将 CPU 资源让给其他任务。

MSH 通过动态调度和资源管理来优化程序的性能：

  • 动态调度：MSH 在运行时根据主任务线程的实际状态动态分配辅助任务，而不是依赖静态的预设配对。这种方法可以更灵活地应对线程的状态变化和任务调度需求。
  • 线程处理：对于新创建的线程，MSH 可以从阻塞线程中窃取辅助任务或从辅助任务池中获取新的任务。当线程恢复时，它会优先重用之前的辅助任务。
  • 提高并发度：MSH 允许将多个辅助任务分配给一个主任务线程，从而提高系统的并发处理能力。
  • 高效运行：MSH 的运行时系统在执行这些操作时非常高效，确保了优化和资源利用的效果。有关运行时设计的详细内容将在文献的指定章节中介绍。

4 Design

MSH 通过 性能分析 和 两步选择逻辑 来优化 yield 操作的插入：

  1. 选择标准：MSH 关注那些内存瓶颈显著且可能会导致高 L3 缓存未命中的加载指令。
  2. 性能分析：收集加载指令的缓存未命中情况和基本块的执行次数，并基于这些数据进行分析。
  3. 两步选择：
    • 首先，根据加载指令的缓存未命中率和执行频率进行排序。
    • 其次，估算每个加载指令的延迟开销，选择总延迟开销低于界限的指令进行 yield 操作。
  4. 配置参数：通过调整缓存未命中阈值和延迟开销界限来优化主任务延迟和辅助任务吞吐量之间的平衡。

在选定的加载指令位置，MSH 插入预取指令，以减少因缓存未命中引起的延迟。

  • 插入预取指令：在选定的加载指令位置，MSH 插入预取指令，以减少因缓存未命中引起的延迟。
  • Yield 操作：
    • 寄存器保存/恢复：优化 yield 操作中的寄存器保存和恢复，以减少开销，同时确保程序的正确性。
    • 控制权转移：在主任务和辅助任务之间进行指令指针和堆栈指针的交换，实现 CPU 资源的有效利用。
  • 跳过 Yield 的标志：插入的代码会检查一个标志，允许在需要时跳过 yield 操作，从而避免额外的延迟开销。这使得 MSH 在不需要进行 stall cycle harvesting 的情况下，可以提高系统的运行效率。

关于优化yield的保存与恢复：主要关注循环
image.png

MSH 如何在主任务和辅助任务中插入和优化 yield 操作：

  1. **主任务 yield**：

    • 默认情况下，yield 操作将 CPU 资源返回给主任务。
    • 在特殊情况下（例如紧密的循环），yield 操作会分配给下一个辅助任务，以提高资源利用率。

  2. **辅助任务 yield**：

    • 使用数据流分析来控制 yield 操作的间隔，确保辅助任务在合理时间内释放 CPU 资源。
    • 分析包括状态定义、转换函数和合并操作，用于计算和优化 yield 操作的插入位置，确保在保持正确性的前提下，限制延迟开销。

9 Conclusion

我们推出了 MSH，这是一个可以透明且高效地收集内存停顿周期的软件系统。通过分析、程序分析、二进制检测和运行时调度的协同设计，MSH 完全收获了停顿周期，同时将延迟开销降至最低，并提供延迟吞吐量权衡的细粒度控制。因此，MSH 是收集内存停顿的最佳解决方案，并为 CPU 周期收集环境带来了宝贵的变化。