关键字优先填充与提前返回

形式陈述

一行有四个字，当前读取只要最后一个。下层正在逐字送回数据，是否必须等四个字全部到齐才能回答这次读取？又能否先把它要的那个字送来？这其实是两个问题：提前返回决定何时回答请求，关键字优先决定下层按什么次序送字。

本页沿用非阻塞未决事务的只读内存、地址分解、请求身份、资源重试和保留路合同。改变的是完成接口：不再一次 complete(t) 安装整行，而用 deliver(t,o) 交付事务 $t$ 的块内第 $o$ 个字， $0\le o<K$ 。数据仍由可信不可变内存读取，不由调用者提供。

每条未决记录增加一个长度 $K$ 的接收标记数组 $R$ ，初始全假，以及尚未到达的字数 $z=K$ 。填充数据保存在该事务保留路的数据数组中；这些位置在逻辑上充当填充缓冲。正常驻留有效位仍为假，所以没有到达的旧数组内容不能被读出。

一次合法 deliver(t,o) 执行：

验证原事务身份仍存活、偏移合法且 $R[o]$ 为假；失败时状态完全不变
写入 $A[t.bK+o]$ ，置 $R[o]=\mathrm{true}$ ，令 $z\leftarrow z-1$
只返回目标列表中偏移恰为 $o$ 的请求，并把它们移出列表；其余目标继续等待
只有 $z=0$ 时才将整行设为驻留有效，释放 MSHR 和路的保留关系

读取接口也增加一个分支：没有驻留命中，但找到同块事务且 $R[o]$ 已真时，生成新请求并直接从填充缓冲返回，状态为 FORWARD。它不占等待目标槽。若所需字尚未到达，则仍按目标容量作 MERGE 或 RETRY；普通 HIT、新块 MISS 与其他资源规则不变。

当前等待目标已经全部返回，不意味着事务可以释放。尚未到达的字仍属于这一原事务，路必须继续保留，旧身份仍可接收其余合法字。否则迟到字将失去可靠归属，或被错误送进一个重用位置的新事务。

假设初次建立事务的请求偏移为 $c$ 。关键字优先的纯次序构造是

c,(c+1)\bmod K,\ldots,(c+K-1)\bmod K.

它恰好遍历每个偏移一次。参考函数 critical_order(K,c) 只返回这个完整次序，不发起填充、不修改事务。驱动器也可按 $0,1,\ldots,K-1$ 或其他不重复排列调用 deliver；返回值正确性与排列无关。

直觉

整行模式把“货到齐”和“顾客拿到所需商品”放在同一时刻。逐字模式把它们拆开：某位顾客已经拿到所需的字，可以继续自己的工作；负责接收整箱货的登记单却还不能撤掉。

偏移三先到使初次读取返回，随后同字读取从缓冲转发；其余字仍保留事务，最后一拍才使整行有效 — 读取寿命短于整行填充寿命

正确性需要把前页的不变量细化。对于一条未决事务， $R[o]$ 为真恰好表示该字已经由本身份的一次合法交付事件写入；这些位置的内容等于相应内存字。每个仍等待的目标都指向尚未接收的偏移，并且只属于一条事务。整行有效与未决保留互斥。

归纳时，deliver 的身份和重复检查确保每一偏移至多写入一次。它写入可信字后，只移动与该偏移有关的目标，因此不会提早回答另一字，也不会漏掉当前字的等待者。FORWARD 只在相应标记为真时读数据，不需要借用整行有效位。最后一个字到达时，所有 $R[o]$ 都真，整行逐字正确，才可切换为驻留状态。未接收字的目标不可能在这时残留，因此释放不会丢掉请求。

如果每条存活事务的所有未到达偏移最终都被交付，那么每个已接收读取最终返回，而且每条事务最终释放。只承诺“每个当前目标需要的字最终到达”还不够：其余字永不返回时，目标虽已完成，MSHR 和路会永久被占住。这是请求活性与资源回收活性的区别。

关键字优先没有改变这份安全证明。它只是把初次请求最需要的字排到前面。后来合并的读取可能需要另一个偏移，所以“初始请求更早返回”不能自动推成“所有请求都更早返回”。

例子与边界

取 $K=4,S=1,W=1,M=2,T=2$ ，内存仍为 $A[i]=17i+11$ 。先读字节地址 12，即块 0 的偏移 3，再读地址 0，二者合并在同一事务下。选择次序 $3,0,1,2$ 。

交付偏移	这次返回的地址	接收标记，按偏移 0 至 3	事务存活	整行有效
3	12	假、假、假、真	是	否
0	0	真、假、假、真	是	否
1	无	真、真、假、真	是	否
2	无	真、真、真、真	否	是

第一拍后，地址 12 的值 62 已经返回。此时再次读 12 得到 FORWARD，也返回 62；目标列表只剩地址 0。再读新块首址 16 则得到 ways-reserved：还有空闲 MSHR，但唯一的路仍在接收块 0，不能抢走。

第二拍以后，所有现有等待目标都已得到结果，仍然要接收第三、第四拍。若这时直接删除记录，下一次 deliver 就找不到原身份。若为了“修复”而允许仅凭事务序号或组号投递，又可能把迟到数据写进另一个新事务。这两种错误都来自把目标列表为空误当成整行传输结束。

另一个错误是第一拍后就把整行设为有效。假定初始数据数组中偏移 0 仍是零，接着读地址 0，普通命中便会错误返回 0，而真正内存值为 11。逐字标记不是性能附加信息，而是部分填充期间的可读性证据。

为了谈时间，再额外规定一个服务模型：一条已经发出的事务第一字在 $L$ 时间后到达，其后每隔 $\tau>0$ 到达一个字；排列不影响 $L,\tau$ ，没有其他事务争用，也没有错误重传。初始偏移为 $c$ 时，自然顺序加提前返回的等待是

L+c\tau,

关键字优先加提前返回的等待是 $L$ ；两种排列的整行完成都在 $L+(K-1)\tau$ 。例如 $L=20,\tau=2,K=4,c=3$ ，初次读取分别等 26 与 20，整行都在 26 完成。若两者都坚持整行到齐才回答，改变排列不会得到这里的六单位收益。

这个例子也能显示后来请求的代价：偏移 0 在自然顺序的 20 时刻到达，旋转顺序则在 22 到达。若硬件不支持旋转突发、首字选择需要额外开销，或者下层存在排队，必须重建时间模型，不能直接移植上述公式。

推论与应用

参考程序提供独立的 BeatCache，没有给它整行 complete 接口。单字交付可乱序，重复偏移、旧身份和复制身份都原子拒绝。 $K=1$ 时第一拍也是最后一拍，此时提前返回与完整安装恰好重合；没有必要为这个退化情形强行声称性能差异。

等待目标的容量随实际响应释放。若 $T=1$ ，先等偏移 3，交付该字以后就可以让另一个尚未到达字的读取进入目标列表；即使 $K$ 还有三个字没来，也无需一直把已返回请求算成占槽。对已到达字的 FORWARD 更不占槽。与此同时，MSHR 和路容量要直到最后一字才释放，三种资源的寿命不可混记。

参考 deliver 扫描未决表和最多 $T$ 个目标，构造响应与剩余目标列表，通常为 $O(M+T)$ ；最后一拍还删除未决项，并可能释放长度 $K$ 的接收数组，含回收的成本为 $O(M+T+K)$ 。响应批次另占 $O(t+1)$ 空间， $t$ 是本拍完成数。逐字标记为每条事务增加 $O(K)$ 空间，数据则已经放在保留路中，没有再复制一份整行缓冲。critical_order 创建长度 $K$ 的元组，时间和输出空间都是 $O(K)$ 。

把所有 $K$ 拍相加，线性扫描参考程序的最坏开销可以达到 $O(K(M+T))$ ；这不意味着硬件每拍都必须串行扫描全部目标，也不抵消按每拍精确归属证明的意义。若改成按偏移组织目标队列或用并行比较，需要另写结构与资源成本。

终点任务要求同时交出请求返回表、整行有效位和未决记录寿命。只画“CPU 继续执行”的箭头会漏掉最关键的检查：它继续依赖的字必须真的到达，而未完成的整行仍要有唯一所有者。

参考资料

Princeton COS375, Fall 2015, Cache lecture，PDF 第 32 页 “Block Size Increase: Fill Time”。区分所需字一到就继续与先请求所需字这两种机制；本文的逐字身份和回收协议是明确给出的教学模型。
David Kroft, “Lockup-Free Instruction Fetch/Prefetch Cache Organization,” ISCA, 1981：原论文。逐字目标识别和返回数据的相关原始设计背景。

形式陈述 ​

反向链接

形式陈述