Cache 地址映射、容量计算与命中率分析（执行时间）

Cache 核心原理与计算

是什么

• 定义：Cache（高速缓冲存储器） 是位于 CPU 和主存之间的高速小容量存储器。主存与 Cache 均划分为大小相等的块（Block，在 Cache 中称为行/Line）。

• 大白话：Cache 就像是桌面上放的“近期常用文件夹”。把大书架（主存）上的书按“页（块）”拿几页放在桌上，下次直接拿桌上的看（命中），不用每次都跑去书架找。

核心内容

1. 主存地址的划分（按映射方式分类）

主存地址的总位数由主存空间决定（如 $256\text{ MB}=2^{28}\text{ B}\to 28\text{ 位}$）。无论哪种映射，低位均为 块内地址（Offset），位数 $={\log }_2(\text{块大小})$。

映射方式	主存地址结构划分	关键字段含义与位数计算
直接映射 (每个主存块只能去唯一固定的 Cache 行)	[ Tag / 标记 ] + [ Cache行号 ] + [ 块内地址 ]	$\text{Cache行号位数}={\log }_2(\text{Cache行数})$ $\text{Tag位数}=\text{主存地址位数}-\text{行号位数}-\text{块内地址位数}$
全相联映射 (每个主存块可以去任意 Cache 行)	[ Tag / 标记 ] + [ 块内地址 ]	$\text{Tag位数}=\text{主存地址位数}-\text{块内地址位数}$ (无行号/组号字段)
K路组相联映射 (每个主存块去固定组里的任意行)	[ Tag / 标记 ] + [ Cache组号 ] + [ 块内地址 ]	$\text{Cache组数}=\text{总行数}/K$ $\text{Cache组号位数}={\log }_2(\text{Cache组数})$ $\text{Tag位数}=\text{主存地址位数}-\text{组号位数}-\text{块内地址位数}$

【Tag 计算实战示例（2020统考真题）】：

主存地址 32 位，Cache 数据区容量 32KB，主存块大小 64B，采用 8 路组相联映射（指一组有8行）：

1. 块内地址位数 $={\log }_2(64\text{ B})=6\text{ 位}$

2. Cache 行数 $=\frac{32\text{ KB}}{64\text{ B}}=\frac{2^{15}\text{ B}}{2^6\text{ B}}=512\text{ 行}$

3. Cache 组数 $=\frac{512}{8}=64\text{ 组}=2^6\to \text{组号位数}=6\text{ 位}$

4. $\text{Tag位数}=32-6-6=20\text{ 位}$

2. Cache 总容量计算公式（全条件对比）

Cache 的总容量由 数据存储容量（Data） 和 标记阵列容量（Tag Array） 两部分组成：

$\text{Cache 总容量}=\text{行数}\times \text{行大小(字节)}+\text{行数}\times \text{单行标记开销(比特)}$

单行标记开销（SRAM 存储元）组成：

$\text{单行标记开销 (bit)}=\text{Tag 位数}+\text{有效位 Valid}+\text{脏位 Dirty}+\text{替换算法位 Replacement}$

• 有效位（Valid）：固定 $1\text{ bit}$（指示该行数据是否有效）。

• 脏位/修改位（Dirty）：

  • 写回法（Write-back）：需要 $1\text{ bit}$（标记该行是否被修改过）。

  • 全写法/直写（Write-through）：需要 $0\text{ bit}$（数据同步写回主存，无需脏位）。

• 替换算法位（Replacement）：

  • 直接映射：$0\text{ bit}$（位置固定，无需替换算法）。

  • 全相联 / 组相联映射：

    • FIFO（先进先出）：${\log }_2(K)\text{ bit}$（$K$ 为组内行数，全相联时 $K=\text{总行数}$）。

    • LRU（近期最少使用）：$\lceil {\log }_2(K)\rceil \text{ bit}$（如 8 路组相联占 ${\log }_{2}8=3\text{ bit}$）。

    • RAND（随机）：$0\text{ bit}$。

3. Cache 行号/组号的定位方法

Cache 组索引（Set Index） 指的就是该主存块/主存地址被映射到的 Cache 组号（即cache索引就是cache组号）

给定一个具体的字节物理地址（如 320），求解其对应的 Cache 行号/组号：

• 第一步（求主存块号）：

  $\text{主存块号}=\lfloor \frac{\text{字节物理地址}}{\text{块大小(B)}}\rfloor$

• 第二步（计算定位）：

  • 直接映射（求行号）：

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

  • 组相联映射（求组号）：

    $\text{Cache 组号}=\text{主存块号}\mathrm{mod}\text{Cache 总组数}$

  • 全相联映射：无行号/组号概念，可放入任意空闲行。

  • (注：若题目明确要求“Cache 行号从 1 开始”，则结果需 $+1$)

【数组寻址三步法示例】：

• 步骤一：求元素的字节物理地址

  $\text{字节物理地址}=\text{Base}+(i\times N+j)\times S$

  • $\text{Base}$：数组首地址（如 320）。

  • $i,j$：目标元素下标（如 $a[0][31]$ 即 $i=0,j=31$）。

  • $N$：总列数（如 $a[256][256]$ 中 $N=256$）。

  • $S$：单元素大小（如 $\text{int}$ 型 $S=4\text{ B}$）。

  • 计算：$\text{地址}=320+(0\times 256+31)\times 4=320+124=444$。

• 步骤二：求元素所在的主存块号

  $\text{主存块号}=\lfloor \frac{\text{字节物理地址}}{B}\rfloor =\lfloor \frac{444}{64}\rfloor =6$

• 步骤三：求映射到的 Cache 行号

  $\text{Cache 行号}=\text{主存块号}\mathrm{mod}C=6\mathrm{mod}8=6$

4. 命中率差异分析（数组访问模式）

在 C 语言二维数组（如 $a[256][256]$，$\text{int}$ 占 4B，按行优先存储）遍历中：

• 按行遍历（a[i][j]）：按内存连续地址顺着读，空间局部性极其优异。

  • 若 1 个 Cache 块能装 $N$ 个元素（$N=\text{块大小}/\text{sizeof(element)}$）：

  • 每访问 $N$ 个连续元素，仅第 1 个元素未命中，后续 $N-1$ 个元素连续命中。

  • 命中率公式：

    $\text{Hit Rate}=\frac{N-1}{N}$

    （如 $N=16$ 时，命中率为 $15/16=93.75\%$）。

• 按列遍历（a[j][i]）：跨行跳着读，跨行访问步长 $=\text{列数}\times \text{sizeof(element)}$。

  • 抖动/乒乓效应（Thrashing）：若跨行步长恰好是 Cache 总容量的整数倍，同列元素会全部映射到同一个行/组中。

  • 每次访问都会强制覆盖上一行的缓存数据，导致命中率暴跌为 0%。

5. 题干关键词与标记开销速查

• 映射方式描述：

  • 直接映射：“直接映射方式”、“主存块只能映射到固定的 Cache 行中”。

  • 全相联映射：“全相联映射方式”、“可以装入任意一行”、“采用相联存储器（CAM）按内容寻址”。

  • 组相联映射：“K 路组相联”、“按每 K 行分组”。

• 标记开销速记口诀：

  $\text{单行标记 (bit)}=\text{Tag}+\underset{\text{(默认必带 1 位)}}{\text{Valid(1)}}+\underset{\text{(写回法 1 位 / 直写法 0 位)}}{\text{Dirty(0/1)}}+\underset{\text{(直接映射/RAND为0, LRU为 }{\log }_{2}K\text{)}}{\mathrm{Replacement}}$

• (注：若题干说明“不考虑其他控制位”，则只算 1 bit 有效位)

6. CPU 执行时间与 Cache 缺失罚时计算

$\text{总 CPU 执行时间}=T_{\text{base}}(\text{基础时间})+T_{\text{miss}}(\text{缺失损失})$

• 基础执行时间（理想无缺失）：

  $T_{\text{base}}=\text{指令条数}\times \text{CPI}\times \text{CPU 时钟周期}$

• 缺失总罚时（Cache 缺失损失）：

  $T_{\text{miss}}=\text{缺失次数}\times \text{缺失损失 (Miss Penalty)}$

  $\text{缺失次数}=\text{指令条数}\times \text{每条指令平均访存次数}\times \text{Cache 缺失率}$

【2013 统考真题演练】：

• 已知：指令条数 $=100$ 条，$\text{CPI}=4$，时钟周期 $=1.25\text{ ns}$，平均每条指令访存 $=1.2$ 次，缺失率 $=5\%$，单次缺失损失 $=85\text{ ns}$。

• 求解：

  1. $T_{\text{base}}=100\times 4\times 1.25\text{ ns}=500\text{ ns}$

  2. 缺失次数 $=100\times 1.2\times 5\%=6\text{ 次}$

  3. $T_{\text{miss}}=6\times 85\text{ ns}=510\text{ ns}$

  4. $T_{\text{total}}=500\text{ ns}+510\text{ ns}=1010\text{ ns}(1.01\mu \text{s})$

例题

• 题目：

  主存 256MB，按字节编址，数据 Cache 共 8 行，每行 64B。数组 int a[256][256] 首地址为 320。在直接映射、写回法（1 位脏位）、无替换算法条件下：

  1. 数据 Cache 总容量是多少？

  2. 求 a[0][31] 对应的 Cache 行号。

  3. 比较按行遍历与按列遍历的 Cache 命中率。

• 分析：

  1. 主存 28 位（$256\text{ MB}=2^{28}\text{ B}$），块内偏移 6 位（$64\text{ B}=2^6\text{ B}$），行号 3 位（$8=2^3$），$\text{Tag}=28-6-3=19\text{ bit}$。单行标记 $=19(\text{Tag})+1(\text{Valid})+1(\text{Dirty})=21\text{ bit}$。总容量 $=8\times 64\text{ B}+8\times 21\text{ bit}$。

  2. a[0][31] 地址 $=320+31\times 4=444$。主存块号 $=\lfloor 444/64\rfloor =6$。Cache 行号 $=6\mathrm{mod}8=6$。

  3. 每个 Cache 块装 $64/4=16$ 个元素。按行遍历每 16 个元素缺失 1 次，命中率 $15/16=93.75\%$；按列遍历因跨行步长 $1024\text{ B}$（Cache 容量 $512\text{ B}$ 的 2 倍）导致同 Cache 行频繁冲突替换，命中率为 $0\%$。

• 答案：

  1. 数据 Cache 总容量为 $512\text{ B}+168\text{ bit}$（或 $533\text{ B}+0.25\text{ B}$）。

  2. a[0][31] 对应的 Cache 行号为 6。

  3. 按行遍历命中率为 $93.75\%$，按列遍历命中率为 $0\%$。

⚠️ 易错点

Warning

• Cache 容量 vs 数据容量：题目问“Cache 总容量”必须包含标记阵列容量（Tag + 状态位），不能只算数据区大小。

• ==$32\text{ KB}/64\text{ B}$ 计算陷阱==：计算机中 $1\text{ KB}=1024\text{ B}=2^{10}\text{ B}$，故 $32\text{ KB}/64\text{ B}=2^{15}/2^6=2^9=512$ 行，绝不是 500。

• 组相联映射组号计算：$K$ 路组相联中，组号位数由组数决定（$\text{组数}=\text{总行数}/K$），而不是直接用总行数计算。

• 直写法 vs 回写法修改位：直写法（Write-through）与主存时刻一致，无修改位（0 bit）；回写法（Write-back）才需要 1 bit 修改位。

• ==漏算基础执行时间 $T_{\text{base}}$==：计算总执行时间切勿只算 $T_{\text{miss}}$，必须加上指令内部执行的 $T_{\text{base}}$。

• 指令数 vs 访存次数：Cache 缺失率是针对访存操作而言的，计算缺失次数必须用“$\text{指令条数}\times \text{每条指令平均访存次数}\times \text{缺失率}$”。