3.3 Cache 的基本原理与映射方式

程序访问的局部性原理，Cache 的工作原理与性能计算，直接映射、全相联映射与组相联映射。

程序访问的局部性原理

• 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息，因为程序中存在循环；
• 空间局部性：在最近的未来要用到的信息，很可能与现在正在使用的信息在存储空间上是邻近的，因为指令通常是顺序存放、顺序执行的，数据一般也是以向量、数组等形式簇聚地存储在一起的。

Cache 的基本工作原理

把主存与 Cache 都划分为大小相等的块（Cache 的块也称为行），Cache 与主存之间以块为单位交换信息。CPU 发出读请求时：

1. 若访存地址在 Cache 中命中，就将此地址转换成 Cache 地址，直接对 Cache 进行读操作，与主存无关；
2. 若 Cache 不命中，则仍需访问主存，并把此字所在的块一次性地从主存调入 Cache（若此时 Cache 已满，则需根据某种替换算法用这个块替换 Cache 中原来的某块信息）。

地址映射方式

由于 Cache 行数比主存块数少得多，因此主存中只有一部分块的信息可放在 Cache 中。必须应用某种方法，把主存的地址定位到 Cache 中，称为地址映射。为了区分 Cache 中的行来自主存的哪一块，每行需要一个标记（Tag）；同时还需要一个有效位（V）说明该行中的信息是否有效。

直接映射

主存中的每一块只能装入 Cache 中的唯一位置：

• 优点：实现简单，只需比较一次 Tag，速度快；
• 缺点：不够灵活，即使 Cache 中别的位置空着也不能占用，冲突概率高，块冲突时会出现频繁的”抖动”，命中率最低。

全相联映射

主存中的每一块可以装入 Cache 中的任何位置，每行的标记用于指出该行取自主存的哪一块，所以 CPU 访存时需要与所有行的标记进行比较。

• 优点：比较灵活，Cache 块的冲突概率低，空间利用率高，命中率也高；
• 缺点：标记的比较速度较慢，实现成本较高，通常需采用昂贵的按内容寻址的相联存储器。

组相联映射

将 Cache 分成 $Q$ 个大小相等的组，每个主存块可以装入固定组中的任意一行，即组间采用直接映射、组内采用全相联映射：

每组有 $r$ 行时称为 $r$ 路组相联。当 $Q = 1$ 时变为全相联映射；当 $r = 1$ 时变为直接映射。

下面的模拟器默认采用 2 路组相联、LRU 替换。切换映射方式，对比同一段访存序列的命中率：

即时练习