在多核系统中，来自多个核心的访问会竞争共享 cache 的容量。对共享 cache 的管理不善会降低系统性能，并导致资源分配不公，因为一个行为不当的应用可能会降低共享该 cache 的所有其他应用的性能。

处理共享 cache 干扰主要有两种方法:

  1. 在各核心之间对 cache 进行分区，以避免干扰并提供公平性保证
  2. 修改替换策略以避免病态行为

Cache Partitioning

cache partitioning 避免了共享 cache 中的性能病态问题，并能提供强大的隔离性和公平性保证

cache partitioning 方案有两个主要考虑因素：

  1. 如何在 cache 中强制执行分区大小？
    1. 最常见机制是为每个应用程序分配专用的 way，使得任何给定的应用程序只能从其分区当前分配的 way 中进行插入和踢出
    2. 更先进的方案: 修改替换策略，以确保在平均情况下遵守分区规则
  2. 如何确定分区大小？

Utility-Based Cache Partitioning(UCP, 2006)

Moinuddin K Qureshi and Yale N Patt. Utility-based cache partitioning: A lowoverhead, high-performance, runtime mechanism to partition shared caches. In 2006 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO’06), pages 423–432. IEEE, 2006.

UCP 的 insight：LRU 在共享 cache 中效果不佳，因为它倾向于将最多的 cache 容量分配给发出最多内存请求的应用程序，而不是从 cache 中获益最多的应用程序

为了解决这个问题，UCP 在 core 之间动态分区 cache ，并提出了一种轻量级的运行时机制来估计每个 core 的分区大小: 将更大的 cache 分区分配给更有可能因额外 cache 空间而看到 hit rate 提升的应用程序

为了找到每个竞争应用的 hit rate 曲线，UCP利用了 LRU 策略的栈特性：如果一个访问在 n-way LRU 管理 cache 中 hit ，那么当 cache way 数多于 n 时（假设 set 数保持不变），该访问也保证会 hit。

UCP 部署了采样的辅助标签目录，称为Utility Monitors / UMONs: 监控每个应用的重用行为，假设该应用独占整个 cache

  • 对于每个应用，它会统计在每个 MRU 位置上的 cache hit 次数
  • 每个 MRU 位置上的 hit 次数决定了给予该应用额外一个 way 的边际效用

UCP 的分区算法使用 UMONs 收集的信息来确定分配给每个 core 的 way 数，并利用 way 分区来强制执行

ASM-Cache (2015)

Lavanya Subramanian, Vivek Seshadri, Arnab Ghosh, Samira Khan, and Onur Mutlu. The application slowdown model: Quantifying and controlling the impact of interapplication interference at shared caches and main memory. In Proceedings of the 48th International Symposium on Microarchitecture, pages 62–75. ACM, 2015.

hit rate 并不直接对应于性能提升，ASM‑Cache 对共享 cache 进行分区，其目标是最小化应用程序的减速

其核心思想是: 将更多的 cache way 分配给那些因获得额外 cache 空间而减速减少最多的应用程序。

应用程序的减速被定义为: 其与其他应用程序一起运行时的执行时间（共享执行时间）与其在相同系统上单独运行时的执行时间（单独执行时间）之比

  • 共享执行时间可以通过对当前执行进行采样来测量
  • 单独执行时间测量比较困难

为估算应用程序的独立运行时间，ASM‑Cache 利用了这样一个洞察：内存密集型应用的性能与其共享 cache 访问被服务的速率高度相关。

ASM‑Cache 通过以下方式估算共享 cache 服务速率：

  1. 最小化主内存处的干扰，以估算无干扰情况下的平均 miss 服务时间：通过临时赋予应用程序在内存控制器中的高优先级来实现
  2. 测量无干扰情况下的共享 cache miss 次数：通过使用仅服务单一应用程序的采样辅助标签来实现。采样标签中的 miss 计数将与平均 miss 服务时间一起，用于估算如果该应用程序独立运行，其处理请求所需的时间。
    利用此方案，ASM‑Cache 能够估算每个应用程序在不同 cache way 数下的性能下降。

Shared-Cache-Aware Cache Replacement

  • 粗粒度策略（如 LRU ）容易受到颠簸影响，在共享 cache 环境下表现不佳
  • 细粒度策略往往无需重大改动就能很好地适应共享 cache。(可以归因于它们能够区分小部分 cacheline 的访问模式，使得它们能自然地分辨不同应用程序的行为)

Thread-Aware DIP (2008)

Aamer Jaleel, William Hasenplaugh, Moinuddin Qureshi, Julien Sebot, Simon Steely, Jr., and Joel Emer. Adaptive insertion policies for managing shared caches. In 17th International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 208–219, 2008.

DIP 使用 set dueling 在 recency-friendly LRU 和 thrash-resistant BIP 之间进行调节。然而，DIP 在共享 cache 中仍有改进空间，因为它没有区分各个应用程序的缓存行为
如果 DIP 选择了 LRU，所有共享 cachr 的应用程序都将使用 LRU 策略，这在某些应用程序能从 cache 中受益而另一些不能的情况下，是不理想的

Thread-Awared DIP 旨在为共享 cache 提供良好性能，其核心思想是为每个应用程序单独做出选择。

困难之处：对于 n 个共享 cache 的应用程序，对所有 $2^n$ 个组合的行为进行采样成本过高

Thread-Awared 提出了两种方法

  1. TADIP‑Isolated (TADIP‑I): 独立地学习每个应用程序的插入策略，并假设所有其他应用程序都使用 LRU 策略
  2. TADIP‑Feedback (TADIP‑F): 通过为每个应用程序学习插入策略来考虑应用程序间的交互，并假设所有其他应用程序都使用当前对该应用程序表现最佳的插入策略

Promotion/Insertion Pseudo-Partitioning Of Multi-Core Shared Caches (PIPP, 2009)

Yuejian Xie and Gabriel H Loh. Pipp: promotion/insertion pseudo-partitioning of multi-core shared caches. In Proceedings of the 36th Annual IEEE/ACM International Symposium on Computer Architecture, pages 174–183. ACM, 2009.

PIPP 基于 Utility-Based Cache Partitioning ,但他们并未严格强制执行 UCP 分区，而是设计了插入与提升策略来松散地执行分区

PIPP 的主要 insight: 严格的分区会导致 cache 资源利用不足，因为一个 core 可能不会使用其全部分配的份额。

  • 如果 cache 是按 way 划分的，并且如果 $core_i$ 不访问某个特定 set，那么在该 set 中分配给 $core_i$ 的 way 就会被浪费
  • PIPP 允许其他应用程序窃取这些未使用的way
  • PIPP 会根据其分区分配情况为每一个 cacheline 数据插入一个优先级
  • 来自分配大分区的 core 的 cacheline 会以高优先级（与分区大小成比例）插入
  • 来自分配小分区的 core 的 cacheline 则以低优先级插入
  • 在发生 cache hit 时，PIPP 的晋升策略会以 $p_{prom}$ 的概率将该 cacheline 提升一个优先级位置，并以 $1−p_{prom}$ 的概率保持其优先级不变
  • 在踢出时，优先级最低的 cacheline 将被踢出

RADAR (2016)

Madhavan Manivannan, Vassilis Papaefstathiou, Miquel Pericas, and Per Stenstrom. Radar: Runtime-assisted dead region management for last-level caches. In 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 644–656. IEEE, 2016.

RADAR 策略结合了静态和动态程序信息来预测并行程序中的 dead block

RADAR 建立在任务流编程模型（如 OpenMP）之上，其中程序员的 hint 明确指定

  1. 任务间的依赖关系
  2. 每个任务将要访问的地址区域
  • 运行时系统利用这些信息，并结合动态程序行为来预测可能成为 dead regions 的区域
  • 属于 dead regions 的 cacheline 会被降级，并优先从 cache 中踢出

RADAR 有三种变体，它们以不同的方式结合了来自编程模型和架构的信息:

  1. Look-ahead scheme: 利用任务数据流图来窥视即将执行的任务窗口，并利用此信息来识别未来可能被访问的区域以及可能的 dead regions
  2. Look-back scheme: 跟踪每区域访问历史，以预测下一次区域访问可能何时发生
  3. Combined scheme: 利用对未来区域访问和过去区域访问的了解，以做出更准确的预测