Cache映射计算

在刷题时经常会遇到 Cache 与主存相关的计算题，很长一段时间没看教材，具体概念记得不那么清楚了，算起来总是概念一大堆，分不清谁是谁。网上有很多优秀的文章，讲清楚了 Cache 是怎么工作的，也通俗解释了三种映射方式，但文章看多了反而更乱。这篇文章让我们回到 Cache 计算的主线上来，把思路理清楚。

Cache映射计算到底在计算啥

所有题目的计算，基本都是围绕 Cache 工作中最核心的一件事展开：把主存中的内容搬运到Cache里，供CPU使用。但是当CPU需要使用某一段数据时，用的是主存地址去查找。也就是说，CPU并不会刻意去用一个类似 “Cache 地址” 的东西找数据，而是通过硬件电路，把主存地址转换成 Cache 存储器里的地址。这段电路的实现方法，就是我们最熟悉的三种映射方式：直接映射、全相联映射和组相联映射。

需要特别注意，Cache 和主存之间数据的搬运是按“块”进行的，也就是 Cache 和主存都会被划分成大小相同的若干块。

各类映像方法中主存与Cache的关系

现在我们假设CPU给出一个主存地址0x1234E8F8，来看看在不同的映像关系下如何解读。

直接映像

在直接映像当中，其实就是先算出（或者题目直接给了）Cache大小为多少块，然后主存按照滚动标记的方法标记所有的块。现在假设Cache大小为3块，主存有6块，那么：

可以看出实际的主存块对应Cache块的计算公式就是：主存块号 % Cache块数

回到开头给出的主存地址0x1234E8F8，在直接映像的规则下，我们假设Cache共有1024块，块大小为16B（容量16KB）。

现在开始推导主存地址的转换，首选块内的数据需要进行标记，也就是块内偏移，我们按照字节编址也就是需要块大小 16B = \(2^4\)B→ 共4位用来表示一个数据在块内的哪个位置。

接下来是块号的确认，现在已知主存地址需要求得该地址在主存中的块号，也就是主存块号 = 主存地址 ÷ 块大小（16 B）= 0x1234E8F8 ÷ 16。除法在二进制下就是右移 4 位（丢掉块内偏移）。

现在我们得到了主存块号就可以套用上面的公式，即主存块号 % Cache块数 = 0x1234E8F ÷ 1024。1024 =2^10，在二进制里，模2^10就等于只保留这个数的低 10 位。由此我们得到了该地址对应的Cache 块号。

现在我们可以完整的解读出主存地址（32位）：

• 块内偏移：块大小 16B = (2^4)B → 占低 4 位
• Cache 块号（索引）：Cache 共 1024 = (2^{10}) 块 → 占中间 10 位
• Tag：剩余高位 32 - 10 - 4 = 18 位

具体计算过程：

1. 将0x1234E8F8转为 32 位二进制：

   0001 0010 0011 0100 1110 1000 1111 1000

2. 从低位开始取：
   • 块内偏移（低4位）：1000
   • 索引（中间10位）：位4~13，即1010001111（从⑥⑦⑧取出的具体值）
3. 装入 Cache 的地址 =索引 + 块内偏移=1010001111 1000（14位二进制）

结论：直接映像时，CPU只需取地址中间 10 位找到 Cache 块号，再用低 4 位定位块内字节，高位 Tag 用于比较确认是否命中。

全相联映像

与直接映像完全不同，全相联映像的核心思想是：主存中的任意一块可以放入 Cache 中的任意一块，没有任何固定位置的限制。
因此，主存地址中不再需要“索引”字段来指定 Cache 块号，而是把全部高位都当作标记（Tag），依靠硬件并行搜索来定位数据。

还是用同一个例子：Cache 共 1024 块，块大小 16B，主存地址0x1234E8F8。

1. 主存地址的划分
在全相联映像下，主存地址只被切成两部分：

• 块内偏移：与直接映像一致，块大小 16B → 占低 4 位。
• Tag：剩余的全部高位。总地址 32 位，减去偏移 4 位，得到 28 位。
  这 28 位的作用是唯一标识一个主存块（因为主存总块数 = 2^28 块远远超出实际主存容量，余下高位在实际中会按主存大小截断，但地址线保留这些位用于比较）。

对比直接映像：直接映像将中间 10 位用作索引，Tag 仅 18 位；全相联则取消了索引，把索引位也合并进了 Tag，使 Tag 变成了 28 位。这就是为什么全相联的标记位数通常更长。

2. 如何找到对应的 Cache 块？
由于地址里不包含任何 Cache 位置信息，硬件必须进行“按内容查找”：

• 将主存地址中的28 位 Tag同时与 Cache 内所有 1024 个块的标记字段进行比较。
• 同时检查该块的有效位是否为 1。
• 如果某一个块的标记匹配且有效，即为命中，该块的物理编号 k（0～1023）就是目标 Cache 块号。
• 若全部不匹配，则发生缺失，需要从主存调入该块，并放入某个 Cache 块（由替换算法决定，如 LRU）。

3. 装入 Cache 的地址
命中后，CPU 访问 Cache 的地址由两部分组成：

• Cache 块号：由匹配电路给出的 k（10 位二进制，因为 1024 块需要 10 位来表示）。
• 块内偏移：直接取自原主存地址的低 4 位。

因此，Cache 地址 ={k, 块内偏移}，共 10 + 4 = 14 位。

以0x1234E8F8为例：

• 低 4 位块内偏移：1000
• 高 28 位 Tag：0001 0010 0011 0100 1110 1000 1111（即原地址去掉低 4 位）
• 硬件将这 28 位 Tag 与所有 1024 个 Cache 块的标记并行比较，假设备替换后该块被放入第 513 号 Cache 块（二进制1000000001），则最终 Cache 地址为1000000001 1000。
• 注意：这个 513 号块是从匹配结果中得到的，而不是从主存地址中“算出来”的，这正是全相联与直接映像最本质的区别。

组相联映像

组相联映像是直接映像和全相联映像的折中方案：

• Cache 被分成若干组，每组内包含若干个块（如 4 块/组，称为 4 路组相联）。
• 主存块先通过取模运算固定映射到某一组（类似直接映像），但到了该组之后，可以放进组内的任意一块（类似全相联）。

这样既避免了直接映像的高冲突，又不像全相联那样需要在整个 Cache 中并行搜索。

沿用前面的例子：Cache 共 1024 块，块大小 16B，并采用4 路组相联。
则组数 = 1024 ÷ 4 = 256 组。组内可任意存放，组间则是固定的模运算映射。

主存地址划分：
主存地址0x1234E8F8（32 位）被划分为三个字段：

• 块内偏移：4 位（块大小 16B）
• 组索引：256 组 → (\log_2 256 = 8) 位
• Tag：剩余 32 - 8 - 4 = 20 位

映射公式：

• 主存块号 = 主存地址 ÷ 16（右移 4 位）
• 所在组号 =主存块号 % 组数=0x1234E8Fmod 256
  因为 256 = (2^8)，模运算直接保留主存块号的低 8 位。这 8 位恰好就是地址中紧接着块内偏移的中间 8 位，即组索引。

具体数值提取：
将0x1234E8F8展开为二进制：

0001 0010 0011 0100 1110 1000 1111 1000

• 块内偏移（低 4 位）：1000
• 组索引（紧接着的 8 位，位 4~11）：1000 1111（即0x8F，第 143 组）
• Tag（高 20 位）：0001 0010 0011 0100 1110（即0x1234E）

如何找到 Cache 块？

1. 硬件直接提取地址中的8 位组索引，定位到 Cache 的第 143 号组。
2. 将该组的4 个块的标记字段与地址中的20 位 Tag同时进行并行比较（类似全相联，但只比较 4 个块）。
3. 若某个块的标记匹配且有效位为 1，则命中。该块在这一组内的序号（0~3）即为组内块号。
4. 若全不匹配，则发生缺失，需从主存调入，并按替换算法（如 LRU）选择该组内一个块来存放新数据。

装入 Cache 的地址：
命中后，实际的 Cache 地址仍由Cache 块号 + 块内偏移构成（共 14 位）。

• Cache 块号 = 组号 × 每组块数 + 组内块号 =0x8F × 4 + 组内块号
  例如，假设该主存块被放在了第 143 组内的第 1 个块（组内块号=1），则 Cache 块号 = (143 \times 4 + 1 = 573)，二进制1000111101。
• 块内偏移不变，仍为1000。
• 所以最终 Cache 地址 =1000111101 1000。

关键要点：

• 主存地址中的组索引决定了去哪个组找（与直接映像的索引类似，但位数由组数决定，不再直接对应唯一的 Cache 块）。
• 组内搜索得到组内块号，再与组号组合才得到最终的 Cache 块号。
• 这种设计用较少的并行比较器（仅比较组内几块）获得了接近全相联的灵活性，是实际处理器中最常见的 Cache 映射方式。