CPU Cache原理与示例 (3)

CPU Cache原理与示例

因为 Directory 协议是一个中心式的,会有性能瓶颈,会增加整体设计的复杂度。而 Snoopy 协议更像是微服务+消息通讯,所以,现在基本都是使用 Snoopy 的总线的设计。

在分布式系统中一般用 Paxos/Raft 这样的分布式一致性的算法。

在 CPU 的微观世界里,不必使用这样的算法,因为 CPU 的多个核的硬件不必考虑网络会断会延迟的问题。所以,CPU 的多核心缓存间的同步的核心,就是要管理好数据的状态。

这里介绍几个状态协议,先从最简单的开始,MESI 协议,这个协议跟那个著名的足球运动员梅西没什么关系,其主要表示缓存数据有四个状态:Modified(已修改), Exclusive(独占的),Shared(共享的),Invalid(无效的)。

这些状态的状态机如下所示(这个图就是想告诉状态控制有多复杂):

CPU Cache原理与示例

下面是个示例(如果想看一下动画演示的话,这里有一个网页(MESI Interactive Animations),可以进行交互操作,这个动画演示中使用的 Write Through 算法):

MESI 这种协议在数据更新后,会标记其它共享的 CPU 缓存的数据拷贝为 Invalid 状态,然后当其它 CPU 再次read 的时候,就会出现 cache miss 的问题,再从内存中更新数据,意味着 20 倍速度的降低。

能不能直接从隔壁的 CPU 缓存中更新?可以,这就可以增加很多速度了,但是状态控制也就变麻烦了。需要多来一个状态:Owner(宿主),用于标记,更新数据源。出现了 MOESI 协议

MOESI 协议的状态机和演示示例就不写了(有兴趣可以上Berkeley上看看相关的课件),只需要理解MOESI协议允许 CPU Cache 间同步数据,降低了对内存的操作,性能是非常大的提升,但是控制逻辑也非常复杂。

与 MOESI 协议类似的一个协议是 MESIF,其中的 F 是 Forward,同样是把更新过的数据转发给别的 CPU Cache。但是,MOESI 中的 Owner 状态 和MESIF 中的 Forward 状态有一个非常大的不一样——Owner 状态下的数据是 dirty 的,没有写回内存,Forward 状态下的数据是 clean的,可以丢弃,不用另行通知

需要说明的是,AMD 用 MOESI,Intel 用 MESIF。F 状态主要是针对 CPU L3 Cache 设计的(L3 是所有 CPU 核心共享的)。

程序性能

看一下对于程序的影响。

示例一

首先,假设有一个64M长的数组,设想一下下面的两个循环:

const int LEN = 64*1024*1024;

int *arr = new int[LEN];

for (int i = 0; i < LEN; i += 2)

arr[i] *= i;

for (int i = 0; i < LEN; i += 8)
arr[i] *= i;

按想法来看,第二个循环要比第一个循环少4倍的计算量,其应该也是要快4倍的。但实际跑下来并不是,在机器上,第一个循环需要 127 毫秒,第二个循环则需要 121 毫秒,相差无几

这里最主要的原因就是 Cache Line,因为 CPU 会以一个 Cache Line 64Bytes 最小时单位加载,也就是 16 个 32bits 的整型,所以,无论步长是 2 还是 8,都差不多。后面的乘法其实是不耗 CPU 时间的。

示例二

再来看一个与缓存命中率有关的代码,以一定的步长increment 来访问一个连续的数组。

for (int i = 0; i < 10000000; i++)

{

for (int j = 0; j < size; j += increment)

{

memory[j] += j;

}

}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgypyx.html