Okay, three, two, one, let's jam

310 Cache 映射逻辑

5 min read

Cache 映射逻辑

304 高速缓冲存储器Cache

核心逻辑与结构对比

映射方式直接映射 (Direct Mapped)全相联映射 (Fully Associative)组相联映射 (Set-Associative)
核心逻辑固定位置
主存中的一个块只能映射到 Cache 中的一个特定行。这是一种“多对一”的映射关系，简单但容易发生冲突。
地址计算：Cache行号 = 主存块号 % Cache总行数		任意位置
主存中的一个块可以映射到 Cache 中的任何一个空闲行。这是一种“多对多”的映射关系，灵活但硬件复杂。
查找方式：并行比较所有行的 Tag。		组内任意位置
主存中的一个块先映射到一个特定的组，然后在该组内的任何一行存放。这是前两者的折中方案。
地址计算：Cache组号 = 主存块号 % Cache总组数
主存地址结构分为三个字段：Tag (标记), Index (索引/行号), Offset (块内地址)。
Index 字段直接决定了其在 Cache 中的位置。		分为两个字段：Tag (标记), Offset (块内地址)。
无 Index 字段，因为它可以存放在任何位置。		分为三个字段：Tag (标记), Set (组号), Offset (块内地址)。
Set 字段决定了其在 Cache 中的组。
Cache 结构一个简单的线性数组。每个 Cache 行包含一个有效位、一个 Tag 和数据块。类似于一个内容寻址存储器 (CAM)。所有 Tag 必须能被同时比较。硬件成本最高。Cache 被划分为多个组 (Set)，每个组内包含多行 (Way)。在组内进行全相联查找。

结构图示 (Plain Code)

1. 直接映射 (Direct Mapped)

主存地址结构:

+------------------+----------------+------------------+
|      Tag         |     Index      |      Offset      |
|    (标记位)       | (Cache 行号)    |    (块内地址)     |
+------------------+----------------+------------------+

Cache 结构:

Index
  0   +-------+------------------+------------------+
      | Valid |       Tag        |    Data Block    |
      +-------+------------------+------------------+
  1   +-------+------------------+------------------+
      | Valid |       Tag        |    Data Block    |
      +-------+------------------+------------------+
      ...
 M-1  +-------+------------------+------------------+
      | Valid |       Tag        |    Data Block    |
      +-------+------------------+------------------+

2. 全相联映射 (Fully Associative)

主存地址结构:

+------------------------------------+------------------+
|                Tag                 |      Offset      |
|              (标记位)               |    (块内地址)     |
+------------------------------------+------------------+

Cache 结构: (硬件逻辑上需要并行比较所有行的 Tag)

      +-------+------------------+------------------+
Line 0| Valid |       Tag        |    Data Block    |
      +-------+------------------+------------------+
      +-------+------------------+------------------+
Line 1| Valid |       Tag        |    Data Block    |
      +-------+------------------+------------------+
      ...
      +-------+------------------+------------------+
Line N| Valid |       Tag        |    Data Block    |
      +-------+------------------+------------------+

3. 组相联映射 (Set-Associative)

主存地址结构:

+------------------+----------------+------------------+
|      Tag         |      Set       |      Offset      |
|    (标记位)       |   (Cache 组号)  |    (块内地址)     |
+------------------+----------------+------------------+

Cache 结构: (以 2-way 组相联为例)

Set
 0  ┌ Way 0 +-------+------------+------------------+
    │       | Valid |    Tag     |    Data Block    |
    │       +-------+------------+------------------+
    └ Way 1 +-------+------------+------------------+
            | Valid |    Tag     |    Data Block    |
            +-------+------------+------------------+
 1  ┌ Way 0 +-------+------------+------------------+
    │       | Valid |    Tag     |    Data Block    |
    │       +-------+------------+------------------+
    └ Way 1 +-------+------------+------------------+
            | Valid |    Tag     |    Data Block    |
            +-------+------------+------------------+
    ...
S-1 ┌ Way 0 +-------+------------+------------------+
    │       | Valid |    Tag     |    Data Block    |
    │       +-------+------------+------------------+
    └ Way 1 +-------+------------+------------------+
            | Valid |    Tag     |    Data Block    |
            +-------+------------+------------------+

总结

这三种方式是在 硬件成本 和 命中率 (或冲突率) 之间做出的权衡。

特性直接映射全相联映射组相联映射
冲突率高无 (仅有容量失效)低
硬件成本低高中等
查找速度最快 (直接索引)最慢 (并行比较)较快 (组内并行比较)

现代 CPU 的 Cache 设计普遍采用组相联映射，因为它在成本和性能之间取得了最佳的平衡。

Graph View