CPU高速缓存

CPU在摩尔定律的指导下以每18个月翻一番的速度在发展，然而内存和硬盘的发展速度远远不及CPU。这就造了高性能的内存和硬盘价格及其昂贵。然而CPU的高度运算需要高速的数据。为了解决这个问题，CPU厂商在CPU中内置了少量的高速缓存以解决I\O速度和CPU运算速度之间的不匹配问题

局部性原理

在CPU访问存储设备时，无论是存取数据抑或存取指令，都趋于聚集在一片连续的区域中，这就被称为局 部性原理。
时间局部性
如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。 比如循环、递归、方法的反复调用等。
空间局部性
如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。 比如顺序执行的代码、连续创建的两个对象、数组等。

CPU执行计算的流程

  • 程序以及数据被加载到主内存
  • 指令和数据被加载到cpu的高速缓存
  • cpu执行指令，把执行结果写到告诉缓存
  • 高速缓存中的数据写回主内存

image.png

缓存结构

常用CPU多级缓存结构为L1、L2、L3三级缓存结构，如下图
image.png

MESI一致性协议

多核CPU的情况下有多个一级缓存，如何保证缓存内部数据的一致,不让系统数据混乱。这里就引出了一个 一致性的协议MESI。MESI 是指4中状态的首字母。每个Cache line（缓存存储数据的单元）有4个状态，可用2个bit表示，它们分别是

状态 描述 监听任务
M-修改 modified 该cache line有效，数据被修改了，和内存中的数据不一致，数据只存在本缓存行中 缓存行必须时刻监听所有试图读该缓存行的操作
E-独享exclusive 该Cache line有效，数据和内存中的数据一致，数据只存在于本Cache中。 缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S（共享）状态。
S-共享shared 该Cache line有效，数据和内存中的数据一致，数据存在于多个Cache line中。 缓存行也必须监听其它缓存行，使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）
I-无效invalid 该Cache line无效。 无

注意：对于M和E状态而言总是精确的，他们在和该缓存行的真正状态是一致的，而S状态可能是非一致的。如果一个缓存将处于S状态的缓存行作废了，而另一个缓存实际上可能已经独享了该缓存行，但是该缓存却不会将该缓存行升迁为E状态，这是因为其它缓存不会广播他们作废掉该缓存行的通知，同样由于缓存并没有保存该缓存行的copy的数量，因此（即使有这种通知）也没有办法确定自己是否已经独享了该缓存行。
从上面的意义看来E状态是一种投机性的优化：如果一个CPU想修改一个处于S状态的缓存行，总线事务需要将所有该缓存行的copy变成invalid状态，而修改E状态的缓存不需要使用总线事务。

MESI状态转换

image.png

触发事件 描述
本地读取 - local read 本地cache读取本地cache数据
本地写入 - local write 本地cache写入本地cache数据
远端读取 - remote read 其他cache读取本地cache数据
远端写入 - remote write 其他cache写入本地cache数据

本地cache：指当前cpu的cache
触发cache：触发读写事件的cache
其它cache：除了上述两种之外的cache

多核缓存协同操作

假设有三个CPU A、B、C，对应三个缓存分别是cache a、b、 c。在主内存中定义了x的引用值为0。
image.png

单核读取

cpuA发出一条指令，从主存中读取X，主内存通过bus读取到缓存a中（远端读取Remote read）,这时该Cache line修改为E状态（独享）.

双核读取

  • CPU A发出了一条指令，从主内存中读取x。
  • CPU A从主内存通过bus读取到 cache a中并将该cache line 设置为E状态。
  • CPU B发出了一条指令，从主内存中读取x。
  • CPU B试图从主内存中读取x时，CPU A检测到了地址冲突。这时CPU A对相关数据做出响应。此时x 存储于cache a和cache b中，x在chche a和cache b中都被设置为S状态(共享)。

修改数据

CPU A 计算完成后发指令需要修改x.
CPU A 将x设置为M状态（修改）并通知缓存了x的CPU B, CPU B将本地cache b中的x设置为I状态(无效)
CPU A 对x进行赋值。

同步数据

CPU B 发出了要读取x的指令。
CPU B 通知CPU A,CPU A将修改后的数据同步到主内存时cache a 修改为E（独享）
CPU A同步CPU B的x,将cache a和同步后cache b中的x设置为S状态（共享）。

缓存行伪共享

CPU缓存系统中是以缓存行（cache line）为单位存储的。目前主流的CPU Cache 的 Cache Line 大小都是64Bytes。在多线程情况下，如果需要修改“共享同一个缓存行的变量”，就会无意中影响彼此的性能，这就是伪共享（False Sharing）。
举例： 现在有2个long 型变量 a 、b，如果有t1在访问a，t2在访问b，而a与b刚好在同一个cache line中，此时t1先修改a，将导致b被动刷新！

MESI引入的问题及优化

缓存的一致性消息传递是要时间的，这就使其切换时会产生延迟。当一个缓存被切换状态时其他缓存收到消息完成各自的切换并且发出回应消息这么一长串的时间中CPU都会等待所有缓存响应完成。可能出现的阻塞都会导致各种各样的性能问题和稳定性问题。

store Bufferes

为了避免这种CPU运算能力的浪费，Store Bufferes被引入使用。处理器把它想要写入到主存的值写到缓存，然后继续去处理其他事情。当所有失效确认（Invalidate Acknowledge）都接收到时，数据才会最终被提交。

store bufferes风险

  • 就是处理器会尝试从存储缓存（Store buffer）中读取值，但它还没有进行提交。这个的解决方案称为Store Forwarding，它使得加载的时候，如果存储缓存中存在，则进行返回。

  • 保存什么时候会完成，这个并没有任何保证。

    硬件内存模型

    执行失效也不是一个简单的操作，它需要处理器去处理。另外，存储缓存（Store Buffers）并不是无穷大的，所以处理器有时需要等待失效确认的返回。这两个操作都会使得性能大幅降低。为了应付这种情况，引入了失效队列。它们的约定如下：

  • 对于所有的收到的Invalidate请求，Invalidate Acknowlege消息必须立刻发送

  • Invalidate并不真正执行，而是被放在一个特殊的队列中，在方便的时候才会去执行。
  • 处理器不会发送任何消息给所处理的缓存条目，直到它处理Invalidate。

即便是这样处理器已然不知道什么时候优化是允许的，而什么时候并不允许。
干脆处理器将这个任务丢给了写代码的人。这就是内存屏障（Memory Barriers）。
写屏障 Store Memory Barrier(a.k.a. ST, SMB, smp_wmb)是一条告诉处理器在执行这之后的指令之前，应用所有已经在存储缓存（store buffer）中的保存的指令。
读屏障Load Memory Barrier (a.k.a. LD, RMB, smp_rmb)是一条告诉处理器在执行任何的加载前，先应用所有已经在失效队列中的失效操作的指令。
image.png