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 路以上

• 当每组只有一行时，则为直接映射

• 当只有一组时，则为全相联映射