[TOC]

4-7-1 高速缓冲存储器cache—cache的相关基本概念

一、Cache的核心作用与硬件基础

  1. 存储器性能矛盾：主存常用SDRAM（容量大、成本低、速度慢），无法匹配CPU高速运算；SRAM（容量小、成本高、速度快，约为SDRAM的5-10倍），适合作为CPU与主存间的“桥梁”。
  2. Cache设计逻辑：在CPU与主存间增设SRAM作为Cache，复制主存中“常访问/即将访问”的数据，使大部分访存在Cache完成，解决CPU与主存的速度不匹配问题。
  3. 设计依据：程序局部性原理
    • 时间局部性：某存储位置被访问后，未来会多次访问（如循环变量、函数调用）。
    • 空间局部性：某存储位置被访问后，其相邻位置大概率被访问（如数组、顺序代码块）。
    • 实例：C语言数组求和代码中，循环指令兼具时间+空间局部性，数组仅具空间局部性，单个变量仅具时间局部性。

二、Cache访问流程与数据块划分

  1. 访问流程
    • 命中（Hit）：数据在Cache中，访问时间 $T_C$（Cache查找+读取时间，极短）。
    • 缺失（Miss）：数据不在Cache中，需从主存载入数据块到Cache，访问时间近似为主存访问时间$T_M$（远大于$T_C$）。
  2. 数据块划分：主存与Cache划分为固定大小的数据块（如16B、32B），缺失时载入“目标数据所在块”，利用空间局部性提升后续命中率；块过大/过小均会降低命中率（块大减少Cache存块数，块小无法覆盖相邻数据）。
  3. 数据块地址结构：数据块地址=块地址（定位块位置，Cache块地址短于主存）+ 块内偏移地址（定位块内数据位置）。

三、Cache性能评价指标

  1. 命中率（$H$）：$H=\frac{N_C}{N_C+N_M}$（$N_C$为命中次数，$N_M$为缺失次数），越接近 $1$ 越好。
  2. 缺失率：$1-H$，与命中率互补。
  3. 平均访问时间（$T_A$）：$T_A=H×T_C+(1-H)×T_M$，越短越好。
  4. 访问效率（$E$）：$E = \frac{T_C}{T_A} = \frac{1}{H + (1 - H) \cdot R}$（$R=\frac{T_M}{T_C}$，通常$R=5到10$），越接近1越好。

4-7-2 高速缓冲存储器cache—cache的读、写流程

一、Cache读流程（核心目标：快速获取数据，减少CPU等待）

image-20251203134747749
  1. 基本步骤
    1. CPU给出目标数据地址，拆分“块地址+块内偏移地址”。
    2. 用块地址查询Cache：检查Cache中是否存在该块的“有效位”（标记块是否有效）和“标记位”（匹配主存块地址）。
    3. 命中：根据块内偏移地址从Cache块中读取数据，返回CPU。
    4. 缺失：
      • CPU暂停（或切换其他任务），向主存发送“主存块地址”，读取目标数据块。
      • 将主存块写入Cache（若Cache满，需按替换算法淘汰旧块），更新Cache的有效位和标记位。
      • 从Cache块中读取目标数据，返回CPU，CPU恢复执行。
  2. 关键细节：读操作不修改主存数据，仅需保证“Cache与主存数据一致”（缺失时同步主存块到Cache即可）。

二、Cache写流程（核心挑战：保证Cache与主存数据一致性，避免数据不一致）

image-20251203134648613

根据“写操作时是否立即更新主存”，分为三种策略：

  1. 写直达（Write-Through）

    • 流程：CPU写数据时，同时写入Cache和主存；若Cache命中，直接写Cache+主存；若缺失，先将主存块载入Cache（可选，称为“写分配”），再写Cache+主存。
    • 优点：Cache与主存始终一致，无需担心数据丢失（主存是持久存储）。
    • 缺点：每次写操作都需访问主存，主存写速度慢，导致CPU写延迟高。
    • 适用场景：对数据一致性要求高、写操作频率低的场景（如部分嵌入式系统）。

  2. 写回（Write-Back）

    • 流程：CPU写数据时，仅写入Cache，不立即更新主存；为Cache块增设“脏位”（标记块是否被修改）：
      • 命中时：写Cache，置脏位为“1”（表示Cache块与主存不一致）。
      • 缺失时：若淘汰的旧块脏位为“1”，先将旧块写回主存，再载入新主存块到Cache，写Cache并置脏位为“1”；若旧块脏位为“0”，直接载入新块并写Cache。
    • 优点：减少主存写次数，降低CPU写延迟（仅淘汰脏块时写主存）。
    • 缺点：Cache与主存可能不一致，若Cache掉电（如突发断电），未写回主存的脏块数据会丢失。
    • 适用场景：写操作频率高、对延迟敏感的场景（如PC、服务器CPU Cache）。

  3. 写分配（Write-Allocate）与非写分配（No-Write-Allocate）

    • 写分配：写缺失时，先将主存块载入Cache，再写Cache（配合写直达/写回使用，写回必用）。
    • 非写分配：写缺失时，直接写主存，不载入Cache（仅配合写直达使用，减少Cache无效块占用）。
    • 对比：写分配利用空间局部性（后续可能访问该块其他数据），非写分配适合写操作集中在“不常访问块”的场景。
image-20251214163609619

4-7-3 高速缓冲存储器cache — 地址映射

地址映射是“将主存块地址转换为Cache块地址”的规则，决定主存块能存入Cache的哪个块，核心解决“主存容量远大于Cache，如何高效定位块”的问题，分为三类映射方式：

（1）直接映射（Direct Mapping）

image-20251203142109431
  1. 映射规则：主存块i固定映射到Cache块j，公式为j = i mod C（C为Cache总块数）。
    • 例：Cache有8块（C=8），则主存块0→Cache块0、主存块8→Cache块0、主存块16→Cache块0（即主存每C个块为一组，组内块映射到同一Cache块）。
  2. 地址结构：主存地址拆分为“标记位（Tag）+ Cache块地址（Index）+ 块内偏移（Offset）”，其中Cache块地址位数=log₂C，标记位位数=主存块地址位数 - Cache块地址位数。
    • 例：主存容量1MB（2²⁰B），Cache容量32KB（2¹⁵B），块大小16B（2⁴B）：主存块数=2²⁰/2⁴=2¹⁶，Cache块数=2¹⁵/2⁴=2¹¹，地址结构为“标记位5位（16-11）+ Cache块地址11位 + 偏移4位”。
  3. 查询流程：用Cache块地址定位Cache块，对比该块的标记位与主存标记位，若一致且有效位为1，则命中。
  4. 优点：硬件实现简单（无需复杂比较逻辑），查找速度快。
  5. 缺点：冲突缺失严重（不同主存块映射到同一Cache块，频繁替换会降低命中率，如循环访问主存块0、8、16时，会不断替换Cache块0）。
  6. 适用场景：Cache容量较大、主存访问冲突少的场景（如早期CPU Cache）。

（2）全相联映射（Fully Associative Mapping）

  1. 映射规则：主存块可存入Cache的任意块，无固定位置限制。
  2. 地址结构：主存地址拆分为**“标记位（Tag）+ 块内偏移（Offset）”**，标记位位数=主存块地址位数（需完整标记主存块）。
    • 例：同上主存与Cache参数，地址结构为“标记位16位 + 偏移4位”。
  3. 查询流程：将主存标记位与Cache中所有块的标记位同时比较（需“相联比较器”），若某块标记位一致且有效位为1，则命中。
  4. 优点：无冲突缺失（主存块可选任意Cache块，仅当Cache满时才淘汰旧块），命中率最高。
  5. 缺点：硬件成本高（相联比较器结构复杂，Cache块数越多，比较器越复杂），查找速度慢（需遍历所有Cache块比较）。
  6. 适用场景：Cache容量极小的场景（如CPU中的“快表TLB”，通常仅几十到几百块）。

1. 地址结构

全相联映射的主存地址由2部分组成，无“主存分区号”概念：
$$\text{主存地址} = \underbrace{\text{主存数据块地址}}{S\ \text{位}} + \underbrace{\text{块内偏移}}{W\ \text{位}}$$

  • 直接映射地址为三级结构（主存分区号 + cache行号 + 块内偏移），二者结构不同。

2. 容量计算

  • 主存数据块数量：$2^S$ 个；
  • 单个数据块大小：$2^W$ 字节；
  • 主存总容量：$2^S \times 2^W = 2^{S+W}$ 字节。

3. cache行结构

每个cache行包含3部分（无分区号）：
$$\text{cache行} = \text{有效位（1位）} + \text{主存数据块地址（S位）} + \text{数据块副本（}2^W \times 8\ \text{位）}$$

4. cache总容量计算

若cache共有$N$行，则总容量：
$$\text{cache总容量} = N \times \left[1 + S + (2^W \times 8)\right]\ \text{位}$$

image-20251214145701989

（3）组相联映射（Set-Associative Mapping）

  1. 映射规则：结合直接映射与全相联映射的优点，先将Cache分为G个“组（Set）”，每组含K个“块（Way）”（K称为“相联度”，如K=2为2路组相联）；主存块i先按直接映射规则映射到Cache组g=i mod G，再可存入该组的任意K个块中。
    • 例：Cache有8块，分为4组（G=4），每组2块（K=2，2路组相联）；主存块0→Cache组0（可存块0/1）、主存块4→Cache组0（可存块0/1）、主存块8→Cache组0（可存块0/1）。
  2. 地址结构：主存地址拆分为“标记位（Tag）+ 组地址（Set Index）+ 块内偏移（Offset）”，其中组地址位数=log₂G，标记位位数=主存块地址位数 - 组地址位数。
    • 例：同上主存与Cache参数，若G=2¹⁰（1024组），K=2（每组2块），则地址结构为“标记位6位（16-10）+ 组地址10位 + 偏移4位”。
  3. 查询流程：用组地址定位Cache组，将主存标记位与该组内K个块的标记位同时比较，若某块标记位一致且有效位为1，则命中。
  4. 优点：冲突缺失远少于直接映射（同一组有K个块可选），硬件成本低于全相联映射（仅需比较组内K个块），是平衡性能与成本的最优方案。
  5. 缺点：相联度K越大，硬件成本越高（比较器数量随K增加）。
  6. 适用场景：主流CPU Cache（如L1、L2 Cache，常见K=2/4/8路组相联）。
image-20251214152937079

（4）习题课核心结论

  • 映射方式对命中率的影响：全相联 ≥ 组相联（K越大命中率越高） ≥ 直接映射。
  • 硬件复杂度：全相联 ＞ 组相联 ＞ 直接映射。
  • 例题：若Cache容量为64KB，块大小为32B，采用4路组相联（K=4），则Cache组數G=（64KB/32B）/4=（2¹⁶/2⁵）/2²=2⁹=512组，组地址位数=9位。

4-7-4 高速缓冲存储器cache — 替换算法

当Cache缺失且Cache（或组相联的组）已满时，需淘汰旧块以存入新块，替换算法决定“淘汰哪个旧块”，核心目标是“尽可能淘汰未来不访问/晚访问的块”，提升后续命中率。

一、随机替换算法（Random Replacement, RR）

  1. 原理：随机选择一个旧块淘汰，不考虑块的访问历史。
  2. 优点：硬件实现最简单（仅需随机数生成器），无额外存储开销。
  3. 缺点：命中率低（可能淘汰未来即将访问的块，如循环访问的块）。
  4. 适用场景：Cache容量大、块替换频率低的场景（极少单独使用，仅作为基础参考）。

二、先进先出算法（First-In-First-Out, FIFO）

  1. 原理：按“块进入Cache的先后顺序”淘汰，先进入的块先淘汰（认为早进入的块未来访问概率低）。
  2. 实现：为每个Cache块（或组内块）设置“时间戳”，记录进入顺序；淘汰时选择时间戳最早的块。
  3. 优点：实现简单（仅需维护时间戳队列），无访问历史记录开销。
  4. 缺点：存在“Belady异常”——当Cache容量增大时，命中率反而可能降低（例：访问序列为1→2→3→4→1→2→5→1→2→3→4→5，Cache容量为3时命中率高于容量为4时）。
  5. 适用场景：访问序列无明显“近期重复访问”特征的场景（如部分嵌入式系统）。

三、最近最少使用算法（Least Recently Used, LRU）

  1. 原理：淘汰“最近一段时间内最少被访问的块”（基于“局部性原理”，认为近期少访问的块未来也少访问），是实际应用中命中率最高的经典算法。
  2. 实现方式（以组相联Cache为例）
    • 栈实现：为每组维护一个“访问栈”，块被访问时移至栈顶，淘汰时移除栈底（栈底为最近最少使用块）。
    • 计数器实现：为每个块设置计数器，块被访问时计数器清0，其他块计数器加1；淘汰时选择计数器值最大的块（值越大表示越久未访问）。
  3. 优点：命中率远高于RR和FIFO，符合程序局部性原理。
  4. 缺点：硬件实现较复杂（需维护访问栈或计数器，尤其当组相联度K大时），有一定存储开销（计数器/栈的存储）。
  5. 适用场景：主流CPU Cache（如L1、L2 Cache，是最常用的替换算法）。

四、最不经常使用算法（Least Frequently Used, LFU）

  1. 原理：淘汰“一段时间内被访问次数最少的块”（基于“访问频率”，认为访问次数少的块未来访问概率低）。
  2. 实现：为每个块设置“访问计数器”，块被访问时计数器加1；淘汰时选择计数器值最小的块（若值相同，可结合FIFO淘汰早进入的块）。
  3. 优点：对“访问频率差异大”的序列命中率高（如某块频繁访问，计数器值大，不会被淘汰）。
  4. 缺点：
    • 无法处理“突发访问”（如某块早期频繁访问，后期不再访问，但计数器值仍大，会持续占用Cache，导致新块无法存入）。
    • 需定期重置计数器（避免计数器溢出，且防止旧的高频率块长期占用）。
  5. 适用场景：访问频率稳定的场景（如服务器中长时间运行的固定任务）。

五、习题课核心对比与例题

算法 核心逻辑 命中率 硬件复杂度 适用场景
RR 随机淘汰 最低 最低 参考场景
FIFO 淘汰最早进入的块 较低 低 无近期重复访问的场景
LRU 淘汰最近最少使用的块 最高 中 主流CPU Cache
LFU 淘汰访问次数最少的块 较高 中 访问频率稳定的场景

例题：Cache采用4路组相联，某组内块的访问序列为“块A→块B→块C→块D→块A→块E”（E为新块，组已满），各算法淘汰结果：

  • RR：随机淘汰A/B/C/D中的一个。
  • FIFO：淘汰最早进入的块A。
  • LRU：最近最少使用的块为B（最后访问顺序：A→D→C→B），淘汰块B。
  • LFU：访问次数均为1（A被访问2

例题

image-20251203151446589
  1. 块大小 → 决定块内偏移（Offset）位数
  2. Cache 行数 → 决定索引（Index）位数
  3. 主存地址总位数 → 剩余的是标记(Tag)(主存分区号)位数

$Offset 位数=log_2(块大小)$

$Index 位数=log_2(Cache 行数)$

$Cache 行数=\frac{Cache数据区大小}{块大小}$

$Tag(主存分区号)位数=地址总位数−Index 位数−Offset 位数$

考试里至少存在 3 种不同含义的地址：

名称 谁用 包含什么
主存地址 CPU 给出的 Tag + 行号 + 块内地址
Cache 地址 Cache 内部定位 行号 + 块内地址
块表内容 Cache 控制信息 Tag + Valid

Tag (16 bits) | Index (12 bits) | Offset (4 bits)

1. 地址例子

假设 32 位主存地址 = 0x12345678
先转二进制（32 位）：
0001 0010 0011 0100 0101 0110 0111 1000

按 16 | 12 | 4 划分：

  • 高 16 位 0001 0010 0011 0100 = 0x1234 → Tag
  • 中间 12 位 0101 0110 0111 = 0x567 → Index
  • 低 4 位 1000 = 0x8 → Offset

2. 主存分区号

这里的 主存分区号 就是 Tag，即 0x1234。
它的作用是：当我们根据 Index（0x567）找到 Cache 第 0x567 行时，比较这一行中存储的 Tag 是否等于 0x1234，若相等且有效位为 1，则命中。

Offset 不参与 Cache 查找

  • Cache 是按块存储和管理的
  • 查找时只用 Tag 和 Index
  • Offset 只在块内寻址时使用，不决定放在 Cache 哪一行

为什么要有 Offset？

因为 CPU 可能只需要访问一个字节，但 Cache 一次读取/写入的是一个块（16 字节）。Offset 告诉我们在块内精确定位。

地址对齐

通常数据块在内存中按块大小对齐。比如：

  • 块大小 16 B ⇒ 块起始地址的低 4 位都是 0
  • 所以一个块的起始地址 = Tag | Index | 0000