这一部分对应的是lec 24- 27 (b 大上的参考课程为[Summer 20])，主要涉及的是缓存(Cache)的相关原理，包括层次结构、局部性原理、基本设计以及组织方式等。
缓存的存在是为了解决(现在是缓解)Mem 和 CPU 的性能鸿沟，处理器的速度远大于内存读取的速度，导致处理器大部分时间空闲以等待数据抵达，也就是所谓的“内存墙”(Memory Wall)问题
IEC – SI Prefix
在讲座开始，Prof . Dan 澄清了一个区别：
- SI 前缀是基于 10 的幂次，跨阶为 $10^3$，常见于硬盘和网络的资源概念
- IEC 前缀是基于 2 的幂次， 跨界为$2^{10}$，计科中的标准内存描述概念
内存层次结构
关于 MEM – CPU，有一个常见的结构来描述其层次：金字塔型
其表示性能随占位升高而增强，容量随占位提高而降低，即
$$\text{Performece} : Mem(SSD,HDD)\lt DRAM\lt Cache\lt CPU\\ \text{Store Size} : CPU \lt Cache \lt DRAM \lt Memory(SSD,HDD)$$
该架构的核心主要涉及两方面：
- 上一层储存值只会是下一层的子集，即包含性(Inclusive)
- 在宏观上表现为扩展的快速内存空间，是为 幻觉(illusion)
局部性原理
我们前面提及程序可被视为一个 FSM ，那么程序行为在时间和空间上的的高度规律性便是缓存能够工作的理论基础。具体而言，局部性体现在：
- 空间局部性(Spatial Locality)：如果一个内存位置被访问，那么其附近的内存位置被访问的几率会大大上升(连续储存、联合共用)
- 时间局部性(Temporal Locality): 如果一个内存位置被访问，那么在接下来的一段时间可能会被频繁访问(寄存器)
设计思路
了解了内存实现的基本原理，我们便可以着手开始设计，但在实现上，我们首先需要解决四个基本问题：
- 放置(Placement):对于给定的内存地址，其数据应当被放在缓存的那个位置？
- 标识(Identification):如何辨别当前数据是否已经位于缓存中？如何在的话如何快速寻找？
- 替换(Replacement):当缓存已满需要进行替换时，我们的替换策略应当是什么？
- 写入(Write Policy):CPU写入数据时当前数据是否需要写入缓存？这关系到数据的一致性，是“写回”和“写直达”的策略抉择
讲座的剩余部分主要是对前三个基本问题的解析，而设计上的权衡为我们展现了一条清晰的演进路径
直接映射缓存(Direct-Mapped Cache)
直接映射缓存的思想其实相当简单：只考虑为每个主地址设计一个对应的缓存位置，该位置有且只有一个
我猜你肯定想到什么了 ( • ̀ω•́ )？对，就是 Hash，只不过 Hash 函数在这变成了 Address %(Number(Cache))
为了快速定位所索引，我们将内存地址划分为三个字段，也就是所谓的 T-I-O：
- Offset (偏移)：偏移量用于定位块内的具体字节。它的长度由块大小（Block Size） 决定。例如，16字节的块需要4位偏移（$\log_2(16)=4$）。
- Index (索引)：索引用于选择缓存中的哪一个“行”或“槽”。它的长度由缓存容量和块大小共同决定。索引数量 = 缓存容量 / 块大小。
- Tag (标签)：标签是地址中剩下的最高位，它用于检查缓存行中的数据是否确实是CPU当前想要访问的地址的数据，相当于对数据做合法性校验
那么具体的工作流程是——
- CPU给出地址，硬件自动解析出 index, tag 以及 offset。
- 根据
index找到缓存中唯一对应的那个槽。 - 检查该槽的有效位（Valid Bit）。如果为0，则必定是缺失（Miss）。
- 如果有效位是 1 ，那么进行 tag 比较：
- 匹配- 命中(Hit)，取出数据返回 CPU
- 不匹配 – 冲突缺失(Conflict Miss)，从主存中提取相关数据并同步写入 CPU 和 Cache
考虑对 Cache 的性能做出评价时，有如下指标：
- 命中率（Hit Rate）：命中次数 / 总访问次数。
- 缺失率（Miss Rate）：1 – 命中率。
- 命中时间（Hit Time）：从发出地址到从缓存中取出数据的时间。通常为1 ~ ClockCycles。
- 缺失代价（Miss Penalty）：从发出地址到从主存中取出数据并加载到缓存的时间。非常昂贵。
- 平均内存访问时间（AMAT）：衡量缓存性能的黄金指标。$$\text{AMAT} = \text{Hit Times}+\text{Miss Rate}\times \text{Miss Penalty}$$
事实上，我们需要尽可能降低 AMAT，因此需要考虑为什么会出现 Miss
Miss Classification
常见的 Miss 包括：
- 冷启动缺失：系统在首次访问数据时 Cache 必然为空，这一情况无法避免，但和分支预测类似，可以考虑预取(Prefetching)
- 容量缺失：系统所需的工作集数量显著高于缓存容量，这涉及到 Cache 的 Block Size 的设计权衡
- 冲突缺失：事实上这是 DMC 中最主要的冲突，多个内存块映射到同一个内存必然导致重复写入和擦除，而 DMC 的机制决定即使当前 Cache 块还有空闲也会傻乎乎的重复写入和擦除
所以为了尽可能减少冲突缺失，现在大部分 Cache 的设计思路采用的是 组相连(Set-Associative) 机制
组相连缓存(Set-Associative Cache)
组相联缓存的设计核心其实是分组，将缓存划分若干组后，对组内包含的 N 个缓存块(也称N路组相连)。内存地址在被读入时会进行并联检索以进行配对，这类似于 N 分查找，将冲突损失降到了最低
- $N = 1$时就是直接映射缓存
- $N = Number(Block)$ 时即为全相联缓存
多级缓存(Multi-Level Cache)
打开你的设备管理器，在 CPU 的相关界面通常能看到：
图中右下角的 L1, L2, L3 三级缓存就是组相联缓存的具体实现。
多级缓存时通过在 CPU 和主存间设立多级缓存，将 AMAT 转化为层级结构，此时的 AMAT 的计算公式变为：
$$\text{AMAT} = \sum\limits_{i =1}^{n-1}L_i \text{‘s Hit Time}+\text{AMAT}(L_n)$$
写在最后
Cache 的设计本质实际上是硬件成本，访问速度和命中率的综合权衡。它同时也是“层次抽象”又双叒叕的一个体现。通过一个转换接口，上层的软件不必考虑资源调度，只需要使用 Cache 的接口便可使用内存
发表回复