加载存储队列 (Load Store Queue) 与乱序执行微架构

1 微架构宏观视图

现代处理器的微架构包含多个复杂组件，以支持指令的乱序执行。核心数据结构和组件包括：

• 重排序缓冲 (ROB, Reorder Buffer)：负责按程序流顺序管理指令的提交（Retire），包含指令的执行状态。
• 映射表 (Map Table) 与架构映射 (Arch. Map)：用于寄存器重命名，解决数据依赖中的伪依赖问题。
• 保留站 (RS, Reservation Stations)：保存已分发但尚未准备好执行的指令，等待其操作数就绪。
• 空闲列表 (Free List)：管理物理寄存器堆中的可用寄存器。
• 寄存器堆 (Regfile)：存储实际的物理寄存器值。
• 加载存储队列 (LSQ, Load-Store Queue)：专门负责处理内存访问指令（加载和存储），以正确解决内存数据依赖。

2 加载存储队列 (LSQ) 的核心作用

LSQ主要用于解决加载 (Load) 和存储 (Store) 指令之间的依赖关系。在乱序处理器中，这种依赖关系的判断尤为复杂。

2.1 内存依赖的特殊性

考虑以下汇编代码片段：

STR p6, [p4, 4]
LDR p5, [p2, 16]

内存操作具有特殊性，只有当内存地址被计算出来之后，才能知道存储指令和加载指令之间是否存在依赖关系。如果 p4 + 4 等于 p2 + 16，则两者存在依赖；否则，它们是独立的。由于乱序处理器的特性，地址的计算可能以任意顺序发生，这要求硬件提供一种机制来动态检测和解决这种异步的地址和数值解析。

2.2 LSQ 的主要功能

• 管理地址和值的异步解析。
• 保护内存免受推测性写入（Speculative Writes）的影响。
• 促进并发的内存访问，提升访存并行度。
• 支持条目之间的值转发（Forwarding）：如果发现前面的存储指令写入的地址与后续的加载指令读取的地址相同，可以直接将值从存储队列转发给加载指令，而无需等待数据写入缓存。

3 LSQ 的工作原理

内存操作指令按程序原本的顺序（分发顺序，Dispatch order）被插入到 LSQ 中。后续加载指令所需的数据只能来自早前的存储指令或者直接来自内存（L1 D Cache 或 L2/L3 内存层次结构）。此外，如果一个较晚的存储指令写入的内存位置与较早的存储指令完全相同，通常可以消除较早的存储指令的实际写入操作。

具体的工作流程如下：

• 指令插入：加载和存储指令按顺序同时插入到 ROB 和 LSQ 中。
• 处理存储指令 (Stores)：
  • 已完成执行（地址和数据均已就绪）的存储指令会将其信息写入 LSQ。
  • 当该存储指令从 ROB 中提交（Retire）时，位于 LSQ 头部的该指令才会被真正写入到数据缓存（Data Cache）中。
• 处理加载指令 (Loads)：
  • 一旦加载指令的地址被计算出来，该地址就会被发送到数据缓存。
  • 同时，硬件会检查 LSQ。如果发现地址匹配的更旧的存储指令，该存储指令的值将被直接转发给此加载指令。
• 错误推测恢复 (Mis-speculation)：如果乱序核心发生推测错误（例如分支预测失败），属于错误执行路径上的条目将被从 LSQ 中移除。

4 深入探讨：为什么需要 LSQ？

4.1 为什么不能像重命名寄存器那样重命名内存地址？

在指令分发阶段，内存地址通常还是未知的。其次，内存访问的大小可能不同（例如字节、半字、字、双字），且这些访问可能会发生重叠。硬件需要追踪不同宽度的加载和存储之间的复杂依赖关系，这使得像寄存器那样的简单重命名机制无法直接应用于内存地址。

4.2 如果没有 LSQ 会怎样？

如果没有 LSQ，乱序核心将只能允许同一时间存在一条加载或存储指令。这将迫使其他所有指令在分发阶段停滞（Stall），极大地限制了指令级并行度（ILP），导致性能大幅下降。

5 存储队列 (SQ) 与保守加载调度

为了管理这种复杂性，可以将 LSQ 分解为针对存储的结构和针对加载的结构。首先考察存储队列 (SQ, Store Queue)，并采用 保守加载调度 (Conservative load scheduling) 策略。

在保守调度下，加载指令相对于其他加载指令可以乱序执行，存储指令相对于其他存储指令也可以乱序执行，但是加载指令必须严格在所有更旧的存储指令之后按序执行。

5.1 数据结构：存储队列 (SQ)

SQ 包含以下字段：地址 (Address)、相对年龄 (Age/ROB位置)、以及要写入的值 (Value)。同时维护头部 (Head) 和尾部 (Tail) 指针，以及一个“明确的存储位置 (Unambiguous store pos.)”指针。

5.2 保守调度的执行阶段

• 分发 (Dispatch)：在 SQ 尾部分配一个条目。同时在保留站 (RS) 中记录当前的 SQ 尾部作为该加载/存储指令的“加载位置 (Load position)” 或 “存储位置”。
• 发射 (Issue)：对于加载指令，其记录的“加载位置”必须大于或等于当前的“明确的存储位置”（即所有更早的存储指令的地址都必须已知），加载指令才被允许发射。
• 执行 (Execute)：
  • 对于存储指令：计算出的地址和数据被写入对应的 SQ 槽位。
  • 对于加载指令：将地址并行发送给数据缓存 (D$) 和 SQ。在 SQ 中进行完全关联搜索 (CAM)，比较所有的存储地址。找出所有匹配的地址后，选择排在该加载指令之前最年轻的存储指令（利用记录的“加载位置”输入来判断）。如果有匹配，则从 SQ 中“转发”值；如果没有匹配，则从 D$ 中获取值。
• 提交 (Retire)：将 SQ 头部条目的地址和数据写入 D$，并释放该 SQ 头部条目。

保守调度的优点是实现相对简单，但其缺点是显著限制了性能，因为加载指令经常被迫等待那些实际上地址并不冲突的旧存储指令。

6 加载队列 (LQ) 与机会主义加载调度

为了克服保守调度的性能瓶颈，引入了加载队列 (LQ, Load Queue)，从而支持机会主义加载调度 (Opportunistic load scheduling)。

统计表明，平均不到 10% 的加载指令需要从 SQ 中转发数据。即使更旧的存储指令地址未知，它们发生地址冲突的概率也很低。因此，机会主义调度允许加载指令在存在地址未知的更旧存储指令时提前乱序执行。

6.1 解决内存排序违例

当加载指令提前执行时，可能会发生内存排序违例 (Memory ordering violation)。如果一个加载指令过早执行，而随后一个更旧的存储指令计算出了相同的内存地址并写入数据，此时加载指令读取到的就是过期的数据。必须能够检测并修复这种错误（即冲刷流水线并重新获取指令）。

6.2 LQ 的工作机制

LQ 是一个与 ROB、SQ 类似按程序顺序分配的关联可搜索队列，其大小通常占 ROB 容量的 20-30%。LQ 条目包含加载指令的目标地址以及相关状态（如是否需要刷新 Flush）。

• 分发 (Dispatch)：加载指令在 LQ 尾部分配一个条目。存储指令在保留站中记录当前的 LQ 尾部作为“存储位置 (Store position)”。
• 加载执行 (Execute - Load)：加载指令将其地址写入对应的 LQ 槽位，并照常访问 D$ 和 SQ 获取数据。
• 存储执行 (Execute - Store)：存储指令不仅将地址和数据写入 SQ，还会将地址发送到 LQ 中进行匹配。如果发现存在地址匹配的加载指令，并且该加载指令已经提前执行（根据记录的“存储位置”判断其是否比该存储指令年轻），则说明发生了内存顺序冲突。
• 恢复 (Recover)：恢复逻辑会选择比该冲突存储指令年轻的最老的加载指令，处理器冲刷流水线（Flush），并从该加载指令处重新启动执行。

7 周期级执行示例：处理内存依赖与异常

通过分析具体的架构级处理器周期级状态，可以清晰地观察上述机制是如何在真实场景中运作的。在指令发射和执行阶段，主要存在以下数据交互和判定流向：

• 加载指令计算地址后，不仅查询数据缓存，还查询 SQ 查找是否有匹配的未提交存储操作。如果命中且属于比自身更老的指令，则触发值转发（这使得加载指令能够直接从 SQ 获得最新写入但尚未进缓存的值）。
• 当存储指令完成地址计算并写入 SQ 时，它会同时检查 LQ 寻找潜在的内存违例。如果一个更早发出（但在程序逻辑中位于其后）的加载指令被发现从同一个地址读取了数据，即说明其错误地使用了旧值，LQ 会识别出这次内存顺序冲突。
• 一旦检测到违例，硬件会在 ROB 中的相应加载指令条目上设置异常位 (Exception Bit)。
• 随着程序的执行推进，排在前面的旧存储指令逐渐按序提交，将更新的值持久化写入数据缓存。
• 当流水线执行到被标记了异常位的加载指令准备提交时，处理器将截获该异常，丢弃错误路径上的后续状态，并回滚恢复，从而保证程序逻辑结果的绝对正确性。