# 思维导图

Cache

# Cache 的结构

# Cache 是小容量、高速缓冲存储器，由 SRAM 组成

# 一般将 Cache 和主存的存储空间都划分为若干大小相同的块并映射

把主存划分成大小相等的主存块 (Block)
Cache 中存放一个主存块的对应单位称为行 (line) 或槽 (Slot) 或项 (Entry) 或块 (Block)，一段 Cache 行包括：
- Valid 位，1 位
- LRU 位
- Dirty 位，1 位，采用 Write Back (写回、一次性写、回写) 时需要
- Tag 位
- Data 数据
主存块 (Block) 与 Cache 中的行 / 槽 / 项 / 块映射

# Cache 中存放最近访问的数据

# Cache 工作原理

# 程序运行时，CPU 使用的一部分数据 / 指令会预先成批拷贝到 Cache 中，Cache 的内容是主存储器中部分内容的映象 (副本)

# 当 CPU 需从主存读 (写) 数据或指令时，先查看 Cache

失效或缺失 (miss)
若被访问信息不在 cache 中，则直接从 Cache 中取，不用访问主存
命中 (hit)
若被访问信息在 cache 中，则直接访问主存

# Cache 对程序员 (编译器) 是透明的

# 对操作系统程序员也是基本透明的

# 对一些内核高级程序员不是透明的

# 程序访问局部性

# 时间局部性 (Temporal Locality) ：

刚被访问过的存储单元很可能不久又被访问
所以让最近被访问过的信息保留在靠近 CPU 的存储器中

# 空间局部性 (Spatial Locality) ：

刚被访问过的存储单元的邻近单元很可能不久被访问，单个数据不考虑空间局部性
所以将刚被访问过的存储单元的邻近单元调到靠近 CPU 的存储器中

# 块大小的设置需利用空间局部性

块太小，无法利用空间局部性，发生缺失的概率增大

# Cache 在计算机存储层次结构中的位置

#

# Cache 位于 CPU 内，速度几乎与 CPU 一样快

# 块 (Block) 是一个定长块，是两层存储器之间存储信息的最小单元。Cache 是主存一部分的副本

# Cache 替换算法 / 淘汰策略问题

# 当一个新的主存块需要复制到 Cache 中时，如果 Cache 中的对应行已经全部被占满，如何选择被替换掉的 Cache 行？

直接映射（Direct Mapped）Cache
映射唯一，无条件用新信息替换老信息
N 路组相联（N-way Set Associative）Cache
每个主存数据有 N 个 Cache 行可选择，需考虑替换哪一行
全相联（Fully Associative）Cache
每个主存数据可存放到 Cache 任意行中，需考虑替换哪一行

# 先进先出（First In First Out，FIFO）

总是把最近最少用的那一块淘汰掉，利用时间局部性

加一位标记位标记当前哪一行是最先进入的
替换掉之后按顺序将下一行标记为最先进入的，最后一行被替换掉则标记第一行

# 最近最少用（Least Recently Used，LRU）

总是把最近最少用的那一块淘汰掉，利用时间局部性

具体实现：通过给每个 Cache 行设定一个计数器，根据计数值来记录这些主存块的使用情况。这个计数值称为 LRU 位。
- 组相联每组 n 行时，LRU 位长度 = log_2 (n)
- 全相联相当于组相联只有一组，LRU 位长度 = log_2 (Cache 的行数)
- 命中时，被访问行的 LRU 位置 0，其他行 LRU 位加 1，其余不变
- 未命中且该组未满时，新行 LRU 位置为 0，其余全加 1
- 未命中且该组已满时，LRU 位最大的那一行中的主存块被淘汰，新行 LRU 位置为 0，其余加 1
- LRU 位的最大值 = n-1 (从 0 开始计数)
LRU 算法的命中率随组中行数的增大而提高

# 随机替换（Random）

随机地从候选的槽中选取一个淘汰，与使用情况无关
模拟试验表明，随机替换算法在性能上只稍逊于 LRU 算法，而且代价低！

# 最不经常使用 LFU

# 相关指标与术语

# 命中（Hit）：要访问的信息在 Cache 中

Hit Rate (命中率 p)：在 Cache 中的概率
Hit Time (命中时间 Tc) ：访问 Cache 所需时间，包括：判断时间 + Cache 访问

# 失效（Miss）：要访问的信息不在 Cache 中

Miss Rate (缺失率 / 失效率) = 1 - (Hit Rate) = 1-p
Miss Penalty (失效损失 Tm)：从主存将一块数据读取到 Cache 所需时间，包括访问主存块，向上逐层传输块直至将数据块放入发生缺失的那一层所需时间。

# 平均访问时间 = p × Tc + (1-p) × (Tm + Tc) = Tc + (1-p) × Tm

【失效损失 Tm】不包括【命中时间 Tc】！考点

# Cache 抖动

由于内存中不同主存块都映射到 Cache 同一行，某些块在主存和 Cache 之间频繁传送，产生了频繁的 Cache 替换，称之为 Cache 抖动

可能引起 Cache 抖动的 Cache 失效类型
- 容量失效
- 冲突失效
增加容量和相联性，有助于缓解这种现象

# 逻辑地址

CPU 给出的虚拟地址

# 物理地址 / 主存地址

在 Cache 和主存中查询所用的地址

Tag 位，与 Cache 中的 Tag 位比较，相等则命中
Index 位，组号位，只有组相联才有
Offset 位，在 Cache 行或主存块中的偏移量，即最低位块内地址

# 关联度

主存块映射到 Cache 时，可能存放的位置个数

关联度最低？直接映射（关联度为 1）
关联度居中？N - 路组相联映射（关联度为 N）
关联度最高？全相联映射（为 Cache 行数）
Cache 大小和块大小一定的情况下直观结论
- 提高关联度通常能够降低缺失率 (miss rate)
- 提高关联度通常会增加命中时间

# Cache 的失效率（Miss Rate）

# Miss Rate 与 Cache 大小、Block 大小、映射方式、Cache 级数等有关

Cache 大小：
- Cache 越大，Miss Rate 越低
- 但成本越高！
Block 大小：
- Block 越大，Miss Rate 越低，因为空间局部性充分发掘
- Block 大小在 Cache 大小中所占的比例增加到一定程度时， Miss Rate 也会随之增加
- Cache 不扩大时 Cache Block 的总数变少了，冲突变大
Cache 映射方式
- Cache 容量小时， Cache 映射方式对 Miss Rate 有影响
- Cache 容量大时，Cache 映射方式对 Miss Rate 影响不大
  - 映射到同一组的概率降低

# Cache 失效类型

强制失效 (Compulsory misses)
- 首次访问某数据块时，必然引起的 Cache 失效
- 增加 Block 大小，有利于减少此类不命中
容量失效 (Capacity misses)
- Cache 不能存放程序运行所需的所有块，替换后再次被使用所引起的 Cache 失效
- 增加 Cache 大小，有利于减少此类不命中
冲突失效 (Conflict misses)
- 映射到同一组的数据块个数超过组内可容纳的块时，竞争所引起的 Cache 失效
- 全相联没有此类失效，但价格贵且访问速度慢

# Cache 的一致性问题

# 导致 Cache 和主存数据不一致的情况

情况 1：当 Cache 中的内容进行更新时，而没有改变主存中的相应内容时，Cache 和主存之间产生了不一致 (inconsistent)
情况 2：当多个设备都允许访问主存时
- 例：I/O 设备可通过 DMA 方式直接读写内存时，如果 Cache 中的内容被修改，则 I/O 设备读出的对应主存单元的内容无效；若 I/O 设备修改了主存单元的内容，则对应 Cache 行中的内容无效。
情况 3：当多个 CPU 都有各自私有的 Cache 并且共享主存时
- 例：某个 CPU 修改了自身 Cache 中的内容，则对应的主存单元和其他 CPU 中对应的 Cache 行的内容都要变为无效。

# Cache 写机制

写命中 (Write Hit)
要写的单元已经在 Cache 中时
- Write Through (写直达、写通过、直写、写穿透)
  当一个写操作产生时，无论写的是 Cache 还是主存，新值同时写到 Cache 和主存的块中
  - 问题：内存速度太慢，所以会导致 CPU “被拖累”，CPU 性能降低
  - 一种改进措施：在 Cache 和主存之间使用写缓冲 (Write Buffer)
    - 当一个数据等待被写入主存时，先将其存入写缓冲；
    - 在把数据写入 Cache 和写缓冲后，处理器继续执行命令；
    - 当写主存操作结束后，写缓冲里的数据释放
  - 写穿透 / 直达 Cache 可用写分配或写不分配
- Write Back (写回、一次性写、回写)
  当一个写操作产生时，新值仅被写到 Cache 中，而不被写入主存
  - 特点
    - 大大降低主存带宽需求
    - 提高系统性能
    - 控制可能很复杂
  - 每个 Cache 行都设置一个修改位 (“dirty bit - 脏位”)
    - 如果修改位为 “0”，则说明对应主存块没有被修改过
    - 如果对应 Cache 行中的主存块被修改，就同时置修改位为 “1”
    - 只有当修改位为 “1” 的块从 cache 中替换出去时，才把它写回主存
      （写不命中时 Cache 里没有有效的对应块，即使写分配也不需要考虑 Cache 中的数据。但是写分配写入 Cache 新的行时，被替换掉的行不能忘了考虑写回）
    - 修改位为 “0” 的块从 cache 中替换出去时，不写回主存
  - 写回 Cache 通常用写分配
写不命中 (Write Miss)
要写的单元不在 Cache 中时
- Allocate-on-miss (写分配)
  - 更新主存块中相应单元，再将该主存块装入 Cache；
  - 试图利用空间局部性，但增加了从主存读入一个块的开销
- No-allocate-on-write (写不分配)
  - 直接写主存，不把被写数据放入 Cache，同时将 Cache 中该行 Valid 位置 0；
  - 减少了从主存读一个块的开销，但没有利用空间局部性

# Cache 和主存之间的映射

# 直接映射 / 模映射（Direct Mapped）

原理：
- 把主存的每一块映射到一个固定的 Cache 行中。
  Cache 总行数为 N，将存储空间总块数为 M 的主存分成 K = M/N 个组群，每个组群有 N 个块；
  即每个主存地址对应于高速缓存中唯一的地址，也称模映射（本质是哈希）
映射关系为：Cache 行号 = 主存块号 mod Cache 行数
物理地址
- Tag 位，标记位
  长度 = log _2 (主存中块的数量 / Cache 中块的数量) =log_2 (K)
- Index 位，Cache 槽号
  长度 = log _2 (Cache 中块的数量) = Log_2 (N)
- Offset 位，块内地址
  长度 = log _2 (块的大小) (按编址单位算)
特点
- 关联度 = 1
- 易实现 (求低地址就行了) 电路简单，命中时间短
- 淘汰 / 替换策略简单
- 不灵活，Cache 存储空间得不到充分利用，命中率低，抖动多

# 全相联映射（Fully Associative）

原理：
主存块可装到 Cache 任一行 / 槽中，称为全相联映射
Cache 有几个 slot 就最多需要查找多少次 slot，查找时需要一个 slot 一个 slot 比较 Tag 位查找（除非并行同时比较所有 Cache 行的 Tag，硬件实现更复杂）
物理地址
- Tag 位，标记位
  长度 = log _2 (主存中块的数量)
- Offset 位，块内地址
  长度 = log _2 (块的大小) (按编址单位算)
特点：
- 关联度 = Cache 的行的数量
- 块冲突概率低：只要有空闲 Cache 块，都不会发生冲突
- 实现复杂 (比较逻辑的硬件代价大)、速度慢

# 组相联映射（N-way Set Associative）

n - 路组相联将总行数为 N 的 Cache 分成 S = N/n 组，每一组有 n 行；
将存储空间总块数为 M 的主存分成 K = M/S = M*n/N 个组群，每个组群有 S 个块；
把主存块映射到 Cache 固定组的任一行中。即：组间模映射、组内全映射
物理地址
- Tag 位，标记位
  长度 = log _2 (主存中块的数量 / 组的数量) = log _2 (K)
- 组号位
  长度 = log _2 (组的数量) = log _2 (S)
- Offset 位，块内地址
  长度 = log _2 (块的大小) (按编址单位算)
特点
- 关联度 = n
- 结合直接映射和全相联映射的优点。当 Cache 的组数为 1 时，则为全相联映射；
- 每组两个行（2 路组相联）较常用。在较大容量的 L2 Cahce 和 L3 Cahce 中使用 4 路以上
- 当每组只有一行时，则为直接映射
- 当只有一组时，则为全相联映射

计组