Memory Consistency and Cache Coherence

导言

许多现代计算机系统，包括同构和异构体系结构，都支持硬件中的共享内存。在共享内存系统中，每个处理器内核可以对单个共享地址空间进行读写。

要拓展Victima模拟器的cache部分，首先要明白一些缓存一致性的基础知识。

内存一致性Memory Consistency 和缓存一致性Cache Coherence是并行计算和多处理器系统中的两个重要概念，它们帮助确保系统中多个处理器的操作顺序和数据一致性。这两个概念都是为了解决多处理器环境中的关键问题：如何有效地管理并行操作中的数据访问和修改，以确保程序的正确性和效率。通过适当的内存一致性模型和缓存一致性协议，系统可以有效地协调不同处理器的活动，避免数据冲突和错误的程序行为。

内存一致性¶

内存一致性是指在多处理器系统中，内存的访问顺序如何被处理器观察到。它定义了读和写操作的可见性和顺序，确保系统行为的可预测性。当多个处理器并发访问共享数据时，内存一致性模型将规定一个处理器的写操作如何对其他处理器的读操作变得可见。这是通过一组规则来实现的，这些规则定义了不同处理器对共享数据操作的可见顺序。

内存一致性模型的例子包括：

严格一致性（Strict Consistency）：任何处理器上的写操作立即对所有其他处理器可见。
顺序一致性（Sequential Consistency）：所有处理器看到所有内存操作（读/写）的相同顺序。
松弛一致性模型（Relaxed Consistency Models），如最终一致性、因果一致性等，它们允许更多的灵活性，以提高性能和可伸缩性。

缓存一致性¶

缓存一致性是指在多处理器系统中，每个处理器的缓存中的副本保持数据的一致性。当多个处理器缓存同一内存位置的副本时，系统必须确保对该内存位置的任何修改都能反映到所有处理器的缓存中。这是通过缓存一致性协议来实现的，如前面提到的MSI（Modified, Shared, Invalid）协议。

缓存一致性协议的其他例子包括：

MESI（Modified, Exclusive, Shared, Invalid）：在MSI的基础上增加了一个Exclusive状态，提高了效率。
MOESI（Modified, Owner, Exclusive, Shared, Invalid）：在MESI的基础上增加了一个Owner状态，允许更灵活的数据共享和传输。

缓存一致性协议¶

缓存一致性协议是为了解决多核或多处理器架构中,不同缓存之间的数据一致性问题而设计的协议。常见的缓存一致性协议包括:

基于总线的一致性协议/窥探协议（Bus-based Coherence Protocol / Snooping Coherence Protocols）¶

基于总线的一致性协议也叫做Snooping（窥探）协议是由于它们依赖于对总线或网络上所有缓存一致性相关消息的“窥探”来维持一致性。在这种协议中，处理器通过共享总线进行通信。当一个处理器修改了一个缓存块时，它将在总线上广播该操作，以通知其他处理器使其缓存无效或进行相应的更新。

基于总线的协议的优点:

低延迟的一致性操作：由于操作直接在总线上广播，因此可以快速地更新其他缓存，减少等待时间。
概念上的简单性：与基于目录的协议相比，窥探协议通常更直观，因为它们不需要维护一个中央目录来跟踪哪些缓存拥有某个数据的副本。

然而，它在处理器之间共享总线时可能引入瓶颈，并且对总线带宽有一定的要求。

MSI模型¶

MSI代表一种基本的缓存一致性状态模型，其中包括三种状态：Modified（修改）、Shared（共享）和 Invalid（无效）。这种模型用于确保在多核处理器系统中，多个缓存之间数据的一致性。

Modified (M)：数据已被缓存并且修改过，此时该缓存拥有的数据副本是唯一的且最新的。
Shared (S)：表明数据被缓存在多个地方，且没有被修改。
Invalid (I)：数据在此缓存中是无效的，需要从其他地方重新获取。

MESI协议¶

MESI协议是目前最常见的支持写回策略的缓存一致性协议。缓存行有四种状态:

M(Modified):缓存行被修改,与主存数据不一致,该缓存行的拥有者负责将数据写回主存。
E(Exclusive):缓存行与主存一致,但其他缓存都没有该行的缓存副本。
S(Shared):多个缓存共享该缓存行的副本,与主存一致。
I(Invalid):缓存行无效。

通过无效化、共享、独占状态的转换来保证一致性。

MOESI协议¶

在MESI基础上,增加了Owned状态,表示拥有该缓存行但未修改,其他缓存可共享该行。可以减少 writable line的传输。

在MSI和MESI协议中，如果一个处于状态M的一级缓存收到了来自其它一级缓存的GETS请求，那么它就必须将数据发送给发起请求的一级缓存，同时发送给二级缓存，然后将自身的状态改为S。因为协议要求状态S的缓存行必须是干净的。注意到在此期间从该一级缓存发出了一个包含缓存行数据的回应，发往二级缓存：这个包含数据的昂贵回应能否被避免？要想避免这个回应，我们就需要额外的状态来表示一个缓存行是有效、写脏、只读的，用以区别于状态S的有效、未写脏、只读。

Dragon协议¶

AMD的特色协议,通过向每个缓存行添加时间戳来Detect冲突并进行仲裁。

基于目录的一致性协议（Directory-based Coherence Protocol）¶

基于目录的一致性协议是一种在共享存储系统中用于维护缓存一致性的方法。在这种协议中，有一个称为目录（directory）的数据结构，用于跟踪每个缓存块的状态和所在位置。目录记录了缓存块是否在本地缓存、是否被其他缓存拥有或共享等信息。当一个处理器想要访问某个缓存块时，它首先查询目录以确定当前状态，并根据需要与其他处理器进行通信来维护一致性。

基于目录的协议的一个优点是，它减少了处理器之间的通信量，因为缓存一致性信息存储在目录中，而不是每个缓存中。然而，它引入了额外的访问延迟，因为处理器需要与目录进行通信，以了解缓存块的状态和位置。

这种协议的主要优点是全局目录提供了整个系统缓存状态的全局视图,可以避免不必要的缓存间传输,实现高效的缓存一致性维护。典型的如Firefly缓存一致性协议。

但维护全局目录的开销也非常高,且目录可能成为热点。所以此类协议更适用于NUMA系统。

伪共享问题¶

多核并行时，类似cache写冲突，当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。

避免伪共享¶

伪共享的原理我们知道了，一个缓存行是 64 个字节，一个 long 类型是 8 个字节，所以避免伪共享也很简单，笔者总结了下大概有以下三种方式：

（1）在两个 long 类型的变量之间再加 7 个 long 类型（2）重新创建自己的 long 类型，而不是 java 自带的 long （3）使用 @sun.misc.Contended 注解（java8）

参考文献¶

A Primer on Memory Consistency and Cache Coherence ↩