存储器层次结构——高速缓存存储器
文章目录
- 高速缓存存储器
- 层次结构
- 通用的高速缓存存储器组织结构
- 直接映射高速缓存
- 组相联高速缓存
排版较难处理，请务必访问此处阅读
高速缓存存储器
层次结构
高速缓存是介于寄存器和主存储器之间的存储器，L1 高速缓存（一级缓存）的访问速度几乎和寄存器一样快，L1 高速缓存和主存之间又插入了一个更大的 L2 高速缓存，有些现代系统还包括一个更大的位于 L2 高速缓存和主存之间的 L3 高速缓存。
:::color1
高速缓存既保存数据，也保存指令。
- $ i-cache $：只保存指令的高速缓存。通常是只读的。
- $ d-cache $：只保存程序数据的高速缓存。
- 统一的高速缓存：既保存数据，也保存指令的高速缓存。
:::
在$ Intel Core i7 处理器的高速缓存层次结构中，每个 C P U 芯片有 4 个核，，每个核有私有的 的高速缓存层次结构中，每个 CPU 芯片有 4 个核，，每个核有私有的的高速缓存层次结构中，每个CPU芯片有4个核，，每个核有私有的L1 i-cache、 、、L1 d-cache $和 L2 统一的高速缓存。所有的核共享片上 L3 统一的高速缓存。
这个层次结构的一个有趣的特性是所有的 SRAM 高速缓存存储器都在 CPU 芯片上。
通用的高速缓存存储器组织结构
一个通用高速缓存的结构可以用一个元组来完全确定：
- 组数 (
)：整个高速缓存被划分为
个互不相交的“组”（Set），从组0一直到组
。组索引需要
个比特来定位。
- 行数 (
)：每一个组内包含
个“行”（Line）。根据
的取值不同，高速缓存可以分为直接映射高速缓存（
）、组相联高速缓存（
）和全相联高速缓存（只有一个组，
）。
- 块大小 (
字节)：每一行中包含一个高速缓存块（Cache Block），存储着真正从主存中复制过来的连续数据，大小为
字节。块偏移需要
个比特来定位。
高速缓存中的每一行都由三个关键部分组成：
- 有效位（Valid bit）：每行有
个有效位。用来指示这一行是否包含有效的数据（1表示有效，0表示无效）。
- 标记位（Tag bits）：每行有
个标记位（其中
，
为主存地址的总位数）。因为多个主存地址可能会映射到同一个缓存组，标记位用来唯一确定当前缓存块中存储的到底是哪一个内存块。
- 数据块（Data Block）：即图中的
。它是实际存放数据的地方，共
个字节。
高速缓存的总大小（Capacity，通常指能够存储的纯数据容量，不包括有效位和标记位等开销）由公式决定：字节，即：总容量 = 组数
每组的行数
每块的字节数。
图中的硬件地址结构是 CPU 寻址高速缓存（Cache）的核心机制。一个系统拥有 $ m $ 位主存地址，当 CPU 试图从主存中读取一个字时，它不会直接把整个地址发送给主存，而是将这 $ m $ 位地址划分成三个逻辑字段。
地址结构的字段描述- 块偏移（Block Offset）：
位
- 含义：用来在选中的高速缓存块（Cache Block）中定位目标数据的具体字节位置。
- 对应关系：由于高速缓存中每个数据块包含
字节，因此需要地址的低
位作为偏移量。例如，若
字节，则需要
位（可表示偏移量 0, 1, 2, 3）。
- 组索引（Set Index）：
位
- 含义：用来决定该内存地址映射到高速缓存中的哪一个“组”（Set）。
- 对应关系：通用高速缓存被划分成
个组。地址中间的这
位相当于一个数组的下标，告诉硬件应该去组 0 到组
中的哪一组去查找数据。
- 标记（Tag）：
位
- 含义：用来唯一标识映射到同一个高速缓存组的不同内存块。
- 对应关系：主存的大小远远大于高速缓存，这意味着会有很多不同的主存块映射到同一个高速缓存组中。地址的高
位（其中
）会与高速缓存行中的“标记位”进行比对，以确定当前缓存行里存的数据到底是不是 CPU 想要的那个内存块。
当 CPU 携带这个位地址去高速缓存中查找数据时，两者的结构通过以下三个步骤产生联系，实现“缓存寻址与命中判定”：
第一步：组选择（利用组索引![]()
位）
硬件抽取地址中间的位，作为索引定位到高速缓存对应的组。
- 结构联系：地址的
位直接对应高速缓存的
个组。由于硬件需要并行访问，组索引就像一个多路复用器的选择信号，瞬间帮 CPU 在纵向上筛选出具体某一个“组”空间。
第二步：行匹配（利用标记![]()
位与有效位）
进入选定的组后，硬件检查该组内的所有个行。对于每一行，硬件会同时做两件事：
- 检查该行的有效位（Valid bit）是否为 1。
- 将地址中的
位标记，与该行硬件结构里自带的
位标记字段进行相等性比较。
- 结构联系：如果组内某一行同时满足“有效位为1”且“标记完全匹配”，这就是一次缓存命中（Cache Hit）。这说明主存中的那个数据块此时此刻正躺在这一个高速缓存行里。如果找不到满足条件的行，就是缓存缺失（Cache Miss）。
第三步：字抽取（利用块偏移![]()
位）
一旦确定缓存命中，硬件就会来到该行对应的数据块（Data Block）中。
- 结构联系：数据块在结构上是一个从
到
字节的数组。地址底部的
位块偏移正是这个数组的下标。硬件根据
位的数值，精确地从
字节的数据块中抽取出 CPU 请求的那个字节或字（Word），并返回给 CPU。
| 衍生出来的量 | |
|---|---|
| 参数 | 描述 |
| $ M=2^m $ | 内存地址的最大数量 |
| $ s=\log_2(S) $ | 组索引位数 |
| $ b=\log_2(B) $ | 块偏移位数 |
| $ t=m-(s+b) $ | 标记位数 |
| $ C=B \times E \times S $ | 不包括像有效位和标记位这样开销的高速缓存大小（字节） |
直接映射高速缓存
根据每个组的高速缓存行数 E，高速缓存被分为不同的类。每个组只有 1 行（E=1）的高速缓存称为直接映射高速缓存。
- 组选择
- 核心操作：CPU 从主存地址中抽取出中间的
位组索引。
- 硬件行为：将这
位组索引视为一个无符号数，作为高速缓存组数组的下标，直接定位到对应的组
（在多个组中纵向筛选出目标组）。
- 行匹配
- 核心操作：在选中的组
中，检查是否存在一行满足命中条件。
- 判定条件：必须同时满足以下两个条件：
- 该行的有效位（Valid bit）必须为 1。
- 该行硬件结构中的标记位（Tag）必须与地址中的
位标记完全相等。
- 结果：若同时满足则缓存命中（Cache Hit），进入字选择；若都不满足，则为缓存缺失（Cache Miss）。
- 字选择
- 核心操作：在命中的那一行中，定位并提取出 CPU 请求的具体字节或字。
- 硬件行为：将地址中低位的
位块偏移视为字节数组的下标。由于高速缓存块是一个从
到
字节的数组，硬件根据 $b$ 位的数值，精准抽取出请求的起始字节并返回给 CPU。
- 行替换
- 核心操作：当发生缓存缺失（且需要将新数据读入该组）时，如果该组内已经没有空闲行（有效位均为 1），就必须腾出空间。
- 策略机制：硬件依据替换策略（如LRU 最久未使用算法、LFU 最少使用算法）在当前组内选择一个“牺牲行”将其驱逐。若该牺牲行是脏数据（被修改过），需写回主存；随后将新读入的内存块写入该行，并更新标记位和有效位。
- 注：对于直接映射高速缓存（
），由于每组只有一行，无需策略，直接覆盖即可。
- 冲突不命中
- 核心操作：这是一种特殊的缓存缺失现象（又称碰撞缺失）。
- 发生原理：当程序的访问模式导致多个不同的主存块被频繁映射到同一个高速缓存组时，即便高速缓存的总空间还非常充裕，这些块也会在这个特定的组里交替发生行替换，互相将对方驱逐（俗称“缓存抖动”抖动，Cache Thrashing），导致连续访问时持续不命中。
高速缓存之所以选择中间的位（组索引 $ s $ 位）而不是高位来做索引，是为了最大化利用局部性原理，减少冲突不命中。
:::
如果使用“高位”做索引
:::danger
- 映射规律：高位相同的连续内存块会被映射到同一个缓存组中。
- 致命缺陷：程序在运行时通常具有空间局部性（即倾向于顺序访问连续的内存块，如数组、连续的代码指令）。
- 结果：如果用高位索引，当程序顺序读取
0000,0001,0010,0011这四个相邻的块时，它们全都会争夺同一个组（组 00）。这会导致该组发生严重的频繁替换（缓存抖动），而剩下的组 01、10、11 却完全闲置。
:::
使用“中间位”做索引
:::color1
- 映射规律：中间位做索引时，相邻的内存块会被均匀、交错地散列到不同的缓存组中（如
0000到组00，0001到组01，0010到组10…）。 - 巨大优势：当程序具有空间局部性、顺序访问一整块连续内存时，这些块会依次存入不同的缓存组。
- 结果：4个组都能被同时、均衡地利用起来，连续的内存访问绝不会在同一个组内“打架”，从而大幅降低了冲突不命中率。
:::
组相联高速缓存
一个$ 1<E<C/B $的高速缓存通常称为 E 路组相联高速缓存。
比如 2 路组相联高速缓存：
1. 组选择
- 机制：CPU 抽取主存地址中的
位组索引。
- 过程：将这
位无符号数作为组数组的下标，定位到对应的一个高速缓存组。由于它是组相联的，这一步在纵向上筛选出包含了
个可选行的“目标组”。
2. 行匹配和字选择
- 行匹配（并行检索）：
- 过程：硬件会同时（并行地）检查该选定组中的所有
个行。
- 命中判定：对于任意一行，必须同时满足“该行的有效位为 1”且“该行的标记位（Tag）与地址中的
位标记完全一致”。如果找到这样的一行，即为缓存命中（Cache Hit）。
- 字选择（数据抽取）：
- 过程：一旦行匹配成功，硬件利用地址中的低
位块偏移作为字节数组的下标，从该行的数据块（包含
字节）中精确抽取出 CPU 请求的字节或字，并将其返回。
- 注：如果组内没有任何一行的标记能匹配成功，或者匹配成功的行有效位为 0，则为缓存缺失（Cache Miss），进入第三阶段。
3. 行替换
- 触发条件：当发生缓存缺失，需要从主存中将包含目标字的数据块加载到当前组时触发。
- 替换逻辑：
- 有空闲行：如果该组内存在有效位为 0 的空闲行，则直接将新块写入该空闲行，设置有效位为 1，并填入相应的标记。
- 无空闲行（需要驱逐）：如果整个组的
个行都满了（有效位全为 1），硬件必须根据既定的替换策略（如LRU 最久未使用算法、LFU 最少使用算法）挑选出一个“牺牲行”。
- 写入与更新：将牺牲行的数据腾空（若该行为脏数据，需先写回主存），随后把从主存读入的新数据块写入该行，并更新其标记位。
1. 组选择
- 机制：由于整个高速缓存结构中只有一个组（组 0），因此主存地址中不需要专门的组索引位（
）。
- 过程：CPU 根本不需要进行任何计算或检索，硬件默认且必须总是直接选择组 0。
2. 行匹配和字选择
- 行匹配（全并行检索）：
- 过程：因为所有的数据块都挤在同一个组里，硬件必须同时（并行地）对组 0 内的所有高速缓存行进行检索。
- 命中条件：硬件会逐一比对。必须有一行同时满足：
- 有效位必须被设置（即有效位 = 1）。
- 高速缓存行中某一行的标记位必须与地址中的
位标记位相匹配。
- 字选择（数据抽取）：
- 过程：如果上述 1 和 2 的条件同时满足，即为缓存命中（Cache Hit）。
- 抽取：硬件接着利用地址底部的
位块偏移作为该行数据块（
）的起始字节下标，精准地抽取出 CPU 请求的字或字节。
- 注：如果遍历完组内所有的行，都没有找到“有效”且“标记匹配”的行，则判定为缓存缺失（Cache Miss），随后会触发第三阶段的行替换。
:::danger
一些衡量高速缓存性能的指标
- 不命中率：在一个程序执行或程序的一部分执行期间，内存引用不命中的比率。$ 不命中数量/引用数量 $。
- 命中率：命中的内存引用比率。$ 1-不命中率 $
- 命中时间：从高速缓存传送一个字到 CPU 所需的时间，包括组选择、行确认和字选择的时间。
- 不命中处罚：由于不命中所需要的额外的时间。
:::
有关写的问题当 CPU 执行写操作（修改数据）时，如何保持高速缓存（Cache）与低一层存储（如主存）之间的数据一致性。
这个问题需要分写命中和写不命中两种情况来讨论，并结合产业界的最优解进行总结：
1. 写命中（Write Hit）
当 CPU 准备写入一个字，且该字所在的块已经缓存在 Cache 中时，有两种更新策略：
- 直写（Write-through）
- 机制：立即将
的副本写回到低一层（如主存）中。
- 优缺点：最简单，但缺点极其明显。每次写操作都会引发一次总线事务，产生巨大的总线流量，拖慢系统速度。
- 机制：立即将
- 写回（Write-back）
- 机制：尽可能地推迟更新。只更新当前 Cache 行中的副本，而不立即写回低一层。只有当替换算法判定这一行需要被驱逐（替换）时，才把它写回低一层。
- 硬件开销：每一行必须额外维护一个修改位/脏位（Dirty bit），用来表明这个缓存块是否被修改过。
- 优缺点：显著减少了总线流量，但增加了硬件实现的复杂性。
2. 写不命中（Write Miss）
当 CPU 准备写入一个字，但该字所在的块不在 Cache 中时，同样有两种处理方式：
- 写分配（Write-allocate）
- 机制：先从低一层加载包含
的块到 Cache 中，然后更新这个缓存块。
- 设计意图：试图利用接下来的空间局部性（之后可能还会读写这个块内的其他数据）。
- 机制：先从低一层加载包含
- 非写分配（Not-write-allocate）
- 机制：避开 Cache，直接把这个字
写到低一层存储中，不把数据块加载到 Cache 里。
- 机制：避开 Cache，直接把这个字