408 计算机组成原理高频考点精讲:Cache 映射方式(Cache Mapping Schemes)¶
模块归属:计算机组成原理 · 存储系统
考点层级:超高频核心考点(历年总考查 9 次,近十年考查 6 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:6 次(2016 年第 15 题、2018 年第 44 题、2019 年第 46 题、2021 年第 16 题、2022 年第 16 题、2025 年第 43 题)
- 历年总考查频次:9 次(含 2009#44、2010#16、2012#43、2016#15、2018#44、2019#46、2021#16、2022#16、2025#43)
- 出题形式:
- 单项选择题:聚焦主存地址字段划分、比较器数量与位宽分析、Cache 单行位数与总容量计算、简单循环遍历的 Cache 缺失率估算。
- 综合应用题(43/44/45 题):作为统考大题的核心枢纽,深度联动虚拟页式存储管理(TLB 映射、页表翻译、物理地址形成)、程序循环访存行为、缺页异常处理以及平均访存时间(AMAT)量化分析。
- 命题特点提炼:
- 物理地址“三段式”切分是底层解题基石:无论直接映射还是组相联映射,必须优先通过“块内偏移位数由块大小确定、组索引位数由 Cache 组数确定、高位全部归入主存标记 Tag”完成物理地址切分。
- Cache 容量维度的严谨区分:命题频繁考查“Cache 数据区容量”与“Cache 总容量(含 Tag、有效位、脏位、替换控制位)”的差异,必须看清设问要求。
- 组相联映射硬件参数的精确考查:高频考查“比较器数量精确等于组内行数(即路数 \(K\))”以及“比较器位宽精确等于 Tag 位数”。
- 软硬件结合与访存行为量化:近十年真题多次引入 C 语言数组循环遍历,深入考查数组首地址非对齐(跨 Cache 块/跨页)、一次迭代内读写复合访存等工程细节。
- 虚拟地址与物理地址协同:深入考查虚拟地址页内偏移与 Cache 索引位的重合区间,引出虚拟索引物理标记(VIPT)机制下的并行查找逻辑。
近十年考查年份分布(2016~2025):
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
√ - √ √ - √ √ - - √
(#15) (#44) (#46) (#16) (#16) (#43)
注:2018#44、2019#46、2025#43 均为 13~15 分的综合应用大题。
二、 具体考察内容¶
1. Cache 映射的核心机理与基本概念¶
高速缓冲存储器(Cache)与主存储器均被划分为大小相等的块(Block),主存中的块通常称为主存块,Cache 中的块通常称为 Cache 行(Cache Line) 或 Cache 槽(Slot)。设块大小为 \(B\) 字节,则主存与 Cache 之间以“块”为单位进行数据调入与写回。
由于主存容量远大于 Cache 容量,主存块数远多于 Cache 行数,主存块映射到 Cache 行必然是多对一的映射关系。Cache 映射机制的作用是建立一套硬件规则,确定特定主存块在调入 Cache 时可以放置在哪些 Cache 行中,以及 CPU 访存时如何在 Cache 中准确定位该主存块。
Cache 不命中(Miss)主要由三种原因引起(3C 模型): 1. 强制缺失(Compulsory Miss / Cold Miss):首次访问该主存块时 Cache 中尚无此数据,必须从主存调入。 2. 容量缺失(Capacity Miss):Cache 总容量有限,无法容纳程序工作集的所有块,先前调入的块被替换出 Cache 后再次被访问所引起的缺失。 3. 冲突缺失(Conflict Miss):在直接映射或组相联映射中,多个主存块争用同一个 Cache 槽位或同一个 Cache 组,即使 Cache 中仍有其他空闲行,目标行已被占用而发生挤占替换所引起的缺失(全相联映射不存在冲突缺失)。
2. 三大地址映射方式详解¶
三种映射方式对比示意:
1. 直接映射 (Direct Mapped)
主存块号 i ----( i mod M )----> 固定映射到 Cache 第 j 行
[ 硬件简单,比较器 1 个,但冲突缺失率高 ]
2. 全相联映射 (Fully Associative)
主存块号 i ------------------> 可映射到 Cache 任意空闲行
[ 灵活性最高,无冲突缺失,但需要 N 个比较器并行比较,硬件代价大 ]
3. 组相联映射 (Set Associative, K-Way)
主存块号 i ----( i mod Q )----> 映射到固定的第 q 组,组内 K 行中任意存放
[ 折中方案,需要 K 个比较器并行比较,性能与成本最佳平衡 ]
(1) 直接映射(Direct Mapping)¶
- 映射规则:每个主存块只能映射到 Cache 中唯一的固定行号。 设 Cache 总行数为 \(M = 2^c\)$ \text{,主存块号为} $\(i\)$ \text{,则映射的 Cache 行号} $\(j\) 为: $\(j = i \bmod 2^c = i \bmod M\)$ 在二进制层面,主存块号的最低 \(c\) 位即为 Cache 行号。
- 物理地址划分: $\(\begin{array}{|c|c|c|} \hline \text{主存标记 (Tag)} & \text{Cache 行号 (Index/Line)} & \text{块内偏移 (Offset)} \\ \hline t \text{ 位} & c \text{ 位} & b \text{ 位} \\ \hline \end{array}\)$
- 硬件判断逻辑:
- 利用物理地址中间 \(c\) 位索引到指定的 Cache 行;
- 读取该行的有效位,若有效位为 1,且该行保存的 Tag 与地址高 \(t\) 位完全一致,则 Cache 命中;
- 若有效位为 0 或 Tag 不匹配,则 Cache 缺失。
- 硬件代价:仅需要 1 个比较器,比较器位宽为 \(t\) 位。
- 优缺点:硬件设计最简、查找延迟最小;但空间利用率低,若两个频繁访问的主存块恰好映射到同一行,将发生剧烈的“抖动”(Thrashing),冲突缺失率极高。
(2) 全相联映射(Fully Associative Mapping)¶
- 映射规则:主存中的每一个块可以映射到 Cache 中的任意一行中。
- 物理地址划分:地址中取消了行号/组号字段,仅保留主存标记与块内偏移。 $\(\begin{array}{|c|c|} \hline \text{主存标记 (Tag)} & \text{块内偏移 (Offset)} \\ \hline t \text{ 位} & b \text{ 位} \\ \hline \end{array}\)$ 其中 \(t = m - b\)(\(m\) 为物理地址总位数)。
- 硬件判断逻辑: 由于主存块可存放在任意行,CPU 访存时必须将物理地址的 Tag 与 Cache 所有行的 Tag 同时进行并行比较。
- 硬件代价:若 Cache 共有 \(N\)$ \text{行,则需要 } $\(N\) 个比较器并行工作,或者采用昂贵、高功耗的相联存储器(CAM,Content-Addressable Memory)。
- 优缺点:空间利用极其充分,完全消除了冲突缺失,命中率最高;但比较电路硬件开销巨大、功耗高、延迟大,通常仅用于容量极小的高速部件,如虚拟存储管理中的页表缓冲器(TLB)。
(3) 组相联映射(Set-Associative Mapping)¶
- 映射规则:将 Cache 划分为 \(Q\)$ \text{个大小相同的“组”(Set),每组包含} $\(K\)$ \text{个 Cache 行,称为 } $\(K\)$ \text{路组相联(} $\(K\)-way Set-Associative)。 主存块映射到固定的“组”,但在组内可任意放置于 \(K\) 个空闲行中的任意一行(“组间直接映射,组内全相联”)。 设 Cache 总组数为 \(Q = 2^s\)$ \text{,主存块号为} $\(i\)$ \text{,则映射的目标组号} $\(q\) 为: $\(q = i \bmod 2^s = i \bmod Q\)$
- 物理地址划分: $\(\begin{array}{|c|c|c|} \hline \text{主存标记 (Tag)} & \text{Cache 组号 (Set Index)} & \text{块内偏移 (Offset)} \\ \hline t \text{ 位} & s \text{ 位} & b \text{ 位} \\ \hline \end{array}\)$
- 硬件判断逻辑:
- 利用物理地址中间 \(s\) 位索引到指定的 Cache 组;
- 将该组内所有 \(K\)$ \text{行的 Tag 与地址高} $\(t\)$ \text{位通过} $\(K\) 个比较器并行比较;
- 若某行的有效位为 1 且 Tag 匹配,则命中该行,通过多路选择器(MUX)输出数据。
- 硬件代价:需要 \(K\)$ \text{个比较器,比较器位宽为} $\(t\) 位。
- 体系演化:
- 当 \(K = 1\) 时,每组只有 1 行,退化为直接映射;
- 当 \(K = N\)(\(N\)$ \text{为 Cache 总行数,此时组数} $\(Q = 1\))时,退化为全相联映射。 现代高性能通用 CPU 的 L1/L2 Cache 普遍采用 4 路、8 路或 16 路组相联映射。
3. 主存物理地址划分位数的系统推导方法¶
给定系统参数:按字节编址,主存物理地址总宽度为 \(m\)$ \text{位,Cache 数据区容量为} $\(C\)$ \text{字节,主存块大小为} $\(B\)$ \text{字节,组相联路数为} $\(K\)。推导步骤如下:
地址划分系统推导逻辑链:
[ 块大小 B ] --------------------------> 块内偏移 b = log2(B)
[ 容量 C / 块大小 B ] ------------------> Cache 总行数 M = C / B
[ 总行数 M / 路数 K ] ------------------> Cache 组数 Q = M / K ---> 组号位数 s = log2(Q)
[ 主存位数 m - s - b ] ----------------> Tag 标记位数 t = m - s - b
- 块内偏移位数(Offset,记为 \(b\)): $\(b = \log_2 B\)$ 例如,块大小 \(B = 64\text{B}\)$ \text{,则} $\(b = \log_2 64 = 6\) 位。
- Cache 总行数(Lines,记为 \(M\)): $\(M = \frac{C}{B}\)$ 例如,Cache 数据区容量 \(32\text{KB}\)$ \text{,块大小} $\(64\text{B}\)$ \text{,则总行数} $\(M = \frac{32 \times 1024}{64} = 512\) 行。
- Cache 组数(Sets,记为 \(Q\)$ \text{)与组号位数(} $\(s\)): $\(Q = \frac{M}{K} = \frac{C}{K \times B}\)$ $\(s = \log_2 Q\)$ 例如,8 路组相联(\(K = 8\)$ \text{),组数} $\(Q = \frac{512}{8} = 64\)$ \text{组,则组号位数} $\(s = \log_2 64 = 6\) 位。
- 主存标记位数(Tag,记为 \(t\)): $\(t = m - s - b\)$ 若主存地址 \(m = 32\)$ \text{位,则} $\(t = 32 - 6 - 6 = 20\) 位。
特别注意: 在全相联映射中,\(s = 0\)$ \text{(无需组号),} $\(t = m - b\); 在直接映射中,\(K = 1\)$ \text{,组数} $\(Q = M\)$ \text{,组号位即行号位} $\(c = \log_2 M\),\(t = m - c - b\)。
4. Cache 行内部结构与总容量精确计算¶
408 统考中对 Cache 容量的考查分为两个截然不同的概念: * Cache 数据区容量(Data Array Capacity):仅统计 Cache 用于缓存主存纯数据的容量,即 \(M \times B\)。 * Cache 总容量(Total Cache Size):物理芯片上实际制造的全部静态存储位,包括数据区与标记项目录区(Tag Directory)。
+------------------------------------------------------------------------------------+
| 单个 Cache 行构成 |
+--------------------+----------------+-------------------+-----------------+--------+
| 有效位 (Valid Bit) | 脏位 (Dirty) | 替换位 (Replace) | 主存标记 (Tag) | 数据区 |
| 1 bit | 0 或 1 bit | r bits | t bits | 8*B bit|
+--------------------+----------------+-------------------+-----------------+--------+
| <------------------------- 标记项 (Tag Directory) ------------------------> | |
+------------------------------------------------------------------------------------+
(1) 标记项各组成部分解析¶
- 有效位(Valid Bit,必占 1 位): 指示当前 Cache 行中的数据是否有效。系统上电复位或发生进程上下文切换清空 Cache 时,所有行的有效位均被初始化置 0。
- 主存标记位(Tag,占 \(t\) 位): 存放该行所缓存主存块的物理地址高 \(t\) 位,用于命中匹配。
- 脏位/修改位(Dirty Bit / Modified Bit):
- 写回策略(Write-Back):必占 1 位。写命中时只更新 Cache,当该行被替换时,根据脏位是否为 1 决定是否写回主存。
- 直写策略(Write-Through):通常为 0 位。因为写命中时同时更新 Cache 和主存,Cache 中的数据始终与主存保持一致,无需维护脏位。
- 替换控制位(Replacement Bits,占 \(r\) 位): 用于记录行替换策略所需的状态信息。
- 直接映射:由于每个主存块只能映射到固定行,不存在行选择问题,因此无需替换位(0 位)。
- 全相联 / 组相联映射:
- LRU 算法(最近最少使用):对于 \(K\)$ \text{路组相联,若采用精确计数器法,组内} $\(K\)$ \text{个行需区分先后次序,每行需维护} $\(\lceil \log_2 K \rceil\) 位计数器(如 2 路需 1 位,4 路需 2 位,8 路需 3 位)。
- FIFO 算法(先进先出):每行维护到达次序,位宽同样为 \(\lceil \log_2 K \rceil\) 位。
- RAND 算法(随机替换):硬件由伪随机数生成器产生替换行索引,行内无需替换位(0 位)。
(2) 精确计算公式¶
- 单个 Cache 行的总位数 \(W_{\text{line}}\): $$ \text{W_{\text{line}} = (8 \times B) + t + 1 + (\text{Dirty}) + (\text{LRU}) \quad (\text{单位: bit})} $$
- Cache 总容量 \(C_{\text{total}}\): $$ \text{C_{\text{total}} = M \times W_{\text{line}} = (Q \times K) \times W_{\text{line}} \quad (\text{单位: bit})} $$ 若题目要求以字节(Byte)表示,则 \(C_{\text{total(Byte)}} = C_{\text{total}} / 8\)。
5. 命中判断硬件逻辑与比较器参数¶
组相联 Cache 访存时的硬件数据通路如下:
CPU 物理地址 [ Tag (t位) | 组号 (s位) | 块内偏移 (b位) ]
| | |
| v |
| +----------+ |
| | 组译码器 | |
| +----+-----+ |
| | |
| 定位到第 q 组 (包含 K 行)|
| | |
| +------+------+ |
| | | |
| Line 0 Line K-1 |
| [Tag_0] [Tag_K-1] |
v | | |
+--------+-----+ | |
| | v |
+--+---+ +--+---+ +---+--+ |
|比较器0| |比较器1| ... |比较器| |
+--+---+ +--+---+ +---+--+ |
| | K-1 |
+---+----+------------------+ |
| |
命中生成逻辑 (Hit Logic) v
| +------------------+
+----------------------->| 数据多路选择器 |<--- 块内偏移
+--------+---------+
|
v
目标字/字节输出
核心考点判定规则:¶
- 比较器的数量: 在组相联映射中,比较器用于在该组内并行比对所有候选行的 Tag。因此,比较器的个数精确等于组内行数,即路数 \(K\)(与 Cache 总行数或总组数无关)。
- 直接映射(\(K = 1\)):需要 1 个比较器。
- \(K\)$ \text{路组相联:需要} $\(K\) 个比较器。
- 全相联映射:需要 \(N\)$ \text{个比较器(} $\(N\) 为总行数)。
- 比较器的位数(位宽): 比较器比较的对象是“CPU 物理地址的 Tag”与“Cache 行中保存的 Tag”,因此比较器的位宽精确等于主存标记 Tag 的位数 \(t\)。
6. 常见替换算法原理与硬件开销对比¶
当 Cache 产生缺失且目标组中所有行均被有效数据占满时,必须通过替换算法淘汰一行以腾出空间。
| 替换算法 | 核心思想 | 硬件开销模型 | 优缺点分析 |
|---|---|---|---|
| LRU (Least Recently Used) |
保护局部性:淘汰最近一段时间内最久未被访问的行 | \(K\)$ \text{路组相联每行需} $\(\lceil \log_2 K \rceil\) 位计数器;访问命中时计数器清零,其余行计数器递增 | 最贴合时间局部性原理,缺失率最低;控制逻辑相对复杂 |
| FIFO (First In First Out) |
队列原则:淘汰最早调入 Cache 的行 | 每行需记录调入次序,位宽为 \(\lceil \log_2 K \rceil\) 位 | 实现简单;无法反映局部性,频繁访问的常驻行可能被错误淘汰(Belady 异常) |
| LFU (Least Frequently Used) |
频次统计:淘汰被访问次数最少的行 | 每行需维护较宽的访问计数器(如 8~16 位),开销大 | 能反映全局频次,但早期高频后不再访问的数据长期滞留,对突发性局部性响应差 |
| RAND (Random) |
随机选择:随机抽取组内一行淘汰 | 依靠伪随机数发生器,行内无需任何附加位(0 位) | 硬件极简;完全未利用局部性,可能淘汰重要数据,缺失率较高 |
三、 近十年真题精讲(2016~2025)¶
1. 2016 年统考 408 真题第 15 题¶
【题号及考查方向】¶
- 题号:2016 年第 15 题
- 考查方向:直接映射 Cache 的数组遍历缺失率定量分析、复合访存指令的访存行为建模。
【题干与选项】¶
有如下 C 语言程序段:
若数组a 以及变量 k 均为 int 型,int 型数据占 4B,数据 Cache 采用直接映射方式,数据区大小是 1KB,块大小是 16B,该程序段执行前 Cache 为空,则该程序段执行过程中,访问数组 a 的 Cache 的缺失率是( )。A. 1.25%
B. 2.5%
C. 12.5%
D. 25%
【详细解析】¶
- 块容纳元素数计算:
主存块大小为 16B,每个
int占 4B,因此每个 Cache 块可以容纳 \(16\text{B} / 4\text{B} = 4\) 个连续的数组元素。 - 单次循环内部访存行为剖析:
语句
a[k] = a[k] + 32;包含两次对数组a[k]的访存操作: - 第一步:读取
a[k]的值(读操作); - 第二步:将计算结果写回
a[k]的内存单元(写操作)。 因此,循环迭代 1000 次,对数组a的总访存次数为: $$ \text{N_{\text{access}} = 1000 \times 2 = 2000 \text{ 次}} $$ - 块内访存缺失规律推导:
考察同一个 Cache 块中存放的 4 个连续元素(如
a[0], a[1], a[2], a[3]): - 读
a[0]:初始未命中,发生 1 次强制缺失,系统将包含a[0]~a[3]的整块调入 Cache; - 写
a[0]:该块已在 Cache 中,命中; - 读
a[1]:已在 Cache 块中,命中; - 写
a[1]:命中; - 读
a[2]、写a[2]、读a[3]、写a[3]:全部命中。 因此,对于每个主存块中的 4 个元素,共引发 \(4 \times 2 = 8\) 次访存,其中仅有第 1 次读操作发生缺失,其余 7 次访问全部命中。 - Cache 容量与冲突判断:
Cache 数据区容量为 1KB,共 \(1\text{KB} / 16\text{B} = 64\)$ \text{行。数组
a占用} $\(1000 \times 4\text{B} = 4000\text{B}\),需要 250 个块。虽然 250 个块超过了 Cache 的 64 行容量,主存块会发生轮换覆盖,但由于本程序为单趟单向顺序线性遍历,已被淘汰的块在后续循环中不会再次被访问,因此冲突替换不会导致重复访问缺失。 - 缺失率计算: 缺失率(Miss Rate)为: $$ \text{Miss Rate} = \frac{\text{缺失次数}}{\text{总访存次数}} = \frac{250}{2000} = \frac{1}{8} = 12.5\% $$
【正确答案】¶
C
2. 2018 年统考 408 真题第 44 题¶
【题号及考查方向】¶
- 题号:2018 年第 44 题
- 考查方向:虚拟存储器与 Cache 联合寻址、TLB 与 Cache 映射方式判定、Cache 标记项与附加位开销计算、物理地址判定与命中判断。
【题干与设问】¶
某计算机采用页式虚拟存储管理方式,按字节编址。CPU 进行存储访问的过程如题 44 图所示。
题 44 图结构简示:
CPU 虚拟地址 (32 位): 虚页号 (20 位, [31:12]) | 页内地址 (12 位, [11:0])
虚页号划分为: 10 位页目录号 + 10 位页表号
[TLB 结构]:
包含若干项,每项包含: Tag (20 位) | 有效位 (1 位) | 实页号 (16 位)
通过全相联并行比较虚页号 Tag
[物理地址合成]:
实页号 (16 位) + 页内地址 (12 位) = 物理地址 (28 位)
物理地址切分为: Tag (20 位) | Cache 组号 (3 位) | 块内偏移 (5 位)
[数据 Cache 结构]:
组号索引到某组,每组包含 2 行:
每行包含: Tag (20 位) | 有效位 (1 位) | Data
配有 2 个比较器与 1 个多路选择器
根据题 44 图回答下列问题:
(1) 主存物理地址占多少位?
(2) TLB 采用什么映射方式?TLB 用 SRAM 还是 DRAM 实现?
(3) Cache 采用什么映射方式?若 Cache 采用 LRU 替换算法和回写(Write Back)策略,则 Cache 每行中除数据(Data)、Tag 和有效位外,还应有哪些附加位?Cache 总容量是多少?Cache 中有效位的作用是什么?
(4) 若 CPU 给出的虚拟地址为 0008C040H,则对应的物理地址是多少?是否在 Cache 中命中?说明理由。若 CPU 给出的虚拟地址为 0007C260H,则该地址所在主存块映射到的 Cache 组号是多少?
【详细解析】¶
- 设问 (1) 解析:
- 方式一:页式管理中,物理地址由实页号与页内地址拼接而成。图中实页号为 16 位,页内地址为 12 位,故物理地址位数为 \(16 + 12 = 28\) 位。
- 方式二:根据图中数据 Cache 的地址切分,物理地址划分为 Tag(20 位)、组号(3 位)、块内偏移(5 位),总位数为 \(20 + 3 + 5 = 28\) 位。
- 设问 (2) 解析:
- TLB 映射方式:TLB 中虚页号进入后与所有项的 Tag 均有对应的比较器进行并行匹配,无固定索引规则,故 TLB 采用全相联映射。
- 存储介质:TLB 要求与 CPU 同频或极低延迟响应,采用静态存储器(SRAM)芯片实现。
- 设问 (3) 解析:
- Cache 映射方式:由图可知,组索引译码后选中一组,组内包含 2 行数据与 2 个比较器并行比较,因此 Cache 采用 2 路组相联映射。
- 附加位分析:
- 采用 2 路组相联 LRU 替换算法:2 行之间只需记录谁是最近使用、谁是最久未使用,因此每行需要 1 位 LRU 替换控制位(或每组 1 位)。
- 采用回写策略(Write Back):为了标记 Cache 行中的数据是否被 CPU 修改过,每行必须包含 1 位脏位/修改位(Dirty Bit)。
- Cache 总容量计算:
- 组号 3 位,总组数 \(Q = 2^3 = 8\) 组。
- 2 路组相联,总行数 \(M = 8 \times 2 = 16\) 行。
- 块内偏移 5 位,块大小 \(B = 2^5 = 32\text{B} = 256\) 位。
- 单个 Cache 行的位数为: $$ \text{W_{\text{line}} = \text{Data}(256\text{b}) + \text{Tag}(20\text{b}) + \text{有效位}(1\text{b}) + \text{脏位}(1\text{b}) + \text{LRU位}(1\text{b}) = 279 \text{ 位}} $$
- Cache 总容量为: $$ \text{C_{\text{total}} = 16 \times 279 = 4464 \text{ 位} = 558 \text{ 字节}} $$
- 有效位的作用:指示当前 Cache 行中的信息是否有效(即是否已经调入了真实有效的主存块数据)。
- 设问 (4) 解析:
- 虚拟地址
0008C040H寻址:- 切分虚拟地址:低 12 位为页内地址
040H,高 20 位为虚页号0008CH。 - 查 TLB 表:第 2 项的 Tag 为
0008CH,且有效位为 1,命中了实页号0040H。 - 拼接物理地址:实页号
0040H拼接页内地址040H,得到 28 位物理地址为0040040H。 - 查 Cache:将物理地址
0040040H按20 + 3 + 5切分: - 低 5 位为块内偏移:
00000B = 0; - 中间 3 位为组号:
010B = 2(组号为 2); - 高 20 位为 Tag:
00400H。 - 比对第 2 组中的 2 行:
- 第 1 行 Tag 为
00400H,但其有效位为 0(无效); - 第 2 行 Tag 为
10040H,Tag 不匹配。 - 结论:在 Cache 中不命中。理由:尽管第 2 组中有一行的 Tag 匹配,但该行有效位为 0,数据无效。
- 切分虚拟地址:低 12 位为页内地址
- 虚拟地址
0007C260H对应 Cache 组号:- 虚拟地址低 12 位为
260H。根据虚拟页式存储原理,虚拟地址与物理地址的低 12 位(页内地址)完全相同。 - 物理地址低 12 位为二进制:
0010 0110 0000B。 - 物理地址中块内偏移占低 5 位(
00000B),紧随其后的 3 位(第 5~7 位)表示 Cache 组号。 - 取第 5~7 位:
011B = 3。因此该主存块映射到的 Cache 组号为 3。
- 虚拟地址低 12 位为
【参考答案汇总】¶
(1) 物理地址占 28 位。
(2) TLB 采用全相联映射;用 SRAM 实现。
(3) Cache 采用 2 路组相联映射;除 Data、Tag、有效位外,还应有脏位(1 位)和 LRU 替换控制位(1 位);Cache 总容量为 4464 位(或 558 字节);有效位的作用是指示所在 Cache 行中的信息是否有效。
(4) 对应的物理地址是 0040040H;Cache 不命中,因为组号 2 中 Tag 匹配的行有效位为 0,另一行 Tag 不匹配;0007C260H 映射到的 Cache 组号是 3。
3. 2019 年统考 408 真题第 46 题¶
【题号及考查方向】¶
- 题号:2019 年第 46 题
- 考查方向:指令 Cache 的 4 路组相联映射、主存物理地址三段式切分、指令地址 Cache 组号精确定位。
【题干与设问】¶
对于上题(题 45 中给出的机器代码),若计算机 M 的主存地址为 32 位,采用分页存储管理方式,页大小为 4KB,则第 1 行的 push 指令(虚拟地址 0040 1000H)和第 30 行的 ret 指令(虚拟地址 0040 107FH)是否在同一页中(说明理由)?若指令 Cache 有 64 行,采用 4 路组相联映射方式,主存块大小为 64B,则 32 位主存地址中,哪几位表示块内地址?哪几位表示 Cache 组号?哪几位表示标记(tag)信息?读取第 16 行的 call 指令(虚拟地址 0040 1025H)时,只可能在指令 Cache 的哪一组中命中(说明理由)?
【详细解析】¶
- 指令是否在同一页的判断:
- 页面大小为 4KB(\(2^{12}\text{B}\)$ \text{),故虚拟地址的低 12 位为页内偏移,高} $\(32 - 12 = 20\) 位为虚拟页号。
push指令虚拟地址0040 1000H,高 20 位虚拟页号为00401H;ret指令虚拟地址0040 107FH,高 20 位虚拟页号为00401H。- 两者的虚拟页号相同,因此两条指令位于同一虚拟页面中。
- 32 位主存物理地址的三段式切分:
- 块内地址:主存块大小为 \(64\text{B} = 2^6\text{B}\),因此块内地址占 低 6 位(即第 0~5 位,
[5:0])。 - Cache 组号:指令 Cache 总行数为 64 行,采用 4 路组相联,因此组数 \(Q = 64 / 4 = 16\)$ \text{组。由于} $\(16 = 2^4\),因此 Cache 组号占 4 位(即第 6~9 位,
[9:6])。 - 主存标记(Tag):物理地址共 32 位,扣除块内地址 6 位与组号 4 位,主存标记占 \(32 - 6 - 4 = 22\) 位,位于 高 22 位(即第 10~31 位,
[31:10])。 call指令在 Cache 中的组号定位:- 读取指令时,CPU 提供虚拟地址
0040 1025H。 - 页大小为 4KB(12 位),在分页虚存体系下,虚拟地址的低 12 位与物理地址的低 12 位完全相同。
call指令虚拟地址的低 12 位为十六进制025H,转换为二进制为: $\(025\text{H} = 0000\ 0010\ 0101\text{B}\)$- 根据第 2 问的地址切分规则:
- 第 0~5 位为块内地址:
10 0101B(37); - 第 6~9 位为 Cache 组号:
0000B(即十进制 0)。
- 第 0~5 位为块内地址:
- 结论:读取该指令时,只可能在指令 Cache 的第 0 组中命中。
【参考答案汇总】¶
- 在同一页中。理由:页大小为 4KB,虚拟地址高 20 位表示虚拟页号,两条指令的虚拟地址高 20 位均为
00401H,页号相同,故在同一页中。 - 32 位主存地址中,第 0~5 位(低 6 位)表示块内地址,第 6~9 位(中间 4 位)表示 Cache 组号,第 10~31 位(高 22 位)表示 Tag 标记信息。
- 只可能在第 0 组中命中。理由:页大小为 4KB,虚拟地址与物理地址的低 12 位完全相同。
call指令地址的低 12 位为025H = 0000 0010 0101B,其中第 6~9 位对应 Cache 组号,取值为0000B,故映射在第 0 组。
4. 2021 年统考 408 真题第 16 题¶
【题号及考查方向】¶
- 题号:2021 年第 16 题
- 考查方向:直接映射 Cache、回写策略下的 Cache 行最小物理位数精确计算。
【题干与选项】¶
若计算机主存地址为 32 位,按字节编址,Cache 数据区大小为 32KB,主存块大小为 32B,采用直接映射方式和回写(Write Back)策略,则 Cache 行的位数至少是( )。
A. 275
B. 274
C. 258
D. 257
【详细解析】¶
- 物理地址字段划分:
- 主存物理地址总宽度为 32 位,按字节编址。
- 主存块大小为 \(32\text{B} = 2^5\text{B}\),因此块内偏移占 5 位。
- Cache 数据区大小为 32KB,每个 Cache 块为 32B,因此 Cache 总行数(块数)为: $$ \text{M = \frac{32\text{KB}}{32\text{B}} = 1024 = 2^{10} \text{ 行}} $$
- 采用直接映射方式,每块对应唯一的 Cache 行,Cache 行号占 10 位。
- 主存标记 Tag 占用的位数为: $$ \text{t = 32 - 10 - 5 = 17 \text{ 位}} $$
- 单个 Cache 行的组成结构与位宽统计: 根据 Cache 行的硬件物理规范,Cache 行由数据区与标记项两部分构成:
- 数据区(Data Array):每块包含 32B,换算为比特位: $$ \text{32 \times 8 = 256 \text{ 位}} $$
- 主存标记位(Tag):需记录 17 位物理地址高位,占 17 位。
- 有效位(Valid Bit):指示数据是否有效,必占 1 位。
- 脏位/修改位(Dirty Bit):题目明确指明采用回写(Write Back)策略,必须维护数据修改状态,占 1 位。
- 替换控制位(Replacement Bits):本题采用直接映射方式,每个主存块只能放入唯一的固定行,无多行替换选择,因此无需替换位(0 位)。
- Cache 行总位数汇总: $$ \text{W_{\text{line}} = 256 + 17 + 1 + 1 = 275 \text{ 位}} $$
【正确答案】¶
A
5. 2022 年统考 408 真题第 16 题¶
【题号及考查方向】¶
- 题号:2022 年第 16 题
- 考查方向:8 路组相联 Cache 内部比较器硬件数量与比较器位宽推导。
【题干与选项】¶
某计算机主存地址为 32 位,按字节编址,某 Cache 的数据区容量为 32KB,主存块大小为 64B,采用 8 路组相联映射方式,该 Cache 中比较器的个数和位数分别为( )。
A. 8,20
B. 8,23
C. 64,20
D. 64,23
【详细解析】¶
- 主存地址三段式划分推导:
- 主存地址总位数为 32 位,按字节编址。
- 主存块大小为 \(64\text{B} = 2^6\text{B}\),因此块内地址占 6 位。
- Cache 数据区总容量为 32KB,块大小为 64B,故 Cache 总行数为: $$ \text{M = \frac{32\text{KB}}{64\text{B}} = \frac{32 \times 1024}{64} = 512 \text{ 行}} $$
- 采用 8 路组相联映射,即每组包含 8 个 Cache 行,因此 Cache 组数为: $$ \text{Q = \frac{512}{8} = 64 = 2^6 \text{ 组}} $$ 因此,Cache 组号占 6 位。
- 主存标记 Tag 位数为: $$ \text{t = 32 - 6 - 6 = 20 \text{ 位}} $$
- 比较器硬件参数判定:
- 比较器的个数:在组相联映射中,CPU 访问时先通过组号索引到某一个确定的组。由于该组内有 8 行,主存块可能放置在这 8 行中的任意一行,为了保证最快的访问速度,硬件上必须对该组内的 8 行 Tag 进行并行比较。因此,比较器的个数等于组内行数(路数),即 8 个。
- 比较器的位数:每个比较器负责比对“CPU 物理地址中的 Tag”与“Cache 行中的 Tag”,因此比较器的位数必须与 Tag 的宽度严格相等,即 20 位。
【正确答案】¶
A
6. 2025 年统考 408 真题第 43 题¶
【题号及考查方向】¶
- 题号:2025 年第 43 题
- 考查方向:8 路组相联 Cache 与页式虚存综合大题、虚拟索引识别、数组首地址非对齐跨块存储分析、缺失率计算、AMAT 周期计算、缺页次数综合分析。
【题干与设问】¶
计算机 M 字长为 32 位,按字节编址,数据 Cache 的数据区大小为 32KB,采 8 路组相联,主存块大小为 64B,Cache 命中时间为 2 个时钟周期,缺失损失为 200 个时钟周期,采用页式虚拟存储,页大小为 4KB。数组 d 的起始地址为 0180 0020H(VA31~VA0)。
(2)
d[100] 的 VA 是多少?d[100] 所在主存块中对应的 Cache 组号是多少?(3) 设代码已经在 Cache 中,
i, x 已装入内存,但不在 Cache,则 d[0] 在其主存块内的偏移量是多少?执行 for 的过程中,访问 d 的 Cache 缺失率和数组元素的平均访问时间分别是多少?(缺失率用百分比表示,保留两位小数)(4)
d 分布在几个页中?若代码已在主存,d 不在主存,则执行 for 的过程中,访问 d 所引起的缺页次数是?
【详细解析】¶
- 设问 (1) 解析:
- 块内地址位数:主存块大小为 \(64\text{B} = 2^6\text{B}\),故块内地址占 6 位(对应地址最低的 0~5 位)。
- Cache 组号位数:Cache 数据区容量为 32KB,总行数为 \(32\text{KB} / 64\text{B} = 512\)$ \text{行。采用 8 路组相联,总组数} $\(Q = 512 / 8 = 64 = 2^6\) 组。故 Cache 组号占 6 位(对应地址的 6~11 位)。
- VA 中可作为 Cache 索引的位:页面大小为 4KB(\(2^{12}\text{B}\)),虚拟地址与物理地址的低 12 位(VA11~VA0)完全一致。Cache 组号位于地址的第 6~11 位,完全落在低 12 位的页内偏移范围内。因此,虚拟地址中的 VA11~VA6(即第 6 位到第 11 位) 可以直接作为 Cache 组索引(此即虚拟索引物理标记 VIPT 机制的核心硬件依据)。
- 设问 (2) 解析:
d[100]的虚拟地址:int型占 4B,起始地址 \(\&d[0] = \text{0180 0020H}\)。 $\(\&d[100] = \text{0180 0020H} + 100 \times 4 = \text{0180 0020H} + 400\text{D} = \text{0180 0020H} + \text{190H} = \text{0180 01B0H}\)$- 对应 Cache 组号:
提取
0180 01B0H的低 12 位:1B0H = 0001 1011 0000B。- 低 6 位([5:0])为块内偏移:
11 0000B = 30H = 48; - 第 6~11 位([11:6])为 Cache 组号:
000110B = 6。 故d[100]所在主存块对应的 Cache 组号为 6。
- 低 6 位([5:0])为块内偏移:
- 设问 (3) 解析:
d[0]在主存块内的偏移量: \(d[0]\) 的起始地址为0180 0020H,其低 6 位为0020H的低 6 位,即二进制10 0000B = 32D,故偏移量为 32(或 32 字节)。- 跨 Cache 块分析与缺失次数:
- 数组
d共有 2048 个int元素,总数据大小为 \(2048 \times 4\text{B} = 8192\text{B} = 8\text{KB}\)。 - 每个 Cache 块为 64B,可容纳 \(64 / 4 = 16\) 个
int元素。 - 由于起始偏移量为 32B,第 1 个 Cache 块只容纳了后半段的 \((64 - 32) / 4 = 8\) 个元素(
d[0]~d[7]); - 中间剩余元素数为 \(2048 - 8 = 2040\)$ \text{个,整整跨越} $\(\frac{2040}{16} = 127.5\) 块,即:
- 127 个完整的 Cache 块(容纳 \(127 \times 16 = 2032\) 个元素);
- 最后剩余 \(2040 - 2032 = 8\)$ \text{个元素(
d[2040]~d[2047]),存放在第} $\(1 + 127 + 1 = 129\) 个 Cache 块的前半部分(32B)。 - 因此,数组
d实际跨越并占据了 129 个主存块。 - 在顺序遍历执行中,首次访问这 129 个块的第一个元素时均产生冷缺失,共发生 129 次缺失。
- 数组
- 总访存次数与缺失率:
- 语句
d[i] = d[i] / x;包含一次读d[i]和一次写d[i],每次循环访问数组d两次。 - 2048 次循环共产生 \(N_{\text{access}} = 2048 \times 2 = 4096\) 次访存。
- 访问
d的 Cache 缺失率为: $\(\text{Miss Rate} = \frac{129}{4096} \approx 3.1494\% \approx 3.15\%\)$
- 语句
- 数组元素平均访问时间:
- 发生缺失 129 次,每次损失 200 个时钟周期;
- 命中次数为 \(4096 - 129 = 3967\) 次,每次耗时 2 个时钟周期。
- 平均访问时间为: $$ \text{T_{\text{avg}} = \frac{129 \times 200 + 3967 \times 2}{4096} = \frac{25800 + 7934}{4096} = \frac{33734}{4096} \approx 8.2358 \approx 8.24 \text{ 个时钟周期}} $$
- 设问 (4) 解析:
- 分布在几个页中:
- 页面大小为 4KB(4096B)。
- 数组起始地址
0180 0020H,低 12 位页内偏移为020H = 32B。 - 第 1 个页剩余容量为 \(4096 - 32 = 4064\text{B}\);
- 数组总大小为 8192B,跨过第 1 页后剩余 \(8192 - 4064 = 4128\text{B}\);
- 第 2 个页容纳 4096B,剩余 \(4128 - 4096 = 32\text{B}\) 进入第 3 个页;
- 因此,数组
d分布在 3 个页面 中。
- 缺页次数:
- 由于代码已在主存,而数据数组
d完全未调入主存,在顺序访问执行过程中,当首次访问跨入第 1 页、第 2 页、第 3 页的首个数据时,均会触发一次缺页异常中断以调入物理页。 - 因此,访问
d所引起的缺页次数为 3 次。
- 由于代码已在主存,而数据数组
【参考答案汇总】¶
(1) 组号占 6 位,块内地址占 6 位。VA 中的 VA11~VA6(第 6 位到第 11 位)可以作为 Cache 索引。
(2) d[100] 的 VA 是 0180 01B0H。所在主存块对应的 Cache 组号是 6。
(3) d[0] 在其主存块内的偏移量是 32。访问 d 的 Cache 缺失率约为 3.15%;数组元素的平均访问时间约为 8.24 个时钟周期。
(4) d 分布在 3 个页中。引起的缺页次数是 3 次。
四、 综合大题应用与考查拓展¶
1. 虚存、TLB 与 Cache 的联合访问全流程模型¶
在现代计算机体系结构中,CPU 执行访存指令时,存储层次涉及虚拟地址(VA)向物理地址(PA)的转换以及物理地址在 Cache/主存中的查找。
CPU 产生虚拟地址 VA (例如 32 位)
|
+-----------------------------------+
| |
[VA 高位: 虚页号] [VA 低位: 页内偏移 (如 12 位)]
| |
v |
TLB 并行查找 |
+----+----+ |
| 命中 | 缺失 (查多级页表) |
v v |
取出实页号 (PA 高位) |
| | |
+----+---+ |
| |
v v
拼接形成物理地址 PA [ Tag (高位) | Cache 组号 (中位) | 块内偏移 (低位) ]
|
v
Cache 组相联查找
+----+----+
| 命中 | 缺失 (产生 Cache Miss, 访主存调块)
v v
读写 Cache 访问主存 / 下级 Cache
经典工程机制:虚拟索引物理标记(VIPT,Virtually Indexed Physically Tagged)¶
- 原理:若 $$ \text{Cache 组索引位数} + \text{块内偏移位数} \le \text{虚拟页内偏移位数} $$(即 $$ \text{Cache 组数} \times \text{块大小} \le \text{页面大小} $$),则 Cache 组号完全落在页内偏移中。由于虚实地址转换时不改变页内偏移,CPU 可以在向 TLB 查询实页号的同时,直接利用虚拟地址的对应位并行索引 Cache 组。
- 当 TLB 查得物理页号并生成物理 Tag 后,Cache 的目标组也已完成寻址,两者的 Tag 直接送入比较器。这种重叠访问完全隐藏了 Cache 索引的译码延迟。2025 年统考第 43 题第 (1) 问正是对该机制的直接考查。
2. 循环程序数组访存行为分析模型¶
在 408 综合大题中,程序数组访问与 Cache 缺失率的计算是得分关键点。需掌握以下通用分析范式:
(1) 访存次数定界¶
- 区分读/写复合语句:
sum += a[i];:对数组a[i]仅进行 1 次读;a[i] = a[i] + 1;或a[i] = a[i] / x;:先读后写,对数组a[i]发生 2 次访存。- 缺失率公式的分母必须严格采用总访存次数,不可误写为数组元素个数。
(2) 边界对齐效应(首地址偏置)¶
- 若数组首地址严格与 Cache 块边界对齐(例如偏移量为 0),则占用块数计算最为简单:$$ \text{\lceil N \times \text{sizeof(元素)} / B \rceil} $$。
- 若数组首地址未对齐(如 2025#43 偏移量为 32B):
- 第 1 个块只能容纳前半段剩余空间的数据;
- 末尾数据溢出进入额外的追加块;
- 实际跨越的 Cache 块数往往比“理论总字节数 / 块大小”多出 1 块。在缺失次数统计中必须严谨推导。
(3) 二维数组遍历方向与步长¶
- C 语言二维数组采用行优先存储(Row-Major):
- 外层行、内层列遍历(
for i ... for j ... A[i][j]):空间局部性极佳,每块仅首个元素缺失,缺失率为 $$ \text{1 / (\text{块容量} \times \text{每次访存数})} $$。 - 外层列、内层行遍历(
for j ... for i ... A[i][j]):步长大,跨行跨块跳跃访问。若单列数据量超过 Cache 容量,每个元素均引发缺失,缺失率飙升至接近 100%。
3. 写策略对 Cache 附加位与性能的深层影响¶
| 写策略组合 | 命中写操作处理 | 缺失写操作处理 | Cache 行硬件附加位 | 适用场景与性能特点 |
|---|---|---|---|---|
| 写回法 + 写分配 (Write-Back + Write-Allocate) |
只写 Cache,修改标记置 1 | 将主存块调入 Cache,随后在 Cache 中更新 | 必须包含 脏位(1 位) | 大幅降低主存写总线带宽消耗,是主流数据 Cache 的标准搭配 |
| 全写法 + 非写分配 (Write-Through + No-Write-Allocate) |
同时写入 Cache 和主存(常配写缓冲) | 直接在主存中写入,不调入 Cache | 无需脏位(0 位) | 数据强一致性,实现简单;但写操作频繁占用总线,多用于 L1 指令 Cache 或多核早期设计 |
4. 408 综合大题标准答题模板¶
题型一:物理地址划分与字段位数推导模板¶
- 写出推导依据:
- 块内偏移位数:$$ \text{b = \log_2(\text{块大小})} $$;
- 组号位数:组数 $$ \text{Q = \frac{\text{Cache 数据区容量}}{\text{路数 } K \times \text{块大小}}} $$,组号位数 \(s = \log_2 Q\);
- Tag 标记位数:$$ \text{t = \text{物理地址位数} - s - b} $$。
- 给出规范图表或明确区间:
- 明确指出:第 \(0 \sim b-1\)$ \text{位为块内偏移,第} $\(b \sim b+s-1\)$ \text{位为 Cache 组号,第} $\(b+s \sim m-1\) 位为 Tag 标记。
题型二:Cache 总容量与行位数计算模板¶
- 逐项罗列行构成:
- 数据区:$$ \text{块大小} \times 8 $$ 位;
- 标记字段:\(t\) 位;
- 有效位:1 位;
- 脏位:回写策略计 1 位(直写策略计 0 位);
- 替换控制位:\(K\)$ \text{路组相联 LRU 计} $\(\lceil \log_2 K \rceil\) 位(直接映射计 0 位)。
- 累加单行位数:\(W_{\text{line}} = \text{Data} + \text{Tag} + \text{Valid} + \text{Dirty} + \text{LRU}\)。
- 计算总容量:$$ \text{C_{\text{total}} = \text{总行数 } M \times W_{\text{line}}} $$(若题目要求字节,除以 8)。
题型三:访存地址定位与命中判断模板¶
- 地址转换:利用虚拟页内偏移与物理地址低位一致性,求出物理地址十六进制。
- 字段提取:转换为二进制,截取中间组号字段与高位 Tag 字段。
- 查表比对与结论说明:
- 定位到目标组;
- 逐行核对:先看有效位是否为 1,再看 Tag 是否一致;
- 得出“命中”或“不命中”,并阐明原因(如“有效位为 0,故不命中”)。
五、 考点速记清单¶
1. 核心三段式切分与容量计算公式¶
- 块内偏移位:\(b = \log_2(\text{BlockSize})\)
- Cache 组数:\(Q = \frac{\text{CacheDataSize}}{K \times \text{BlockSize}}\)
- 组号位数:\(s = \log_2(Q)\)
- 主存 Tag 位:\(t = \text{AddrBits} - s - b\)
- 比较器数量:\(\text{Num}_{\text{comp}} = K\)(路数)
- 比较器位宽:\(\text{Width}_{\text{comp}} = t\)(Tag 位数)
- Cache 单行位数:$$ \text{W_{\text{line}} = (8 \times B) + t + 1_{\text{有效}} + 1_{\text{脏(写回)}} + (\lceil \log_2 K \rceil)_{\text{LRU}}} $$
- 平均访存时间:\(\text{AMAT} = T_{\text{hit}} + \text{MissRate} \times T_{\text{miss}}\)
2. 映射方式核心特征速查表¶
| 特征项 | 直接映射 | 全相联映射 | \(K\) 路组相联映射 |
|---|---|---|---|
| 映射规则 | \(j = i \bmod M\)$ \text{ | 任意空闲行 | } $\(q = i \bmod Q\) |
| 地址切分结构 | Tag + 行号 + 块内偏移 | Tag + 块内偏移 | Tag + 组号 + 块内偏移 |
| 比较器个数 | 1 个 | \(M\)$ \text{个(总行数) | } $\(K\) 个(路数) |
| 比较器位宽 | Tag 位数 | Tag 位数 | Tag 位数 |
| 行替换控制位 | 无(0 位) | \(\lceil \log_2 M \rceil\)$ \text{位 | } $\(\lceil \log_2 K \rceil\) 位 |
| 冲突缺失 | 严重(易抖动) | 完全无 | 适中(\(K\) 越大越小) |
3. 高频避坑口诀与判定定律¶
- 比较器数量看路数,切勿误写总行数:组相联下每次只在选中的一组内比对,\(K\)$ \text{路只需要} $\(K\) 个比较器。
- 比较器位宽看 Tag,不要掺和组内号:比较器只负责对比高位标记,组号已通过外部译码器选定。
- 总容量含标记项,切莫只算数据区:大题若问“Cache 总容量”,必须把 Tag、有效位、脏位、替换位加上数据区后再乘以总行数。
- 读写一次算两次,缺失率分母倍增:类似
a[k] = a[k] + 1先读后写,循环一次访存 2 次,算缺失率时分母必须翻倍。 - 首址偏移若非零,多占一块需防范:数组首地址不对齐块边界时,首尾元素各占一个残缺块,实际占用块数比整数除法多 1。
- 低位页内不改变,虚实索引常并行:虚拟页内偏移与物理地址低位一致,组索引落在低 12 位时,可直接用虚拟地址查 Cache。