Cache命中率，缺失率数组元素平均访问时间

是什么

• 定义：Cache 性能分析是研究程序在特定存储层次结构下的访存行为（命中率、缺失率、平均访存时间 AMAT）及底层硬件根据物理地址检索、比对 Tag、调块和替换的定量分析体系。

• 大白话：CPU 读写数据时，硬件是按“整块（Cache Line）”从主存往 Cache 进货的。算缺失率就是看“总共进了几次货 / 总共访问了几次”；算 AMAT 就是看“平均每次找数据要花几个时钟周期”；算块数时，只要数据总大小是块大小的整数倍且首地址不对齐（有偏移），所占块数就在对齐块数的基础上直接加 1。

核心内容

1. 核心参数与物理地址切分标准

设主存块大小为 $B\text{ 字节}$，Cache 总容量为 $C\text{ 字节}$，采用 $K$ 路组相联映射：

• 块内偏移位数：$b={\log }_2(B)$

• Cache 总行数与组数：$\text{总行数}=C/B$，$\text{组数 }S=\frac{C/B}{K}=2^s$（组号占 $s$ 位）

• Tag 标记位数：$t=\text{物理地址总位数}-s-b$

• 单块容纳元素数：

  $E_{\text{block}}=\frac{\text{主存块大小 }B}{\text{单个元素大小 sizeof}(T)}$

2. 数组占用 Cache 块数与缺失次数的两种标准求解法

在无容量失效与冲突失效的前提下（$\text{数组总大小}\le \text{Cache 容量}$），求数组占用主存/Cache 块数的标准方法：

方法一：首尾地址块号定位法（考场最严谨通用解法）

1. 求首字节与末字节物理地址：

   • 首字节地址：${\text{Addr}}_{\text{first}}=A_{\text{start}}$

   • 末字节地址（必须减 1 字节）：${\text{Addr}}_{\text{last}}=A_{\text{start}}+\text{TotalBytes}-1$

2. 求首块号与末块号（截去低 $b$ 位或除以 $B$）：

   • ${\text{Block}}_{\text{start}}=\lfloor {\text{Addr}}_{\text{first}}/B\rfloor$

   • ${\text{Block}}_{\text{last}}=\lfloor {\text{Addr}}_{\text{last}}/B\rfloor$

3. 闭区间计数求总块数：

   $\text{跨越的总块数}={\text{Block}}_{\text{last}}-{\text{Block}}_{\text{start}}+1$

4. 总缺失次数：==总缺失次数 = 跨越的总块数 $\times 1$==。

方法二：元素分布容量推导法（首-中-尾分段推导）

设起始地址块内偏移量为 $\Delta$ 字节（低 $b$ 位的值）：

1. 首个主存块：容纳前 $\lfloor (B-\Delta )/\text{sizeof}(T)\rfloor$ 个元素，占用 1 块；

2. 中间完整主存块：剩余元素按每块装满 $E_{\text{block}}$ 个元素划分，占用 $\lfloor \text{剩余元素数}/E_{\text{block}}\rfloor$ 块；

3. 末尾主存块：剩余的零头元素溢出至新块的前半段，占用 1 块；

4. 累计相加：总块数 $=1+\text{中间完整块数}+1$。

3. “偏移量 $\ne 0$ 则加 1”法则的适用边界与反例

• 适用充要条件：

  只有当 数组总大小是 Cache 块大小的整数倍（408 考研真题最常见的场景，如 4KB、6KB、8KB 数组对应 32B/64B 块）时：

  • 首地址对齐（$\Delta =0$）：$\text{总块数}=\text{基准对齐块数}=\frac{\text{数组总大小}}{\text{块大小}}$

  • 首地址不对齐（$\Delta \ne 0$）：==$\text{总块数}=\text{基准对齐块数}+1$==

• 不适用的反例（非常规情况）：

  若数组总大小不是块大小的整数倍，上述“直接加 1”法则失效。

  • 反例：主存块大小 $64\text{ B}$，数组总大小仅 $16\text{ B}$。

    • 首地址对齐（偏移 $0\text{ B}$，范围 $0\text{ B}\sim 15\text{ B}$）：占用 1 块。

    • 首地址偏移 $20\text{ B}$（范围 $20\text{ B}\sim 35\text{ B}$）：依然落在同一个 $64\text{ B}$ 块内，占用 1 块（未加 1）。

4. Cache 性能评价三大指标

1. 总访问次数 $N_{\text{access}}$：

   • 纯读取（如 sum += a[i]）：每轮循环产生 1 次读访问。

   • 读写复合（如 a[i] = a[i] / x 或 a[i] = 2 * a[i]）：每轮循环产生 1 次读 + 1 次写 = 2 次访问。

   • 寄存器变量（如 i, k）不计入 Cache 访存。

2. 缺失率与命中率：

   $\text{Cache 缺失率 }M=\frac{\text{总缺失次数}}{N_{\text{access}}}\times 100\%$

   $\text{Cache 命中率 }H=1-M$

3. 平均访存时间（AMAT）：

   $\text{AMAT}=t_c+M\times t_{\text{penalty}}$

   （$t_c$ 为 Cache 命中时间，$t_{\text{penalty}}$ 为缺失损失/缺失惩罚）。

5. 遍历方向（按行 vs 按列）的局部性模型

• 按行遍历（空间局部性极好）：

  访问顺序与内存物理排布完全一致，命中率稳定为 $\frac{E_{\text{block}}-1}{E_{\text{block}}}$。

• 按列遍历（跨步长跳跃）：

  • Cache 能装下且不冲突（$\text{数组大小}\le \text{Cache 容量}$）：首轮列遍历将所有涉及的块调入后常驻，后续列遍历完全命中，命中率与按行遍历完全相同。

  • Cache 装不下或冲突置换剧烈：调入的块在复用前被置换淘汰，==命中率骤降甚至跌至 $0\%$==。

6. 组相联 Cache 访存与缺失处理硬件标准 6 步

Step 1: 地址拆分 → 将物理地址切分为 [ Tag (高位) | 组号 Index (中间位) | 块内偏移 Offset (低位) ]
Step 2: 组定位   → 根据“组号”选中对应的 Cache 组
Step 3: 并行比对 → 将 Tag 与该组内所有行的 Tag 同时比对，并检查有效位 (Valid)
Step 4: 判定命中/缺失：
        - 命中 (Hit)  → 按块内偏移取出目标数据送 CPU，更新 LRU
        - 缺失 (Miss) → 启动缺失处理流程 (Step 5 ~ Step 6)
Step 5: 访存调块 → 访问主存，将该地址所在的主存块（块内偏移清零的起始地址）整块读出
Step 6: 填入Cache并送CPU → 写入该组空闲行（或 LRU 替换），写入 Tag，有效位置 1，更新 LRU，并将目标数据送 CPU

例题

• 题目（2025 统考 408 真题综合演练）：

  计算机 M 字长 32 位，按字节编址。数据 Cache 容量 32KB，8 路组相联，主存块大小 64B。Cache 命中时间为 2 个时钟周期，缺失损失为 200 个时钟周期。

  已知数组定义为 int d[2048];（sizeof(int) = 4），起始虚拟地址为 0180 0020H（代码已在 Cache 中，变量 i 和 x 在寄存器中，数组已在主存但不在 Cache 中）。

  执行如下程序段：

  C

  for (i = 0; i < 2048; i++)
      d[i] = d[i] / x;
  

  求：

  1. d[0] 在所在主存块内的偏移量。

  2. 用规范方法推导数组 $d$ 占用的主存块数，并计算数据 Cache 缺失率及平均访问时间 AMAT。

  3. 若起始地址改为 0180 0000H，缺失次数是多少？

  4. 简述 CPU 首次读取 d[0] 时的 Cache 访问及缺失处理过程。

• 分析：

  1. 块大小 $64\text{ B}=2^6\text{ B}$ $\to$ 块内偏移占低 6 位。0180 0020H 低 6 位为 10 0000B = 20H（十进制 32）。

  2. 数组总大小 $2048\times 4\text{ B}=8192\text{ B}=2000\text{H}$（是 64B 的整数倍）。

  3. 总访问次数：每次循环 1 次读 + 1 次写，总访问次数 $=2048\times 2=4096$ 次。

  4. 占用块数推导：

     • 方法一（首尾地址法）：首地址 0180 0020H（块号 60000H），末地址 0180 0020H + 2000H - 1 = 0180 201FH（块号 60080H），块数 $=\text{60080H}-\text{60000H}+1=80\text{H}+1=129$ 块。

     • 方法二（容量推导法）：首块装 8 个元素，中间 127 块装 $127\times 16=2032$ 个元素，尾块装 8 个元素，总块数 $=1+127+1=129$ 块。

  5. 缺失次数 $=129$ 次。

  6. 缺失率 $=129/4096\approx 3.15\%$。

  7. $\text{AMAT}=2+(129/4096)\times 200\approx 8.30$ 周期。

  8. 对齐情况（0000H）：$\Delta =0$，占用块数 $=8192\text{ B}/64\text{ B}=128$ 块，缺失 128 次。

• 答案：

  1. d[0] 在主存块内的偏移量为 20H（或十进制 32）。

  2. 数组 $d$ 占用的主存块数为 129 块。

     访问数组 $d$ 的 Cache 缺失率为 $3.15\%$；

     数组元素的 平均访问时间为 $8.30$ 个时钟周期。

  3. 若起始地址改为 0180 0000H，Cache 缺失次数为 128 次。

  4. 访问及缺失处理规范过程：

     • 地址解析：物理地址 0180 0020H 解析为标记 Tag（01800H）、Cache 组号（0 组）、块内偏移（20H）。

     • Cache 比对：CPU 索引到数据 Cache 第 0 组，并行比对该组 8 个行对应的 Tag 并检查有效位。

     • 缺失判定：因有效位为 0（未命中），判定发生 Cache 读缺失。

     • 访存调块：CPU 访问主存，将起始物理地址为 0180 0000H、大小为 64B 的主存块整块读出。

     • 写入与送达：将该块写入第 0 组空闲行，有效位置 1，写入 Tag 01800H，更新 LRU 位，并将偏移 20H 处的 d[0] 送给 CPU 执行除法。

⚠️ 易错点

Warning

• “偏移加 1”法则的前提限制 $\to$ 只有当数组总大小是块大小的整数倍时，偏移不为 0 才必然多占 1 块。若数组本身极小（未填满一个块），即使有偏移也不一定会加 1。考场上最稳妥的仍是首尾地址块号定位法。

• 末尾字节地址未减 1 $\to$ 计算末字节地址公式为 $\text{首地址}+\text{总大小}-1$。若漏减 1，当数据恰好对齐块边界时，会把下一块的第 0 个字节算入，导致多算 1 块。

• 复合赋值语句访问次数漏算 $\to$ a[i] = a[i] / x 是先读后写，循环一次产生 2 次 Cache 访问。若算缺失率时分母只写 2048，缺失率直接算翻倍。

• 读写时序与命中关系 $\to$ 首次读取某个元素发生读缺失并将整块拉入 Cache 后，紧随其后的“写回”操作以及同块内的后续元素访问全部命中，不会重复缺失。

• 调块起始地址必须清零偏移量 $\to$ 发生缺失向主存调块时，调入的是整块。如访问 0180 0020H 缺失，调入块的主存起始地址必须清零低 6 位，写为 0180 0000H。