非阻塞缓存与未决缺失合并

形式陈述

一次缺失已经发往下层，结果还没有回来。此时另一条读取恰好命中缓存，为什么也要跟着停住？若第三条读取需要同一条尚未返回的缓存行，又是否值得再发一次请求？非阻塞缓存把“当前正在服务哪次读取”拆成若干份未决记录，使这些情况能分别处理。

先固定一个可以完整证明的只读模型。下层内存是含 $N$ 个无符号 32 位字的不可变数组 $A$ 。每个缓存行有 $K$ 个字， $K\mid N$ ；缓存有 $S$ 组，每组 $W$ 路。 $K,S$ 是正的二次幂， $W\ge1$ 。一次 read(a) 的字节地址 $a$ 必须是四的倍数，且 $0\le a<4N$ 。分解为

u=a/4,\qquad b=\lfloor u/K\rfloor,\qquad o=u\bmod K,\qquad s=b\bmod S.

$b$ 是块号， $o$ 是块内字偏移。命中必须同时满足所在组、完整块身份和有效位，不能只比较组号。每路保存数据、有效位、块号、最近使用时间，以及可为空的保留者身份。

至多有 $M\ge1$ 条未决事务，每条至多保存 $T\ge1$ 个等待目标。未决记录又称 MSHR，保存独立事务身份、块号、占用的组与路，以及等候它的请求列表。每个已接收读取都有不同的不可变请求身份；两个读取即使地址相同，也应得到各自的一次响应。事务身份与请求身份不是同一件事：一个事务可以服务多个目标。

参考接口按以下顺序作决定。每次调用是一个原子事件；驱动器可以在两次调用之间任意选择下一件事，但没有并发修改内部数组。

HIT。 先查有效驻留行。命中就返回新请求身份及一个值，并更新最近使用时间。此分支不需要空闲 MSHR。
MERGE。 未命中却有相同块的未决事务，且其目标列表未满：添加新请求，返回原事务身份，不再发第二次下层请求。目标满时返回 RETRY / target-full。
MISS。 这是新块，且有空闲 MSHR 和未被保留的路：按替换策略选位置。本页先取编号最小的无效路；否则在合格驻留路中取最近使用时间最小者，平局取最小路号。旧行立即失效，这一路保留给新事务，直到填充结束。返回新请求与新事务身份。
RETRY。 新块遇到全局 MSHR 满，返回 mshr-full；尚有 MSHR、但该组所有路都被保留，返回 ways-reserved。这三种资源重试都不接收请求，也不改变任何状态，包括序号、替换次序和内部记录。

complete(t) 接受一个当前存活的、由本对象发出的原事务身份。它从可信的 $A$ 取得整行，填入保留路，使该路有效；按原列表次序返回每个等候请求及其所要的字，再释放 MSHR 和保留关系。错误类型、另一个缓存的身份、字段完全相同的复制品，以及已经完成的旧身份都在修改前拒绝。实际返回值不能由调用方随意传入。

保证是按请求身份而非按完成顺序给出的：每个已接收请求恰好返回一次，返回值为 $A[a/4]$ 。HIT 在接收事件返回；MERGE 与 MISS 在其事务完成事件返回。假如每条已接收事务最终都会完成，则每个已接收读取最终都返回。RETRY 本身没有活性承诺，调用者若需要它最终成功，还须有重试公平性和资源最终可用的条件。

直觉

可以把 MSHR 看成一张“货还在路上”的登记单。上面除了货物编号，还写着谁在等、各自要哪一部分，以及货到以后放在哪个位置。新的顾客若要同一批货，只加入登记单；要已经在架上的货，则当场取走。

两条独立未决事务分别保留缓存位置；同块读取合并为两个目标，另一条事务先完成 — 请求身份、事务身份与保留路分别记账

这里有两个常被混淆的容量。MSHR 数量限制正在等待多少个不同块；每条目标列表长度限制多少次读取可以等同一块。还有第三个约束：一个组的路都被占作填充位置时，即使全局仍有空闲 MSHR，也不能再接收映射到该组的新块。

正确性可以逐事件归纳。初始没有未决事务，所有行无效。假定事件前满足四条不变量：

每个未决块只有一条事务，每个被保留的路只有一个事务所有者
有效行不被保留，且数据逐字等于它所标记的内存块
每个尚未返回的已接收请求，恰在一条对应块的目标列表中
已返回请求不再留在任何目标列表中

HIT 只读正确的有效行，生成新身份并立即返回，不加入等待集合。MERGE 只往已找到的唯一同块列表添加新身份。MISS 在检查资源后才分配，选择的路没有所有者，因此不会破坏另一个事务的归属；旧驻留值失效后不可再被命中。complete 找到原身份的唯一记录，将可信整行安装到它仍拥有的位置，把整张目标列表移出等待集合并返回。释放记录以后，旧身份再也找不到，故不能重复响应。失败与重试不改状态，也保持不变量。

这份证明没有要求先来的事务先返回。内存不变，所以两个不同块的返回次序不会改变任何读取值。它也没有证明处理器能够越过任意数据依赖，更没有给寄存器提交、异常或多核可见性作保证；这里的调用者只是能够持有多个独立读取的事件驱动器。

例子与边界

取 $K=4,S=2,W=2,M=2,T=2$ ，令 $A[i]=17i+11$ 。字节地址 $0,16,32,48$ 分别是块 $0,1,2,3$ 的首字。

先读取地址 0 并完成填充。随后读 16，建立块 1 的事务；读 0 立即 HIT；读 20 合并进块 1 的目标列表。再读 24 时目标已满，返回 target-full，不能悄悄丢掉此前等待者，也不能为块 1 再建一条事务。

接着读 32，建立第二条事务。现在再读新块首址 48 得到 mshr-full，但重读驻留地址 0 仍然可以命中。先完成块 2，再完成块 1，返回地址及值依次是

(32,147),\qquad(16,79),\qquad(20,96).

返回次序不同于接收次序，请求身份却不会混淆。包括预热在内，真正发往下层的事务只有三条，而不是每次未命中读取都发一条。

单独把配置改成 $S=1,W=2,M=3$ ：先接收两个不同块的缺失，二者占满该组两路。第三个新块失败的原因是 ways-reserved，不是 MSHR 不够。若错误地把保留路当成普通 LRU 牺牲品，两条事务会指向同一个物理位置；较晚的一次填充可能覆盖较早但尚未正确消费的数据，所有权归纳从这里断开。

$M=1$ 仍允许等待期间的驻留命中与同块合并，只是不允许第二个不同块同时在途。 $T=1$ 则使第二个同块等待者暂时重试。重复读取同一地址也占不同的目标身份，因为调用者仍在等待两次响应。

本页没有写缓冲、脏行、取消、总线错误、地址转换、失效消息或缓存一致性。若内存会变化，仅凭不可变 $A$ 的证明已不足够；若需要取消，还要定义目标何时退出、迟到结果如何识别，以及存储位置何时可重用。Kroft 原始 lockup-free 设计处理了更多情况，包含逐字转发、写入和过时记录管理；这里特意采用更容易审计的整次填充保留一路教学策略，不宣称复现原设计或 gem5。

推论与应用

完整参考程序中的 WholeLineCache 实现上述合同，六项任务要求分别交出接收、合并、重试和完成记录。返回批次交给调用者，缓存内部不保存随运行增长的完成日志。请求上的 origin 只区分 demand 与 prefetch 标签，不改变取值语义。

令 $r\le M$ 是当前未决数， $t\le T$ 是本次响应数。参考实现线性扫描组路和未决列表，命中查找为 $O(W)$ ，合并查找为 $O(W+M)$ ；目标列表追加是摊还常数，若要求一次调用的最坏 Python 列表扩容成本，应再加 $O(T)$ 。新缺失还初始化 $K$ 个接收标记，故为 $O(W+M+K)$ 。整行完成包括寻找与删除列表记录、复制 $K$ 个字以及构造 $t$ 个结果，为 $O(M+K+t)$ 。这些是软件事件成本，不能当成硬件组合电路的周期数。

数据数组占 $SWK$ 个字，路元数据占 $O(SW)$ 。共享参考框架还给每条未决事务保留 $K$ 个接收标记，即使整行模式暂不使用其中的部分有效状态；因此内部辅助空间为 $O(M(K+T+1))$ ，不是只算 MSHR 头部的 $O(M)$ 。下层不可变内存的复制占 $O(N)$ ，构造总成本为 $O(N+SWK)$ 。返回批次、调用者保存的旧身份和诊断快照另计；snapshot() 与 check() 遍历数据和目标，未参与每次正常转移。

以上按可容纳地址和计数器的字操作计费。参考程序的序号与时间戳单调增长，运行 $E$ 个事件后需要 $O(\log(E+1))$ 位，任意精度整数运算不能在无界运行中永久按常数位成本计算。程序明确限制几何与输入数组规模，并拒绝布尔值冒充地址或容量；这些有限校验边界不是硬件容量标准。

非阻塞允许重叠等待，能否转化为更短程序时间还取决于独立请求、下层服务能力、资源冲突和真正的关键依赖。增加 MSHR 只能扩大可同时接收的集合，不能从安全不变量推出吞吐翻倍。

参考资料

David Kroft, “Lockup-Free Instruction Fetch/Prefetch Cache Organization,” ISCA, 1981：原论文。未决状态、目标识别与乱序返回的历史来源；本文保留路策略和只读整行协议另行定义并证明。
gem5 项目，Classic Caches 官方文档。说明非阻塞缓存中的 MSHR、写缓冲以及索引/替换分工；不作为本教学机的逐事件规范。

形式陈述 ​

反向链接

形式陈述