[关闭]
@JunQiu 2020-12-10T10:22:44.000000Z 字数 2673 阅读 176

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

pocc(计组) summary_2020/10


一、多级缓存

1、背景

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

2、结构

image_1ekitahhn1tq91een1q3935c1eep42.png-16.4kB

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):缓存存储数据的单元。

image_1ekdqtmjqsbd1vgf1agk1kjt1jjv1k.png-18.1kB

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

image_1ekj2vnhh19ok14u412kt19gst4n4f.png-27.3kB

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操作&状态转换

image_1ekj393kf1fgro63o451se41mpi4s.png-199.8kB

例子:
单核读取:
CPU A发出了一条指令,从主内存中读取x。 从主内存通过bus读取到缓存中(远端读取Remote read),此时该Cache line修改为E状态(独享)

image_1ekj4fnhv1v6417vsci0gs4a4b59.png-542.4kB

多核读取:
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状态(共享)。

image_1ekj4kbio9cbaq07uk1c7t12f566.png-572.9kB

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

image_1ekl2g8ctrmd1h8s1fng9u81v3n9.png-107.5kB

1.4、Store Bufferes(存储缓存)

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

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

image_1ekdsn8pgget4f1hmdvo11qv738.png-7.4kB

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注