04.系统CPU缓存设计思想

目录介绍

01.理解CPU高速缓存
- 1.1 理解存储器结构
- 1.2 为何要CPU高速缓存
- 1.3 CPU三级缓存结构
02.CPU缓存设计思想
- 2.1 CPU三级缓存
- 2.2 数据加载的流程
- 2.3 L1缓存设计思想
- 2.4 L2缓存设计思想
- 2.5 L3缓存设计思想
03.CPU中Cache单位
- 3.1 CPU如何读数据
- 3.2 通过案例理解读写数据
- 3.3 CPU缓存行设计
- 3.4 CPU容量单位
- 3.5 通用缓存设计思路
04.内存&Cache地址映射
- 4.1 如何查找缓存位置
- 4.2 CPU映射方案
- 4.3 直接映射
- 4.4 全相联映射
- 4.5 组相联映射
05.理解Cache块替换策略
- 5.1 缓存替换策略背景
- 5.2 常见替换策略
- 5.3 随机法
- 5.4 FIFO法
- 5.5 LRU最近最少法

01.理解CPU高速缓存

1.1 理解存储器结构

现代计算机系统为了寻求容量、速度和价格最大的性价比会采用分层架构，从 “CPU 寄存器 - CPU 高速缓存 - 内存 - 硬盘”自上而下容量逐渐增大，速度逐渐减慢，单位价格也逐渐降低。
- 1、CPU 寄存器：存储 CPU 正在使用的数据或指令；
- 2、CPU 高速缓存：存储 CPU 近期要用到的数据和指令；
- 3、内存：存储正在运行或者将要运行的程序和数据；
- 4、硬盘：存储暂时不使用或者不能直接使用的程序和数据。

1.2 为何要CPU高速缓存

弥补 CPU 和内存的速度差（主要）：
- 由于 CPU 和内存的速度差距太大，为了拉平两者的速度差，现代计算机会在两者之间插入一块速度比内存更快的高速缓存。
- 只要将近期 CPU 要用的信息调入缓存，CPU 便可以直接从缓存中获取信息，从而提高访问速度；
减少 CPU 与 I/O 设备争抢访存：
- 由于 CPU 和 I/O 设备会竞争同一条内存总线，有可能出现 CPU 等待 I/O 设备访存的情况。而如果 CPU 能直接从缓存中获取数据，就可以减少竞争，提高 CPU 的效率。

1.3 CPU三级缓存结构

CPU缓存结构演变的过程
- 在 CPU Cache 的概念刚出现时，CPU 和内存之间只有一个缓存，随着芯片集成密度的提高，现代的 CPU Cache 已经普遍采用 L1/L2/L3 多级缓存的结构来改善性能。
- 自顶向下容量逐渐增大，访问速度也逐渐降低。当缓存未命中时，缓存系统会向更底层的层次搜索。
CPU三级缓存结构
- L1 Cache：在 CPU 核心内部，分为指令缓存和数据缓存，分开存放 CPU 使用的指令和数据；
- L2 Cache：在 CPU 核心内部，尺寸比 L1 更大；
- L3 Cache：在 CPU 核心外部，所有 CPU 核心共享同一个 L3 缓存。

02.CPU缓存设计思想

2.1 CPU三级缓存

CPU三级缓存
- 三级缓存：CPU 缓存是一个三级结构，其中 L0、L1、L2 是每个处理核心独立的，而 L3 是一颗 CPU 的多个处理器共用的；
- 背景：CPU 处理器的运算速度与内存存取速度、磁盘 I/O 速度不匹配（相差了几个数量级）;
- 目的：提高 CPU 吞吐量；
- 方案：增加一个缓存层来协调两者的速度差，即：在 CPU 和内存中间增加一层「高速缓存」，缓存的存取速度尽可能接近。
为何要设计CPU三级缓存
- 由于 CPU 和内存的速度差距太大，为了拉平两者的速度差，现代计算机会在两者之间插入一块速度比内存更快的高速缓存，CPU 缓存是分级的，有 L1 / L2 / L3 三级缓存。
- 由于单核 CPU 的性能遇到瓶颈（主频与功耗的矛盾），芯片厂商开始在 CPU 芯片里集成多个 CPU 核心，每个核心有各自的 L1 / L2 缓存。其中 L1 / L2 缓存是核心独占的，而 L3 缓存是多核心共享的。

2.2 数据加载的流程

数据加载的流程如下：
- 1、将程序和数据从磁盘加载到内存中；
- 2、将程序和数据从内存加载到缓存中（三级缓存，数据加载顺序：L3->L2->L1）；
- 3、CPU将缓存中的数据加载到寄存器中（L0），并进行运算；
- 4、CPU将数据同步回缓存，并在一定的时间周期之后同步回内存。
CPU 往往需要重复读取同一个数据块，而缓存容量的增大，可以大幅度提升 CPU 内部读取数据的命中率，以此提升 CPU 吞吐量。

2.3 L1缓存设计思想

为什么 L1 要将指令缓存和数据缓存分开？这个策略叫分离缓存，与之相对应的叫统一缓存：
- 分离缓存：指令和数据分别存放在不同缓存中。指令缓存（Instruction Cache，I-Cache），数据缓存（Data Cache，D-Cache）
- 统一缓存：指令和数据统一存放在一个缓存中。
那么，为什么 L1 缓存要把指令和数据分开呢？我认为有 2 个原因：
原因 1 - 避免取指令单元和取数据单元争夺访缓存（主要）：
- 在 CPU 内核中，取指令和取数据指令是由两个不同的单元完成的。
- 如果使用统一缓存，当 CPU 使用超前控制或流水线控制（并行执行）的控制方式时，会存在取指令操作和取数据操作同时争用同一个缓存的情况，降低 CPU 运行效率；
原因 2 - 内存中数据和指令是相对聚簇的，分离缓存能提高命中率：
- 在现代计算机系统中，内存中的指令和数据并不是随机分布的，而是相对聚集地分开存储的。因此，CPU Cache 中也采用分离缓存的策略更符合内存数据的现状；

2.4 L2缓存设计思想

为什么 L1 采用分离缓存而 L2 采用统一缓存？
- 原因 1： L1 采用分离缓存后已经解决了取指令单元和取数据单元的争夺访缓存问题，所以 L2 是否使用分离缓存没有影响；
- 原因 2：当缓存容量较大时，分离缓存无法动态调节分离比例，不能最大化发挥缓存容量的利用率。例如数据缓存满了，但是指令缓存还有空闲，而 L2 使用统一缓存则能够保证最大化利用缓存空间。

2.5 L3缓存设计思想

L3 缓存是多核心共享的，放在芯片外有区别吗？
- 集成在芯片内部的缓存称为片内缓存，集成在芯片外部（主板）的缓存称为片外缓存。
- 最初，由于受到芯片集成工艺的限制，片内缓存不可能很大，因此 L2 / L3 缓存都是设计在主板上，而不是在芯片内的。
后来，L2 / L3 才逐渐集成到 CPU 芯片内部后的。片内缓冲和片外缓存是有区别的，主要体现在 2 个方面：
- 区别 1 - 片内缓存物理距离更短：片内缓存与取指令单元和取数据单元的物理距离更短，速度更快；
- 区别 2 - 片内缓存不占用系统总线：片内缓存使用独立的 CPU 片内总线，可以减轻系统总线的负担。

03.CPU中Cache单位

3.3 CPU缓存行设计

CPU Cache 在读取内存数据时，每次不会只读一个字或一个字节，而是一块块地读取，这每一小块数据也叫 CPU 缓存行（CPU Cache Line）。
- 这也是对局部性原理的应用，当一个指令或数据被访问过之后，与它相邻地址的数据有很大概率也会被访问，将更多可能被访问的数据存入缓存，可以提高缓存命中率。
当然，块长也不是越大越好（一般是取 4 到 8 个字长，如 64 字节）：
- 前期：当块长由小到大增长时，随着局部性原理的影响使得命中率逐渐提高；
- 后期：但随着块长继续增大，导致缓存中承载的块个数减少，很可能内存块刚刚装入缓存就被新的内存块覆盖，命中率反而下降。而且，块长越长，追加的部分距离被访问的字越远，近期被访问的可能性也更低，无济于事。

3.4 CPU容量单位

几种容量单位：
- 字节（Byte）：字节是计算机数据存储的基本单位，即使存储 1 个位也需要按 1 个字节存储；
- 字（Word）：字长是 CPU 在单位时间内能够同时处理的二进制数据位数。多少位 CPU 就是指 CPU 的字长是多少位（比如 64 位 CPU 的字长就是 64 位）；
- 块（Block）：块是 CPU Cache 管理数据的基本单位，也叫 CPU 缓存行；
- 段（Segmentation）/ 页（Page）：段 / 页是操作系统管理虚拟内存的基本单位。

3.5 通用缓存设计思路

事实上，CPU 在访问内存数据的时候，与计算机中对于 “缓存设计” 的一般性规律是相同的：
- 对于基于 Cache 的系统，对数据的读取和写入总会先访问 Cache，检查要访问的数据是否在 Cache 中。
- 如果命中则直接使用 Cache 上的数据，否则先将底层的数据源加载到 Cache 中，再从 Cache 读取数据。
通用缓存设计思路是什么
- image

04.内存&Cache地址映射

4.1 如何查找缓存位置

CPU 怎么知道要访问的内存数据是否在 CPU Cache 中，在 CPU 中的哪个位置，以及是不是有效的呢？
- 这就是下面要讲的内存地址与 Cache 地址的映射问题。
无论对 Cache 数据检查、读取还是写入，CPU 都需要知道访问的内存数据对应于 Cache 上的哪个位置，这就是内存地址与 Cache 地址的映射问题。
- 事实上，因为内存块和缓存块的大小是相同的，所以在映射的过程中，我们只需要考虑 “内存块索引 - 缓存块索引” 之间的映射关系，而具体访问的是块内的哪一个字，则使用相同的偏移在块中寻找。

4.2 CPU映射方案

目前，主要有 3 种映射方案：
- 1、直接映射（Direct Mapped Cache）：固定的映射关系；
- 2、全相联映射（Fully Associative Cache）：灵活的映射关系；
- 3、组相联映射（N-way Set Associative Cache）：前两种方案的折中方法。
CPU映射方案如下所示
- image

4.3 直接映射

直接映射是三种方式中最简单的映射方式，直接映射的策略是：在内存块和缓存块之间建立起固定的映射关系，一个内存块总是映射到同一个缓存块上。
- 1、将内存块索引对 Cache 块个数取模，得到固定的映射位置。例如 13 号内存块映射的位置就是 13 % 8 = 5，对应 5 号 Cache 块；
- 2、由于取模后多个内存块会映射到同一个缓存块上，产生块冲突，所以需要在 Cache 块上增加一个组标记（TAG），标记当前缓存块存储的是哪一个内存块的数据。其实，组标记就是内存块索引的高位，而 Cache 块索引就是内存块索引的低 4 位（8 个字块需要 4 位）；
- 3、由于初始状态 Cache 块中的数据是空的，也是无效的。为了标识 Cache 块中的数据是否已经从内存中读取，需要在 Cache 块上增加一个有效位（Valid bit）。如果有效位为 0，则 CPU 可以直接读取 Cache 块上的内容，否则需要先从内存读取内存块填入 Cache 块，再将有效位改为 1。
直接映射
- image

4.4 全相联映射

理解了直接映射的方式后，我们发现直接映射存在 2 个问题：
- 问题 1 - 缓存利用不充分：每个内存块只能映射到固定的位置上，即使 Cache 上有空闲位置也不会使用；
- 问题 2 - 块冲突率高：直接映射会频繁出现块冲突，影响缓存命中率。
基于直接映射的缺点，全相联映射的策略是：
- 允许内存块映射到任何一个 Cache 块上。这种方式能够充分利用 Cache 的空间，块冲突率也更低，但是所需要的电路结构物更复杂，成本更高。
具体方式：
- 1、当 Cache 块上有空闲位置时，使用空闲位置；
- 2、当 Cache 被占满时则替换出一个旧的块腾出空闲位置；
- 3、由于一个 Cache 块会映射所有内存块，因此组标记 TAG 需要扩大到与主内存块索引相同的位数，而且映射的过程需要沿着 Cache 从头到尾匹配 Cache 块的 TAG 标记。

4.5 组相联映射

组相联映射是直接映射和全相联映射的折中方案，组相联映射的策略是：
- 将 Cache 分为多组，每个内存块固定映射到一个分组中，又允许映射到组内的任意 Cache 块。显然，组相联的分组为 1 时就等于全相联映射，而分组等于 Cache 块个数时就等于直接映射。

05.理解Cache块替换策略

5.1 缓存替换策略背景

缓存替换策略是在计算机系统中用于管理缓存的一种策略。
- 缓存是一种用于存储临时数据的高速存储器，其目的是提高数据访问速度和系统性能。当缓存已满并且需要为新数据腾出空间时，缓存替换策略决定哪些数据应该被替换掉。缓存替换策略的选择是为了优化缓存的性能和效率。

5.2 常见替换策略

常见的缓存替换策略包括最近最少使用（LRU）、最不经常使用（LFU）、先进先出（FIFO）等。每种策略都有其优点和局限性，适用于不同的应用场景和需求。

5.3 随机法

随机法：使用一个随机数生成器随机地选择要被替换的 Cache 块，实现简单，缺点是没有利用 “局部性原理”，无法提高缓存命中率；

5.4 FIFO法

FIFO 先进先出法：记录各个 Cache 块的加载事件，最早调入的块最先被替换，缺点同样是没有利用 “局部性原理”，无法提高缓存命中率；

5.5 LRU最近最少法

LRU 最近最少使用法：记录各个 Cache 块的使用情况，最近最少使用的块最先被替换。这种方法相对比较复杂，也有类似的简化方法，即记录各个块最近一次使用时间，最久未访问的最先被替换。与前 2 种策略相比，LRU 策略利用了 “局部性原理”，平均缓存命中率更高。