摘要

尽管大型多级缓存的昂贵配置和内存预取的进步，内存墙仍然限制着现代乱序处理器的性能。目前的乱序超标量处理器大部分时间都在访存相关的停顿上，这包括了多处理器原子操作的停顿、寄存器与多级缓存速度不匹配的停顿和数据相关的停顿。本文分析了三篇近年的 ISCA 论文对内存墙的思考和改进。

自由原子操作

论文：Free Atomics: Hardware Atomic Operations without Fences
期刊：ISCA 2022

简介

大多数指令集架构（如 x86、ARMv8、RISC-V）提供了同步原语 Read-Modify-Write（RMW）指令，以用于实现互斥锁、屏障等多线程/进程通信的必要工具。

这些 RMW 指令将序列化所有未完成（即等待 commit）的 Load 和 Store 操作，这意味着存储缓冲区在原子 RMW 发出之前将被排空，且后续的内存操作都不能执行，直到原子 RMW 写入和释放缓存块锁。这种序列化很容易通过用内存屏障将原子 RMW 指令隔离的方式实现，代价是性能降低。

下表量化了这些损失，将耗时分为排空存储缓存和等待原子 RMW commit 的时钟周期。大多数的耗时发生在排空存储缓存，在大多数情况下超过了 100 个时钟周期；在一些应用场景下，甚至能够超过 700 个时钟周期。观察结果证明了原子 RMW 的延迟会随着 ROB 大小的增加而增加。尽管很重要，但很少有人致力于优化原子 RMW 的性能，这篇论文提供了一种思路以优化原子 RMW 的性能问题。

这项工作的重点是 x86-TSO 内存模型。事实上，在较弱的内存模型（如 ARMv8 模型）中，应用于原子 RMW 的屏障实际上需要一个更强的顺序保证，因此删除内存屏障将是一个更复杂的过程。文章的主要贡献有以下几点：

• 一种通过集体持有多个高速缓存行锁以有效压缩原子 RMW 指令的机制。
• 对乱序执行内存操作（包括原子 RMW）时可能出现的活锁和死锁情况进行了详细的阐述，并提供恢复这种死锁的简单解决方案。
• 启用从/到原子 RMW 的写后读定向的同时保证操作的原子性和一致性。这允许了 Free atomics 在彼此之后执行而不放弃目标缓存行的权限，通过增加锁的局部性来提高性能。

背景

在 ISA 层面，在设计原子内存操作时有两个主要的选择，它们与系统执行的内存一致性无关：原子 RMW 指令和 LL/SC（链接加载、条件存储）指令。原子 RMW 指令是单条指令，为原子操作提供直接支持，如 fetch-and-increment、test-and-set、compare-and-swap；LL/SC 是一对指令，可以在软件中实现相同的原子操作。关键的区别在于，由于 LL/SC 是不同的指令，原语（通常指 LL-op-SC）是可中断的，而原子 RMW 指令不是。此外，一个 LL/SC 指令对会因为相关的外部事件而失败，如一致性失效和缓存换出。因此，LL/SC 指令对通常包含在一个自旋循环中，当存储条件成功时退出。相反，从程序员的角度来看，原子 RMW 总是成功的。这给原子 RMW 指令带来了优势：它简化了代码，但更重要的是，避免了 LL/SC 对在成功或者失败之前被打断的情况，因此不需要在软件层面进行任何清理。

原子 RMW 指令被 x86、ARMv8 和 RISC-V 等架构所支持。实现原子 RMW 指令的一种方式是将其与其他内存操作隔离执行，即在执行原子 RMW 前所有 Load 指令必须被 commit，所有 Store 指令必须从存储缓存中排空。此外，一旦获得了相应的缓存行的读写许可，就会触发缓存锁定机制，以保证原子性。在这种情况下，锁定缓存意味着防止任何外部请求对缓存行进行换出或修改。

下图描述了根据 x86 架构规范的 fetch-and-increment 原子 RMW 指令的执行情况，该指令被解码为 5 个微指令：

1. Mem_Fence1：这个内存屏障保证了在所有先前的内存操作 commit 并退出存储缓存前，原子 RMW 不会发射。这带来了很高的性能成本，此外，这个屏障也保证了原子 RMW 不被打断（如由于之前的内存指令造成的错误预测）。最后，它还可以防止在清空存储缓存之前就获得缓存行锁时可能出现的死锁情况。
2. Load_Lock：这个微指令是一个普通的 Load 操作，用于设置一些内存标志以表明其责任和特定功能。首先，它不能被前瞻执行，这就保证了 Load_Lock 不能被打断。其次，它获得了目标缓存行的一致性许可（不仅仅是读取许可），因为它后面总是有一个存储操作。最后，它锁定了缓存行，防止本地和外部请求访问缓存行。
3. Add：这是一个算逻微指令，由于数据相关，它不能在 Load_Lock 访存之前发射。
4. Store_Unlock：当它执行时（commit 之后），这个微指令将数据写入目标缓存行，将其解锁并退出存储缓存。这使得缓存行能够再次接收其他内部和外部的内存请求。
5. Mem_Fence2：这个内存屏障防止在原子 RMW commit 之前发射更多的 Load 指令。后续 Load 指令的等待时间带来了性能损失。

实现

Free atomics 的目的是通过移除原子 RMW 周围的屏障并允许它们部分乱序执行，来提高原子 RMW 的性能。Free atomics 具有三种特色：允许乱序前瞻执行、移除围绕原子 RMW 的屏障、启用从/到原子 RMW 的写后读定向。Free atomics 实现了最严格的第一类原子操作，即等价于有屏障的原子 RMW。

由于篇幅原因，这里仅详细介绍如何实现乱序前瞻。

允许乱序前瞻执行

由于内存屏障只在内存操作之间加强顺序，原子 RMW 指令（特别是 Load_Lock 微指令）事实上可以在成为流水线最后一条指令前发射，因此可能会乱序执行。然而，这么做意味着原子 RMW 指令可能会被错误的分支预测和异常中断。

当一条指令被中断时，被中断的指令所执行的微架构状态更新必须被取消，在这方面，由原子 RMW 指令组成的微指令与其他微指令类似。除了高速缓存的锁定机制，其他微指令都会直接中断。随着原子 RMW 指令的前瞻执行，有可能 Load_Lock 在被中断之前就已经（前瞻地）锁定了目标缓存行。在这个时候，Store_Unlock 不可能已经执行。因此，必须提供一种机制在原子 RMW 指令被中断的情况下解锁缓存行，否则，缓存行将永远被锁定，无法被其他的内存请求访问，系统最终会陷入死锁。为了解决这个问题，每个成功锁定其目标缓存行的 Load_Lock 都拥有在被中断时解锁的责任。当 Load_Lock 被中断时，它通过执行与 Store_Unlock 相同的动作来解锁缓存行。下图显示了一个对地址 A 的原子 RMW 的中断。当发现一个较早的条件分支 CondBr 被错误预测时，有义务解锁目标缓存行的 Load_Lock(LdL) 被中断。然后，锁被解除，所有后续的微操作，包括 Store_Unlock(StU) 都被取消。

在有内存屏障的控制前瞻路径中乱序发射原子操作并不能显著提高性能。这是因为分支如果不依赖于 Load，或者它们所依赖的 Load 已经获得了数据，它们往往能快速得到完成。因此，以前瞻方式发射一个有屏障的原子 RMW 并没有带来什么性能优势，然而，以乱序前瞻方式发射原子 RMW 的能力为下一个优化铺平了道路：移除屏障。

解除屏障

围绕原子 RMW 的屏障并不是为了执行 x86-TSO 一致性，因为 Load_Lock 和 Store_Lock 是以原子方式执行的，这意味着 Load_Lock 不能在之前的 Store 之前执行。这些屏障反而使得内存操作的前瞻重排机制失效，例如前瞻 Load→Load 的重排序。文章展示了这种屏障可以被完全移除，并解决了相关的挑战：防止活锁和死锁。

启用写后读定向

现代处理器的乱序执行实现了写后读定向，使得 Load 操作可以从最早的 Store 中获得相同地址的数据。这是一种在前一个 Store 还没有写入缓存时保障顺序语义的方法，只要 Store 的数据可用，就不会使 Load 停滞。由于屏障式原子 RMW 是孤立执行的，所以转发是不可能的。然而，Free atomics 在存在尚未执行的 Store 情况下执行 Load_Lock，开启了定向的可能。为了得到最大的性能，Free atomics 允许这种定向，从而有利于特定的软件习惯。

成果

通过对原子 RMW 的解锁，Free atomics 打破了在发射原子 RMW 前排空存储缓存的停滞，同时允许多个原子 RMW 同时锁定告诉缓存行，并实现对锁定行的本地访问。这带来了很大的性能提升。考虑所有应用平均时间减少了 12.5%，而原子操作密集型应用平均时间减少了 25.2%。

寄存器文件预取

论文：Register File Prefetching
期刊：ISCA 2022

简介

现代的乱序处理器受限于 Load 指令的延迟，这种现象形象地成为内存墙。因此多级缓存的结构已经变得无处不在，每一代新处理器都会投资于比以前更大、更昂贵的缓存。而内存墙不仅仅是最后一级高速缓存（LLC）和 DRAM 之间的单体墙，而是包括寄存器文件、片上缓存和主存之间的多个延迟墙。

因此，克服内存墙不仅需要在 DRAM 和 LLC 之间预取，还需要在不同层次的高速缓存和寄存器文件之间进行预取。这篇论文把注意力集中在 L1 高速缓存和寄存器文件之间的预取上。文章的主要贡献有以下几点：

• 尽管 L1 数据缓存的延迟明显小于主存的延迟，但它对现代乱序处理器的性能有非常大的影响，这是与以前主要关注主存和高速缓存延迟的预取工作不同的新见解。
• 提出了寄存器文件预取（RFP），将 Load 数据从 L1 数据缓存预取到寄存器文件，并减少了 L1 数据缓存的关键性延迟。文章展示了 RFP 如何智能地使用现有的乱序调度逻辑，并且不需要额外的带宽/功率开销或昂贵的流水线修改。
• 展示了 RFP 相对之前技术（如加载地址预测技术）的优越性，以及为什么这些先前的技术由于受限的 L1 带宽陷入瓶颈。显示了 RFP 的独特设计是如何使其对这些限制具有鲁棒性，并以较低的功率实现更高的性能。

由于篇幅原因，接下来将只介绍 RFP 的背景和基本概念。

背景

值预测（Value Prediction）

值预测（VP）通过预测打破真数据相关，以释放更高的指令级并行性（ILP）。然而，它提供了有限的覆盖范围，因为需要很高的精度来避免预测错误的排空。相比之下 RFP 不需要排空，因此允许低置信度的预测。然而，与 VP 不同，RFP 受到 L1 带宽和流水线延迟的限制。当它们结合起来时，可以提供更高的性能。

加载地址预测（Load Address Prediction）

与VP相关的一个想法是加载地址预测（AP），因为地址比数据容易预测。这类方案在取指时预测加载地址，并向 L1 数据高速缓存发起请求。指令在乱序分配的时候，数据从缓存中被读取，并被用作指令的预测值。如果预测的地址是错误的，就需要进行流水线排空。此外，由于大多数现代处理器 L1 有不低的延迟，加之读取端口的数量非常有限，再次限制了从 L1 高速缓存中提前获取的机会。地址预测器也需要额外的带宽来验证数据的正确性，这进一步减少了可用于在早期读取 L1 缓存数据的备用带宽。

内存预取（Memory Prefetching）

内存预取是一种得到广泛研究的技术，通过学习缓存缺失的地址模式来隐藏 DRAM 内存延迟。L1-RF 预取的性能潜力是相当重要的，这在传统上被以前的工作所忽视。

概念

RFP 的目标是通过预取 Load 数据到寄存器文件来隐藏 L1 的延迟。RFP 的预取是使用预先预测的地址进行的，执行时相应的 Load 会检查预测的地址是否与 Load 的地址相匹配。如果是，预取的数据就会提供给依赖者，并且加载过程完全绕过高速缓存。否则，Load 就会像传统的乱序流水线一样进行缓存访问，并向依赖者提供数据。下面将描述如何建立 RFP ——从任何预取器设计所固有的三个重要的设计选择开始——时效性、带宽和准确性。

时效性

为了提高时效性，预取可以在前端取指后立即启动。然而，在有像 uop-cache 这样的取指延迟优化的情况下，从前端调度并不能产生很大的超前执行。此外，RFP 的目标是不增加任何重新检查数据的额外 L1 带宽压力，因此需要跟踪所有在途 Store 指令，这将是非常复杂的。最后，寄存器文件没有标记位（与高速缓存相反），这意味着需要在物理寄存器文件中找到一个位置来存储预取的数据。因此，我们在重命名阶段后执行 RFP 预取，我们可以重新使用分配给 Load 的寄存器文件条目。这也使我们能够重新使用现有的内存消歧逻辑，以确保正确性和数据转发。

实验数据显示，63% 的 Load 在分配时没有准备好操作数，这意味着如果在重命名后启动 RFP 预取，我们有足够的机会来完成 RFP 预取。对于剩下的 37% 的 Load，即使它们的操作数已经准备好了，在分配时，Load 只有在被乱序调度策略选中并通过流水线（下图）到达执行单元后才能执行（至少3个周期），这仍然给了我们一个适度的超前执行窗口，可以在 Load 被调度的时候调度和检索预取请求，并且隐藏了 Load 的一小部分延迟。

带宽

传统的 AP 方案需要两次缓存访问——第一次用于检索预测数据，第二次用于验证，这给稀缺的 L1 带宽带来了巨大压力。为了缓解这个问题，通过 RFP 可以保证如果预取的地址是正确的，寄存器文件中的数据将与缓存和在途 Store 保持一致而不需要经过验证，这意味着 RFP 对 L1 带宽非常节省。由于 RFP 的预取将在重命名后启动，它将执行内存消歧、存储检查等，并确保只要预取地址是正确的，数据就是正确的。

准确性

在 RFP 的情况下，一个错误的预取需要原始的 Load 请求检索到正确的数据。因此，RFP 的错误预测会消耗额外的 L1 带宽，需要最小化。注意到，与传统的 AP 相比，RFP 的错误预取成本较低，因为传统的 AP 在预测错误时需要将全流水线排空。因此，RFP 可以更积极地预取，但为了减少对未预取的 Load 的干扰，RFP 预取应该被赋予较低的 L1 缓存访问优先级。

成果

下图总结了 RFP 对基准处理器不同类别的工作负载所带来的速度提升。它还显示了 RFP 实现的覆盖率，我们将其定义为所有 Load 中预取有用的一部分，并且通过预取正确获得了数据。RFP 比基准线提高了 3.1% 的速度，同时预取了 43.4% 的 Load。

矢量超前执行

论文：Vector Runahead
期刊：ISCA 2021

简介

目前的超标量内核对现代工作负载的服务很差。从数据库到图形处理，许多工作负载的特点是稀疏的间接内存访问。其特点是高延迟的缓存缺失，这是目前的 stride prefecher 所无法预测的。对于这些工作负载，即使是乱序的超标量处理器也会在大部分时间内停滞不前，因为它们充足的重排缓冲区和发射队列资源仍然不足以提供能够隐藏当今 DRAM 延迟所需的内存级并行性。

然而，这种性能差距并不是不可逾越的。超前执行是迄今为止最有前途的技术，在 ROB 头部出现内存滞留时进入 runahead 模式。在 runahead 模式中，未来内存访问的地址被计算出来，内存访问被猜测性地发出。这篇文章提出了 Vector Runahead，这是一种新型的超前执行技术，通过三个关键的创新克服了传统超前执行的限制。

背景

为了缓解内存访问造成的瓶颈，标准的超前执行在一个全窗口停滞后将当前架构状态保存为 checkpoint，并进入 runahead 模式。然后，处理器继续前瞻地产生内存访问，当阻塞的内存访问返回时，runahead 终止，排空流水线，架构状态恢复到进入 runahead 时的状态，并恢复正常执行。在 runahead 模式下产生的预取将未来的数据带入处理器缓存，减少了正常模式下即将发生的停顿次数，从而提高了性能。

精确超前执行（PRE）是超前执行中最先进的技术，通过三个关键机制改进了标准超前执行：

1. PRE 利用可用的后端（发射队列和物理寄存器文件）资源，在 runahead 模式下前瞻地执行指令，从而消除了进入和退出 runahead 模式时释放和刷新进程状态的需要。
2. PRE 只前瞻地预执行需要在全窗口停滞后产生内存访问的指令。
3. PRE包括一个机制，在 runahead 模式下快速回收后端资源。

尽管 PRE 消除了一些由间接内存访问引起的全 ROB 停顿，但它未能预取大多数间接内存访
问。超出超前执行间隔范围的访问很快就会使核心再次停滞，从而导致核心再次进入 runahead 模式。

改进

矢量超前执行克服了 PRE 的基本限制。矢量超前执行改变了 runahead 模式的结束条件，即一旦阻塞性 Load 缺失从主存返回，矢量超前执行不是返回到正常模式，而是继续执行 runahead 模式，直到 Load 依赖链的所有 Load 都被发射。此外，矢量超前执行在 runahead 模式下对动态指令流进行矢量化，这实际上相当于以更快的速度向前运行。以下图为例，当矢量 runahead 模式启动时，对数组 A 的多次访问被矢量化，也就是说，同一内存操作在多个归纳变量偏移处被并行地前瞻发射。依赖于数组 A 值的指令也被矢量化，包括对数组 B 的访问和依赖数据值。在 runahead 模式下对依赖指令流进行矢量化，同时在 runahead 模式下保持到最后一个依赖 Load 被发射，可以前瞻地预取整个依赖链。矢量超前执行指令流的效果是：在发出下一批并行的依赖内存访问之前，同时从循环的多个迭代中发出相同的内存操作。与原始指令流相比，这种有效的内存访问的重排序使矢量超前执行首先发出对 A 的一批访问，然后是对 B 的一批访问，最后是对依赖数值的一批访问。换句话说，即使独立的内存访问在原始动态指令流中可能彼此相距甚远，矢量超前执行也会并行地发出这些访问。它带来了两个关键的好处：

1. 在 runahead 模式下，它大大增加了有效的取指、译码带宽，也就是说，我们是一次取指、译码多个循环迭代。
2. 它需要很少的后端硬件资源，也就是说，在矢量 runahead 模式下，一条矢量指令对应于原代码中多个循环迭代的多个标量指令，只占用一个发射队列槽。

成果

更高的内存级并行性为矢量超前执行带来了性能上的显著改善。下图展示了在各项基准的测试结果。与基准乱序核心和 PRE 相比，矢量超前执行分别产生了 1.79 倍和 1.49 倍的平均速度。