从局部性出发系统掌握 Cache 的块、行与地址结构,比较三种映射方式,梳理替换算法、容量计算和读写策略,并能分析一次 Cache 访问流程。
Cache 是主存的高速、小容量副本,通常由 SRAM 实现。它并不改变程序可见地址空间,而是利用时间局部性和空间局部性减少 CPU 等待主存的平均时间。408 中必须把 “地址映射”“命中判定”“替换” 和 “写一致性” 作为一条连续链条掌握。
# 一、基本原理与术语
# 1. 局部性与块传送
- 时间局部性使刚访问的内容值得在 Cache 中保留,例如循环体内反复访问的指令和变量。
- 空间局部性使相邻内容值得随目标数据一起调入,例如顺序访问数组。
故 Cache 与主存以同样大小的块为单位交换数据,而非按单个字节交换。
| 名称 | 含义 |
|---|---|
| 主存块 | 主存中参加 Cache 交换的一段连续数据 |
| Cache 块 | Cache 中存放一个主存块副本的数据区域 |
| Cache 行 | Cache 的一行,包含数据块和该块的元数据 |
| 块大小 | 一个块含有的字节数;决定块内偏移位数 |
| 块内偏移 | 在已经命中某块后,定位块内具体字节或字的地址部分 |
若块大小为 B,则块内偏移为 位:
# 2. 命中、缺失与平均访问时间
访问地址时,Cache 先检查候选行中是否存在有效且标记匹配的主存块:
- 命中(hit):直接从 Cache 取得数据;
- 缺失(miss):访问主存并把相应主存块调入 Cache,必要时替换旧块。
若命中率为 ,Cache 命中时间为 ,缺失时总访问主存所需时间为 ,在常见串行访问模型下:
也常写为
其中第二式的 “缺失代价” 必须按题目定义:它可能是额外的主存等待,而不是完整主存访问时间。
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 的映射
设主存块号为 ,Cache 共有 行。映射方式规定一个主存块允许被放到 Cache 的哪些位置,并在命中率、比较硬件和访问延迟之间权衡。
# 1. 直接映射
主存块只能映射到唯一的一行:
其中 为目标 Cache 行号。硬件只需定位一行并比较一次 tag,速度快、成本低;但多个块若模 相同,就会不断争用同一行,即使其他行空闲也会发生冲突缺失。
# 2. 全相联映射
任意主存块可放入任意 Cache 行。冲突最少,但查询时必须把地址 tag 与所有有效行并行比较,并由选择器选出命中数据;若全满还须在整个 Cache 范围执行替换。它的硬件成本和延迟最高。
# 3. 组相联映射
路组相联把 行划分为 个组,每组 行。主存块先唯一映射到一组:
其中 为目标组号。
再可放入该组任意一路。它在直接映射和全相联之间折中。
路组相联的含义是 “每组有 行”,不是 “Cache 一共有 组”。
| 映射方式 | 主存块可放位置 | tag 比较器数量 | 是否需选择器 | 冲突与复杂度 |
|---|---|---|---|---|
| 直接映射 | 唯一一行 | 1 | 通常不需要 | 冲突多、硬件最简单 |
| 路组相联 | 指定组内任意一路 | 需要 | 适中 | |
| 全相联 | 任意一行 | Cache 行数个 | 需要 | 冲突最少、硬件最复杂 |
关联度描述一个主存块可放置的行数:全相联 组相联 直接映射。关联度升高可降低冲突缺失,但比较器、选择器和替换逻辑的代价也随之上升。
例题 3.6:组相联映射
Cache 容量为 ,块大小为 ,采用四路组相联。第 10000 个主存块映射到哪一组?
【解】 Cache 总行数为
四路组相联的组数为 ,故
该主存块可放入第 784 组中的任意一路。
# 三、物理地址与 Cache 行结构
# 1. 地址字段
从命中判定角度,物理地址可逻辑拆为:
| 字段 | 作用 | 位数 |
|---|---|---|
| 块内偏移 | 在已命中块内定位数据 | ,其中 为块大小(B) |
| 块匹配字段 | 缩小可能命中的行集合 | 直接映射为 ;全相联为 0;组相联为 ,其中 为行数、 为组数 |
| Tag | 与候选行保存的 tag 比较,确认是否真命中 | 物理地址位数减去其余字段位数 |
例如直接映射的地址格式为
组相联则把行号换为组号;全相联没有中间的行号或组号字段。
# 2. Cache 行的元数据
一条 Cache 行不只有数据块,还需元数据控制访问:
| 字段 | 作用 |
|---|---|
| valid 有效位 | 为 1 表示该行保存着可用于比较的有效数据 |
| tag 标记 | 标识该行缓存的是哪个主存块 |
| dirty 脏位 | 回写法中表示数据是否已被修改、替换前是否需写回 |
| reference 访问位或替换信息 | 服务于 LRU、Clock 等替换算法 |
| data block 数据块 | 主存块的副本 |
若题目要求计算 Cache 总容量,应把题目指定的 tag、valid、dirty 和替换位一起计入;若题目明确不计某字段,也不可擅自加入。数据区容量与 “整个 Cache 实现所需位数” 不是同一概念。
设共有 行,每块为 B,数据区容量为 B;若每行附加元数据共 bit,则实现所需总位数为
# 四、块替换
直接映射中候选位置唯一,缺失时新块直接覆盖原行,无需选择算法。全相联和组相联在候选集合已满时,才需要从候选行中选出牺牲块。
替换的一般过程为:
- 根据映射方式确定候选集合;
- 在其中检查所有 valid 为 1 的行的 tag;
- 命中则返回数据并更新必要的替换信息;
- 未命中而存在 valid 为 0 的空行时,优先装入空行;
- 候选集合已满时,依据替换策略选牺牲行;若采用回写且牺牲行 dirty 为 1,先写回主存。
| 策略 | 思想 | 典型元数据 |
|---|---|---|
| Random | 随机挑选 | 无 |
| FIFO | 淘汰最早调入者 | 常由组维护次序 |
| LRU | 淘汰最近最少使用者 | 需记录最近使用次序 |
| LFU | 淘汰访问次数最少者 | 访问计数器 |
| Clock | 根据访问位循环寻找候选 | 每行常用 1 位访问位 |
教材型题目若规定 路组相联采用 LRU,常按每行 位替换信息计算。例如 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,则不需要这次写回。
# 六、易错点小结
- 块内偏移只由块大小决定,与三种映射方式无关。
- 直接映射的 “行号” 不是 tag;行号定位候选行,tag 才确认该行是否保存所需主存块。
- 全相联没有 index 字段,不等于没有 tag。
- 替换算法只对全相联或组相联的满候选集合有意义;直接映射直接覆盖。
- 回写法必须有脏位;直写法通常不需要依靠脏位决定写回。
- 命中率公式中的时间含义必须先读清题设,避免把 “缺失代价” 和 “完整主存时间” 混用。
