CPU多级缓存 & 缓存一致性维护协议 MESI

pocc(计组) summary_2020/10

一、多级缓存

1、背景

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

2、结构

3、局部性原理

在CPU访问存储设备时，无论是存取数据抑或存取指令，都趋于聚集在一片连续的区域中，这就被称为局部性原理。

时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。比如循环、递归、方法的反复调用等。

空间局部性（Spatial Locality）：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。比如顺序执行的代码、连续创建的两个对象、数组等。

4、多级缓存引发的问题

cache 给系统带来性能上飞跃的同时，也引入了新的问题“缓存一致性问题”。

多核CPU的情况下存在多个一级缓存，比如coreA、coreB均从主存上读取了变量A=0，此时coreA执行A++,A缓存中的值为1，但此时coreB缓存中变量的值任为0，导致缓存不一致的问题。为此，引入了缓存一致性协议MESI。

二、缓存一致性协议MESI

解决缓存一致性最常见的方案是总线嗅探（Bus Snooping Protocol）。

比如当CPU0修改自己私有的Cache时，硬件就会广播通知到总线上其他所有的CPU。对于每个CPU来说会有特殊的硬件监听广播事件，并检查是否有相同的数据被缓存在自己的CPU，这里是指CPU1。如果CPU1私有Cache已经缓存即将修改的数据，那么CPU1的私有Cache也需要更新对应的cache line。这个过程就称作bus snooping。

Bus Snooping Protocol方法简单，但要需要每时每刻监听总线上的一切活动。我们需要明白的一个问题是不管别的CPU私有Cache是否缓存相同的数据，都需要发出一次广播事件。这在一定程度上加重了总线负载，也增加了读写延迟。

另一种基于总线嗅探机制的MESI协议。一种基于写失效（发生更新的时候对应内存地址缓存失效，不需要传递真实的数据）的缓存一致性协议。写失效的协议的好处是，我们不需要在总线上传输数据内容，而只需要传输操作信号和地址信号就好了，不会那么占总线带宽。

1、基本概念

1.1、缓存行

缓存行（Cache line）:缓存存储数据的单元。

MESI协议将cache line的状态占2bit，分成modify、exclusive、shared、invalid，分别是修改、独占、共享和失效。

1.2、cache操作

MESI协议中，每个cache的控制器不仅知道自己的操作（local read和local write），每个核心的缓存控制器通过监听也知道其他CPU中cache的操作（remote read和remote write），进而确定自己cache中共享数据的状态是否需要调整。

local read（LR）：读本地cache中的数据；
local write（LW）：将数据写到本地cache；
remote read（RR）：其他核心发生read；
remote write（RW）：其他核心发生write；

1.3、cache操作&状态转换

例子：
单核读取：
CPU A发出了一条指令，从主内存中读取x。 从主内存通过bus读取到缓存中（远端读取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进行赋值。

1.4、Store Bufferes（存储缓存）

当你需要修改本地缓存中的一条信息，那么你必须将I（无效）状态通知到其他拥有该数据的CPU缓存中，并且等待确认。等待确认的过程会阻塞处理器，这会降低处理器的性能。这个等待远远比一个指令的执行时间长的多。

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

1、Store Bufferes的影响

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

2、Store Bufferes产生的问题
Store Buffer 的空间也是有限的，如果这样的情况发生的太多，在 cache miss 的情况下会经常有，那么一旦 store buffer 满了，后面的指令依然要像上一文中那样等待？

因此引入了Invalidate Queue, 这个队列会将 Invalidate 消息缓存起来，然后马上给一个 Invalidate Acknowledge 消息，等需要的时候再去处理。

多CPU的情况：Address Bus(地址总线竞争)

1.5、内存屏障（memory barrier）

1.6、MESI模拟工具

https://www.scss.tcd.ie/Jeremy.Jones/VivioJS/caches/MESIHelp.htm

1.7、拓展Directory Protocols

由于 Snooping 依赖基于共享总线的广播和监听，当 CPU 核数大于 8 个以后，共享总线就需要处理更多信号，解决更多冲突，成为瓶颈。因此抛弃广播网络、拥抱点对点网络通信是获得扩展性的前提。失去广播网络后，如何保证对同一个 Block 的写入顺序在各 CPU 核中保持一致，又重新成为难题。

主要原理主要使用分片思想，分而治之，减少信号传输。

三、Reference

• 缓存与存储的一致性策略：从 CPU 到分布式系统
• CPU缓存一致性协议MESI
• 一文解决内存屏障