缓存块、标记与直接映射

形式陈述

缓存保存较低层内存中若干连续块的副本。先定义直接映射模型：字节地址宽度为 $A$ ，块大小 $B=2^b$ 字节，数据容量 $C$ ，行数 $S=C/B=2^s$ ，其中 $A\ge b+s$ 。容量C不含tag、valid及其他元数据。

地址按定宽整数的无符号规则解释为 $a\in[0,2^A-1]$ ，再分解为

offset=a\bmod B,\quad q=\lfloor a/B\rfloor,\quad index=q\bmod S,\quad tag=\lfloor q/S\rfloor.

块号q只能放在index指定的唯一缓存行。该行valid为真且保存的tag相等，才命中；否则缺失。缺失后填入的是从 $qB$ 开始的整个块，而不只是请求的那一个word。本文访问不跨块，跨块访问须先拆为覆盖各块的请求。

直觉

index是查哪一行的路标，tag是核对该行目前属于谁的证件，offset是到行内取哪个字节的位置。多个内存块可以有同一个index，所以“找到行”并不等于“找到了数据”。

valid区分“这一行已经有合法副本”和“元数据恰好长得像目标”。冷启动时tag的旧比特值没有意义；不检查valid会把未初始化数据误判为命中。

例子与边界

取 $A=32,C=32$ B、 $B=8$ B。共有四行，offset占3位，index占2位，tag占27位。地址 $0x2c=44$ 对应块号5、index=1、tag=1、offset=4，块基址是 $0x28$ 。

地址 $0x0c$ 的index也为1、offset也为4，但tag为0。若只比较index，这两个地址会被误认为同一个缓存内容。回写逐出行时，反向重建块地址应使用旧tag： $base=(tag\cdot S+index)B$ ，不能用新请求的tag。

冷启动后依次读取 $0x00,0x20,0x00,0x20$ 。它们的块号为0、4、0、4，全部映到index=0。每次都替换前一个块，所以四次全缺失，另三行一直空着。这是位置约束造成的冲突，不能用“总共只有两个块，小于容量四块”来证明命中。

把第二个独立对象的基址改为 $0x28$ ，两对象分别映到index=0和1。重复同样的对象交替读取，前两次填入，后两次命中。程序的逻辑访问顺序没变，物理布局改变了冲突。

地址 $0x00$ 与 $0x04$ 位于同一八字节块的两个word。第一次读0x00填整块后，0x04也可命中。但取得四个字节后如何组成寄存器值，还要按字节序解释；tag/index/offset没有完成这一步。

推论与应用

组相联保留按index找组的规则，让每组有多个候选行。写策略另决定何时把修改传播到下层，二者是不同设计轴。

外存模型按块传输计费，却未施加这里的直接映射约束；理想缓存又允许全相联和最优替换。不能拿理想缓存中可同时驻留的两个块，直接断言它们在此映射下不会冲突。

参考资料

UC Berkeley CS61C，Direct Mapped Cache，课程笔记，访问于 2026-10-08，映射、有效位与tag。
David A. Patterson and John L. Hennessy, Computer Organization and Design RISC-V Edition, 2nd ed., 2021，Ch. 5。本文地址配置与布局反例均独立给定。