Store Set 内存依赖预测

让store先排成一条链 ​

集合里有三条在途store S0、S2、S5。如果让load分别等三者，需要三个等待来源。本协议先约束S2等S0、S5等S2，再让load只等S5。等到S5完成时，前面那条链也已经完成了。

这条链可能比真实依赖更保守。load实际只读S0的位置，但集合中碰巧还有无关的S5，它仍会等S5。预测器用较简单的等待表示，交换了部分调度自由。是否划算要看省下多少重放、增加多少等待，不能只统计“训练后没有错”。

冷启动、热身与地址模式变化 ​

继续使用四条程序：PC0x100的store晚到槽4=17，PC0x104的load读4，后面的store与load传播 2*v1+1。第一次SSIT为空，模式与盲猜一样：load先读3，第6轮发现冲突，重放I1–I3，并学习

SSIT[0x100] = 0
SSIT[0x104] = 0

重新运行同一个程序，初始扫描在集合0的LFST放I0，让I1等I0。第1轮I1地址已知也不执行；第6轮I0地址和数据齐全、标DONE，I1才从它转发17。I2接着产生35，I3得到35，不发生重放。

轮数相同并不否定少做两次load的事实，也不允许宣称已经测出加速。这里老store始终压住退休，教学阶段安排让三种情况都在第10轮结束。

再保持两个PC不变，只让I0这次写槽9，I1仍读槽4。学到的集合仍让I1等I0，但实际地址已不冲突，正确load值是3，后续值为7。这是假依赖：结果正确，等待却不必要。参考器输出5次 predicted-store 等待尝试；该计数是驱动访问候选时记录的尝试次数，不等于5条不同load，更不是硬件停顿周期的普遍定义。

合并两个集合，然后检查LFST生命周期 ​

先训练两对PC：store A=0x300与load X=0x304组成集合0；store B=0x308与load Y=0x30c组成集合1。再训练A与Y，四个PC立即都属于0。

新窗口按程序序是S0(A)、S1(B)、L2(X)。初始前驱表为 [无,0,1]，LFST[0]=1。即使S1地址和数据先到，也不能先标DONE，因为它还等S0。

S0完成时，LFST仍指向1，必须保留。接着S1完成，才因“表项仍是我”清掉LFST。L2等到S1完成后执行真实地址查询；它不会把“等的是S1”误当成“必须从S1拿数据”。本例L2读槽2，S0、S1分别写0、1，所以最终还是读内存槽2的初值0。

这个例子把三个身份分开：集合号0表示预测分组，前驱1表示调度等待者，实际来源−1表示读已提交内存。三者混用会把一个性能建议变成错误的数据路由。

训练与恢复同时发生时怎么办 ​

违例load及年轻后缀已经由底层取消；更老store仍保留。本文完成PC集合合并后，重新扫描所有活跃未完成项，重建它们的链和LFST。已经完成的项不被追溯地标成“尚未完成”，新加的等待边只约束还没执行或完成的工作。

如果不重建，LFST可能仍指向被取消的代次，或两个刚合并的组各有一条旧链却只剩一个表项。本页用 O(n) 扫描避开这类悬空身份和链覆盖问题。真实窄带硬件通常需要其他恢复结构，不能把这个全窗口扫描当成无成本的组合电路。

显式清历史也会清SSIT并重建当前等待边；它可以让load更早猜测，之后仍靠独立检测兜底。清表没有清架构内存，也不取消已经正确退休的结果。外部调用者不应绕开窗口直接改正在使用的SSIT。

等待链的性质与安全底线 ​

每次建立前驱时，LFST只保存扫描中已经经过的store，所以前驱年龄严格小于当前年龄。无论是预测边还是原本load结果的真实数据依赖，都指向更老生产者。由年龄严格递减，等待图不可能形成环。

在一次重建之后，固定一个集合。当时仍未完成的store按年龄形成一条链；一条load只需等链中它之前的最后store。沿链归纳，最后者DONE时，所有更老链成员也已DONE；已经在重建前完成的store本来就具备字段。于是这个等待完成条件确实覆盖该集合中的相关在途store，而不必给load保存整组动态前驱。

若期间出现新冲突合并或恢复，旧链不被假定仍完整，协议重新建链。即使某个load早已执行而未受新约束，它的错误仍由地址/来源检测发现并恢复。预测器不能删除这道检查：空历史、清表、新路径和变化的地址模式都可能让它漏掉真实依赖。

因此一般正确性来自重放页的退休前缀证明。这里加入的等待只会限制执行许可，不会改变真实来源选择或架构提交值；在有限驱动与持续调度下，严格年龄方向也不会给最老项增加一个年轻阻塞者。训练后未见重放只是一次运行的事实，不是任何输入都不会再违例的定理。

成本和更接近硬件的取舍 ​

设历史表有p个不同PC，窗口n项、k个活动集合。普通完整PC查表和LFST访问在散列表均摊常数模型下计费；训练同组或加入一个新成员为均摊O(1)。合并两个已有集合要扫描全部p个PC，最坏O(p)，随后重建链O(n)。历史表占O(p)，LFST至多O(min(k,n))，每项另存一个前驱年龄。

这不是原论文无tag定长SSIT的容量模型。完整键避免PC索引冲突，但历史可增长；全表合并更直接，却没有固定表更新的低成本。若改成哈希槽、有限集合号、周期清除或置信计数，必须重新说明别名、替换和动态身份恢复。原论文研究过这些取舍，并不提供“任意工作负载都接近最优”的保证。[1, §6]

公开执行器仍承担前两页的队列扫描和排序；若发生r次训练恢复，集合与重建额外总代价可保守写为 $O(\sum _{t=1}^r(p_t+n))$。日志中排序输出SSIT、保存取消列表和全状态均另有费用。PC、年龄、代次和整数值若不能装入一个机器字，还需按位成本计费。

可执行终点要求交付实际SSIT、LFST和前驱表，重新运行冷/热/变址/清表四种条件，并保留来源查询与退休证据。学到了哪些关系、这次等了谁、最终读了谁的值，应在答案里分别可见。