criticality 是一种比 MLP 更通用的成本函数

Srinivasan 等人的定义：

  • critical load: 任何需要尽早完成以防止处理器停顿的 load
  • non-critical load: 可以容忍较长延迟的 load

criticality 驱动的 cache 优化会优先处理 critical load 而非 non-critical load

研究确定，load criticality 可以根据依赖于该 load 的指令链的特征来确定

如果一次 load 满足以下任一标准，则被归类为 critical load：

  1. 该 load 为一次误预测分支提供数据
  2. 该 load 为另一次引发 L1 Cache miss 的 load 提供数据
  3. 在该 load 之后的一个 N 周期窗口内发出的独立指令数量低于某个阈值

这种 criticality 的定义同时考虑了依赖指令的类型以及其依赖链中的指令数量

Srinivasan 等人通过实验说明优化 critical load 的重要性:

  • 如果所有 critical load 都能由 L1 Cache 满足，其结果将比传统内存层次结构平均提升 40%
  • 如果随机选择同等比例的 load 在 L1 Cache 中 hit，平均提升则仅为 12%

通过以增加 non-critical load 的延迟为代价来降低这些 critical load 的延迟，有可能提升整体性能

Critical Cache(1998)

  • Srikanth T Srinivasan and Alvin R Lebeck. Load latency tolerance in dynamically scheduled processors. In Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, pages 148–159. IEEE Computer Society Press, 1998.
  • Srikanth T Srinivasan, R Dz-Ching Ju, Alvin R Lebeck, and Chris Wilkerson. Locality vs. criticality. In Computer Architecture, 2001. Proceedings. 28th Annual International Symposium on, pages 132–143. IEEE, 2001.

为了优化 critical load ，Srinivasan 等人使用了一个 Critical Cache 作为被 critical load 访问过的 cacheline 的 victim cache

结果发现，critical cache 相比普通的 victim cache 并未带来任何收益(反而更差)，原因是：

  1. critical load 的工作集非常大，导致 critical cache 无法显著降低 critical load 的miss rate；
  2. 由于 non-critical load 与 critical load 之间存在空间局部性，普通的 victim cache 能够提供与 critical cache 相当的 critical load miss rate；
  3. critical cache 因其整体更高的 miss rate 削弱了其优势

Srinivasan 等人总结认为，构建违反 locality 以利用 criticality 的内存层次结构非常困难，因为 non-critical load miss rate 的增加与 critical load miss rate 的降低之间存在权衡。所以基于 criticality 的技术可以用来补充 locality，而非取代 locality

Criticality-Aware Multi-Level Cache Hierarchy(CATCH, 2018)

  • Brian Fields, Shai Rubin, and Rastislav Bodík. Focusing processor policies via critical-path prediction. In Proceedings of the 28th Annual International Symposium on Computer Architecture, ISCA ’01, pages 74–85. ACM, 2001.
  • Anant Vithal Nori, Jayesh Gaur, Siddharth Rai, Sreenivas Subramoney, and Hong Wang. Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies. In 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA), pages 96–109. IEEE, 2018.

CATCH 能在硬件中准确检测程序的 criticality，并利用一组新颖的 cache 间预取器来确保 critical load 以 L1 Cache 的延迟得到服务

CATCH 采用了一种基于程序数据依赖图（DDG）的 criticality 定义(该定义最初由 Fields 等人在 2001 年提出)，其核心思想是分析程序的 DDG 以找到关键路径，即具有最大加权长度的路径，其中的权重基于操作延迟。位于关键路径上的所有 load 指令都被视为关键指令

CATCH 利用硬件中数据依赖图的优化表示来学习关键路径，该方法仅占用 3 KB 的面积。此方法用于枚举一小部分 critical load 指令（关键PC）。

critical load 在 Timeliness Aware and Criticality Triggered（TACT）预取器的帮助下，从 L2 Cache 或 LLC 预取到 L1 Cache 中。TACT 利用目标 critical load 附近 load 指令的地址或数据之间的关联性来触发向 L1 Cache 的预取。TACT预取器的意义在于，LLC 中的 critical load 可以以 L1 Cache 的延迟提供服务