计算机体系结构 · 第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都已对其他核可见” |
同一条内存操作有不同时间点:
- 地址/数据计算完成:知道访问哪里、Store要写什么。
- 执行或转发完成:Load拿到了一个值,可能还在投机状态。
- ROB退休:架构结果按程序顺序确认。
- 跨核可见:写通过内存层次传播,在相应内存模型下可由其他核观察到。
尤其是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(内存依赖投机失败)。正确修复需要:
- 识别冲突的较老Store和已执行的较年轻Load;
- 阻止错误Load及其依赖的投机结果退休;
- 从适当检查点恢复、冲刷并Replay受影响指令(具体范围依实现);
- 重新执行Load,让它读到正确的Store转发值或后续正确的内存值;
- 重新执行依赖消费者,恢复按序提交。
仅将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排序与一致性探测相关的情形。
真实实现资料(课后可查)
- RISC-V BOOM · The Load/Store Unit:LDQ/STQ、STA/STD、转发和内存顺序恢复。
- gem5 · O3CPU:Store在提交后写Cache、LSQ别名检查及memory-order squash路径。
- Intel 64架构内存排序手册:不同地址的Store→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不变量并重练。不因测验改变下一讲编号。