物理寻址与命中判定 —— 一个物理地址怎么在缓存里找到数据
本篇是缓存组织拆分的寻址与命中篇：讲清为什么缓存按物理地址组织（PIPT）、物理地址怎么拆成 Tag/Index/Offset 三段，以及命中判定为何是一套并行硬件电路而非程序。配套一篇"32KB/8-way/64B"的算例，把位数公式落到真实配置上。阅读前提：熟悉虚拟地址/物理地址概念；映射结构（直接映射/全相联/组相联）见映射结构篇，逐级下探与时钟域见访问流程篇。
一、前提：缓存按物理地址组织
程序访问用虚拟地址(VA)，但 VA 先经 MMU + TLB 查页表翻译成物理地址(PA)，缓存再拿 PA 来查（PIPT）。用 PA 而非 VA 的原因：同一物理页可能被多个虚拟地址映射（共享内存、多进程共享 .so）——用 VA 索引会让同一份数据在缓存里存多份且互不一致（aliasing）。
现代 L1 常用 VIPT（VA 低位做索引、PA 做 tag，让查 TLB 和查缓存并行以省延迟），但对外语义等价物理寻址。下文按"物理地址寻址"讲。
TLB 本身也是一层缓存,也会 miss。 VA→PA 翻译若 TLB miss,要走一次几十上百拍的 page walk——它能主导整个程序性能(一个"迭代次数不变、只改步长却暴跌 5 倍"的经典实验),详见 tlb。
二、物理地址拆成三段
缓存不是按地址挨个存、逐个比对，而是把物理地址切成三段，用中间段直接算出"只可能在哪一组"，再比对 tag。这样查找是 O(1)。
| 段 | 决定它的因素 | 作用 |
|---|---|---|
| Offset | cache line 大小（64B → 6 位） | 字节在 line 内的偏移 |
| Index | 组数 set 数（S 组 → log₂S 位） | 直接算出落在哪一组，不查找 |
| Tag | 剩下的高位 | 存在行元数据里，确认该组某条行是不是目标 |
位数公式（物理地址共 m 位）：
Offset 位数 b = log2(行大小) 如 64B → 6 位
Index 位数 s = log2(组数) 如 64 组 → 6 位
Tag 位数 = m - s - b 剩下全给 tag三、命中判定：一套硬件电路，不是一段程序
先纠正一个常见误解：缓存查找不是 CPU 执行一段代码去"遍历比对"，而是由专门的硬件电路在一个时钟周期内完成的组合逻辑。没有指令、没有循环、没有先后——地址一送进来，电路"通电"就同时出结果。所以缓存命中判定是真正的 O(1)（准确说是"一个门延迟级别"）。
判定要素还是那三步，但每一步对应的是电路而非运算：
| 逻辑步骤 | 硬件实现 | 代价 |
|---|---|---|
| 拆 Tag/Index/Offset | 纯连线：把地址总线的不同位分接到不同模块 | 零（只是布线） |
| Index → 选中一组 | 译码器(decoder) | 一级门延迟 |
| 组内 W 条 tag 与目标比对 | W 个比较器(comparator)同时通电比 | 并行，一个周期 |
| tag 相等 且 valid=1 | 每路一个 AND 门 | 并行 |
| 汇总"有没有命中"+ 选出数据 | OR 门(是否命中) + 多路选择器 MUX(选中那条的数据) | 并行 |
硬件数据通路（组相联，W 路）
要点：图里 W 个比较器是同时工作的——不是"比完第 0 路再比第 1 路"，而是所有 way 的 tag 一起送进各自比较器、同一瞬间出结果，OR 门一汇总就知道命不命中。way 数 W 越大 = 比较器越多 = 芯片面积和功耗越大，这正是相联度不能无限提高的物理原因。
逻辑等价的伪代码（仅用来说明"电路算什么"）
下面这段 C 不是缓存的实现，缓存里没有 CPU 去跑它——它只是把上面那套电路"要判定什么"用大家熟悉的语法写出来，帮助理解。真实硬件里，for 那几路是并行的，不存在循环的先后：
// ⚠️ 这是电路逻辑的“文字描述”，不是运行的程序
struct Line { bool valid; uint64_t tag; int state; uint8_t data[64]; };
struct Set { Line way[W]; }; // 一组 = W 条 line
Set cache[S]; // 整个缓存 = S 组
// 地址三段：纯取位（硬件是分线，不是移位运算）
int offset = pa & ((1<<B)-1);
int index = (pa >> B) & (S-1); // 译码器：选组
uint64_t tag = pa >> (B + log2(S)); // 高位：送去比较
Set *set = &cache[index];
for (int w = 0; w < W; w++) // 硬件里这 W 路【同时】比，不是循环
if (set->way[w].valid && set->way[w].tag == tag) // 比较器 + AND门
return HIT(w); // OR门汇总 + MUX 选数据
return MISS;三个别被伪代码误导的点：
- 拆三段是"分线"不是"运算"：
pa & mask、pa >> B在硬件里就是把地址总线的某几根线直接接到对应模块，没有 ALU 参与、零延迟。 - 那个
for在硬件里是并行的：W 个比较器 + W 个 AND 门同时出结果，一个周期内 OR 门就汇总完。伪代码写成循环只是语法所限。 - 命中 =
valid && tag 相等两个条件都满足：valid=0 表示这条 line 是空的/被失效过（如被别的核 invalidate），即使 tag 恰好相等也不算命中。
数字 demo：查地址 0xD6 在不在
用一个便于手算的小缓存：8 位物理地址、line = 4 字节、直接映射 4 组（即 B=2, S=4, 每组 1 条）。手算就是"硬件把这几根地址线怎么分"：
地址 0xD6 = 1 1 0 1 0 1 1 0 (二进制)
└──┬──┘ └┬┘ └┬┘
Tag Idx Off
bit7:4 3:2 1:0电路一次到位（下面写成"步骤"只为讲解，硬件是同时发生）：
· 取 bit[1:0] = 0b10 = 2 → Offset，MUX 最后按它选行内第 2 字节
· 取 bit[3:2] = 0b01 = 1 → Index，译码器选中第 1 组
· 取 bit[7:4] = 0b1101=0xD → Tag，送进比较器
· 比较器：cache[1].tag == 0xD ? 且 cache[1].valid==1 ?
都成立 → hit 信号=1，MUX 输出 cache[1].data[2]
否则 → miss 信号=1，触发去 L2/内存取整条 line 填进 cache[1]换成 8 路组相联时，Index 定到第 1 组后，该组 8 个比较器同时把各自 way 的 tag 和 0xD 比，8 个 AND 门 + 一个 OR 门汇总——仍是一个周期出 hit/miss。这就是"如何根据 PA 判断数据是否在 cache"的硬件真相。
cache 里存了物理地址吗？—— 没有，Index 隐含、只存 Tag
一个自然的疑问：既然用物理地址来判断"在不在"，cache 里存了这个地址吗？否则怎么确认某条 line 装的就是地址 PA 的数据？
答案：cache 不存完整物理地址，每条 line 只存 Tag。复原一个地址要三段，但三段的信息来源不同：
| 段 | 从哪来 | 存进 cache 吗 |
|---|---|---|
| Index | 由这条 line 待在第几组"隐含"表达 | ❌ 不存 |
| Tag | 显式存在这条 line 的元数据里 | ✅ 存 |
| Offset | 只定位行内第几字节，与"是不是这条 line"无关 | ❌ 不存 |
核心洞察：一条 line 待在第几组，本身就等于记住了它的 Index。 因为规则是"只有 Index==组号的地址才会被放进这一组"——所以看到某条 line 在第 1 组，就知道它的 Index 一定是 1，无需再存。于是 cache 只额外存 Tag，就能和"隐含的 Index"拼出完整地址来判断：
用 0xD6 的例子复原：0xD6 = 1101 01 10，落在第 1 组。cache[1] 里只存了 tag=1101 + valid，既没存 01(Index)、也没存整段 11010110。判定时：译码器用 Index=01 选中第 1 组（这一步就"用掉"了 Index）→ 比 cache[1].tag(1101)==查询Tag(1101) → 相等且 valid → 命中。要复原这条数据的地址高 6 位，就是 组号01 拼 tag1101 = 110101——Index 从"它在第几组"免费得到，不必存。
为什么这么设计？省存储。若每条 line 都存完整 48 位物理地址，几千条 line 光地址就好几 KB 纯开销；而 Index 由位置隐含、免费，只需存 Tag（高位那几十位）。这也带出一个连带规律：相联度越高 → Index 位越少 → Tag 越长 → 每条 line 的 tag 存储开销越大（全相联无 Index，整段高位都得进 tag，这是全相联"贵"的原因之一，见映射结构篇）。
一句话：cache 不存完整地址，只存 Tag；Index 由"数据落在第几组"隐含表达，Offset 与身份无关。译码器用 Index 选组、比较器比 Tag，两者合起来唯一确定物理地址——既能判定，又省存储。
地址能"唯一精准定位"到一条 line 吗？——定位到组是精准的，组内不是
一个常见直觉：给一个物理地址，cache 里就有它唯一、精准、确定的位置。这半对半错——必须把"组"和"组内 way"分开看：
| 定位到 | 由什么决定 | 是否唯一精准 |
|---|---|---|
| 哪一组 (set) | Index，从地址算出来 | ✅ 唯一、精准、确定——同一地址永远落同一组 |
| 组内哪条 way | 数据装入时由替换策略动态选的空槽 | ❌ 不唯一（除非直接映射） |
分结构看：
- 直接映射（每组 1 条 line）：组 = 唯一位置，所以"地址 → 唯一精准位置"成立。
- N 路组相联：地址只能精准定位到一个组，它在组内 N 条 way 的哪一条不确定——所以查找时才要"组内并行比 N 个 tag"去找。如果地址能直接算出唯一 way，就根本不需要比 tag 了。
- 全相联：地址连组都不限定，可能在任意 line。
关键因果：正因为地址不能唯一确定组内 way，才需要 Tag 比对——Tag 的作用就是"在这一组的 N 个候选里，认出到底哪条（如果有）是我"。
一句话："算到组"是精准唯一的（Index 决定，O(1) 译码）；"组内定到 way"要靠比 tag（不是算的）。两步合起来——算到组 + 比出 way——才唯一确定一条 line。 只有直接映射因为"每组就 1 条"，才让地址直接等于唯一位置。
一条 cache line 里到底存了什么（不只是数据和 Tag）
除了 64B 业务数据和 Tag，每条 line 还挂着一串元数据(metadata)——这些位是缓存能正确工作的关键：
| 字段 | 作用 | 何时需要 |
|---|---|---|
| Valid | 这条 line 有没有装有效数据（空的/被 invalidate 过则为 0） | 总是 |
| Tag | 地址高位，命中判定用（见上一节） | 总是 |
| Dirty | 缓存里改过、比内存新（write-back 用，决定驱逐时要不要写回） | 写回缓存 |
| MESI 状态 | 多核一致性状态 M/E/S/I | 多核（单核只需 valid+dirty，见 mesi） |
| 替换位 | LRU/PLRU 的"年龄"，组满时决定踢谁 | 组相联/全相联 |
| （ECC 校验位） | 检错纠错 | 看设计 |
注意：MESI 状态其实包含了 valid/dirty 的信息——I 就相当于 invalid，M 就相当于 dirty。所以多核缓存里，"valid+dirty"和"MESI 状态位"往往合二为一，用几个状态位统一表达。这些位对软件完全透明，但命中判定要看 valid、驱逐要看 dirty、一致性协议要看 MESI、替换要看 LRU 位——业务数据只是 line 的一部分。
miss 之后：填充与替换
miss 之后由缓存控制器（也是硬件状态机，非软件）去下一级取数据、按替换策略腾位置：
要点：命中 O(1)；miss 且组满时按替换策略踢一条，若踢的是脏行(MSI 的 M 态)要先写回——这就是"驱逐(evict)触发写回"。
四、算例：32KB / 8-way / 64B 的各段位数
设：物理地址 48 位，L1 数据缓存 32 KB、8 路组相联、cache line 64 B。
① 每组大小 = 8 way × 64 B = 512 B
② 组数 S = 32 KB / 512 B = 64 组
③ Offset 位 b = log2(64) = 6 位
④ Index 位 s = log2(64) = 6 位
⑤ Tag 位 = 48 − 6 − 6 = 36 位于是一个 48 位物理地址被这样解读：
47 ............... 12 | 11 ...... 6 | 5 ..... 0
└──── Tag (36) ──────┘└─ Index(6) ─┘└ Offset(6)┘给你一个地址，硬件取 bit[11:6] 作 Index 选中 64 组里的某组，取 bit[5:0] 作行内偏移，剩下 bit[47:12] 和该组 8 条 way 的 tag 并行比对——匹配且 valid 即命中。这就是"如何根据物理地址判断是否在 cache"的完整答案。
这个配置正是现代服务器 CPU 一个核的 L1d 典型量级——真实容量与组织（L1/L2 私有、L3 共享）见访问流程篇。
五、通往映射结构
地址的三段拆法、命中判定的硬件电路都讲完了，还剩一个关键问题没回答：地址允许落在组内哪几条 way？ 直接映射只许 1 条、全相联许全部、组相联许 N 条——三种结构怎么取舍、冲突失效怎么产生，就是下一篇映射结构篇的主题。