Lecture 10：知识 - Cache

描述：Cache 以局部性换取速度：CPU 先在小而快的 Cache 中找，未命中才按块访问主存。高频题是地址分解、映射方式、关联度、替换、写策略和平均访问时间。

3.1 局部性与基本工作过程

3.1.1 时间局部性和空间局部性

• 数组应尽量按其存储顺序遍历。例如二维数组按行优先存放时，内层循环连续改变列下标，通常比跨行跳跃更具空间局部性。
• 循环体中的指令通常连续存放，内循环又反复执行，因而既有空间局部性也有时间局部性。

3.1.2 块、行、标记与有效位

• 主存与 Cache 都划分为大小相等的块；Cache 的块称Cache 行，块含多个字节，长度为块长/行长。
• Cache 容量远小于主存，只保存主存活跃块的副本。每行至少有：数据区、标记（tag）和有效位（valid）；标记说明该行来自哪个主存块，有效位说明行内容是否可用。
• CPU–Cache 之间按本次指令要求的访问粒度交换（可为字节、半字、字等，教材常简写为“按字”），Cache–主存之间按块交换。把一整块调入的依据是空间局部性。

3.1.3 读写命中与 TLB 关系

• 在操作系统与硬件正确维护页表、TLB 和 Cache 一致性的普通模型中，有效 TLB 命中可作为当前可用映射，针对本次正常访问的 Cache 命中也建立在可用地址转换之上。因此 408 常规模型不列出“TLB 命中而页表无有效映射”或“发生缺页却 Cache 命中”等组合；页表已修改但旧 TLB 项尚未失效属于过期翻译错误，不是正常命中路径。
• TLB/Cache 缺失处理可由硬件完成；教材简化模型中，TLB 未命中需查驻主存的页表，实际页表项读取也可能被 Cache 命中，不一定每次访问 DRAM。在源 PDF 采用的普通透明 Cache 模型中，正常访问时的查找、填充和替换流程由硬件管理。

3.2 命中率与平均访问时间

定义：#命中率

设 $N_c$ 为 Cache 命中次数，$N_m$ 为未命中次数：

$$H=\frac{N_c}{N_c+N_m},\qquad \text{缺失率}=1-H$$

若 $T_C$ 为命中时间、$T_M$ 为未命中时的总访问时间，则：

$$T_{avg}=H\times T_C+(1-H)\times T_M$$

• 若 Cache 未命中需“先查 Cache 再查主存”，则 $T_M$ 应包含已经花掉的 Cache 查找时间，不能只写主存时间。
• 例：若主存速度是 Cache 的 1/5（即 $T_M$ 的主存部分为 $5T_C$），命中率 $0.95$，且未命中再访问主存，则 $T_{avg}=0.95T_C+0.05(T_C+5T_C)=1.25T_C$；相对只用主存的 $5T_C$，平均访问时间约缩为四分之一。

3.3 三种地址映射

3.3.1 直接映射

主存每个块只能进入唯一 Cache 行：

$$\text{Cache 行号}=\text{主存块号}\bmod\text{Cache 总行数}$$

• 若主存块号低 $c$ 位为行号，主存块号其余高 $t$ 位为 tag，则 $t=\text{主存块号位数}-c$。
• 访问时用中间行号找到唯一行，比较行内 tag 与地址高位 tag，并检查有效位；相同且有效则命中，再用低位块内偏移取数据。否则取整块主存数据覆盖该行，不需要替换算法。

3.3.2 全相联映射

主存任一块可进入任一 Cache 行。地址只有 tag + 块内偏移，访问时需并行比较所有行的标记，常借助按内容寻址的相联存储器。

全相联在 Cache 满时需全局替换；主存–外存层因缺失 I/O 代价极高，常采用全相联思想以减少频繁外存调入。

3.3.3 $N$ 路组相联映射

把 Cache 分为若干组，每组 $N$ 行。主存块先按直接映射确定唯一组，再可放入该组任意一路：

$$\text{组号}=\text{主存块号}\bmod\text{组数}$$

• 地址划分为 tag + 组号 + 块内偏移；同组内的 $N$ 个 tag 并行比较，命中后由块内偏移读数据。
• 一组满了才在组内替换。它在直接映射的快/省与全相联的高命中之间折中，是现代 Cache 常见组织。

题型：#地址位数与映射计算

给定主存地址位数 $A$、块大小 $B=2^b$ 字节、Cache 数据区容量 $C$、关联度 $N$：

$$ \begin{aligned} \text{块内偏移位}&=b\ \text{Cache 总行数}&=C/B\ \text{组数}&=(C/B)/N\ \text{组号位}&=\log_2(\text{组数})\ \text{tag 位}&=A-b-\text{组号位} \end{aligned} $$

例：32 位按字节编址、块 64 B、数据区 32 KB、8 路组相联：偏移为 6 位；总行数 $32KB/64B=512$，组数 $512/8=64$，组号 6 位，tag 为 $32-6-6=20$ 位。

• 求某字节地址的主存块号，先除以块大小；直接映射行号为“块号模总行数”；组相联组号为“块号模组数”，具体可落在该组的任一路。
• 计算 Cache 总容量时不要漏掉 tag、有效位与脏位等控制位：总行数 × (数据位 + tag 位 + 控制位)。

2018 年原页图题：TLB、页表与物理地址 Cache

原 PDF 第 3 页的图题给出 32 位虚拟地址（20 位虚页号、12 位页内地址）、两级页表（虚页号拆为 10 位页目录索引与 10 位页表索引）、全相联 TLB，以及 2 路组相联、按物理地址查找的 Cache。由图中字段可还原访问链：

虚拟地址：20 位虚页号 | 12 位页内地址
                ↓ TLB 命中取实页号；未命中则查两级页表
物理地址：16 位实页号 | 12 位页内地址（共 28 位）
                ↓ 按物理地址拆分
Cache 地址：20 位 tag | 3 位组号 | 5 位块内偏移

• 主存物理地址为 $16+12=28$ 位，按字节编址时可表示 $2^{28}$ B，即 256 MiB。TLB 对虚页号采用全相联匹配；TLB 通常用 SRAM 等高速电路实现，而页表驻留在主存中的部分通常使用 DRAM，不应把两者的存储介质混同。
• Cache 的块长是 $2^5=32$ B，组号 3 位表示 $2^3=8$ 组；2 路意味着每组 2 行，共 $8\times2=16$ 行，数据区容量 $16\times32=512$ B。图中虚页号 0x00324 的有效 TLB 项给出实页号 0xF800；若页内偏移为 0，则物理地址 0xF800000 对应 tag=0xF8000、组 0、偏移 0，可与图中组 0 的有效 Cache 行匹配。
• 若题目只计每行 1 位有效位、20 位 tag、1 位脏位，且 2 路 LRU 用每组 1 位记录最近使用路，则 Cache 总容量为 $16\times(256+20+1+1)+8=4456,bit=557,B$。原 PDF 的 $(1+20+1+1+2^5\times8)\times2=558,bit$ 只乘了每组 2 行，漏掉 8 组；它还把 LRU 位按每行 1 位计。若刻意沿用原图的“每行 1 个替换位”简化口径，修正组数后为 $16\times279=4464,bit$，而不是全 Cache 仅 558 bit。实际硬件总量还取决于额外控制位的约定。

源 PDF 数值例题复算

1. 32 位按字节编址、32 KB 数据 Cache、块长 64 B、8 路组相联：块内偏移 6 位；共 $32,KB/(64,B\times8)=64$ 组，组号 6 位，tag 为 20 位。数组 int s[1024] 从 0x008000C0 开始，占 $4,B\times1024/64,B=64$ 个主存块，起始地址分解为 tag=0x00800、组号=3、块内偏移=0。顺序执行一次 s[k]=2*s[k] 时，每块含 16 个元素；忽略写策略额外访问，首次读入每块各缺失一次，因此共有 64 次强制缺失，其余块内访问命中。
2. 主存地址空间 256 MB、直接映射 Cache 有 8 行、每行数据 64 B，且每行只有 1 个有效位：地址 28 位、偏移 6 位、行号 3 位、tag 19 位；每行总位数为 $512+1+19=532$，Cache 含数据和标记项的总容量为 $8\times532=4256,bit$。tag 计算应减去行号位，不能把有效位误当地址字段。
3. 对十进制地址 3200，主存块号为 $3200/64=50$。直接映射到 $50\bmod8=2$ 号行；若改为 2 路组相联，共 4 组，映射到 $50\bmod4=2$ 号组，可放入该组两路中的任一路。
4. 在上题直接映射结构中，地址 0x0123456 的 28 位写作 0000 0001 0010 0011 0100 0101 0110，拆成 19 位 tag | 3 位行号 | 6 位偏移：行号为 001，偏移为 010110。访问时先查 1 号行的有效位与 tag，命中后再按偏移取字节。

若主存地址为 32 位、块长 16 B、Cache 有 4K 行，只计算 tag 位而暂不计有效/脏位，则关联度越高、组号越短、tag 越长：直接映射、2 路、4 路、全相联的 tag 分别为 16、17、18、28 位，对 4K 行的 tag 总开销分别是 64K、68K、72K、112K bit。

3.4 关联度与替换算法

定义：#关联度

一个主存块可映射到的 Cache 行数。直接映射关联度为 1，全相联为 Cache 总行数，$N$ 路组相联为 $N$。

• Cache–主存缺失代价比主存–外存缺失小得多，因此 Cache–主存可采用直接映射换速度；主存–外存更重视避免缺失，适合高关联度映射。

Cache 缺失可按 3C 模型分为：

提高关联度主要减少冲突缺失，并不会自动消除强制缺失或容量缺失；块过大也可能减少有效行数，不能只按“空间局部性”无限增大块长。

• LRU 的一种年龄计数实现：令 0 表示最近使用。命中年龄为 $k$ 的行时，把原先比它更新、年龄小于 $k$ 的有效行年龄加 1，再把命中行置 0；装入新行时将其他有效行年龄加 1、新行置 0，淘汰年龄最大的行。具体硬件也可用栈、伪 LRU 等近似实现。
• 直接映射位置唯一无选择，不用替换算法；全相联在全局替换，组相联只在组内替换。

源 PDF 用 4 行 Cache 和访问序列 1,2,3,4,1,2,5,1,2,3,4,5 演示替换。按图中具体随机选择，RA 命中 5 次、缺失 7 次；FIFO 命中 2 次、缺失 10 次；严格 LRU 命中 4 次、缺失 8 次。RA 的结果依随机选择而变，不能把图中一次轨迹当作固定结论。

表中“命中/缺失”分别是 12 次访问的次数，不是命中率分数。FIFO 命中不改变装入先后；LRU 命中会更新最近使用次序；LFU 按累计访问次数淘汰，同频时必须先约定行号或 FIFO 等平局规则。本例 LFU 的首次满载替换在 3、4 两块同频时选择 3，因此不同平局规则可能得到不同轨迹。

3.5 Cache 写策略

3.5.1 写命中

• 写缓冲一般由 SRAM FIFO 实现：CPU 先把待写信息放入缓冲，由专门控制电路逐项写主存，可掩盖部分慢写延迟。

3.5.2 写不命中

• 写分配的代价是每次写不命中都要读入整块；是否值得取决于后续是否还会访问附近数据。

3.6 多级 Cache

• 现代机器常有 L1、L2（以及更低层）Cache：越靠近 CPU，越快越小；越远越慢越大。L1 常分离为指令 Cache 与数据 Cache，主要目的是减少流水线中取指与访存的资源冲突。
• 教材常举“L1 对 L2 全写、L2 对主存回写”的组合，以便由 L2 吸收频繁写；真实处理器也大量采用各级回写、不同包含关系与一致性协议。各级 Cache 之间是否写分配同样取决于实现，不能把“全写 + 非写分配”视为统一标准。

相关知识

• 科目导航：计算机组成原理导航
• 阅读顺序：上一篇：主存储器 · 下一篇：虚拟存储器
• 关联专题：虚拟内存与局部性

3.7 本节复盘

• Cache 按块与主存交换、按 CPU 指令的字节/半字/字等粒度提供数据；tag 指明主存块来源，有效位判定行是否可用，局部性是其效果基础。
• 直接映射最快最简单但冲突大；全相联命中率高但比较慢且贵；$N$ 路组相联折中。关联度越高，命中率潜力越高、判定和 tag 开销也越大。
• 命中率 $H=N_c/(N_c+N_m)$，平均时间按命中/未命中时间加权；地址题先算偏移、行/组数、tag，再计算控制位容量。
• 直接映射无需替换；RA/FIFO/LRU/LFU 的依据分别是随机、调入先后、近期使用、累计频率。写命中区分回写/全写，写不命中区分写分配/非写分配。