Toki

小林系统 CPU cache结构、缓存命中、缓存一致性、伪共享

cache 以 cache line 为单位从内存读入数据，一个cache line的大小一般为64B：

一个 int array[15] 大小若为60B，则可一次性全部读入 cache

多个cache line位于同一个 cache set中，用 set index 标记，这被称为组相联缓存结构。

CPU/寄存器以字为单位读取数据，字地址 = tag + index + offset，从而从 cache 中查找到所需的数据：

几种cache结构：直接映射 Cache、全相连 Cache、组相连 Cache

我们希望尽可能多的缓存命中，这要求我们提高程序的局部性，可以从空间局部性和时间局部性两方面下手

spatial locality：CPU更可能访问最近访问数据的周边数据

采用形式1，让同一段时间使用的数据尽可能放在同一个 cache line 中

temporal locality：最近访问的数据可能被再次访问

分支预测器会动态地根据历史命中数据对未来分支进行预测，将对应分支的指令提前加载到指令缓存中。

对于以下这段代码，如果先排序再变0则会在一段时间内重复使用某几条指令，从而提高temporal locality，提高运行速度

实际上，CPU 自身的动态分支预测已经是比较准的了，所以只有当非常确信 CPU 预测的不准，且能够知道实际的概率情况时，才建议使用这两种宏

如果你肯定某个分支执行的概率较大，我们可以用一个宏 likely/unlikely 向编译器暗示：

如果有多个计算密集型线程，每个线程都会使用大量的数据，如果让其中的某个线程在多个CPU间不停的切换，那么势必会对大家的缓存命中率都造成影响，我们可以把某个线程绑定在一个固定的CPU上：

缓存与内存可能出现数据不一致的的情况，为此有两种写策略：

要写的 cache line 发生了 cache miss，fetch 策略会先读到缓存中再写入缓存

多核CPU都有自己的缓存，为了维护这些数据的一致性，在修改缓存时需要同步其他CPU的缓存，进行 Write Propagation 写传播。

它最常见的实现方式是 Bus Snooping 总线嗅探，CPU需要监听总线的一切活动，在写发生时，会将数据广播到其他CPU

而多核CPU如果对同一数据进行了多次写入，还需要保证这些写操作发生的顺序，与传播到其他CPU、被观测到的顺序是一样的，需要进行 Transaction Serialization 事务串行化，利用 MESI 协议保证

MESI 分别指：modified、exclusive、shared、invalidated，这些状态针对单个 cache line

基本原则如下：

当一个数据被读入一个CPU的缓存时，如果其他CPU的缓存中没有这个数据，则进入 exclusive 状态
如果多个CPU的缓存读取了这个数据，则所有读入这个数据的 cache line 进入 shared 状态
在需要写本缓存前，其他shared状态的缓存需要进入 invalidated 状态，本缓存进入 modified 状态；在有其他缓存读写该数据前，需要将数据写入内存，并进入shared或invalidated 状态
invalidated 的缓存需要读写时，需要先从内存读取数据；不关心任何其他缓存的读写
exclusive、modified 状态下的缓存写入无需通知其他CPU
shared、exclusive、modified 状态的数据读取直接从缓存中读取

以上的内存也可以替换为L3缓存