Cache地址映射

考情分析

三种映射方式的地址结构和各字段计算常以大题出现。组相联是实际使用最广泛的方案，也是出题重点。

大纲定位

考纲第三章（六）「高速缓冲存储器（Cache）」第 2 条：Cache 和主存之间的映射方式。

要求到什么程度：不只是"知道有三种映射"，而是给定 Cache 参数和一个具体主存地址，能算出它落在哪一行/哪一组、标记是多少、Cache 总容量是多少。大题里这几问经常连着出。

地址结构基础

访问 Cache 时，主存地址被分为三个字段：

$$[\underset{\mathrm{高}\mathrm{位}}{\underbrace{\text{tag（标记）}}}\underset{\mathrm{中}\mathrm{位}}{\underbrace{\text{index（组/行号）}}}\underset{\mathrm{低}\mathrm{位}}{\underbrace{\text{offset（块内偏移）}}}]$$

• offset：由块大小决定，块大小为 $2^b$ 字节，则 offset 占 $b$ 位
• index：由 Cache 行数/组数决定
• tag：剩余高位，存在 Cache 的标记字段中，用于命中判断

位数不够，还要会写位区间

真题的给分点常要求写成 $[\text{高}:\text{低}]$ 的位区间形式，只答"18 位"会丢分。换算规则很简单——从第 0 位开始，由低到高依次排：

$$\text{offset}=[b-1:0],\text{index}=[b+s-1:b],\text{tag}=[m-1:b+s]$$

其中 $m$ 是主存地址总位数，$b$ 是 offset 位数，$s$ 是 index 位数。

从地址到字段值：三个必备换算

上面算的都是位数。但真题给的往往是一个具体的字节地址，问它落在哪一组、标记是多少——要的是取值。这三个换算必须能默写：

$$\text{主存块号}=\lfloor \frac{\text{字节地址}}{\text{块大小}}\rfloor$$$$\text{Cache 组号（或行号）}=\text{主存块号}modS(S=\text{组数，直接映射时}=\text{行数})$$$$\text{tag}=\lfloor \frac{\text{主存块号}}{S}\rfloor$$

反过来，由 tag 和组号可以重构回主存块号，用来检验：

$$\text{主存块号}=\text{tag}\times S+\text{组号}$$

编者注（易错）：不能拿字节地址直接对组数取模。必须先除以块大小剥掉块内偏移，再取模。这一步做错，后面全错。

还有一个隐含前提：题目给的常常不是"Cache 有多少行"，而是"Cache 数据容量是多少"。中间隔了一步：

$$\text{Cache 行数}=\frac{\text{Cache 数据容量}}{\text{块大小}},\text{组数 }S=\frac{\text{行数}}{k}$$

单位也要先统一。题目说"块大小 4 个字、每字 32 位"时，先折成字节：$4\times 32÷8=16$ B。

直接映射

规则：主存块 $i$ 只能映射到 Cache 行 $imodN$（$N$ 为 Cache 总行数）。

$$\text{Cache 行号}=\text{主存块号}modN$$

图 7.27 cache 和主存之间的直接映射方式

图中 Cache 有 $2^c$ 行，主存有 $2^m$ 块。第 0 块、第 $2^c$ 块、第 $2\times 2^c$ 块……都只能落在第 0 行——相隔 $N$ 个块的主存块争同一行。

地址结构：

$$[\underset{\mathrm{高}\mathrm{位}}{\underbrace{\text{tag}}}\underset{{\log }_{2}N\text{位}}{\underbrace{\text{index（行号）}}}\underset{{\log }_2\text{块大小}\text{位}}{\underbrace{\text{offset}}}]$$

特点：

• 实现简单，比较快（只需检查一行）
• 冲突严重：主存中间隔 $N$ 个块距离的不同块，都映射到同一行，会相互驱逐（抖动）
• 命中率相对较低

例：Cache 8 行，块大小 64 B，主存地址 32 位。

• offset：${\log }_{2}64=6$ 位，位区间 $[5:0]$
• index：${\log }_{2}8=3$ 位，位区间 $[8:6]$
• tag：$32-6-3=23$ 位，位区间 $[31:9]$

全相联映射

规则：主存块可以放到 Cache 中任意一行。

图 7.30 全相联映射方式下主存块和 cache 行对应关系

注意图下方的地址划分：全相联的标记字段就是整个主存块号，没有中间的 index 段。

地址结构：

$$[\underset{\mathrm{高}\mathrm{位}}{\underbrace{\text{tag（即主存块号）}}}\underset{{\log }_2\text{块大小}\text{位}}{\underbrace{\text{offset}}}]$$

没有 index 字段（没有行号约束）。

特点：

• 灵活，冲突率最低，命中率最高
• 查找时需要与所有行的 tag 同时比较（全相联比较），硬件开销大
• Cache 较大时，比较器数量很多，通常只在小型 Cache（如 TLB）中使用

组相联映射

规则：Cache 被分为 $S$ 组，每组 $k$ 行（$k$ 路组相联）。主存块 $i$ 映射到组 $imodS$，在该组内可以放任意一行。

$$\text{Cache 组号}=\text{主存块号}modS$$

图 7.32 组相联映射方式下主存块和 cache 行对应关系

这张图把地址划分和块映射画在了一起：主存地址 = 标记 8 位 + cache 组号 3 位 + 块内地址 9 位，其中标记与组号合起来才是主存块号（图下方的花括号）。主存按 8 块一组分成"组群"，第 $j$ 组群的第 $t$ 块落在第 $t$ 组。

查找通路：

图 7.31 组相联映射方式的硬件实现

图中是 2 路组相联的实现，编号对应五个动作：① 用组号选中一组 → ② 把地址中的标记与该组两行的 tag 分别送比较器 → ③ 比较结果与有效位 V 相与 → ④ 命中的那一路打开三态门放出数据 → ⑤ 两路的命中信号相或得到 hit，并经多路选择器输出。$k$ 路组相联就是 $k$ 个比较器并联，这也是硬件开销随 $k$ 增长的原因。

特点：

• 比直接映射冲突少（同一组内有 $k$ 个位置可选）
• 比全相联硬件开销小（只需 $k$ 路比较器）
• $k=1$ 时退化为直接映射，$k=N$（组数 $S=1$）时退化为全相联
• 实际 CPU 中最常用（2 路、4 路、8 路组相联）

例：4 路组相联，Cache 共 16 行（4 组），块大小 64 B，主存地址 32 位。

• offset：${\log }_{2}64=6$ 位
• index（组号）：${\log }_{2}4=2$ 位（$S=16/4=4$ 组）
• tag：$32-6-2=24$ 位

三种映射对比

特性	直接映射	全相联	组相联（$k$ 路）
映射规则	固定行	任意行	固定组内任意行
index 字段	行号	无	组号
tag 位数	最少	最多	居中
比较器个数	1	行数	$k$
冲突率	高	最低	低
硬件复杂度	简单	复杂	中等
命中率	低	最高	高
典型用途	早期设计	TLB	现代 CPU Cache

Cache 总容量

算完 tag 位数不算完——大题几乎必接一问"Cache 总容量是多少"。总容量不只是数据区，每行还要带标记和若干控制位：

$$\text{每行位数}=\underset{\text{有效位 V}}{\underbrace{1}}+\underset{\text{tag}}{\underbrace{t}}+\underset{\text{数据}}{\underbrace{8\times \text{块大小}}}+\underset{\text{脏位，仅回写策略}}{\underbrace{[1]}}+\underset{\text{替换算法位}}{\underbrace{[\cdot ]}}$$$$\text{总容量}=\text{行数}\times \text{每行位数}$$

编者注（易错）：脏位只在回写（write back）策略下才有，写直达没有脏位。替换算法位是否计入要看题目是否提到替换算法——题目没说就不加。只答数据区容量是最常见的丢分点。

交互可视化

加载可视化中...

加载可视化中...

加载可视化中...

解题动作清单

映射这一块的真题分两型，起手式不同，先判是哪一型。

第一型：给参数求各字段位数

1. 写出主存地址总位数 $m$（按字节寻址时 $m={\log }_2$（主存容量/字节））
2. 单位统一：把"字""双字"折成字节
3. offset $={\log }_2$（块大小字节数）
4. 行数 $=$ Cache 数据容量 $÷$ 块大小（题目直接给行数就跳过）
5. index：直接映射取 ${\log }_2$（行数）；组相联取 ${\log }_2$（组数），组数 $= $ 行数 $÷k$；全相联为 0
6. tag $=m-\text{index}-\text{offset}$
7. 写成位区间：offset $=[b-1:0]$，index $=[b+s-1:b]$，tag $=[m-1:b+s]$
8. 若问总容量：每行位数 $=$ 有效位 $+$ tag $+$ 数据 $(+$ 脏位 $)$，再乘行数

第二型：给具体地址问落在哪、标记多少

1. 先判题给的是字节地址还是块号——给块号的话块内偏移已经剥离，直接跳到第 3 步
2. 主存块号 $=\lfloor$ 字节地址 $÷$ 块大小 $\rfloor$
3. 组号（行号）$=$ 主存块号 $modS$
4. tag $=\lfloor$ 主存块号 $÷S\rfloor$
5. 反代检验：$(\text{tag}\times S+\text{组号})\times \text{块大小}+\text{块内偏移}$ 应还原成原地址

完整走查例题

题：按字节编址，主存地址 32 位。Cache 采用 4 路组相联，数据容量 64 KB，块大小 64 B，采用回写策略。 (1) 各字段位数与位区间？(2) 字节地址 0000 8B3CH 落在哪一组，标记是多少？(3) Cache 总容量？

(1) 先补出行数和组数这两个中间量：

$$\text{行数}=\frac{64\text{KB}}{64\text{B}}=1024,S=\frac{1024}{4}=256$$

• offset $={\log }_{2}64=6$ 位 $\Rightarrow [5:0]$
• index $={\log }_{2}256=8$ 位 $\Rightarrow [13:6]$
• tag $=32-6-8=18$ 位 $\Rightarrow [31:14]$

(2) 0000 8B3CH $=35644$。

$$\text{块号}=\lfloor \frac{35644}{64}\rfloor =556,\text{块内偏移}=35644-556\times 64=60$$$$\text{组号}=556mod256=44,\text{tag}=\lfloor \frac{556}{256}\rfloor =2$$

反代检验：$(2\times 256+44)\times 64+60=556\times 64+60=35584+60=35644$ ✓

(3) 回写策略，所以每行要带脏位：

$$\text{每行位数}=1+18+64\times 8+1=532\text{bit}$$$$\text{总容量}=1024\times 532=544768\text{bit}=68096\text{B}=66.5\text{KB}$$

数据区只有 64 KB，标记和控制位又占掉 2.5 KB——这就是"总容量 $>$ 数据容量"的来源。

考点清单

• 直接映射 index = 行号，组相联 index = 组号，全相联无 index
• 块号 $=\lfloor$ 字节地址 / 块大小 $\rfloor$，不能拿字节地址直接取模
• tag $=\lfloor$ 块号 / 组数 $\rfloor$；反过来 块号 $=$ tag $\times$ 组数 $+$ 组号
• 行数 $=$ 数据容量 / 块大小，是从"容量"到"位数"的必经中间步
• 给分点常要位区间 $[\text{高}:\text{低}]$，不是只要位数
• 总容量 $=$ 行数 $\times$（有效位 $+$ tag $+$ 数据 $+$ 脏位），脏位仅回写才有
• $k$ 路组相联需要 $k$ 个比较器；$k=1$ 是直接映射，$k=$ 行数是全相联

教材出处

• 袁春风《计算机组成与系统结构（第 3 版）》§7.5 高速缓冲存储器：图 7.27（p238）、图 7.30（p241）、图 7.31 / 图 7.32（p243）

真题练习

相关真题（25题）

2026Q182分2026Q192分2025Q4312分2024Q172分2023Q4314分2022Q162分2021Q162分2021Q448分2020Q152分2020Q4410分2019Q467分2018Q4415分2016Q152分2016Q4513分2015Q152分2015Q162分2014Q162分2013Q162分2013Q439分2012Q172分2011Q4412分2010Q172分2010Q4412分2009Q142分2009Q212分

上一篇Cache 基本概念下一篇Cache 替换策略