考研笔记

Cache 和主存的映射方式

映射方式回答一个问题：主存的某一块，可以放进 Cache 的哪些行？

答案的取值范围只有三种——只能放一行（直接映射）、任意一行（全相联）、某一组内的任意一行（组相联）。三种方式的全部差别，都可以从这一句话推出来：能放的位置越多，命中率越高，但要并行比较的标记也越多，需要的比较器就越多。

这是 第 2 章立下的”面积换时间”那条线在本章的第一次出现，而且是最干净的一次：比较器的数量就是相联度本身。

机制

三种映射方式

设 Cache 共 行，主存块号为 。

直接映射：每个主存块只能放进唯一确定的一行。

行号
  • 硬件最简单：行号一算就出来，只需 1 个比较器
  • 冲突缺失最严重：即使 Cache 空着，映射到同一行的两个块也会互相驱逐
  • 不需要替换算法——目标行只有一个，没得选

全相联映射：任何主存块可以放进任何一行。

  • 命中率最高，没有冲突缺失
  • 需要 个比较器同时比较全部标记，硬件代价随容量线性增长
  • 标记位最长（整个主存块号都要存）
  • 只适用于行数很少的场合，如 TLB

组相联映射：Cache 分成 组，每组 行（称 路组相联，）。组间直接映射、组内全相联。

组号
  • 需要 个比较器
  • 退化为直接映射，（）退化为全相联——三种方式是同一个连续谱的两端和中间

地址划分的统一公式

主存地址被切成三段：

标记剩余高位行号组号中间位块内地址低位
方式块内地址中间段位数标记位数
直接映射块大小总位数
全相联0总位数
路组相联，总位数

块内地址位数在三种方式下都一样，它只由块大小决定。相联度提高一倍，组号少 1 位、标记多 1 位。

先按编址单位确定”块大小”的含义：按字节编址时块大小以字节计，按字编址时以字计。这是拆地址前必须先定的事。

比较器数量：面积换时间的第三次应用

flowchart LR
    D["直接映射<br/>1 个比较器"] --> DR["硬件最省<br/>冲突缺失最多"]
    S["N 路组相联<br/>N 个比较器"] --> SR["折中<br/>现代 CPU 的选择"]
    F["全相联<br/>C 个比较器"] --> FR["命中率最高<br/>硬件不可扩展"]

    classDef cheap fill:#fdebd0,stroke:#e67e22
    classDef mid fill:#d5f5e3,stroke:#27ae60
    classDef rich fill:#d6eaf8,stroke:#2874a6
    class D,DR cheap
    class S,SR mid
    class F,FR rich

疑问点：全相联的标记比较是逐个比较还是并行比较，组相联的路数为什么很少

是并行比较，而且必须并行。 全相联 Cache 给每一行都配一个比较器，一次访问时所有比较器同时把本行标记与地址中的标记段比对，结果送进一个编码器给出命中的行号。逐个比较需要 拍，Cache 就失去了存在的意义。 这种”给每个存储单元配比较器、按内容并行检索”的结构，就是下面要讲的相联存储器。

组内行数（路数）确实很少，而且理由正是硬件代价： 比较器数量 = 路数，面积与功耗随路数线性增长； 更关键的是多路选择器的延迟随路数增长——命中判断在 Cache 访问的关键路径上，多一级选择就多一点延迟，可能直接拉低整个 CPU 的主频； 而命中率的收益在 4~8 路之后已经非常平坦。 于是现代 CPU 的典型取值是 L1 用 48 路，L2/L3 用 816 路，容量很小的 TLB 才用全相联。

设计哲学就是 2.2.1里那条”面积换时间”：先行进位加法器用面积换进位延迟，桶形移位器用面积换移位周期，这里用比较器面积换命中率。三处的取舍形式完全一样——收益递减而成本线性，所以最优点总在中间。

相联存储器

疑问点：什么是相联存储器

相联存储器（Associative Memory / CAM，按内容访问的存储器）是一种不给地址、给内容的存储器。

普通存储器：输入地址 → 输出内容。 相联存储器：输入一个内容（或它的一部分，称检索字）→ 所有单元并行比较 → 输出匹配单元的地址或它携带的数据。

实现方式就是每个存储单元自带一个比较器，加上一个屏蔽寄存器指定”比较哪几位”。

它在 408 里出现在三个地方： 全相联 Cache 的标记阵列（本节）； TLB（快表）——TLB 行数少、要求一拍出结果，是相联存储器最典型的应用； 组相联 Cache 的组内比较（小规模的相联比较）。

特点是速度快、硬件成本高、容量做不大——这三条互为因果，与全相联 Cache 的评价完全一致。

边界

边界辨析：组相联的划组规则存在两种口径，答案不同

这是本章唯一一处两本主流教材给出不同答案的地方，必须两种都会算。

题目：某计算机按字编址，Cache 有 4 行，Cache 与主存交换的块大小为 1 个字。Cache 初始为空，采用 2 路组相联映射和 LRU 替换，访问的主存地址依次为 0, 4, 8, 2, 0, 6, 8, 6, 4, 8，命中次数是多少？

块大小 1 个字，所以块号 = 字地址；4 行 2 路 → 2 组。

口径一：组号 块号 组数（低位取模）。 这是王道正文、唐朔飞教材和统考真题的口径。 十个地址全是偶数， 全为 0，全部挤进第 0 组：

步地址组结果组 0（左为 LRU）
100缺失0
240缺失0, 4
380缺失，淘汰 04, 8
420缺失，淘汰 48, 2
500缺失，淘汰 82, 0
660缺失，淘汰 20, 6
780缺失，淘汰 06, 8
860命中8, 6
940缺失，淘汰 86, 4
1080缺失，淘汰 64, 8

命中 1 次。

口径二：主存按 Cache 总行数分区，区内 4 块按每组 2 块顺序分配。 这是蒋本珊教材的口径，也是这道题的参考答案所采用的：块 0,1,4,5,8,9 → 第 0 组，块 2,3,6,7 → 第 1 组，即组号 块号。

步地址组结果组 0组 1
100缺失0—
240缺失0, 4—
380缺失，淘汰 04, 8—
421缺失4, 82
500缺失，淘汰 48, 02
661缺失8, 02, 6
780命中0, 82, 6
861命中0, 82, 6
940缺失，淘汰 08, 42, 6
1080命中4, 82, 6

命中 3 次。

同一道题，两种口径给出 1 次和 3 次两个答案。参考答案取的是 3 次。

层次辨析：考场上一律用低位取模，理由不只是"主流"

口径二在位段划分上讲不通，这是选择口径一更硬的理由。 按口径二，主存块 0 和块 1 同属第 0 组，而它们的”区号” 都是 0。如果标记就取区号，硬件将无法区分这两块；要区分就必须把标记定义成”块号的第 0 位加上第 2 位以上”这样一个不连续的位段。 一个不能用连续位段实现的划分规则，不可能是真实硬件的地址译码方式——它只能作为纸面上的分配约定存在。 而口径一（低位取模）的位段划分是干净的：低位是组号、高位是标记，两段连续，这正是 上面那张地址划分表的形式。

所以做题规则是： 默认一律用”组号 = 块号 mod 组数”，这是王道正文、唐朔飞教材和全部统考真题的口径。 只有当算出的答案不在选项里时，才回头考虑是否为非统考口径的题。 另一个识别信号是结果退化：像本题这样十个地址在低位取模下全落进同一组，这种”组相联退化成全相联”的题面在统考里不会出现。

“这种有争议的题考试真的会出吗”——统考不会。 这道题是教辅从其他教材的习题里收录进来的，参考答案自己也注明了”不同教材关于组相联映射的介绍并不相同”。它的价值不在答案，而在于让人第一次意识到”划组规则是一个约定，不是自然法则”；把两种口径各推一遍 trace，比记住”选 C”有用得多。

疑问点：两种划法在地址位段上分别取哪一段

常见的概括是”第一种低位区别组号（取模），剩下是标记；第二种高位区别组号（除法），剩下低位做标记”。 前半句完全正确，后半句需要修正。 口径二取的不是高位，而是”次低位”。若真的用最高位做组号，主存的高地址段会整体映射到一组、低地址段映射到另一组，与参考答案给出的分组 {0,1,4,5,8,9} / {2,3,6,7} 对不上。 实际的规则是先按每组 2 块连续分配、再循环，落到位段上取的是块号的第 1 位（中间位），剩下的位（含第 0 位）才是标记——这正是它位段不连续、无法用简单译码实现的原因。

直接映射不需要替换算法。 目标行唯一，“替换”就是无条件覆盖。题目若说”直接映射采用 LRU 替换算法”，本身就是错的。

全相联的标记位最长，直接映射最短。 因为中间段越长，留给标记的位越少。一道题问”哪种映射方式所需标记位最多”，答案永远是全相联。

冲突缺失只存在于直接映射和组相联。 见 3.5.2。

“相联度越高越好”是错的。 收益递减而成本线性，并且大相联度会拉长命中判断的关键路径。

对照速查

直接映射 路组相联全相联
主存块可放的位置唯一 1 行组内 行任意行
定位公式—
比较器数量1
标记位数最少中最多
冲突缺失最多中无
需要替换算法不需要需要需要
硬件复杂度最低中最高
典型用途早期 / 大容量低成本现代 L1~L3TLB
地址段位数
块内地址块大小，三种方式相同
行号 / 组号直接 ；组相联 ；全相联 0
标记总位数减去以上两段

考点

  • 三种映射是同一个连续谱： 是直接映射， 是全相联
  • 比较器数量 = 相联度，这是”面积换时间”在本章的形式
  • 直接映射不需要替换算法
  • 全相联标记位最长、无冲突缺失、只用于 TLB 等小容量场合
  • 块内地址位数只由块大小决定，三种方式相同
  • 相联存储器按内容并行检索，用于 TLB 和全相联 Cache
  • 组相联划组一律用”组号 = 块号 mod 组数”；蒋本珊口径只在个别教辅习题中出现，统考不用
  • 现代 CPU L1 用 48 路，L2/L3 用 816 路

链接

反向链接