作者:Carlos0321

资料来源:https://segmentfault.com/a/1190000038771532

1. 什么是缓存

缓存，也叫高速缓存，是计算机内存的一种。本质上和硬盘一样，都是用来存储数据和指令的。两者最大的区别就是阅读速度。通常，程序存储在内存中。CPU执行程序时，执行一条指令后从内存读取下一条指令需要10万个时钟周期(缓存读取速度是200个时钟周期，相差500倍)。如果每次都从内存中取指令，那么CPU在运行时会花很多时间读指令。这显然是浪费资源。

如何解决这个问题？肯定有人会问，不能直接把程序存到缓存里吗？

答案是肯定的。但是，缓存的成本太贵了。如下图所示。以2015年的售价为例，1GB SRAM的价格约为327680美元，而1GB普通硬盘的价格仅为0.03美元。用缓存存储程序成本太高，得不偿失。

于是，有人提出了这样一个方法，在CPU和内存之间增加一个高速内存。这种高速存储器容量很小，只用来存储CPU执行时常用的指令。既保证了硬件成本，又提高了CPU的访问速度。这个高速内存就是缓存(cache)。

2. 缓存的定义

高速缓存是一种小型快速的存储设备，它充当存储在较大和较慢设备中的数据对象的缓冲区。使用缓存的过程称为缓存。

如下图所示，主存可以作为存储设备，L3是主存的缓冲区。从L3访问数据的过程称为缓存。

3. 计算机中的高速缓存3.1 高速缓存相关名词

如下图所示，数据总是以块为单位在缓存和主存之间来回复制。

如果我们的程序请求一个数据字，该数据字被存储在编号为10的块中。考虑以下情况:

1.空在缓存行中，这称为冷未命中。

2.缓存中有数据块，但没有数据块10。这被称为缓存未命中。接下来，缓存请求主内存将该块复制到缓存中，缓存收到后会替换一个已有的数据块，从而将新的数据块存储在缓存中。最后，高速缓存将数据块10返回给CPU。

3.缓存中有数据。当内存中的数据块放在缓存中时，就会发生冲突，称为冲突未命中。

最常用的放置策略是k+1层的块I必须放置在k层的块(i mod 4)中。例如，k+1层中的0，4，8，12将被映射到k层中的块0。块1、5、9、13将被映射到块1。

4.如果缓存中有数据块10，将直接返回给CPU。这称为缓存命中。

3.2 计算机中的高速缓存存储器模型

缓存完全由硬件管理，硬件逻辑必须知道如何找到缓存中的块，并确定它是否包含特定的块。因此，缓存必须以非常严格和简单的方式构建。在计算机中，缓存模型如下图所示。

我们可以把缓存看作是一个包含$ s = {2 s} $个缓存组的数组。每个组包含$ e = {2 e} $个缓存行。每行包含一个$ b = {2 b} $字节的数据块。

一般来说，缓存的结构可以用元组(S，E，B，m)来描述。缓存大小(或容量)c是指所有块大小的总和。不包括标志和有效位。因此，c = s× e× b。

每个缓存内存有M位，可以形成$ m = {2 m} $个不同的地址，$m = t+s+b$。每个数据块由以下三部分组成。

有效位:有效位为T位，T一般为1，表示该行是否包含有效信息。

标志位:标志位是s位。唯一标识存储在缓存中的块(数组索引)。

Block:数据块为$ b = {2 b} $ bytes。表示CPU请求的内容在数据块中的偏移量。

对上述内容中出现的参数进行汇总:

3.3 计算机中有哪些缓存

下表显示了现代计算机中使用的各种缓存。

3.4 硬件读取高速缓存的过程

当一条load指令指示CPU从主存地址A读取一个字W时，主存地址A会被送到cache，cache会根据以下步骤判断地址A是否命中:

分组选择:根据地址划分，将中间的S位表示为一个无符号数作为分组的索引，即可得到该地址对应的分组。

行匹配:根据地址划分，可以得到T位的标志位。由于组中的任何行都可以包含映射到该组的任何数据块，因此有必要线性搜索该组中的每一行，以确定是否存在标志位匹配且有效位被设置的行。如果有，缓存命中，否则，缓存未命中。

字提取:如果找到相应的缓存行，B位可以表示为一个无符号数作为块偏移量，以获得相应位置的字。

当缓存命中时，单词W将被快速提取并返回给CPU。如果高速缓存未命中，CPU将等待，并且高速缓存将从主存储器请求包含字W的数据块。当请求的块从主存储器到达时，高速缓存将把这个块保存在它的一个高速缓存行中，然后从存储的块中提取字W，并把它返回给CPU。

4. 直接映射高速缓存

上面我们已经介绍了计算机中的缓存模型，我们可以根据每组中缓存线e的数量将缓存分为不同的类型。我们来看看直接映射缓存的具体例子(E=1)。

4.1 组选择

分组选择图如下所示。假设有S组，每组由一行组成，缓存块为8字节。CPU发送一个地址来获取数据字，缓存将地址分为三部分。对于图中的地址，块偏移量是4。组索引是1，粉红色的是T位标记。因此，高速缓存提取组索引为1，这是图中的第二行。

4.2 行匹配

然后，检查地址中的标记位是否与高速缓存行中的标记位匹配。如果匹配，将选择下一个单词。如果不匹配，就说明错过了。如果未命中，缓存必须再次从内存中提取数据块，覆盖该行中的数据块。

4.3 字选择

当标志位匹配时，表示命中，然后检查地址中的块偏移量是否为4，即值应该从缓存行中数据块的第5位取出，并返回给CPU。

4.4 模拟直接映射缓存

现在，我们来模拟一下直接映射缓存的过程，以便更好地理解缓存是如何工作的。假设，内存地址为4字节，S=4组，E=1行/组，B=2字节/块。其结构图如下所示。

我们模拟CPU从缓存中读取地址为0，1，7，8，0的数据。下面是具体流程。

1.读取地址0的数据。标志为0，索引位为00，偏移位为0，块号为0。缓存行中没有数据，组0的有效位为0，地址的tag位与组0的tag位不匹配，所以未命中。然后，缓存从内存中取出block 0、block 1共2个字节，存储在group 0中。如下图所示。

2.读取地址1的数据。标志为0，索引位为00，偏移位为1，块号为1。缓存线中有数据，组0的有效位为1，地址1的标记位与组0的标记位匹配，所以命中。如下图所示。

3.读取地址7的数据。标志为0，索引位为11(3)，偏移位为1，块号为3。缓存中有数据，组3的有效位为0，地址的tag位与组0的tag位不匹配，所以未命中。然后，缓存从内存中取出块6和块7，共2个字节，存储在组3中。如下图所示。

4.读取地址8的数据。标志为1，索引位为00，偏移位为0，块号为4。缓存中有数据，组0的有效位为1，地址的tag位与组0的tag位不匹配，因此丢失。然后，缓存从内存中取出块8和块9，共2个字节，存储在组0中。如下图所示。

5.读取地址0的数据。标记位为0，索引位为00，偏移位为0，块号为0。缓存中有数据，组0的有效位为1，地址的tag位与组0的tag位不匹配，因此丢失。然后，缓存从内存中取出block 0、block 1共2个字节，存储在group 0中。如下图所示。

最终结果如下:缓存命中率20%。

注意:块大小是2个字节，所以从内存中获取数据总是从偶数倍数开始，所以您将看到M[8-9]而不是M[7-8]。

如果你理解了上面缓存的全过程，考虑如何编程模拟缓存？在下面的文章中，我将详细解释如何用C语言模拟缓存。

4.5 直接映射高速缓存的缺陷

观察上面的过程，我们实际上可以发现，在步骤5中，当读取地址0的数据时，我们必须再次将数据从内存中提取到缓存行中。当读取地址8处的数据时，M[8-9]替换高速缓存行中的M[0-1]。

主要原因是每个组中只能存储一行缓存。假设E = 2，每组有2条高速缓存线，则M[8-9]和M[0-1]很有可能同时存在于组0中。当我们在步骤5中访问时，我们不需要再次从内存中检索数据。因此，存在E = 2的双向关联高速缓存。

5. 两路相联高速缓存

由直接映射高速缓存中的冲突未命中引起的问题源于每组只有一行的限制。组关联高速缓存放宽了这一限制，因此每个组保存不止一个高速缓存行。下图显示了双向关联缓存。

5.1 组选择

其组选择与直接映射缓存相同，组索引位标识组。如下图所示，此处不再赘述。

5.2 行匹配

组关联缓存中的行匹配比直接映射缓存中的行匹配更复杂，因为它必须一次检查多行的标志位和有效位，以确定所请求的字是否在集合中。如下图所示。

5.3 字选择

选字的过程和缓存直接映射的过程一样，这里不再赘述。

5.4 模拟两路相联高速缓存

下面，我们模拟下一个双向关联缓存的过程，从而加深对缓存工作原理的理解。假设，存储器地址为4字节，S=2组，E=2行/组，B=2字节/块。其结构图如下所示。

我们模拟CPU从缓存中读取地址为0，1，7，8，0的数据。下面是具体流程。

1.读取地址0的数据。标记为00，索引位为0，偏移位为0，块号为0。& gt缓存中没有数据，组0的有效位为0，地址的tag位与组0的第一行和第二行的tag位不匹配，因此丢失。然后，缓存从内存中取出block 0，block 1，共2个字节，存储在group 0的第一行。如下图所示。

2.读取地址1的数据。标记为00，索引位为0，偏移位为1，块号为1。缓存中有数据。组0第一行的有效位为1，地址1的标记位与组0第一行的标记位匹配，所以命中。如下图所示。

3.读取地址7的数据。标记是01，索引位是1，偏移位是1，块号是1。缓存中有数据，组1的有效位为0，地址的tag位与组1中第一行和第二行的tag位不匹配，因此丢失。然后，缓存从内存中取出块6和块7，共2个字节，存储在组1中。如下图所示。

4.读取地址8的数据。标记位是10，索引位是0，偏移位是0，块号是0。缓存中有数据。组0的第一个有效位是1，第二个有效位是0。地址的标记位与组0的第一行和第二行的标记位不匹配，因此被遗漏。然后，缓存从内存中取出block 8和block 9，共2个字节，存放在group 0的第二行。如下图所示。

5.读取地址0的数据。标记为00，索引位为0，偏移位为0，块号为0。缓存中有数据。组0第一行的有效位为1，地址的tag位与组0第一行的tag位匹配，所以命中。如下图所示。

与直接映射缓存相比，双向关联缓存每组增加一行，缓存命中率提高15%。避免了cache频繁从内存中访问数据的情况，提高了程序的运行速度。

6. 全相联高速缓存

全关联高速缓存中的行匹配和字选择与组关联高速缓存中的相同，因此不详细描述该过程。其结构图如下所示。

相关性是不是越高越好？

答案是否定的，相关性越高，成本越高。实现起来很难，也很贵，很难让它更快。更高的相关性将增加命中时间，因为复杂性增加了。此外，它还会增加未命中的惩罚，因为选择受害线的复杂性也增加了。

相关度的选择最终成为命中时间和脱靶惩罚的折中。一般来说，高性能系统将为L1高速缓存选择较低的关联性(这里，未命中损失仅为几个周期)，并在较低层上使用较低的关联性，具有较高的未命中损失。例如，在英特尔酷睿i7系统中，一级和L2高速缓存是8路组关联的，而三级高速缓存是16路组关联的。

7. 真实计算机系统中的缓存

到目前为止，我们一直认为缓存只保存数据。然而，实际上，高速缓存存储数据和指令。只保存指令的高速缓存称为i-cache。只存储程序数据的缓存称为d-cache。同时保存指令和数据的缓存称为统一缓存。

下图显示了英特尔酷睿i7处理器的高速缓存层次结构。每个CPU芯片有四个核心。每个内核都有自己的L1 i缓存、L1 d缓存和L2统一缓存。所有内核共享片上三级统一高速缓存。其具体参数如下表所示。

8. 缓存的评价指标

最后，介绍了一些衡量高速缓存性能的指标:

8.1 不命中率

在程序或程序的一部分执行过程中，内存引用未命中的比率，等于:未命中数/引用数。

8.2 命中率

命中的内存引用比率。它等于:

8.3 命中时间

将一个字从缓存传送到CPU所需的时间，包括组选择、行确认和字选择的时间。一般来说，L1缓存的命中时间是4个时钟。L2的报时是:10点钟。

8.4 未命中惩罚

失误所需的额外时间。对于主存，通常需要50 ~ 200个时钟周期。

例如:

假设高速缓存命中时间是1个时钟周期，高速缓存未命中损失是100个时钟周期。

下面计算的97%缓存命中率和99%缓存命中率的平均访问时间是多少？公式是命中时间加上未命中惩罚乘以百分比系数。

97%命中率:$ 1+0.03 乘以100 = 4$时钟。

90%命中率:$ 1+0.01 乘以100 = 2$时钟。

结论:命中率提高了2%，平均访问时间减少了50%。

9. 总结

计算机中有各种各样的缓存，比如文件缓存就是在内存中缓存一些需要高速访问的变量，每次访问都可以直接读出。浏览器缓存根据服务器同意的一组规则工作。如果在浏览过程中访问了同一张图片，可以从浏览器缓存中调出并即时显示。数据库经常需要把从数据库中查询到的数据或者频繁更新的数据放到缓存中，这样下一次查询就会直接从缓存中返回，这样就减轻了数据库的压力。

知道这么多基本概念有什么用？如果我们理解了计算机系统是如何在内存中组织和移动数据的，我们就可以在编写程序时将数据项存储在适当的位置，CPU可以更快地访问它们，从而提高程序的执行效率。

作者:Carlos0321

资料来源:https://segmentfault.com/a/1190000038771532