从局部性出发系统掌握 Cache 的块、行与地址结构,比较三种映射方式,梳理替换算法、容量计算和读写策略,并能分析一次 Cache 访问流程。

Cache 是主存的高速、小容量副本,通常由 SRAM 实现。它并不改变程序可见地址空间,而是利用时间局部性和空间局部性减少 CPU 等待主存的平均时间。408 中必须把 “地址映射”“命中判定”“替换” 和 “写一致性” 作为一条连续链条掌握。

# 一、基本原理与术语

# 1. 局部性与块传送

  • 时间局部性使刚访问的内容值得在 Cache 中保留,例如循环体内反复访问的指令和变量。
  • 空间局部性使相邻内容值得随目标数据一起调入,例如顺序访问数组。

故 Cache 与主存以同样大小的块为单位交换数据,而非按单个字节交换。

名称含义
主存块主存中参加 Cache 交换的一段连续数据
Cache 块Cache 中存放一个主存块副本的数据区域
Cache 行Cache 的一行,包含数据块和该块的元数据
块大小一个块含有的字节数;决定块内偏移位数
块内偏移在已经命中某块后,定位块内具体字节或字的地址部分

若块大小为 B=2bB=2^b B,则块内偏移为 bb 位:

b=log⁡2B.\boxed{b=\log_2B}.

# 2. 命中、缺失与平均访问时间

访问地址时,Cache 先检查候选行中是否存在有效且标记匹配的主存块:

  • 命中(hit):直接从 Cache 取得数据;
  • 缺失(miss):访问主存并把相应主存块调入 Cache,必要时替换旧块。

若命中率为 hh,Cache 命中时间为 TcT_c,缺失时总访问主存所需时间为 TmT_m,在常见串行访问模型下:

Tavg=hTc+(1−h)Tm.\boxed{T_{\mathrm{avg}}=hT_c+(1-h)T_m}.

也常写为

Tavg=Tc+(1−h)Pmiss,\boxed{T_{\mathrm{avg}}=T_c+(1-h)P_{\mathrm{miss}}},

其中第二式的 “缺失代价” 必须按题目定义:它可能是额外的主存等待,而不是完整主存访问时间。

flowchart TD
    A[CPU 给出物理地址] --> B[由映射字段定位候选行或组]
    B --> C{valid 为 1 且 tag 匹配?}
    C -->|是| D[命中:按块内偏移取数据]
    C -->|否| E[缺失:访问主存块]
    E --> F{有空行?}
    F -->|是| G[装入空行并更新元数据]
    F -->|否| H[按替换策略选牺牲行]
    H --> I{回写且该行 dirty?}
    I -->|是| J[先写回主存]
    I -->|否| K[装入新主存块]
    J --> K
    G --> D
    K --> D

# 二、主存块到 Cache 的映射

设主存块号为 kk,Cache 共有 MM 行。映射方式规定一个主存块允许被放到 Cache 的哪些位置,并在命中率、比较硬件和访问延迟之间权衡。

# 1. 直接映射

主存块只能映射到唯一的一行:

i=kmodM.\boxed{i=k\bmod M}.

其中 ii 为目标 Cache 行号。硬件只需定位一行并比较一次 tag,速度快、成本低;但多个块若模 MM 相同,就会不断争用同一行,即使其他行空闲也会发生冲突缺失。

# 2. 全相联映射

任意主存块可放入任意 Cache 行。冲突最少,但查询时必须把地址 tag 与所有有效行并行比较,并由选择器选出命中数据;若全满还须在整个 Cache 范围执行替换。它的硬件成本和延迟最高。

# 3. 组相联映射

mm 路组相联把 MM 行划分为 M/mM/m 个组,每组 mm 行。主存块先唯一映射到一组:

s=kmod(M/m),\boxed{s=k\bmod(M/m)},

其中 ss 为目标组号。

再可放入该组任意一路。它在直接映射和全相联之间折中。

mm 路组相联的含义是 “每组有 mm 行”,不是 “Cache 一共有 mm 组”。

映射方式主存块可放位置tag 比较器数量是否需选择器冲突与复杂度
直接映射唯一一行1通常不需要冲突多、硬件最简单
mm 路组相联指定组内任意一路mm需要适中
全相联任意一行Cache 行数个需要冲突最少、硬件最复杂

关联度描述一个主存块可放置的行数:全相联 >> 组相联 >> 直接映射。关联度升高可降低冲突缺失,但比较器、选择器和替换逻辑的代价也随之上升。

例题 3.6:组相联映射

Cache 容量为 256KB256\mathrm{KB},块大小为 64B64\mathrm{B},采用四路组相联。第 10000 个主存块映射到哪一组?

【解】 Cache 总行数为

256KB64B=4096.\frac{256\mathrm{KB}}{64\mathrm{B}}=4096.

四路组相联的组数为 4096/4=10244096/4=1024,故

10000mod1024=784.10000\bmod1024=\boxed{784}.

该主存块可放入第 784 组中的任意一路。

# 三、物理地址与 Cache 行结构

# 1. 地址字段

从命中判定角度,物理地址可逻辑拆为:

Tag∣Index∣Offset.\boxed{\mathrm{Tag}\mid\mathrm{Index}\mid\mathrm{Offset}}.

字段作用位数
块内偏移在已命中块内定位数据log⁡2B\log_2B,其中 BB 为块大小(B)
块匹配字段缩小可能命中的行集合直接映射为 log⁡2M\log_2M;全相联为 0;组相联为 log⁡2S\log_2S,其中 MM 为行数、SS 为组数
Tag与候选行保存的 tag 比较,确认是否真命中物理地址位数减去其余字段位数

例如直接映射的地址格式为

Tag∣Line∣Offset,\mathrm{Tag}\mid\mathrm{Line}\mid\mathrm{Offset},

组相联则把行号换为组号;全相联没有中间的行号或组号字段。

# 2. Cache 行的元数据

一条 Cache 行不只有数据块,还需元数据控制访问:

字段作用
valid 有效位为 1 表示该行保存着可用于比较的有效数据
tag 标记标识该行缓存的是哪个主存块
dirty 脏位回写法中表示数据是否已被修改、替换前是否需写回
reference 访问位或替换信息服务于 LRU、Clock 等替换算法
data block 数据块主存块的副本

若题目要求计算 Cache 总容量,应把题目指定的 tag、valid、dirty 和替换位一起计入;若题目明确不计某字段,也不可擅自加入。数据区容量与 “整个 Cache 实现所需位数” 不是同一概念。

设共有 LL 行,每块为 BB B,数据区容量为 LBLB B;若每行附加元数据共 qq bit,则实现所需总位数为

L(8B+q).\boxed{L(8B+q)}.

# 四、块替换

直接映射中候选位置唯一,缺失时新块直接覆盖原行,无需选择算法。全相联和组相联在候选集合已满时,才需要从候选行中选出牺牲块。

替换的一般过程为:

  1. 根据映射方式确定候选集合;
  2. 在其中检查所有 valid 为 1 的行的 tag;
  3. 命中则返回数据并更新必要的替换信息;
  4. 未命中而存在 valid 为 0 的空行时,优先装入空行;
  5. 候选集合已满时,依据替换策略选牺牲行;若采用回写且牺牲行 dirty 为 1,先写回主存。
策略思想典型元数据
Random随机挑选无
FIFO淘汰最早调入者常由组维护次序
LRU淘汰最近最少使用者需记录最近使用次序
LFU淘汰访问次数最少者访问计数器
Clock根据访问位循环寻找候选每行常用 1 位访问位

教材型题目若规定 mm 路组相联采用 LRU,常按每行 log⁡2m\log_2m 位替换信息计算。例如 2 路、4 路、8 路时分别为 1、2、3 位;实际硬件可有更复杂实现,应以题设为准。

# 五、写策略

读操作缺失需要决定如何装入;写操作还要保证 Cache 与主存副本的一致性。写策略通常分 “写命中” 和 “写未命中” 两个维度。

# 1. 写命中

策略动作特点
直写法 Write Through同时写 Cache 和主存一致性直观,但主存写流量大,常配写缓冲
回写法 Write Back先只更新 Cache,替换该行时再写主存多次修改可合并为一次主存写,必须维护 dirty 位

# 2. 写未命中

策略动作
写分配 Write Allocate先把对应主存块调入 Cache,再写 Cache
非写分配 Not Write Allocate不调入 Cache,直接写主存

常见配对为 “直写 + 非写分配” 与 “回写 + 写分配”。前者倾向直接更新主存,后者倾向在 Cache 中聚集局部写入;这只是常见组合,不应理解为逻辑上唯一允许的组合。

例题 3.7:写策略判断

某 Cache 采用回写法。一行数据被 CPU 修改后,随后该行被替换。替换时应如何处理?

【解】 回写法下修改先停留在 Cache,故该行的 dirty 位被置为 1。替换前必须将该 Cache 块的内容写回对应主存块,随后才能装入新块。若 dirty 位为 0,则不需要这次写回。

# 六、易错点小结

  1. 块内偏移只由块大小决定,与三种映射方式无关。
  2. 直接映射的 “行号” 不是 tag;行号定位候选行,tag 才确认该行是否保存所需主存块。
  3. 全相联没有 index 字段,不等于没有 tag。
  4. 替换算法只对全相联或组相联的满候选集合有意义;直接映射直接覆盖。
  5. 回写法必须有脏位;直写法通常不需要依靠脏位决定写回。
  6. 命中率公式中的时间含义必须先读清题设,避免把 “缺失代价” 和 “完整主存时间” 混用。