Cache

1. Cache 概念

1.1. 定义与类比

• Cache (高速缓存)：一个存放待用事物（如数据或指令）的安全场所，用于加速对这些事物的访问。
• 类比：图书馆中的书桌。书桌上放着当前正在阅读或即将阅读的书籍，避免每次都去书架（主存）查找。
• 计算机中的位置：位于处理器和主存之间的一个或多个存储层次。

1.2. 历史与现状

• Cache 的使用基于局部性原理 (Principle of Locality)：
  • 时间局部性 (Temporal Locality)：如果一个数据项被访问，那么它在不久的将来很可能再次被访问。
  • 空间局部性 (Spatial Locality)：如果一个数据项被访问，那么与它相邻的数据项也很可能在不久的将来被访问。

2. 简单的 Cache 结构与访问 (直接映射)

2.1. 基本问题

当处理器请求数据项 Xn 时： 1. 如何知道 Xn 是否在 Cache 中？ 2. 如果 Xn 在 Cache 中，如何找到它？

2.2. 直接映射 (Direct Mapped) Cache

• 定义：一种 Cache 结构，其中每个主存储器地址仅仅对应到 Cache 中的一个确定位置。
• 映射方法： (块地址) mod (Cache 中的块数)
  • 块地址 (Block Address)：如果块大小为1个字，块地址就是字地址。如果块大小为多个字/字节，则块地址是 (字节地址) / (每块字节数)。
  • 取模运算简化：如果 Cache 中的块数是 2 的幂（例如 2^k），则取模运算简化为取块地址的低 k 位作为 Cache 索引 (Index)。
• 示例：一个有8个字块的 Cache (即 8 个位置)。
  • 需要 log₂(8) = 3 位作为索引。
  • 主存地址 X 被映射到 Cache 字 X mod 8 (即 X 的低3位)。
  • 例如，地址 00001₂ (1), 01001₂ (9), 10001₂ (17), 11001₂ (25) 都映射到 Cache 中的第 001₂ (1) 块。

2.3. 解决数据识别问题：标记 (Tag)

• 问题：由于多个主存地址可能映射到同一个 Cache 位置，如何区分 Cache 中存储的数据项是哪一个主存地址的？
• 解决方案：在 Cache 中为每个数据项增加一个标记 (Tag)。
  • 标记内容：包含地址的高位部分，即那些没有被用作 Cache 索引的位。
  • 作用：当通过索引找到 Cache 中的一个位置后，将该位置存储的标记与请求地址的标记部分进行比较，如果匹配，则说明找到了正确的数据。

2.4. 解决空块/无效数据问题：有效位 (Valid Bit)

• 问题：Cache 刚启动时是空的，或者某些块可能包含无效的旧数据。如何标识一个 Cache 块中的数据是否有效？
• 解决方案：为每个 Cache 块增加一个有效位 (Valid Bit)。
  • 有效位 = 1: 表示该 Cache 块中的数据和标记是有效的。
  • 有效位 = 0: 表示该 Cache 块中的数据是无效的，不能使用。
  • 处理器启动时，所有有效位被清零。

2.5. 重点：Cache 作为预测技术

• Cache 依赖局部性原理，预测处理器接下来可能需要的数据，并尝试将其保留在更高速的存储层次中。
• 当预测错误（Cache 缺失）时，有机制从较低层次的存储器中获取正确数据。
• 现代计算机 Cache 命中率通常高于 95%。

3. Cache 访问过程与示例 (直接映射)

3.1. 访问序列示例

以一个8块（块大小为1个字）的空 Cache 为例，演示一系列地址访问的行为。 * 地址格式 (5位示例)：假设5位地址，低3位为索引，高2位为标记。 * 冲突 (Conflict)：当两个不同的主存地址映射到同一个 Cache 索引时，后访问的会替换掉先访问的。例如，地址 10010₂ (18) 和 11010₂ (26) 都映射到索引 010₂。如果先加载26，再加载18，则18会替换掉26。这种替换体现了时间局部性（最近访问的替换较早访问的）。

3.2. 地址划分

一个32位地址在一个直接映射 Cache 中通常被划分为： * 标记域 (Tag)：用于与 Cache 中存储的标记进行比较。 * Cache 索引域 (Index)：用于选择 Cache 中的哪一个块/行。 * 字节偏移域 (Byte Offset)：用于在一个块内部选择具体的字节（如果块大小大于1字节）。

示例参数 ： * Cache 容量: 1024 个字 (4KB，假设1字=4字节) * 块大小: 1 个字 (4字节) * 地址宽度: 32 位 * 字节偏移: log₂(4字节/块) = 2 位 (地址最低2位) * 索引: log₂(1024块) = 10 位 (地址中字节偏移之上的10位) * 标记: 32 - 10 (索引) - 2 (字节偏移) = 20 位 (地址最高20位)

查找过程 ： 1. 使用地址的索引位选择 Cache 中的一个特定项。 2. 检查该项的有效位是否为1。 3. 如果有效，比较该项存储的标记与地址的标记位。 4. 如果标记匹配且有效位为1，则 Cache 命中 (Hit)，将对应的数据字（或根据字节偏移选择的字节）提供给处理器。 5. 否则，Cache 缺失 (Miss)。

3.3. Cache 总位数计算

Cache 不仅存储数据，还存储标记和有效位。 * 公式: 总位数 = (块数) × (每块数据位数 + 每块标记位数 + 每块有效位数) * 示例 (16KB数据，块大小4字，32位地址)： * 数据大小: 16KB = 4096 字。 * 块大小: 4 字/块。 * 块数: 4096字 / (4字/块) = 1024 块。 * 索引位数 (n): log₂(1024) = 10 位。 * 每块数据位数: 4字/块 × 32位/字 = 128 位。 * 字内偏移位数 (m，用于选择块内哪个字): log₂(4字/块) = 2 位。 * 字节偏移位数 (这里假设为2，包含在字内偏移的考虑中，或者说是字地址的最低两位): 2 位。 * 标记位数: 32 - n (索引) - m (字偏移) - 2 (字节偏移) = 32 - 10 - 2 - 2 = 18 位。 * 注意：原文公式 32 - (n + m + 2) 中的 m 是指 log₂(块中字数)，n 是指 log₂(块数)，+2 是字节偏移。所以这里 m=2, n=10。标记为 32 - (10+2+2) = 18 位。 * 有效位数: 1 位/块。 * 总位数: 2¹⁰ × (4 × 32 + 18 + 1) = 1024 × (128 + 18 + 1) = 1024 × 147 = 147 Kbits。 * 数据存储量为 16KB = 128 Kbits。总存储开销是数据量的 147/128 ≈ 1.15 倍。

3.4. 将地址映射到多字大小的 Cache 块中

• 示例 (64块Cache，每块16字节，字节地址1200)：
  1. 块地址: 字节地址 / 每块字节数 = 1200 / 16 = 75。
  2. Cache 块号 (索引): (块地址) mod (Cache中的块数) = 75 mod 64 = 11。
  3. 地址1200到1215都映射到 Cache 的第11块。

3.5. 块大小对缺失率的影响

• 优点：较大的 Cache 块能更好地利用空间局部性，通常会降低缺失率。
• 缺点：
  1. 竞争增加: 当块大小相对于 Cache 总容量过大时，Cache 中块的总数会变少，导致对这些少量块的竞争加剧，反而可能使缺失率上升（因为一个块在被多次访问前就可能被替换掉）。
  2. 空间局部性减弱: 过大的块中，远距离字之间的空间局部性可能不强。
  3. 缺失代价增加 (Miss Penalty)：从较低存储层次取出并传输较大块所需的时间更长，增加了缺失代价。
• 权衡: 需要在缺失率的降低和缺失代价的增加之间找到平衡点。可以通过优化存储系统（如增加存储器带宽）来支持更大的块。

3.6. 减少缺失代价的技术

当缺失发生时，较大的块会带来较长的传输延迟。 1. 提前重启 (Early Restart)： * 当块中 CPU 所需字一旦返回，处理器就马上继续执行，无需等待整个块传输完毕。 * 对指令 Cache 效果好：指令访问通常具有连续性。 * 对数据 Cache 效果较差：数据访问模式不可预测，且处理器可能在块传输完成前请求其他块的数据，导致 Cache 阻塞。 2. 请求字优先 (Requested Word First) / 关键字优先 (Critical Word First)： * 重新组织存储器传输顺序，首先传输 CPU 请求的那个字到 Cache。 * 然后传输该块的剩余部分（通常从请求字的下一个地址开始，然后绕回块的开头，即 "wrap-around fill"）。 * 比提前重启快，因为它总是最先拿到所需字。 * 但仍受限于与提前重启类似的问题（数据 Cache 阻塞等）。

4. Cache 缺失处理

4.1. 基本流程

• 控制单元检测到缺失。
• 从主存（或较低一级 Cache）取回所需数据。
• 缺失处理由处理器控制单元和独立的 Cache 控制器共同完成。
• 流水线阻塞 (Pipeline Stall)：简单的顺序执行处理器在 Cache 缺失时会阻塞，等待主存操作完成。复杂乱序执行处理器可能在等待时执行其他指令。

4.2. 指令 Cache 缺失处理步骤

1. 将程序计数器 (PC) 的原始值（当前 PC - 4，因为PC已指向下一条指令）送到存储器。
2. 通知主存执行读操作，并等待完成。
3. 写 Cache 项：
   • 将从主存取回的数据写入 Cache 的数据部分。
   • 将地址的高位（来自ALU或PC的原始值）写入标记域。
   • 设置有效位。
4. 重启指令执行的第一步（重新取指），此时指令应在 Cache 中。
5. 数据 Cache 缺失处理类似：处理器阻塞，直到数据从存储器取回。

5. 写操作处理

5.1. 写操作的复杂性

• 如果只写入数据 Cache 而不改变主存，会导致 Cache 和主存不一致 (Inconsistent)。

5.2. 写直达 (Write-Through)

• 定义: 写操作总是同时更新 Cache 和下一级存储器（如主存），以保持二者一致。
• 写缺失处理 (通常采用写分配):
  1. 从主存中取出包含目标地址的块到 Cache (写分配)。
  2. 将新数据写入 Cache 中的对应位置。
  3. 同时，将新数据写入主存中的对应位置。
• 性能问题: 每次写操作都要访问主存，速度慢，可能花费数百个处理器周期，严重影响性能。

5.3. 写缓冲 (Write Buffer)

• 定义: 一个保存等待写入主存数据的缓冲队列。
• 工作原理 (配合写直达):
  1. CPU 执行写操作时，数据写入 Cache 和写缓冲。
  2. 处理器可以立即继续执行。
  3. 写缓冲随后负责将数据异步地写入主存。
• 问题:
  • 如果写缓冲已满，处理器仍需等待。
  • 如果存储器写速度远慢于处理器产生写操作的速度，写缓冲会被填满。
• 改进: 增加写缓冲深度可以减少因写操作突发导致的阻塞。

5.4. 写回 (Write-Back)

• 定义: 当发生写操作时，新值仅仅被写入 Cache 块中。
• 脏位 (Dirty Bit): 每个 Cache 块关联一个脏位。如果块被修改，脏位置1。
• 写回时机: 只有当被修改过（脏位为1）的块被从 Cache 中替换出去时，才需要将其内容写回到较低层存储结构。
• 优点: 显著减少了对主存的写操作次数，可以提高系统性能，尤其是在写操作频繁的场景。
• 缺点: 实现比写直达复杂，需要处理脏位，且在多处理器系统中缓存一致性维护更复杂。

5.5. 写缺失策略

1. 写分配 (Write Allocate) (最常用，尤其配合写直达):
   • 发生写缺失时，先从主存取回数据块到 Cache，然后在 Cache 中进行写操作（同时根据写策略更新主存）。
   • 利用了空间局部性。
2. 不写分配 (No-Write Allocate / Write Around):
   • 发生写缺失时，只更新主存中的数据，不将数据块加载到 Cache。
   • 原因：有时程序会写整个块（如操作系统清零页面），此时先读取旧数据块是不必要的。
   • 一些计算机允许基于每一页来更改写分配策略。

5.6. 写回 Cache 的复杂性

• 不能立即重写块: 在写回 Cache 中，如果发生写缺失时直接重写 Cache 中的块（不知道里面是否是脏数据），可能会破坏尚未写回主存的有效数据。
• 两周期写操作或写缓冲:
  • 两周期: 第一个周期检查命中情况，第二个周期才真正执行写操作。
  • 存储缓冲区 (Store Buffer / Write Buffer): 处理器查找 Cache 并将数据放入存储缓冲区。如果命中，在下一个空闲的 Cache 访问周期将数据从缓冲区写入 Cache。
• 写直达 Cache 的写操作: 通常可以在一个周期内完成（读标记并写数据部分）。
• 写回 Cache 使用写缓冲降低缺失代价: 当替换一个脏块时，可将其移入写回缓冲器，同时从主存读入新块。写回缓冲器再将脏块写入主存。这可以将替换脏块时的缺失代价减少一半（如果下一次缺失不立即发生）。

6. Cache 示例：内置 FastMATH 处理器

6.1. 结构特点

• MIPS 架构，嵌入式微处理器。
• 分离的指令 Cache (I-Cache) 和数据 Cache (D-Cache)。
• 每个 Cache 容量: 16KB (4096 字)。
• 块大小: 16 个字/块 (16 * 4 = 64 字节/块)。
• Cache 块数: 16KB / (64字节/块) = (16 * 1024) / 64 = 256 块。
• 地址划分 (32位):
  • 字节偏移 (选择块内字节): log₂(64) = 6 位 (最低6位)。
    • 其中，字偏移 (选择块内16个字中的一个): log₂(16) = 4 位 (字节偏移的高4位，即地址的 bit 5-2)。
    • 字内字节偏移 (选择字内4个字节中的一个): log₂(4) = 2 位 (字节偏移的低2位，即地址的 bit 1-0)。
  • 索引域 (选择256个块中的一个): log₂(256) = 8 位 (字节偏移之上的8位，即地址的 bit 13-6)。
  • 标记域: 32 - 8 (索引) - 6 (字节偏移) = 18 位 (最高18位)。
• 数据选择: 使用一个 16选1 的多路选择器，由字偏移控制，从块中选择所需的字。
• 实现细节: 可能使用一个大容量 RAM 存数据，一个小容量 RAM 存标记。大 RAM 的额外地址位由块偏移（字偏移）提供。

6.2. 操作

• 12级流水线，峰值时每周期可请求1个指令字和1个数据字。
• 读请求步骤 (与通用描述一致):
  1. 地址送 Cache (PC -> I-Cache, ALU -> D-Cache)。
  2. 命中则通过多路选择器选字返回。
  3. 缺失则从主存加载到 Cache 再返回。
• 写操作:
  • 同时提供写直达和写回机制，由操作系统决定。
  • 有一个单项写缓冲 (One-entry write buffer)。