一. CPU cache结构

1.1 Chache 的意义

CPU在一段较短的时间内，是对连续地址的一段很小的主存空间频繁地进行访问，而对此范围以外地址的访问甚少，这种现象称为程序访问的局部性。

高速缓冲存储器（Cache）技术就是利用程序访问的局部性原理，把程序中正在使用的部分（活跃块）存放在一个小容量的高速Cache中，使CPU的访存操作大多针对Cache进行，从而解决高速CPU和低速主存之间速度不匹配的问题，使程序的执行速度大大提高。

1.2 和寄存器

存储器的三个性能指标——速度、容量和每位价格——导致了计算机组成中存储器的多级层次结构，其中主要是缓存和主存、主存和磁盘的结构。那么在主存之上，cache和寄存器之间的关系是？

image.png

1.3 CPU Chache 的结构原理

CPU缓存通常分成了三个级别：L1，L2，L3。级别越小越接近CPU，所以速度也更快，同时也代表着容量越小。L1 是最接近CPU的, 它容量最小（例如：32K），速度最快，每个核上都有一个 L1 缓存，L1 缓存每个核上其实有两个 L1 缓存, 一个用于存数据的 L1d Cache（Data Cache），一个用于存指令的 L1i Cache（Instruction Cache）。L2 缓存 更大一些（例如：256K），速度要慢一些, 一般情况下每个核上都有一个独立的L2 缓存; L3 缓存是三级缓存中最大的一级（例如3MB），同时也是最慢的一级, 在同一个CPU插槽之间的核共享一个 L3 缓存。

单核CPU cache结构

image.png

多核CPU cache结构

image.png

一级缓存
一级缓存（Level 1 Cache）简称L1 Cache，位于CPU内核的旁边，是与CPU结合最为紧密的CPU缓存，也是历史上最早出现的CPU缓存。由于一级缓存的技术难度和制造成本最高，提高容量所带来的技术难度增加和成本增加非常大，所带来的性能提升却不明显，性价比很低，而且现有的一级缓存的命中率已经很高，所以一级缓存是所有缓存中容量最小的，比二级缓存要小得多。

一般来说，一级缓存可以分为一级数据缓存（Data Cache，D-Cache）和一级指令缓存（Instruction Cache，I-Cache）。

二级缓存
L2 Cache（二级缓存）是CPU的第二层高速缓存，分内部和外部两种芯片。内部的芯片二级缓存运行速度与主频相同，而外部的二级缓存则只有主频的一半。L2高速缓存容量也会影响CPU的性能，原则是越大越好，现在家庭用CPU容量最大的是4MB，而服务器和工作站上用CPU的L2高速缓存普遍大于4MB，有的高达8MB或者19MB。

三级缓存
三级缓存是为读取二级缓存后未命中的数据设计的—种缓存，在拥有三级缓存的CPU中，只有约5%的数据需要从内存中调用，这进一步提高了CPU的效率。

CPU与Cache之间的数据交换是以字为单位的，而Cache与原子性主存之间的数据交换则是以块为单位的。一个块由若干个定长字组成。
当CPU读取主存中的一个字时，该字的主存地址被发给Cache和主存，此时，Cache控制逻辑依据地址判断该字当前是否存在于Cache中：若在，该字立即被从Cache传送给CPU；若不在，则用主存读周期把该字从主存读出送到CPU，同时把含有这个字的整个数据块从主存读出送到Cache中，并采用一定的替换策略将Cache中的某一块替换掉，替换算法由Cache管理逻辑电路来实现。

Cache原理图如图，图中，按内容寻址的相联存储器（表），用于存放与Cache中数据相对应的主存地址，可以快速检索、判断CPU读取的某个字当前是否存在于Cache中。

image.png

1.4 Chache line 结构

整个Cache被分成多个Line，每个Line通常是32byte或64byte ，Cache Line是Cache和内存交换数据的最小单位

image.png

每个Cache Line包含三个部分Valid：当前缓存是否有效Tag：对应的内存地址Block：缓存数据

image.png

1.5 cpu Chache 与cpu 主存交互

Cache与主存都分成块(常常将Cache块说成Cache行)，每块由多个字节组成，大小相等。在一个时间段内，Cache的某块中放着主存某块的全部信息，即Cache的某一块是主存某块的副本(或叫映像)
地址映射是指某一数据在内存中的地址与在缓存中的地址两者之间的对应关系。下面介绍三种地址映射的方式。

1.5.1 全相连映射

全相联映射是指主存中任意一个块都可以映射到Cache中任意一个块的方式，也就是说，当主存中的某一块需调入Cache时，可根据当时Cache的块占用或分配情况，选择一个块给主存块存储，所选的Cache块可以是Cache中的任意一个块。如下图

image.png

当一个主存块调入Cache中时，会同时在一个存储主存块号和Cache块号映射表的相联存储器中进行登记。CPU访存时，首先，根据主存地址中的主存块号M在相联存储器中查找Cache块号C，若找到，则本次访Cache命中，于是将对应的Cache块号取出，并返回Cache地址的块号C字段，紧接着将主存地址的块内字号W直接送Cache地址的块内字号W字段，从而形成一个访Cache的地址，最后根据该地址完成对Cache单元的访问。

优点 命中率比较高，Cache存储空间利用率高。

缺点 相联存储器庞大，比较电路复杂，访问相关存储器时，每次都要与全部内容比较，速度低，成本高，因而只适合于小容量的Cache之用，应用少。

1.5.2 直连连映射

直接相联映射方式是指主存的某块j只能映射到满足如下特定关系的Cache块i中

i = j mod 2c

image.png

1.5.3 组相联映射

相联映射方式在这种方式下，将Cache分成2u组，每组包含2v块。主存的块与Cache的组之间采用直接相联映射，而与组内的各块则采用全相联映射。也就是说，主存的某块只能映射到Cache的特定组中的任意一块。主存的某块j与Cache的组k之间满足如下关系

image.png

如果主存储器中的每个位置都可以缓存在缓存中的两个位置中的任何一个位置，那么一个逻辑问题是：两者中的哪一个？上面右边图中显示的最简单和最常用的方案是使用内存位置索引的最低有效位作为高速缓存内存的索引，并为每个索引提供两个条目。该方案的一个好处是存储在高速缓存中的标签不必包括高速缓冲存储器索引所暗示的主存储器地址的那部分。由于高速缓存标签具有较少的位，因此它们需要较少的晶体管，在处理器电路板或微处理器芯片上占用较少的空间，并且可以更快地读取和比较。也是LRU 因为每对只需要存储一个比特，所以特别简单。

1.6 Chache 替换策略

为了在高速缓存未命中时为新条目腾出空间，高速缓存可能必须逐出现有条目之一。用于选择逐出条目的启发式方法称为替换策略。任何替换策略的根本问题在于它必须预测将来最不可能使用哪个现有缓存条目。预测未来很困难，因此没有完美的方法可以选择各种可用的替代政策。一种流行的替换策略，最近最少使用（LRU），替换最近最少访问的条目。

将一些内存范围标记为不可缓存可以通过避免缓存很少重新访问的内存区域来提高性能。这避免了在没有任何重用的情况下将某些内容加载到缓存中的开销。也可以根据上下文禁用或锁定缓存条目。

主要算法如下

1.6.1.随机法（RAND法）

随机法是随机地确定替换的存储块。设置一个随机数产生器，依据所产生的随机数，确定替换块。这种方法简单、易于实现，但命中率比较低。

1.6.2.先进先出法（FIFO法）

先进先出法是选择那个最先调入的那个块进行替换。当最先调入并被多次命中的块，很可能被优先替换，因而不符合局部性规律。这种方法的命中率比随机法好些，但还不满足要求。先进先出方法易于实现，例如Solar－16/65机Cache采用组相联方式，每组4块，每块都设定一个两位的计数器，当某块被装入或被替换时该块的计数器清为0，而同组的其它各块的计数器均加1，当需要替换时就选择计数值最大的块被替换掉。

1.6.3.最近最少使用法（LRU法）

LRU法是依据各块使用的情况，总是选择那个最近最少使用的块被替换。这种方法比较好地反映了程序局部性规律。

1.7 Chache 写策略

如果将数据写入高速缓存，则必须将其写入主存储器; 这种写入的方式称为写入策略。

在直写高速缓存中，每次写入高速缓存都会导致写入主存储器。在而回写高速缓存中，写入不会立即镜像到主存储器，而是高速缓存会跟踪已写入的位置，将它们标记为脏。只有当数据从缓存中逐出时，这些位置的数据才会写回主存储器。

由于这个原因，回写高速缓存中的读取未命中有时可能需要两次服务器存储器访问：一次首先将脏位置写入主存储器，然后另一次从存储器读取新位置。此外，对尚未映射在回写高速缓存中的主存储器位置的写入可以驱逐已经脏的位置，从而为新的存储器位置释放该高速缓存空间。

还有中间政策。高速缓存可以是直写的，但是写入可以暂时保存在存储数据队列中，通常可以一起处理多个存储（这可以减少总线周转并提高总线利用率）。

来自主存储器的高速缓存数据可能被其他实体（例如，使用直接存储器访问（DMA）的外围设备或多核处理器中的另一个核心）改变，在这种情况下，高速缓存中的副本可能变得过时或过时。或者，当多处理器系统中的CPU 更新高速缓存中的数据时，与其他CPU关联的高速缓存中的数据副本将变得陈旧。保持数据一致的高速缓存管理器之间的通信协议称为高速缓存一致性协议。

1.8 缓存一致性协议

MESI（Modified Exclusive Shared Or Invalid）(也称为伊利诺斯协议，是因为该协议由伊利诺斯州立大学提出的）是一种广泛使用的支持写回策略的缓存一致性协议。为了保证多个CPU缓存中共享数据的一致性，定义了缓存行(Cache Line)的四种状态，而CPU对缓存行的四种操作可能会产生不一致的状态，因此缓存控制器监听到本地操作和远程操作的时候，需要对地址一致的缓存行的状态进行一致性修改，从而保证数据在多个缓存之间保持一致性。

M: 被修改（Modified)

该缓存行只被缓存在该CPU的缓存中，并且是被修改过的（dirty),即与主存中的数据不一致，该缓存行中的内存需要在未来的某个时间点（允许其它CPU读取请主存中相应内存之前）写回（write back）主存。

当被写回主存之后，该缓存行的状态会变成独享（exclusive)状态。

E: 独享的（Exclusive)

该缓存行只被缓存在该CPU的缓存中，它是未被修改过的（clean)，与主存中数据一致。该状态可以在任何时刻当有其它CPU读取该内存时变成共享状态（shared)。

同样地，当CPU修改该缓存行中内容时，该状态可以变成Modified状态。

S: 共享的（Shared)

该状态意味着该缓存行可能被多个CPU缓存，并且各个缓存中的数据与主存数据一致（clean)，当有一个CPU修改该缓存行中，其它CPU中该缓存行可以被作废（变成无效状态（Invalid））。

I：无效的（Invalid）
失效（Invalid）缓存段**，要么已经不在缓存中，要么它的内容已经过时。为了达到缓存的目的，这种状态的段将会被忽略。一旦缓存段被标记为失效，那效果就等同于它从来没被加载到缓存中。