8.2 存储专题（一）：程序的 Cache 命中率

408 Cache 综合题的解题模板——地址字段划分、数组元素到 Cache 行/组的映射、局部性分析与命中率计算、冲突缺失、平均访问时间与主存带宽；配有可完整模拟任意数组访问模式的 Cache 实验。

考查要求 ★★★ 重点掌握 Tag/组号/块内地址元素地址→块号→行号行优先与列优先空间局部性与时间局部性命中率 = 1 − 元素大小/块大小冲突缺失Cache 总容量平均访问时间与带宽

解题模板

Cache 综合题通常给出 Cache 的组织方式和一段访问数组的 C 程序。几乎所有小问都可以按下面的顺序解决：

划分地址：块内地址 = log₂(块大小)，组号（行号）= log₂(组数)，Tag = 地址位数 − 其余两部分。直接映射时组数 = 行数，全相联时没有组号字段。
元素 → 块 → 行：先求元素的主存地址，再求块号 = ⌊地址 / 块大小⌋，最后行号（组号）= 块号 mod 行数（组数）。
分析局部性：一个块能放几个元素？访问顺序与存放顺序是否一致？数组是否比 Cache 大、会不会被替换掉后再次访问？
计算命中率：数清楚”每块第一次访问缺失、其余命中”这类规律，或者数出冲突造成的额外缺失。
计算时间与带宽：平均访问时间、加速比、缺失时需要从主存搬运的数据量。

地址划分与 Cache 容量

综合题（408 真题改编）

某计算机主存地址空间 256 MB，按字节编址；数据 Cache 采用直接映射，共 8 行，每行 64 B。int 型数据为 32 位，数组 int a[256][256] 按行优先存放，首地址为 320（十进制）。(1) 不考虑一致性维护和替换算法的控制位，数据 Cache 的总容量是多少？(2) a[0][31] 和 a[1][1] 所在主存块分别映射到哪一行？

查看解答

(1) 主存地址 log₂ 256M = 28 位。块内地址 log₂ 64 = 6 位，行号 log₂ 8 = 3 位，Tag = 28 − 6 − 3 = 19 位。每行除 64 B 数据外还有 19 位 Tag 和 1 位有效位：

8 \times (64 \times 8 + 19 + 1) = 4256 \text{ 位} = 532 \text{ B}

(2) 行优先存放时 &a[i][j] = 首址 + (i × 256 + j) × 4。

a[0][31]：地址 = 320 + 31 × 4 = 444，块号 ⌊444 / 64⌋ = 6，行号 6 mod 8 = 6；
a[1][1]：地址 = 320 + 257 × 4 = 1348，块号 ⌊1348 / 64⌋ = 21，行号 21 mod 8 = 5。

局部性与命中率

访问数组时的命中率主要由两件事决定：

空间局部性：访问顺序和存放顺序一致时，每个块只在第一次访问时缺失，块中其余元素都命中。若块与数组首址对齐，

\text{命中率} = 1 - \frac{\text{元素大小}}{\text{块大小}}

例如 int 数组、64 B 块：1 − 4/64 = 15/16 = 93.75%。

时间局部性：同一个元素（或同一块）被重复访问。只遍历一次的循环没有时间局部性；重复扫描且数组能整个放进 Cache 时，第 2 轮起全部命中。

若按列访问一个按行存放的大数组，相邻两次访问的地址相差一整行（256 × 4 = 1 KB），远大于块大小，每次访问都落在不同的块上；而在回到同一行之前，Cache 早已被替换了好几遍，所以命中率为 0。

下面的实验会完整模拟程序的全部访问，并逐步演示前 40 次。格子里的数字是该元素所在主存块映射到的行号（组号），数字相同的元素会争用同一个 Cache 行。可以从预置的真题开始，再修改参数，体会每个因素的作用：

动画演示程序访问数组时的 Cache 行为

M×N ×元素单位首址 HCache行块单位

缺失命中当前访问

程序
1for (i = 0; i < 256; i++)
2  for (j = 0; j < 256; j++)
3    sum += a[i][j];

1/42组数 = 8 行 / 1 路 = 8 组；每块 64 个编址单位，可容纳 16 个元素。共 65536 次数据访问，下面逐步演示前 40 次

冲突缺失与相联度

两个数组交替访问时，若它们对应的元素恰好映射到同一行，就会互相替换，即使 Cache 还有空行——这就是冲突缺失。

想一想

在实验中选择「点积」预置，把元素数改为 16、映射方式改为直接映射（数据区仍为 4 行 × 16 B）。命中率是多少？为什么？改为 2 路组相联后呢？

查看解答

a 占 16 × 4 = 64 B，正好等于 Cache 数据区大小，b 紧跟在 a 之后，所以 a[i] 与 b[i] 的地址相差 64 B，总是映射到同一行。直接映射时，访问 a[i] 调入的块马上被 b[i] 替换，接着 a[i+1] 又把 b 的块替换掉……每次访问都缺失，命中率为 0。

改为 2 路组相联后，a[i] 与 b[i] 所在的块可以同时放在同一组的两行中，每块只在第一次访问时缺失，命中率恢复为 75%（每块 4 个元素，1 次缺失、3 次命中）。

这说明：提高相联度可以减少冲突缺失；编程时也可以通过在两个数组之间填充一些空间（padding）来错开映射。

综合题（408 真题改编）

数据 Cache 采用 2 路组相联映射，数据区容量 64 B，主存块 16 B。float a[12] 存放在 00000040H 开始的 48 B 中，float b[12] 紧跟其后。程序计算点积：for (i = 0; i < 12; i++) sum += a[i] * b[i];（sum 和 i 在寄存器中）。(1) 说明访问数组 a 和 b 的局部性；(2) 求数据访问的命中率。

查看解答

(1) 每个块 16 B 可放 4 个 float，a、b 都按顺序访问，具有空间局部性；每个元素只访问一次，没有时间局部性。

(2) Cache 共 64 / 16 = 4 行，分为 2 组。块内地址 4 位，a 的首址 40H 对应块号 4，因此 a 占块 4、5、6，b 占块 7、8、9：

数组元素	a[0..3]	a[4..7]	a[8..11]	b[0..3]	b[4..7]	b[8..11]
主存块号	4	5	6	7	8	9
组号（块号 mod 2）	0	1	0	1	0	1

每个阶段同时活跃的 a 块和 b 块总是分别位于不同组，或者在同一组中各占一行，不会互相替换。每块的 4 次访问中第 1 次缺失、其余 3 次命中，命中率 = 18 / 24 = 75%。

时间与带宽

设 Cache 命中率为 $H$ ，Cache 访问时间为 $t_c$ ，主存访问时间为 $t_m$ ：

访问方式	平均访问时间
先访问 Cache，缺失后再访问主存	$t_a = H \cdot t_c + (1 - H)(t_c + t_m)$
同时访问 Cache 和主存，命中则中止主存访问	$t_a = H \cdot t_c + (1 - H)\, t_m$

加速比 = 无 Cache 时的访问时间 / 有 Cache 时的平均访问时间；“速度提高了多少倍”要在加速比的基础上减 1。缺失时 Cache 和主存之间以块为单位交换数据，因此所需的主存带宽 = 每秒缺失次数 × 块大小。

例题

直接映射 Cache 有 128 个块，主存有 16K 个块，每块 16 个字，按字编址。访问 Cache 需 10 ns，填充一个 Cache 块需 200 ns（填充后直接把字送给 CPU），Cache 初始为空。(1) 写出主存地址格式；(2) CPU 依次读取 16～210 号字，循环 10 次，求命中率；(3) 平均每次循环的读取时间是多少？

查看解答

(1) 主存共 16K × 16 = 2¹⁸ 字，地址 18 位：Tag 18 − 7 − 4 = 7 位 | 行号 log₂ 128 = 7 位 | 块内地址 log₂ 16 = 4 位。

(2) 16～210 号字共 195 个，位于第 1～13 块（块号 = 字号 ÷ 16）。第 1 轮每块第一次访问缺失，共 13 次；13 块远少于 128 行，不会被替换，后 9 轮全部命中：

H = \frac{195 \times 10 - 13}{195 \times 10} = \frac{1937}{1950} \approx 99.3\%

（在上面的实验中选择最后一个预置即可验证。）

(3) 第 1 轮：182 次命中 × 10 ns + 13 次缺失 × 200 ns = 4420 ns；后 9 轮：9 × 195 × 10 ns = 17 550 ns。平均每轮 (4420 + 17 550) / 10 = 2197 ns。

例题

CPU 主频 80 MHz，CPI = 4，平均每条指令访存 1.5 次。Cache 容量 16 KB，块大小 32 B，4 路组相联。CPU 依次从主存 0～99 号单元读出 100 个字（字长 32 位），重复 10 次。(1) 计算机的 MIPS 是多少？(2) Cache 命中率是多少？(3) 若 Cache 速度是主存的 6 倍，有 Cache 比无 Cache 速度提高多少倍？(4) 不考虑 DMA，主存带宽至少为多少才能满足 CPU 的访存要求？

查看解答

(1) MIPS = 主频 / (CPI × 10⁶) = 80 / 4 = 20。

(2) 每块 32 B 可放 8 个字，100 个字占 13 块（第 13 块只有 4 个字），第 1 轮缺失 13 次；400 B 远小于 16 KB，之后全部命中。H = (1000 − 13) / 1000 = 98.7%。

(3) 设 Cache 存取周期为 t，主存为 6t（缺失时按访问主存计）：

\frac{6t \times 1000}{987\,t + 13 \times 6t} = \frac{6000}{1065} \approx 5.63

速度提高约 5.63 − 1 = 4.63 倍。

(4) 每秒执行 20 M 条指令，访存 20 M × 1.5 = 30 M 次，其中缺失 30 M × (1 − 98.7%) = 0.39 M 次，每次缺失从主存读入一块 32 B：主存带宽至少为 0.39 M × 32 B = 12.48 MB/s。

即时练习

即时练习5 题

点击选项即可作答

1
某计算机主存按字节编址，地址 32 位；Cache 数据区 16 KB，4 路组相联，块大小 64 B，采用写回法和 LRU 替换。则每个 Cache 行中 Tag 的位数为（　）。
2
数组 int a[256][256] 按行优先存放，数据 Cache 为直接映射、8 行 × 64 B。若程序按 for (j…) for (i…) sum += a[i][j]; 访问数组，则数据访问的命中率为（　）。
3
short x[128][128] 按行优先存放，首址按 32 B 对齐，数据 Cache 块大小为 32 B。程序按行顺序访问每个元素一次，则命中率为（　）。
4
对于程序 for (i = 0; i < N; i++) sum += a[i] * b[i];（sum、i 在寄存器中），下列说法正确的是（　）。
5
两个大小正好等于 Cache 容量的数组 a、b 相邻存放，程序交替访问 a[i]、b[i]。在直接映射 Cache 中命中率为 0，下列措施中最能有效提高命中率的是（　）。

学完了吗？

标记完成后，侧栏会显示进度。进度仅保存在本浏览器中。