Cache

前面一直没有讲述 Cache 方面的内容，最近较为深入学习了这部分内容，捋了一下写出本文。内容较多涉及较广，画了张思维导图，可以先看看好有个总体把握

首先是存储器的层次结构，大家应该都很熟悉了，就是那个金字塔图，再来看看：

关于这个图就不做解释了，大家应该很熟悉很熟悉很熟悉，放在这里只是过过眼，说明讲述的 Cache 位于哪个层次。下面直接来看 Cache 的一些问题。

基本问题

对于 cache 的设计有 4 个基本问题：块的放置，块的识别，块的写策略，块的替换，在这之前先声明一下名词的事，Cache 的行和块，基本上就一回事，不论英文里面的 Cache Line 还是 Cache block 很多地方就是混用的，不要纠结有什么不同，只不过有时会说 Cache Line 里面的数据由多个 Data blocks 组成的，主要是在知乎上看到过这个问题，有人纠结，这里给出自己的见解。另外后面会涉及到数据和指令两个名词，狭义上讲数据就是数据，指令就是指令，但有时为了说着顺口指令也是包括在数据里面的，因为数据这个词本来就包括很多意思是吧，后面遇到这也不要纠结，从上下文应该很好判断具体什么意思。再者就是 CPU 和实际的 CPU 芯片，CPU 芯片包括的东西很多，比如说 L1 L2 级缓存，但一般后文说的 CPU 单指处理核心。

块的放置

Cache 很小，主存很大，主存的块放在 Cache 哪个地方？三种策略，就是常说的 直接相联，组相联，全相联

1、直接相联

主存中的每一块只能放在 Cache 的唯一位置，映射方法：

图示如下：

优缺点：容易实现，命中时间短，结构简单但冲突率高

2、全相联

主存块能放在 Cache 的任意一行

图示如下：

优缺点：结构复杂但命中率高

3、N 路组相联

所谓组指的是若干 Cache Line 的集合，N 路指的是每个组中包含的 Cache Line 的行数，也称为相联度。一个主存块能放在一组的任意一行中。

图示如下：

优缺点：具备直接相连和全相联的特点

块的识别

CPU 根据地址直接去 Cache 中获取数据时，如何确定 Cache 中哪一行里有我(CPU) 所需要的数据呢？所以一个 Cache Line 里面除了数据还得有其他的东西来标志数据才行，一般就是有效位 V 和 标志 tag。如此便可以将 Cache Line 分为三部分：

1. V：有效位，指明该 Cache Line 是否与某主存块建立映射关系，数据是否有效
2. Tag：标记位，包含了地址信息，可以用来区分所有可能映射到该行的主存块
3. Data：存放在该行的数据

这里我们就可以对地址进行划分，划分方式如下：

如果是直接映射，可以看作一个组里面只有一行，则

如果是组相联，则

如果是全相联，则可以看作是只有一个组，一个组包含所有行，则 ，即没有 index 域

这个计算是所有 Cache 问题的基础，也是有关 Cache 的考题必考的项目，一定要弄明白，来看几个例子，假设地址都是 32 位：

若 Cache 容量为 1K，块大小为 16B，直接映射，则块内偏移有 ，索引 index 有 ，则标记有

若 Cache 容量为 1K，块大小为 16B，全相联，则块内偏移有 ，没有索引 index 域，则标记有

若 Cache 容量为 1K，块大小为 16B，4 路组相联，则块内偏移有 ，索引 index 有 ，则标记有

从这个例题也可以看出，Cache 的结构可以由三元组来表示 <容量，相联度，块大小>

块的替换

当 miss 冲突的时候，就需要决定将哪个块给替换掉，直接相联不需要替换策略，因为其本身的映射方式已经决定了一个主存块应该放进哪个 Cache Line。而组相联和全相联是需要替换策略的，常见的替换策略如下：

• 随机替换
• 先进先出
• 最近最少使用(LRU)

这些替换算法应该都很熟悉，像是页面替换算法与其也类似，但是有一点区别，在 Cache 里，所有的替换算法由硬件来实现，而页面替换算法可由软件实现。虽然硬件本身复杂，但是由硬件来实现某个算法的话，说明该算法容易实现，复杂的东西硬件是“做不了”的。

随机替换算法很容易实现，需要一个随机数产生器，我去查了查资料，这个随机数产生器在现实里面还是挺好实现的，它是把物理上不可预测的随机噪声转换为电信号，具体啥啥啥的就不说了，emmm 我也不懂，不能乱说，就点到为止。

先进先出可以在每组设计位宽为 的计数器，来指定下一个可能被替换掉的块，因为先进先出本身是有顺序的，所以只需要用计数器来指定某一特定块，当替换发生时该计数器加/减 1 就行。

最为常用的方法为 LRU，但要完全实现 LRU 代价很大，每个 Cache Line 需要配一个位宽 的计数器，代价太大不划算。

所以一般采用近似 LRU，什么叫做近似 LRU，近似 LRU 也有几种，这里用 Tree_based Pseudo LRU 来说明。举个例子，4 路组相联就可以这样设计：使用 1 位来表示一组当中哪一对 Cache 行是近期最少使用的，再使用 1 位来记录每对 Cache 中哪一行是近期最少使用的，如此每组则使用 3 位来记录访问情况。不是太清楚？来看个例子，4 路组相联，Cache 里面某组的内容初始化为 A B C D，计数器初始化指向 A。

应该还是挺清楚的吧，计数器的指向就是“近期最少使用的块”简称 LRU 块，当访问某个块后，如果父节点指向自己，则翻转父节点的指向，如果根节点指向自己这边，则翻转根节点的指向，当缺失发生时，替换计数器指向的那个块。

为什么说 LRU 算法比较好，因为这种策略利用了时间局部性，最近访问的数据可能在不久的将来会再次访问，所以需要替换时，将最近最少访问的块替换掉，保留最近常访问的数据，那么由于时间局部性原理，这些数据近期可能再次访问，那么命中率就可能提高。

块写策略

块的写策略分两部分，一是写命中时的策略，要考虑如何更新 Cache 里面的内容，二是写缺失时的策略，要考虑是否需要在 Cache 中分配新的 Line

1、写命中策略

写直达/写通(Write Through)：信息会同时写入 Cache 和下一级存储

写回(Wtrite Back)：信息仅会写入 Cache，被更新的 Cache Line 只有在被替换出去的时候才会写回下一级存储

对于写回策略，每一个 Cache Line 需要 1bit 来标志当前的数据是否 dirty，该行的数据被写时，脏位置 1，当一个 dirty line 被替换的时候，该行数据需要写回下一级存储

写回的优点：写操作速度快，对同一 Cache Line 的多次写操作才会引发对下一级存储的一次写操作

写回的缺点：实现代价高、破坏了数据的一致性

写通的优点：易于实现，保持了数据的一致性

写通的缺点：写操作速度慢

2、写缺失策略

写分配：写缺失时，将相应的主存块调入 Cache 之后再进行写操作，充分利用空间局部性

写不分配：写缺失时，不将主存块调入，直接更新主存，没有很好利用空间局部性

一般写分配与写回搭配，写不分配与写直达搭配

AMAT

AMAT(Average Memory Access Time) 平均访问时间，一般用下面的公式计算：

这个公式也很好理解，一个加权平均值，因为 Cache 的命中率通常很高，直接省去了

而对于 Cache 缺失访问内存的缺失代价一般可以这么计算：

主存访问的延迟和主存带宽是硬件特性，还有个因素块大小也会影响缺失代价，因为传输数据也需要时间，这就与数据多少，这里就是块大小有关。

对于 Cache 的设计，如何降低 AMAT 很重要，从上面公式可以看出，AMAT 由三个因素决定，那要降低 AMAT，直观得看，三个因素都降低 AMAT 不就降低了？

想法没错，但这三个因素通常会相互制约，所以设计时就要取舍平衡，英文名叫 tradeoff

降低缺失率

Mark D.Hill 曾对缺失的类型做了分类，名叫 3C 模型

强制缺失(Compulsory)：又称为冷启动缺失，对 Cache Line 的首次访问导致的缺失

容量缺失(Capacity)：顾名思义，由容量导致的缺失，即采用全相联结构也会出现的缺失类型

冲突缺失(Conflict)：由于多块竞争同一组引起的缺失，与容量缺失的差别在于如果采用全相联的结构则不会缺失。

来看个例子就明白了，Cache 容量 16B，块大小 4B，直接映射，访问顺序：A，A + 4，A + 16，A，A + 8，A + 12，A + 20，A + 4

前面说过，对于 Cache 的所有问题，首先把 容量、块大小、行数、组数、地址划分算清楚，这里也不例外，只不过没涉及到地址，就先略过。因为这是随便举的例子，计算就很简单，容量 16B、块大小 4B、直接映射说明有 4 个 Cache Line，也可以看作是有 4 组，每组里面只有 1 行

只要是第一次访问，那就是强制缺失，所以上述很多块都是强制缺失，没什么问题。

看第三次和第四次分别访问 A+16 和 A，它俩竞争同一块，对于 A+16 来说第一次访问，所以是强制缺失，对于 A 来说不是第一次访问，那到底是容量缺失还是冲突缺失？如果这个 Cache 结构是全相联的话，那么 A 是不会缺失的，因为此时的 Cache 第 2、3 行(从 0 算) 还是空的，所以这个缺失为冲突缺失

最后一次访问的是 A + 4，之前访问过，所以不是强制缺失，那是容量还是冲突？同样的转换成全相联来看，此时 Cache 里面每行都有东西，所以即使是全相联的情况下该块还是会缺失，所以此缺失为容量缺失。

说这么多似乎都不对题，如何才能降低缺失率？先来看第一种方式：

1、调整 Cache 结构

调整 Cache 结构，什么结构，Cache 的结构就是那描述 Cache 的三元组：<容量、块大小、相联度>。

(1)调整块大小

直接来看张图说明块大小对缺失率的影响：

这张图来自计算机组成与设计，是根据实际情况测试出来的，不是胡乱瞎编的。每条缺陷代表不同的 Cache 容量，这里也就可以看出，Cache 容量的提高是可以降低缺失率的，这很明显整体容量变大容纳的数据更多缺失率自然会下降。

但是相对于容量来说，块大小对缺失率的影响是先降低后趋于平缓或者是有升高的趋势的，这说明一定程度提升块大小有利于降低缺失率，而块大小大到一定程度的话，对于缺失率的降低并没有什么作用反而会使缺失率上升。

首先解决第一个问题，为什么一定程度的提高块大小会降低缺失率？试想如果我 Cache 容量为 16B，块大小为 8B，直接映射，同样访问 A，A+4 会有什么不同？当块大小为 4B 的时候，两者都会发生强制缺失，但是当我块大小为 8B 的时候，访问 A+4 就会命中，因为访问 A 时顺便把 A+4 给带进来了。

所以块大小的提升是能够改善强制缺失的，因为访问某个数据时其邻近的数据在近期也可能访问，所以我就把 Cache 的块大小设置的大点，处理前一个缺失时就会把更多的临近数据给带进 Cache，那么随后访问这所谓的 “临近数据” 时就可能不会缺失，降低了缺失率，这就是利用了空间局部性提升块大小降低缺失率。

那为什么块大小到一定程度时，缺失率不降反增了，这个问题其实很简单，当 Cache 容量一定时，块大小越大，说明块数越少，则冲突的可能性越大。有人可能就疑惑，块大小越大的话容纳的东西越多，如果 CPU 就是经常访问当前这个块里面的数据呢？这个问题都有个词“如果”在前面，那我也可假设 CPU 访问相距较远但映射到同一行的数据对吧，Cache 设计要尽量满足各种场景需求，就像一开始说的，这些降低某个指标的因素之间都是相互制约的，提高 A 就可能降低 B，这就需要平衡，tradeoff。

再来说说块太大还有什么缺点：

1. 块太大的话，里面的无用数据可能就更多
2. 缺失代价提高，还记得那个缺失代价的公式吗？块大小提高是会提高传输时间的。

(2)调整 Cache 容量

从上述那张图已经可以看出来了，容量的提升是能够改善缺失率的，这也很好理解，容量提升，容纳的数据更多，自然会在一定程度的降低缺失率。

但也不是无限制的降低，双倍的容量不一定带来双倍的性能，而且容量增加会增加命中时间，想想如果是全相联，且 Cache 的容量很大的话，查找起来那是相当费时。

另外，Cache 容量越大成本功耗等都会增加，要知道 Cache 是很贵的。大容量的 Cache 都不会放在芯片内部，芯片的空间有限，不会存放大容量的 Cache，这也是为什么 L1 L2 Cache 在 芯片内部而 L3 在 芯片外部的原因

(3)调整相联度

提高相联度是能够降低缺失率的，它会减少冲突缺失，相联度越高，缺失率越低，但有个度不会低于全相联的情况。

但相对于直接相联来说提高相联度也增加了命中时间，会出现收益递减的现象。

2、Victim Cache

在直接相联的情况下，如何才能既保证快速命中又避免较高的冲突缺失呢？Jouppi 在 1990 提出一种方案，在主 Cache 的旁边放一个小容量全相联的 Cache 来存放从主 Cache 中驱逐出来的块。有测试一个只有 4 行的 Victim Cache 就能减少容量为 4K 直接映射的 Cache 20%~95% 的冲突缺失。

举个例子，在 L1 和 L2 之间放一个 VC，图示如下：

Victim 的大致工作方式如下，当 L1 的某个块被替换时存放到 VC 中去，当 L1 缺失时先从 VC 中寻找最近被驱逐的块，如果 VC 命中则直接取过来不需要访问下一级存储 L2，反之不命中的话访问 L2

Victim Cache 使得直接相联有种组相联的“错觉”，能够极大改善直接相联的冲突问题。

3、编译器优化

前面都是硬件做的优化，后面来讲述从软件层面来优化，最主要的就是编译器，使用编译器的优化技术来降低缺失率，当然也与我们自身写程序有关，尽量写出对 Cache 友好的程序，这后面都会讲述。先来说说优化的原理是什么，主要有两个方面：

• 改善空间局部性
• 改善时间局部性

所谓改善空间局部性就是尽量将近期会接连访问的数据指令放在一起。而我们的程序是天然就存在这个性质的，比如对于指令来说大多数指令都是顺序执行，满足上述思路，少部分会分支改变顺序执行的模式，使得接连访问的指令可能不在一块儿，所以对于指令布局的改善主要就从分支下手。数据呢，基本上也天然具有这种性质，最典型的数据结构就是数组，相同类型的数据集中在一起，具有良好的空间局部性，但数组过大时也可能会出现一些问题可以进行优化，这后面详述。

所谓的改善时间局部性通常就是变换计算过程使得 Cache 块再被替换之前尽量多使用几次，比如说 A B 两块映射到同一行，原先的计算模型是 A B 交叉访问各 10 次，那么每次访问 A、B 都会缺失，如果我改变计算模型，使得先访问 A 10 次，再访问 B 10 次，那么就只会缺失 2 次，极大降低缺失率。时间局部性是说访问过的数据近期可能再次访问，而改善程序的时间局部性就是把这个 “近期” 缩小，如果能缩小到就是下一次会访问那就再好不过。

上述为总述的理论，下面来看看各种情况实际的例子

(1)指令布局

前面说过大多数指令都是顺序执行，有着良好的空间局部性，主要是分支类的指令破坏了局部性，编译器的优化技术可以改善它。解决方案如下：

1. 先简单测试每种分支跳转与不跳转的概率
2. 构建流图
3. 寻找每个指令组后续可能执行的指令组
4. 按照最大可能的执行顺序方式重排指令组

举个例子：

一图胜千言，应该很容易理解，抓住按照最大可能的执行顺序方式重排指令组。注意一点：改变指令组顺序后可能改变分支指令

(2)数据布局

举例来说明：

Cache 容量 = 80B，块大小 = 8B，直接映射，则此 Cache 有 10 行，现有以下代码：

int a[10];
int b[10];
/***初始化获取数据 略***/
for(int i = 0; i < 10; i++)
    a[i] = b[i];

这个程序很低效，为啥，还是直接来看图：

这里假设 a[0] b[0] 映射到同一行，其余的类推，这是完全有可能的。上图很好理解就不多解释，关键问题是如何才能使 a 和 b 像右侧那样布局，也很简单，来个结构体就行：

struct AB{
    int a;
    int b;
}
struct AB ab[10];
/***初始化获取数据 略***/
for(int i = 0; i < 10; i++)
    ab[i].a = ab[i].b;

如此改善了数据的空间局部性，使得每次 Cache 缺失都会顺便带进有用的数据，降低这些 “顺便带进来的数据” 的强制缺失。

可以简单计算一下两个方案的缺失率：

方案一：访问 20 次，全部缺失，缺失率 100%

方案二：访问 20 次，只有访问 ab[i].a 时会缺失，所以缺失率 50%

对比起来缺失率直接减半，性能效率极大提高

(3)循环交换

关于二维数组遍历先遍历行还是遍历列的问题，这个问题应该都很熟悉，这里再简单说说，同样以例子来说明：

Cache 结构：容量 40B，块大小 20B，全相联，则一行能放 5个 int 型数据，有 2 行。感觉这种 Cache 结构不太合理啊，主要是为了好说明，来看代码：

int x[5][5];
/***初始化获取数据 略***/
for(int j = 0; j < 5; j++)
    for(int i = 0; i < 5; i++)
        x[i][j]++;

这个程序的性能也不好，同样的直接用图说明：

c/c++ 的二维数组以行的形式存储，所以说特定的，在我们这个例子当中，每次 Cache 缺失都会直接获取一个块的数据，也就是二维数组的一行 5 个 int 型数据，但是由于这个程序是以列的形式访问，所以拿进来的 5 个数据只有 1 个有用，其他 4 个数据都是无用数据，所以这种程序的空间局部性不好，在一定时间内我们要尽量访问相邻的数据，所以做如下改善：

int x[5][5];
/***初始化获取数据 略***/
for(int i = 0; i < 5; i++)
    for(int j = 0; j < 5; j++)
        x[i][j]++;

如此便是以行的形式来访问二维数组，同样的，两种方案可以来简单的计算一下缺失率：

方案一：访问 25 次，缺失 25 次，缺失率 100%

方案二：访问 25 次，缺失 5 次，缺失率 20%

因为是特定的例子，缺失率计算起来就很简单，关于二维数组，Cache 计算缺失率的题很常见，虽然说给定的参数不会像这个例子那么特殊，但基本道理是这么个理儿。

(4)循环融合

前面都说的是改善空间局部性，这里来看看改善时间局部性的例子，同样假设Cache 结构：容量 40B，块大小 20B，全相联，则一行能放 5个 int 型数据，有 2 行，现有以下代码：

int a[5][5];
int x[5][5];
/***初始化获取数据 略***/
for(int i = 0; i < 5; i++)
    for(int j = 0; j < 5; j++)
        a[i][j] += 1;
for(int i = 0; i < 5; i++)
    for(int j = 0; j < 5; j++)
        a[i][j] += 2;

不要管这个例子有什么特殊意义，只是举个例子说明。在这个例子当中每个 访问了 2 次， 因为全相联的 Cache 只有 2 行，所以第二次访问 时会缺失，同样的数据在近期可能会再次访问，对于这个程序来说 “近期” 有点长，时间局部性不好，我们要改善：

int a[5][5];
int x[5][5];
/***初始化获取数据 略***/
for(int i = 0; i < 5; i++)
    for(int j = 0; j < 5; j++){
        a[i][j] += 1;
        a[i][j] += 2;
    }

如此 的两次访问就是接连访问的，大大改善了时间局部性，同样的简单计算两种方案的缺失率：

方案一：访问 50 次，缺失 10 次，缺失率 20%

方案二：访问 50 次，缺失 5 次，缺失率 10%

(5)分块

分块(chunk)主要还是对数组来说的，在程序中，我们经常会对数组元素访问，通常如果数组很大，Cache 不能放下整个数组，这时我们可以将数组分块，就跟矩阵分块一样。比如说我一个数组分成了 A B C D，四个块，Cache 的确不能将整个数组放下，但是能一次性放下 chunk A(这里的块和 Cache 里的块重叠，我用英文代替)，我先把所有访问 chunk A 的元素操作完成，这样就避免了访问数组里其他区域元素时替换 chunk A 的数据，改善了时间局部性。

来看个例子：

/***k次遍历数组x[][]***/
for(int k = 0; k < MAXK; k++)
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            x[i][j]++;
/********分块*********/
for(int ii = 0; ii < N; ii += B)
  for(int jj = 0; jj < N; jj += B)
    for(int k = 0; k < MAXK; k++)
      for(int i = ii; i < min(ii + B, N); i++)
        for(int j = jj; j < min(jj + B, N); j++)
          x[i][j]++;

这代码应该也不难理解吧，ii 和 jj 分别代表每一 chunk 第一个元素所在的行与列，然后开始遍历这个 chunk。需要注意两点：

1. 因为不能确保整个矩阵是否能够刚好分块，所以要判断 min(ii + B，N)
2. 而上述的 B 可以称为分块因子，它表示一个 chunk 的行/列数，一般 chunk 都是正方形，行列数相等，而 B 的选取原则是，要使一个 chunk 的元素能够驻留在 Cache 里面，这就需要根据 Cache 的容量相联度块大小来判断

4、预取机制

所谓预取，顾名思义，提前将一些主存块装入 “Cache”，这种机制就不是按需缓存了。之所以 Cache 打引号，是因为预取的时候并不一定先放进 Cache，而是可以在 Cache 旁边设置一个小 buffer，预取的数据/指令先放进这个 buffer，这取决于具体如何设计。预取操作一般会在 Cache 缺失或者一些特殊的预取指令时触发。

预取从实现上分类可分为硬件预取和软件预取，硬件预取的大致实现思路：在 Cache 旁边放置一个预取器，它来预测哪些主存块在将来会被访问，然后提前预取这些将来可能会被访问的主存块。而软件预取就是在编写程序时使用一些特殊的编译制导预取语句。

预取从指令数据上分又可以分为指令预取和数据预取，指令的预取相对来说好做一些，因为指令的访问通常是顺序的，比较好预测，而数据的访问不确定性多一些，要实现比较精准的预测具有一定难度。

来看几个例子：

顺序预取器，简称为 OBL(One Block Lookahead)，从英文名字上看大概就猜到什么意思了，在 Cache 访问缺失的时候，不仅读取缺失的块，还预取与其相邻的下一块。这种预取器对于顺序流有很好的预取效果，比如说指令流。

步幅预取器，一看这名字大概也知道是什么意思了，它会观察学习数据访问的步幅规律确定预取的主存块，比如说，当步幅为 n 时，Cache 缺失时取主存块 i 时，预取第 i + n 块，所以顺序预取器其实就是步幅为 1 的步幅预取器。只不过，步幅预取器实现起来要比顺序预取器复杂的多，因为它要学习步幅，这件事比较麻烦，其实也不复杂，因为前面说过硬件做不了 “复杂” 的事情，我们这里就不展开了，有兴趣的可以去 Google Wiki一下

而软件预取是一些语言提供制导语句，可以使用特殊的预取制导语句来进行预取。

降低缺失代价

这一部分来讲述如何降低缺失代价

1、多级 Cache

最为常见的就是三级 Cache，先来看看其大致结构图示：

先解释一些名词：

• Regs，寄存器
• L1-data，L1 层级的数据缓存，L1-instruction，L1 层级的指令缓存
• unified cache，数据和指令放在一起的 cache

一级 Cache 都是分为两部分，数据 Cache 和 指令 Cache，这种结构叫做哈佛结构，与之区别对应的为冯诺依曼结构，冯诺依曼结构虽然到处都在提及，但现今的实际工程当中不会那么设计，效率很低。就拿指令和数据分开来说，为什么要分开，因为现在的 CPU 都支持流水线，取值和访存是可以分开进行的，取值和访存分开进行除了流水线这一前提之外还有个前提，那就是指令和数据得在两个存储器当中，不然就会引起冲突，这有个专有名词叫做结构相关，关于流水线的设计和其中一些相关性问题后面找时间单独说说。

为什么要使用多级 Cache，虽然把它放在降低缺失代价这里，但其实各个方面都有涉及到。我们想要速度快容量大成本还低的存储器，但这些往往不可兼得，所以在各层级存储之间加入 Cache 平衡速度提高性能。在 Cache 这里同样的道理，考虑空间大小，速度，容量，缺失率，缺失代价，成本等等因素之间的平衡，将 Cache 再次分级。

L1 距离 CPU 核最近，为了跟上核心的处理速度，L1 一定要快，所以 L1 主要解决速度问题，实际的工程设计当中就是专门对 L1 的速度优化过。而对于 L2 速度的要求相对来说不是那么高，通常更关心容量大小，实际工程当中对 L2 也是为了提供更大的容量而进行优化。而 L3 呢，一部分肯定也是有容量的考虑，再者就是为了更快的解决共享，处理器之间通信的问题。

关于多级 Cache 有几个常见的性能指标：

首先就是 AMAT，这个计算公式前面说过，在多级 Cache 中：

所以，

加上 L3 的话就依次类推，不再详述。

另外上面所说的缺失率，那叫局部缺失率，还有一种缺失率叫做全局缺失率

一般说来，全局缺失率更具有参考意义，举个例子说明，通常 L2 的局部缺失率很大，而且一般 L1 的命中率越高，L2 的局部缺失率越大，why？因为 L2 局部缺失率计算式的分母是访问 L2 的次数，而访问 L2 的次数是访问 L1 缺失的次数，L1 命中率越高缺失的次数越少，则分母越小，分母越小得出来的数可能就更大，但能说 L2 的性能就不好吗？不能。

多级 Cache 对于层级之间的数据是否重复可以分为包含式 Cache 和独占式 Cache：

• 包含式 Cache(Inclusive Cache)：拿 L1 L2 来举例说明，L1 的数据一定在 L2 中，但 L2 中的数据不一定在 L1 中

• 独占式 Cache(Exclusive Cache)：L1 和 L2 中的数据不重叠

• 非包含非独占 NINE(Non-inclusive Non-exclusive)：恰如其名，不好定义后面举例说明

(1)Inclusive

如果 CPU 访问块 X，L1 中命中，直接从 L1 取数据

如果 CPU 访问块 X，L1 缺失，L2 命中，从 L2 中取块放进 L1

如果 CPU 访问块 X，L1 缺失，L2 缺失，L3 命中，从 L3 中取块放进 L2 和 L1

如果要驱逐 L1 中的块，直接驱逐就是，没有 L2 的事儿

如果要驱逐 L2 中的块，驱逐时要将 L1 中相应的块置为无效，因为必须满足包含的关系，L2 中没有的，L1 也必须没有。

所谓驱逐就是替换操作将某块替换出去

看个例子：

1. 初始情况 L1 L2 都为空
2. read X，L1 miss,，L2 miss，假设 L3 hit，从 L3 将块取过来放进 L2，L1
3. read Y，同上
4. 驱逐 L1 中的 X，直接驱逐就是，L2 不参与
5. 驱逐 L2 中的 Y，将 L1 中 Y 所在的行置为无效

(2)Enclusive

如果 CPU 访问块 X，L1 中命中，直接从 L1 取数据

如果 CPU 访问块 X，L1 缺失，L2 命中，该块从 L2 移动到 L1，注意移动这个词，移动则说明 L2 中该块就没了

如果 CPU 访问块 X，L1 缺失，L2 缺失，L3 命中，从 L3 将该块取过来只放进 L1

如果驱逐 L1 中的块，将该块移动到 L2，这是填充 L2 唯一的方式，此时 L2 就像一个 Victim Cache

看个例子：

1. 初始情况 L1 L2 都为空
2. read X，L1 L2 都 miss，假设 L3 hit，则从 L3 将 X 取过来只放进 L1
3. read Y，同上
4. 驱逐 X 时，将 X 从 L1 移动到 L2

(3)NINE

去这种名字都是两相像又两不像，来看其规则：

如果访问块 X，L1 hit，则直接从 L1 取数据

如果访问块 X，L1 miss，L2 hit，则将该块从 L2 中取过来放进 L1

如果访问块 X，L1 miss，L2 miss，L3 hit，则将该块从 L3 取过来放进 L1 和 L2

如果驱逐 L1 中的块，没 L2 的事儿，与 inlcusive 一样

如果驱逐 L2 中的块，没 L1 的事儿，没有 inclusive invalidation 这个步骤

看个例子：

1. 初始情况 L1 L2 都为空
2. read X, L1 miss，L2 miss，假设 L3 hit，从 L3 将 X 取过来放进 L1 和 L2
3. read Y，同上
4. 驱逐 L1 中的 X，直接驱逐
5. 驱逐 L2 中的 Y，直接驱逐

2、write buffer

对于读缺失，通常会导致阻塞，因为 CPU 想要继续处理，必须取得读的数据。但是写缺失不一样，CPU 不需要写操作的结果，只要写进去就行了，所以一般对于写缺失可以不阻塞，使其在 “后台” 完成写操作，以此来降低写缺失的代价。

如何实现呢？我们可以在 Cache 旁边放一个 write buffer，当需要向下一级存储写的时候就先把数据写到速度较快的 buffer 中，buffer 再慢慢写到下一级存储，处理器则去处理其他事情。来看看示例图：

看着这个图，有没有与什么写策略联系起来？没错，write through 写通，前面说过，写通虽然能够很好的保证数据一致性，但是慢，因为每次都要写当前一级的存储，还要写下一级的存储。所以 write buffer 就是一个很好的解决方案，一般来说高性能的 CPU 写通模式的 Cache 旁边都要放一个 write buffer，当然不是说只有写通会有，比如说写回策略脏块被替换出去写到下一级存储时也可以交由 write buffer 来做，这看具体设计，tradeoff。

除了使得 CPU 不阻塞暂停之外，write buffer 还有一个作用，那就是减少写的流量(英文名 write traffic，没找到相关的中文专有名词，也不知翻译对没得，意思应该差不太多)。它可以吸收(absorb) 写操作，关于吸收我在 xv6 的某个地方(emm，记不清那儿了) 也讲述过，意思都一样，当 CPU 对同一个块多次写时，因为 write buffer 的存在吸收掉着多次写操作，使得只对下一级存储进行一次写操作，减少写流量。

另外再说明一点，write buffer 的存在并不一定使得 CPU 不暂停阻塞，如果 write buffer 满了的话，CPU 需要等待 write buffer 为空，这个就很好理解了吧，与生产者消费者问题一个道理。

上述就是 write buffer 的两个主要作用，一是“不阻塞”CPU，让写操作后台完成以此来隐藏写的延迟，二是吸收写操作减少写流量。有意思的是这两个作用对 write buffer 的状态要求不同，buffer 为空对第一个功能有利，而 buffer 满对第二个功能有利，想想是这个理儿对吧。

说了这么多，那 write buffer 到底啥样？write buffer 是一个 FIFO，通常深度(就理解为能够支持的 Cache 块数)不用太多，几项就能够有很好的性能了。每一项需要包括哪些信息呢？数据肯定是必不可少的，再者就是块的地址信息，因为需要知道 buffer 里面的数据写到哪儿去。

上述都是说的 write buffer 的好，那它有没有什么问题呢？提出这个问题，那当然就是有问题的，一个典型的问题就是 写缺失后紧接着读缺失，以写通写不分配来举例说明：

假如现在有这么一种情况，要将 ebx 寄存器里的值写到 eax 所表示的内存中去，然后紧接着又把 eax 所表示的内存值给读到 ecx 中去。再假设写的时候发生缺失，这时直接将数据写到 write buffer，然后 CPU 就直接返回去处理其他事情即读取相同地址的数据，又发生读缺失，读缺失需要阻塞从下一级存储获取数据，但是这时 write buffer 还没有完成写操作，则读取的数据错误。

流水线上也有这样的错误，叫做数据相关，怎样解决这个问题呢？最简单的方法就是读缺失的时候暂停等待，另外插一句，CPU 的设计里面一般什么相关性的问题都有个万能解决方法，那就是暂停等待，只不过效率很低。所以一般地可以加一层判断逻辑，读缺失的时候先检查 buffer 的地址部分，看是否有冲突，没有则继续，否则等待写操作完成。

3、非阻塞 Cache

前面的 write buffer 可以解决一部分写缺失和写回的阻塞问题，但是读缺失是需要阻塞等待取得数据才能继续往下执行。但比如说有两条读操作指令：read A，miss；read B hit；虽然 read A miss，需要把 A 的数据取过来才能继续 read A 这条指令的执行。但是这并不影响 CPU 处理 read B 这条指令啊，如果 read A miss 时不阻塞就好了，这就是 非阻塞 Cache 机制的思想，想要解决的问题。

非阻塞 Cache 不需要等待之前的 Cache 缺失完成，它可以同时为多个 miss 服务，现在被主流的 CPU 广泛采用，前面说过一般地写缺失和写回由 write buffer 来处理，所以这里 非阻塞 Cache 实际上只需要考虑读缺失的问题。

要想同时接受多个 miss 同时为多个 miss 服务，肯定是需要一个东西来记录 miss 状态，这个东西叫做 Miss Status Holding Register，也叫做 miss buffer，专门来存放 miss 的状态信息。如果某个请求 miss 时就会去 MSHR 中检查是否有相同的缓存请求，如果有合并，如果没有，追加进 MSHR，排队等待 miss 处理，特别的如果 MSHT 满了，那么 CPU 等待。

降低命中时间

这一小节来讲述降低第三个因素，命中时间，对于 Cache 的命中时间可以简单分为两个部分，使用 index 查找的时间还有就是使用 tag 进行比较的时间，一般地相联度越高，tag 比较的次数就越多，花的时间就越多。

1、更简洁的 Cache

前面降低缺失率一块儿说过，Cache 的结构会影响命中时间，所以我们可以减小容量大小，减小相联度来降低命中时间，但是缺失率又会上升，需要 tradeoff，一般来说 L1 的容量很小，相联度也比较低，因为对于 L1 来说距离核心更近，它需要跟上 CPU 的速度，此外还有工艺，功耗等各个方面的因素就不具体说明了。

2、路预测 way prediction

直接映射命中时间低缺失率高，组相联命中时间高缺失率低，因为 n 路组相联需要进行 n 次比较才能知道该组是否有 CPU 需要的数据。而路预测顾名思义，预测该组的哪一行可能有需要的数据。如果预测正确命中时间只比直接映射长那么一丢丢，如果预测错误则需要按原来普通的 n 次比较，会花费更多的时间。至于路预测的实现方式在这里先不说明，它跟分支预测比较相似，后面我讲述分支预测的时候再详细说明。

还有其他的一些降低命中时间的技术就更复杂了，比如说 pipeline cache，把 Cache 也做成流水线的形式，以此来提高性能。光想想感觉就挺复杂的，我也没研究那么深，就不再多说了。

Cache 控制器

一个 Cache 控制器的实现还是有些复杂的，就算简单的 Cache 控制器，涉及的东西也很多，数字逻辑的知识，verilog 语言等等，这些都不讲述，我们来看一个简单的 Cache 控制器的 状态机 即可。有兴趣的可以详细参考 计算机组成与设计 这本书的 Cache 控制器实现，作者还提供了一个 Cache 控制器的源码，有兴趣的可以看看。

这里来看一个写回写分配的一个例子，也是那书上提供的一个实例：

逻辑还是很简单的，分为三种情况：

• CPU 请求，比较标记，命中则返回数据
• CPU 请求，比较标记，缺失，需要从下一级将相应的块取过来替换掉当前块，当前块不脏，则直接将当前块替换掉，也就是分配操作，然后转到标志比较操作
• CPU 请求，比较标记，缺失，需要从下一级将相应的块取过来替换掉当前块，当前块脏，则先进行写回操作，再转到分配操作读入新块，再转到标志比较操作返回数据

Cache 一致性

每个处理器共享主存，但是由于处理器都有自己的 Cache，不同处理器保存的存储器视图都是由各自的 Cache 得到的，如果没有什么防范措施，不同处理器的 Cache 对于同一个地址上的数据保存的值可能就不一样，这就是 Cache 一致性的问题。

举个例子：

上述假设 Cache 的写策略是写通，CPU A 和 CPU B 先后读取 X 没问题，但是可以看出当 CPUA 向 X 写入 1 时，CPUA 的 CacheA 缓存的 X 和 主存中的 X 都变为 1，但是 CPUB 的 CacheB 缓存的 X 块并未变化，这就是一致性的问题，需要解决。

比较常用的解决方案就是监听协议，核心思想就是当一个 CPU 对自己的 Cache 进行写操作时，广播事件告知其他 CPU，其他 CPU 监听到该时间之后就检查是否有相同的数据缓存在自己的 Cache 中，有的话就置为无效。

监听协议较为简单，但要时刻监听，开销大性能不高，所以使用状态机来改善了该机制，就是现在主流 CPU 会使用的一致性协议，MESI 协议。本来想说说 MESI 协议的，但是 Wiki 上面讲述的很清楚了，我再讲的话估计就是重复一遍，没意思，这真不是我懒，写到这已经写了一万二的字数了怎么都不算懒了吧。对 MESI 协议有兴趣的可以去看看，有中文版本的，我在网上搜了很多讲述 MESI 协议的，就 Wiki 写得最详细清楚。

TLB

上面就是 Cache 的一些知识，这里再来讲述一种特殊的 Cache ：TLB，它用来缓存页表项，加速地址转换。大家应该都知道一些虚拟存储，但其中的一些概念可能还是模模糊糊，比如说什么是虚拟内存，其概念众说纷纭，这个问题我比较认同这位大佬的答案 https://www.zhihu.com/question/295194595/answer/999804696 大家可以参考参考。另外各类地址的意思，怎么转换可以参考我前面讲计算机启动当中关于分段分页地址转换的讲述，本文就不做过多叙述。

在没有 TLB 的时候，想想如何转换地址并获取数据

1. CPU 将 VA 发送给 MMU
2. MMU 访问内存获取页表项，在 x86 架构中 CR3 指出页表位置，VA 的页号指出页表项位置
3. MMU 根据页表项的物理页号和 VA 的偏移量组合成物理地址
4. 将物理地址送去缓存
5. 取得的数据送到 CPU

每次访存很慢，所以得想办法加快，很容易就想到 Cache，在 MMU 里面设置一个 Cache 专门来缓存页表项，这就 TLB。既然 TLB 本质上是一个 Cache，那它的结构也就不言而喻，主要还是那几部分组成，标记数据有效位等等，只不过数据换成了页表项，标记换成了虚拟地址。这里先提前说一句，这之前说的 Cache 里面的标记域都是物理地址，但其实是有几种模式的，后面讨论。

来看看有了 TLB 之后如何进行地址转换然后获取数据：

就多了一个先查询 TLB 的过程，不再赘述。有了 TLB 之后，MMU 对于页表项的获取就会先从 TLB 内进行，当 TLB 缺失的时候才会访问内存中的页表，由于局部性原理，命中率较高，根据 AMAT 的计算公式可知加入 TLB 之后获取页表项转换地址的速度将大大加快。

L1 分为 DL1 和 IL1 来支持取指和访存同时进行，因为访问 Cache 比较 tag 需要进行地址转换，所以为支持取指访存同时进行 TLB 也分为 DTLB 和 ITLB，也有可能再向下分级，二级 TLB，三级 TLB 等等。

所以到现在一个完整的访存过程如下所示：

这个图大家脑子里应该是都有一张的，一些地方一时反应不过来的可以再仔细看看想想，每种情况具体步骤我就不再说明了。

Cache 寻址

最后这一部分来讲讲 Cache 的寻址方式，首先会根据地址的 index 域来查找某个组，然后根据地址的 tag 来与 Cache 行中的 tag 比较判断是否命中，这个地址是虚拟地址还是物理地址呢？tag 和 index 两部分的可以有着不同组合：

• VIVT(Virtual Index Vitual Tag)：tag 和 index 均使用虚拟地址
• PIPT(Physical Index Physical Tag)：tag 和 index 均使用物理地址
• VIPT(Virtual Index Phsical Tag)：tag 使用物理地址，index 使用虚拟地址

按照组合情况应该还有一种 PIVT，但是这种情况没有意义，因为要先使用物理地址的 index 去查找定位 Cache 中的某组，则说明地址已经转换过，那我比较 tag 的时候干嘛还要去使用虚拟地址呢，使用虚拟地址是可能会出现问题的。

主要会出现两种问题：歧义和别名。

歧义是指相同的虚拟地址映射到不同的物理地址，这主要是因为每个进程都有自己的地址空间，相同的虚拟地址映射到同样的物理地址是完全有可能的。

这与 Cache 有何相关，举个例子，进程 A 的 VA 0x100 映射到 PA 0x200，进程 B 的 VA 0x100 映射到 PA 0x300，如果不做任何处理，从 A 切换到 B 时，B 访问 0x100 时会命中，而对应的 PA 是 0x200 不是 0x300，导致错误。一般地解决方法就是切换进程的时候冲刷 Cache。

别名问题设置不同的虚拟地址映射到相同的物理地址，这主要是因为进程通讯共享内存。

这又如何与 Cache 相关，同样来看个例子：VA 0x100 和 VA 0x200 都映射到 PA 0x300，假如 index 域为 8~11，则两个虚拟地址的 index 域不同，那么缓存时就有可能将 PA 0x300 的数据缓存到两个不同的 行，导致错误。一般地解决方法也就是直接冲刷 Cache，对共享页的数据不缓存，这两种做法较为低效，较为高效的是想办法使 VA 索引到相同的 Cache 行，这个算法就较为复杂一般是交由软件操作系统来做。

VIVT

VIVT 的寻址过程如上，先用 index 查 Cache，然后用 tag 做比较，命中的话再用 offset 选取相应的数据块，最后返回给 CPU。如果不命中 MMU 则将 VA 转换为 PA，访存然后将主存中的块加载到 Cache，重新获取数据返回给 CPU。

VIVT 的优点就是不需要每次都将 VA 转换为 PA，速度快。但现在的 CPU 基本不用这种方式，主要原因就是前面提到的那两个问题歧义和别名，两个都有。

PIPT

这种方式我们应该很熟悉了，首先就把虚拟地址转换为物理地址，然后用物理地址的 index 去查 Cache，tag 去比较，命中的话根据 offset 返回数据，不命中的话则要访存将主存块加载到 Cache，然后返回数据给 CPU。因为每次都要进行地址转换所以性能较差，但由于物理地址的唯一性，不会存在歧义别名问题。

VIPT

VIPT 先用虚拟地址的 index 查询 Cache，再用物理地址的 tag 进行比较，因为在查找过程可以同时进行地址转换，所以 VIPT 的性能是高于 PIPT。考虑歧义问题，不同进程中相同的虚拟地址映射到不同的物理地址，但由于 Cache 使用物理地址，物理地址唯一不会产生歧义。那别名问题呢？这个需要好好说到说到。

一个虚拟地址映射到一个物理地址，虚页号和实页号一般不会相同，但是页偏移是相同的，这是用页号页偏移来对地址进行划分。对于 Cache 我们也将地址划分为 tag index offset，其中的 index 可以看作是组数。

对于别名问题是说多个虚拟地址映射到同一个物理地址，如果 index 位置在 PageOffset 之内，那么这多个虚拟地址的 index 域是相同的，它们会映射到相同的 Cache 行，这种情况就不会造成别名问题，反之 index 位置超过 PageOffset 时，多个虚拟地址对应 index 域可能不同，那么它们就会映射到不同的 Cache 行，造成问题。

用数值来说满足什么条件呢？我们来计算一下：加入上述 PageOffset 的位数为 p，index 位数为 i，offset 位数为 o，index 位置要在 PageOffset 之内，所以有   则

举个例子来说明，Cache 容量 16KB，4 路组相联，Cache Line 32B，页大小 4K，现有虚拟地址 0x00001000，0x00002000 映射到物理地址 0x00003000。

，所以 index 为地址的 5~11 位，刚好在 4K(0~11 位) 之内，由于 PageOffset 相同，所以两虚拟地址的 index 相同，映射到了 Cache 同一组，然后物理 tag 唯一使得两者一定映射到同一行

如果 Cache 容量 32KB，4 路组相联，Cache Line 32B，页大小 4K，现有虚拟地址 0x00001000，0x00002000 映射到物理地址 0x00003000。

，所以 index 为地址的 5~12，超出 PageOffset 范围，两虚拟地址的 index 最高位不同，则映射到不同的 Cache 组，造成同一物理地址存在两个 Cache Line 中，产生别名问题。

有什么解决方案呢？从上面的图就可以看出，只要 index 在 PageOffet 范围内就行，有些什么方案？

• 提高相联度，相联度提高之后组数减少，index 也就减少。
• 使用大页，页变大，则 PageOffset 涵盖的范围就更广，就更可能覆盖到 index

上述就是关于 Cache 的一些问题，最后再来辨析一个问题：CPU 能不能和主存直接交换数据

我们常说，书上也常说，CPU 可以和主存直接交换数据，不能与辅存比如说磁盘等直接交互数据，但真的是这样的吗？其实不然，理论和工程实践上是有差异的，虽然我不是做芯片这方面的研究，但是对于这个问题我专门去向这方面研究的老师还有网上的大佬求证过，现代的 CPU 是不会直接与主存的数据进行交互的，而是与 cache 直接交互数据，cache 再与主存直接交互数据。

回想我们前面讲述的，CPU 和主存之间隔了三级 Cache 呢，而且还有各种 buffer 来帮助读写操作，所以 CPU 其实距离主存挺远的。想想 CPU 如果和主存能够进行数据交互的话会如何设计？主存与 CPU 之间势必会有数据线相连，而 cache 肯定是会与主存直接交互数据的，那么 cache 也会有数据线和主存相连，这样设计浪费空间且复杂，所以现代的 CPU 不会这么设计。

但是书上又经常说主存与 CPU 进行数据交互，这就略去了 cache 在这之间的作用，但是我们也不要纠结谁对谁错，平常所学习的都是理论，理论与现实总是有差距，学习知识只要保证能够在现有的知识结构上自圆其说就行。

好了本文就到这里，有什么问题还请批评指正，也欢迎大家来同我交流学习。

写留言