计算机体系结构 · 第11课|Load/Store Queue 与内存依赖预测:Load为什么敢越过Store?

2026年10月30日|第2周第4课|约18分钟

承接第10课:ROB确保结果按程序顺序退休,错误路径可以恢复。但寄存器依赖由Rename标签明确表示;内存依赖却要等地址算出来才知道。今天讨论一条更年轻的Load可否先运行、读到哪一份值、猜错后怎样撤销,以及为什么这不等同于违反内存模型。

1. 动机:一条地址未知的Store要阻塞整个后端吗?(约2分钟)

按照程序顺序:

S0: STORE [R8], 42        # 较老,R8的值还没算出
L1: r1 = LOAD [0x100]     # 较年轻,地址已经确定
I2: r2 = r1 + 1           # 依赖L1

如果最终R8=0x200,S0与L1访问不同位置,L1本来可以立即读0x100;若R8=0x100,L1必须观察到正确的较老写入,而不能读到被覆盖前的旧值。

真正的问题不是“Load是否比Store年轻”,而是“它们最终访问的字节范围是否重叠,以及最近的较老写入是否已有可转发的数据”。

两种极端策略都不完美:

  • 保守等待:任何较老Store地址尚未确定,Load都等待;容易浪费可并行执行的周期。
  • 激进投机:Load先执行,之后检查是否猜错;可能收益明显,但猜错要Replay、冲刷流水线,消耗带宽和能量。

实际乱序CPU通常使用LSU(Load/Store Unit)与某种Load/Store Queue来解决这个折衷。

flowchart TD
    A["Decode / Rename:保留程序年龄顺序"] --> B["Load Queue (LQ/LDQ)"]
    A --> C["Store Queue (SQ/STQ)"]
    C --> D["Store地址STA与数据STD分别就绪"]
    B --> E{"Load地址已知;检查较老Store"}
    D --> E
    E -->|"已知同址、数据可用"| F["Store-to-Load Forward"]
    E -->|"可能冲突、数据未齐"| G["等待 / 稍后重试"]
    E -->|"可证明不冲突或预测可绕过"| H["访问Cache(可能是投机)"]
    D --> I{"后来发现较老Store与已执行Load冲突?"}
    H --> I
    I -->|"是且所读值错误"| J["内存顺序违例 → Replay/恢复"]
    I -->|"否"| K["允许在满足其他条件后按序退休"]
    F --> K
    G --> E

2. 符号、假设与四种“先后”要分开(约2分钟)

本讲的基本算例限定:单核、普通可缓存内存、对齐4字节Load/Store、无MMIO、无Fence、无其他核并发写入。使用真实程序顺序 (S_i\prec L_j) 表示Store更老;物理地址 (a)、长度 (w);访问字节区间 ([a,a+w))。实现可以乱序执行,但ROB依然按序退休。

符号/结构 内容 不等于什么
LQ / LDQ 在途Load的年龄、地址、是否执行/取值来源、可能的Store依赖等 不等于L1数据缓存
SQ / STQ 在途Store的年龄、地址、数据、掩码、已提交状态等 不等于所有已全局可见的内存
ROB 统一追踪指令年龄、完成和异常并按序退休 不负责替代字节级别名检查
Store Buffer Store提交后仍可能等待写入缓存/一致性传播的缓冲(具体组织依实现) 不等于“所有Store都已对其他核可见”

同一条内存操作有不同时间点:

  1. 地址/数据计算完成:知道访问哪里、Store要写什么。
  2. 执行或转发完成:Load拿到了一个值,可能还在投机状态。
  3. ROB退休:架构结果按程序顺序确认。
  4. 跨核可见:写通过内存层次传播,在相应内存模型下可由其他核观察到。

尤其是Store从ROB退休,不必然代表全局可见。这个区别会贯穿第五周的TSO、RVWMO和一致性专题。

3. 内存依赖为何比寄存器依赖难?(约2分钟)

寄存器重命名时,源标签已经确定。例如较年轻指令读R1,Rename能直接找到最近的较老写者的物理寄存器。内存访问却存在动态地址:

S0: STORE [p], v       # p来自长延迟除法,尚未知
L1: r = LOAD [q]       # q现在已知

是否依赖由运行时判断:

[ \operatorname{overlap}(S_0,L_1) \iff [a_s,a_s+w_s)\cap[a_l,a_l+w_l)\ne\varnothing. ]

对相同宽度、对齐且全覆盖的简化模型,退化为 (a_s=a_l)。对字节Store和较宽Load,则必须逐字节检查,而不只看起始地址是否相同。

Store Address Generation(STA) 和 Store Data Generation(STD) 可以在不同时间就绪:即使地址已经确定,写入数据尚未产生,Load仍可能必须等待。BOOM文档明确讨论这两项可以独立准备,gem5 O3也区分Load读、Store提交后写Cache及必要的重调度。

为了发现早已投机执行的年轻Load与新揭晓的Store地址是否冲突,需要保留Load执行信息,并对有关在途Load做年龄和地址检查。这个搜索可能由CAM、banked队列或其他实现完成;“一定所有LSQ都使用同一个全相联CAM”并不是架构要求。

4. Store-to-Load Forwarding:转发哪一个Store?(约2分钟)

若Load访问地址A,更老Store中有多个也写A,必须选程序顺序上离Load最近、其有效字节覆盖当前读取的相应写入,而非最早写入或最后算出地址的那条。

内存原值:M[A] = 5
S0: STORE [A], 11
S1: STORE [B], 17
S2: STORE [A], 29
L3: r = LOAD [A]

当S0、S1、S2的地址与数据均已明确、L3为完整4字节读取且所需转发机制可用,L3应从S2取得29。S2还没写进Cache、尚未对其他核可见,也不妨碍同核向更年轻的Load转发正确值。

形式化地,对于地址范围已知且覆盖Load字节的Store集合:

[ S^*=\arg\max_{S_i\prec L_j,\ \mathrm{covers}(S_i,L_j)} \mathrm{age}(S_i). ]

但要当心:这是整字全覆盖的简化式。如果某个较年轻Store只覆盖Load的一部分字节,正确值可能需要从多个Store和缓存逐字节合并;某些微架构不支持任意合并,会让Load等待重试。不能跳过最近的部分重叠Store,直接取更老整字Store而假装读值正确。

再考虑三个不同情况:

  • 已知同址、数据齐全:可以按实现能力直接Forward,绕过普通Cache读等待。
  • 已知同址、数据未齐:不能读旧Cache值凑数,须等待、唤醒或使用等价正确机制。
  • 较老Store地址未知:无法证明不冲突,只能保守等待或依赖预测进行可恢复投机。

5. 预测“No Alias”与违例Replay(约3分钟)

假设程序顺序:

S0: STORE [p], 21       # 在较早时刻地址未知
L1: r = LOAD [X]        # 预测与S0不同,先从Cache读到旧值7
I2: t = 2*r             # 暂时使用了投机值

若后来发现 (p=X),L1原本应观察较老Store写入的21,已读取的7不正确,I2的值也因此不可信。

发生了 Memory Ordering Violation(内存依赖投机失败)。正确修复需要:

  1. 识别冲突的较老Store和已执行的较年轻Load;
  2. 阻止错误Load及其依赖的投机结果退休;
  3. 从适当检查点恢复、冲刷并Replay受影响指令(具体范围依实现);
  4. 重新执行Load,让它读到正确的Store转发值或后续正确的内存值;
  5. 重新执行依赖消费者,恢复按序提交。

仅将L1的物理寄存器改成21并不自动修复已经用7算过的I2,更不能允许错误消费者产生不可回滚的架构副作用。

检查点与第10课分支误预测类似,但根因不同:分支是预测控制流错,LSQ Replay是预测内存依赖错。两者都可能需要清理年轻ROB/IQ/LSQ状态及恢复Rename映射。

实现边界:不同设计在Store地址计算、Store提交或有关队列比较时检测违例;恢复可能从违反的Load开始,或冲刷更宽的年轻指令后缀。不能把某一种BOOM/gem5内部时机当成所有CPU的唯一规则。

6. 一张周期Trace:正确猜测与错误猜测(约2分钟)

设Cache初始 (M[X]=7,\ M[Y]=9),两处为不同4字节字。Store地址p直到周期9才算出,Store数据21从周期3就已准备;Load L1地址Y在周期4可用,L2地址X在周期5可用。

S0: STORE [p], 21          # 最老
L1: a = LOAD [Y]           # 较年轻
L2: b = LOAD [X]           # 更年轻
I3: c = b + 4
周期 推测执行事件 如果p最终为Y 如果p最终为其他地址Z
3 S0数据21准备,地址未知 暂不能确认别名 暂不能确认别名
4 L1先读Y,得到投机值9 后续可能错误 可保留9
5 L2先读X,得到投机值7 不与S0别名 可保留7
6 I3用b计算投机结果 仍为投机结果 仍为投机结果
9 p地址揭晓 L1与较老S0冲突,须采取正确恢复 没有这项冲突

这里故意不把“所有年轻指令全部冲刷”写成唯一方案:最小数据依赖修复集合与某实现实际冲刷范围不同。若机器简单地冲刷违例Load以后的整个ROB后缀,L2/I3也可能被重新执行,即使其数学值没有变。

同地址读与Store Buffering不是矛盾

在x86-TSO类常见语义下,较年轻Load可越过不同地址的较老Store;但对同地址读取,要通过转发或正确排序得到本线程较老Store的效果。另一个核仍可能暂时看不到这个Store。

Core 0:                Core 1:
STORE X = 1            STORE Y = 1
r0 = LOAD Y            r1 = LOAD X
初始 X=Y=0

在允许Store Buffering的TSO模型中,两个Load都读0可能被允许,因为各核的不同地址Load先于对方缓冲中的Store对外可见。这不是让同一核的Load[X]合法地无视自己更老的Store[X]。

注意微架构“先发一条Load再Replay”是内部执行猜测,内存模型约束的是软件最终可观察到的合法效果;它们不能混为一谈。另需区分普通同步良好的程序与高级语言中的非原子数据竞争。

7. 预测收益有明确阈值,不是“越激进越快”(约2分钟)

对一次“较老Store地址尚未知”的Load,建立一个明确简化的决策模型:

  • 如果本次提前执行且没有别名,平均比保守等待节省 (B>0) 周期;
  • 若发生别名违例,Replay等使它相对保守策略额外损失 (C>0) 周期;
  • 预测器估计发生别名的概率 (p),并且只考虑这两类情况,不计额外功耗与资源争用。

则投机相对等待的期望周期收益:

[ G=(1-p)B-pC=B-p(B+C). ]

因此:

[ \boxed{\text{投机在此模型下有利}\iff p<\frac{B}{B+C}} ]

独立数值例:若正确投机节省9周期,错误Replay额外损失27周期,则当 (p<9/36=0.25) 时有正期望收益。若预测别名概率30%,期望收益 (0.7\times9-0.3\times27=-1.8) 周期,倾向等待。

这个阈值不是硬件“标准常量”。实际 (B,C,p) 与Load命中层级、ROB阻塞、分支/缓存竞争和负载分布相关;还存在多条Load共享一次Replay、资源占用引起的间接成本。预测器应基于实测更新,而非只背一个阈值。

一个最简单策略是未知地址全部等待。更积极的策略可使用Load/Store PC历史、Store Sets等预测可能依赖的较老Store。误报提高等待,漏报提高Replay;预测准确率高也不一定性能好,因为不同事件的代价可能相差悬殊。

8. 机制边界:五个常见误区(约2分钟)

误区一:只要地址未知,后面的Load必须全部等待。
这是保守实现选择,不是所有OoO设计的硬件/ISA要求。可允许可恢复投机,但必须检查真正的依赖与内存模型约束。

误区二:Store地址知道就可以立即从它Forward。
Store的数据可能还没准备,或者只覆盖Load的一部分字节。转发必须满足字节和数据有效性合同。

误区三:Load已经拿到Cache返回值就一定“完成且正确”。
有未解决的较老Store时,这个值仍可能是投机结果。它可能唤醒下游,但不能越过尚未解决的正确性边界不可逆地提交。

误区四:只要按序退休,Store就已经对其他核可见。
错误。Store可以已退休但仍驻留Store Buffer、等待后续一致性传播;全球可见性受具体内存模型和硬件协议约束。

误区五:所有Load–Load物理执行都必须严格按程序顺序。
不能一概而论。特定ISA(例如x86-TSO)对可观察的Load顺序有更严格要求,RVWMO又有自己的排序规则;物理上即使投机乱序发起,也可通过违例检测与Replay满足允许的架构行为。BOOM文档还专门说明了同地址Load排序与一致性探测相关的情形。

真实实现资料(课后可查)

9. 小结与下一讲(约1分钟)

今日从“地址未知”走到五个连续的正确性边界:

程序顺序/指令年龄
      ↓
Store地址与数据分别准备
      ↓
Load检查较老Store(可能等待或预测绕过)
      ↓
正确字节来自Forward或Cache(错误则Replay)
      ↓
ROB按序退休 → Store可能仍待全局可见

记住三对区别:① 已知不冲突 vs 预测不冲突;② Load取到值 vs 该值已被验证可提交;③ Store退休 vs 跨核全局可见。

下一讲(第12课,2026年10月31日):分支预测与前端投机——两位饱和计数器、BHT/BTB、错误预测恢复成本,以及为何准确率之外还要看预测器覆盖率和关键路径。(保持第2周既定课号,不因测验成绩改编号。)


四级分级测评(共100分;首次不提供标准答案)

作答后按Lv1–Lv4逐项评阅。前三题可客观判分;Lv4需要对步骤、反例与不变量人工/自评,不将开放证明伪装为自动验证。各题答案与解析不在本讲义中公布。

Lv1|内存消歧与投机条件|15分|单选|预计2分钟

程序顺序中较老Store的地址尚未知,较年轻Load地址已经确定;没有Fence/MMIO,普通可缓存内存。以下哪种描述最准确?

A. Load必须无条件等待,因为任何提前执行都会违反ISA。
B. 可以在有依赖预测、在途跟踪与正确恢复机制时投机执行;若稍后发现较老Store冲突,必须修复相关结果。
C. 只要Load已经从L1命中,就证明与所有较老Store无依赖。
D. Store在ROB中比Load更老,就意味着Store数据已经对其他核全局可见。

可选提示(不泄露答案) 区分“已经证明地址不同”和“猜测地址不同”。再思考即使猜错是否有恢复路径。

Lv2|预测收益与Replay代价|20分|数值|预计4分钟

在一个明确的两结果性能模型中,允许一条Load在较老Store地址未知时投机:

  • 若没有别名冲突,它相对于等待节省 12周期;
  • 若有冲突,恢复与Replay相对于等待额外损失 36周期;
  • 预测器估计别名概率为 10%;
  • 两种情况互斥,忽略其他资源争用。

求每次选择投机的期望净节省周期数。正数代表投机有利,负数代表等待更有利。填写一个数值,单位为周期。

可选提示(不泄露答案) 把“无冲突”与“有冲突”分别作为两种结果,加权比较相对于保守等待的收益和损失。

Lv3|转发、部分重叠与全局可见性|25分|多选|预计5分钟

针对具有LSQ、按序退休与正确内存依赖恢复能力的乱序CPU,哪些判断成立?选择所有成立项。

A. 只要一条Store尚未从ROB退休,后续Load绝不能从它取得数据。
B. 在数据与覆盖条件满足时,Load可以从程序顺序上最近的有效较老同址Store转发,而不等待该Store对其他核可见。
C. Load从较老S0转发了地址A的值后,即使另一条介于S0与Load之间的更年轻Store S1后来也解析成写A,该Load此前的值也无条件正确。
D. 如果较年轻的部分重叠Store不能单独覆盖整条Load,微架构可以采用正确的逐字节合并,也可以阻塞等待;不能直接忽略其写入。
E. 一旦年轻Load产生错误值,只要稍后把Cache修好,就允许其所有错误依赖消费者保持已提交状态。
F. Store从ROB退休之后仍可能暂存于缓冲中,尚未达到相应内存模型的跨核可见阶段。

可选提示(不泄露答案) 逐项检查:转发是否要求“已全局可见”?最近的较老写入是什么?字节覆盖是否完整?ROB提交的结果还能否回滚?

Lv4|双Store、投机转发与精确Replay设计|40分|开放推导|预计10分钟

假设:单核,普通可缓存、对齐4B整字访问;无其他核写入、无Fence/MMIO。Load可在较老Store地址未知时投机。Load有已完成标记,Store地址揭晓后可检查更年轻的在途Load;ROB按程序顺序退休;错误投机结果在提交前可以被恢复。

初始Cache内容 (M[X]=5,\ M[Y]=8),X与Y是不同的4B地址。

按程序顺序:

S0: STORE [X], 11              # 地址与数据均已知;暂未对外可见
S1: STORE [p], 21              # 数据已知,但p直到周期9才揭晓
L2: a = LOAD [Y]               # 周期4执行,暂读到8
L3: b = LOAD [X]               # 周期5执行;因S1地址未知,
                               # 投机从已知S0转发到11
I4: c = 2*b + 3                # 周期6按投机b执行

A|逐条年龄与取值来源(12分)

写出在周期6时,L2/L3各自潜在依赖哪些较老Store、哪些地址已知或未知、L3为什么只能被标记为投机值而不是永久正确。写出LQ至少应保留的三个状态字段(可用概念名,不要求特定硬件位名)。

B|情况一:周期9时p=X(12分)

判断是否有内存顺序违例。若有,说明应从哪里恢复、哪些值与消费者必须重新验证,以及最终b与c应满足什么。解释为何“只把b改成正确数值、不处理I4”不充分,并说明错误结果为什么不能提前退休。

C|情况二:周期9时p=Y(10分)

与情况一比较:哪条Load此前读取了不正确的值?另一条Load此前从哪个Store取值可以保持正确?设计至少一个能够区分这两种情况的自动断言或比较规则。

D|实现与内存模型边界(6分)

说明最小必须恢复的数据依赖集合与实际采用“从违例Load开始冲刷年轻ROB后缀”的实现为什么可能不同;再说明S0或S1的Store已退休时,是否必然可推出“其他核已观察到该写入”。最后给出一条帮助避免频繁Replay、但可能带来假依赖等待的预测规则。

可选提示(不泄露答案) 依据**程序顺序**寻找Load之前最近的同址写入,但不要把“地址还未知”当成已经证实不同;消费者依赖Load产生的旧数值,应在恢复后重新检查。对不同p取值分别比对Y与X,最后分清内部Replay和跨核可见性。

作答模板:

Lv1:
Lv2:
Lv3:(写字母组合)
Lv4:
 A:
 B:
 C:
 D:

评分与后续:80分及以上继续既定专题;60–79分补一题针对性执行Trace;低于60分回看第9–11课的ROB、Rename和LSQ不变量并重练。不因测验改变下一讲编号。