缓存一致性协议
0. 前言
缓存一致性协议的场景是，多核 CPU 中，每个核心都有自己的缓存，为了保证这些缓存的数据一致，设计了缓存一致性协议。本文内容涵盖MESI协议、MOESI协议、MESIF协议、基于目录的缓存一致性、ACE协议、CHI协议等。
1.理论分析
首先从理论的角度，分析如何设计一个缓存一致性协议。
1.1 Write-invalidate 和 Write-update
b) Write-update：写入数据的时候，把新的结果写入到有这条 Cache Line 的其他 Cache
1.2 MESI 协议
Invalid：不在缓存中
当 Read hit 的时候，状态不变。
当 Read miss 的时候，首先会检查其他缓存的状态，如果有数据，就从其他缓存读取数据，并且都进入 Shared 状态，如果其他缓存处于 Modified 状态，还需要把数据写入内存；如果其他缓存都没有数据，就从内存里读取，然后进入 Exclusive 状态。
当 Write hit 的时候，进入 Modified 状态，同时让其他缓存进入 Invalid 状态。
当 Write miss 的时候，检查其他缓存的状态，如果有数据，就从其他缓存读取，否则从内存读取。然后，其他缓存都进入 Invalid 状态，本地缓存更新数据，进入 Modified 状态。
值得一提的是，Shared 状态不一定表示只有一个缓存有数据：比如本来有两个缓存都是 Shared 状态，然后其中一个因为缓存替换变成了 Invalid，那么另一个是不会收到通知变成 Exclusive 的。Exclusive 的设置是为了减少一些总线请求，比如当数据只有一个核心访问的时候，只有第一次 Read miss 会发送总线请求，之后一直在 Exclusive/Modified 状态中，不需要发送总线请求。
Invalid：不在缓存中
状态中，M 和 E 是独占的，所有缓存里只能有一个。此外，可以同时有多个 S，或者多个 S 加一个 O，但是不能同时有多个 O。
它的状态转移与 MESI 类似，区别在于：当核心写入 Owned 状态的缓存时，有两种方式：1）通知其他 Shared 的缓存更新数据；2）把其他 Shared 缓存设为 Invalid，然后本地缓存进入 Modified 状态。在 Read miss 的时候，则可以从 Owned 缓存读取数据，进入 Shared 状态，而不用写入内存。它相比 MESI 的好处是，减少了写回内存的次数。
Invalid: Invalid
需要注意的是，SharedClean 并不代表它的数据和内存一致，比如说和 SharedDirty 缓存一致，它只是说缓存替换的时候，不需要写回内存。
1.4 MESIF 协议
Forward：同时有多个缓存有这个数据，但是不能修改数据，且这个缓存负责响应请求
MESIF 相比 MESI 的区别是，添加了 Forward 状态：Forward 其实是特殊的 Shared，主要是考虑到有多个缓存处于 Shared 状态的时候，如果来了一个读请求，那么哪个 Shared 缓存负责响应是不确定的。MESIF 协议中，Forward 就是负责响应的那一个 Shared，所以 Forward 最多只有一个，其他 Shared 都不会响应。这样的好处是简化了在片上网络的传输。
如果多个 Cache 属于 Shared 状态，没有 Forward，那么新的 Cache 请求就会发送到内存里，由于 Shared 的数据没有经过修改，所以内存中的数据和 Shared 是一致的。同时，这个新的 Cache 会进入 Forward 状态。
1.5 基于目录的缓存一致性
上面的缓存一致性协议中，经常有这么一个操作：向所有有这个缓存行的缓存发送/接受消息。简单的方法是直接广播，然后接受端自己判断是否处理。但是这个方法在核心很多的时候会导致广播流量太大，因此需要先保存下来哪些缓存会有这个缓存的信息，然后对这些缓存点对点地发送。这样就可以节省一些网络流量。
怎么记录这个信息呢？一个简单的办法（Full bit vector format）是，有一个全局的表，对每个缓存行，都记录一个大小为 N（N 为核心数）的位向量，1 表示对应的核心中有这个缓存行。但这个方法保存数据量太大：缓存行数正比于 N，还要再乘以一次 N，总容量是 \(O(N^2)\) 的。
一个稍微好一些的方法（Coarse bit vector format）是，我把核心分组，比如按照 NUMA 节点进行划分，此时每个缓存行都保存一个大小为 M（M 为 NUMA 数量）的位向量，只要这个 NUMA 节点里有这个缓存行，对应位就取 1。这样相当于是以牺牲一部分流量为代价（NUMA 节点内部广播），来节省一些目录的存储空间。
但实际上，通常情况下，一个缓存行通常只会在很少的核心中保存，所以这里有很大的优化空间。比如说，可以设置一个缓存行同时出现的缓存数量上限（Limited pointer format），然后保存核心的下标而不是位向量，这样的存储空间就是 \(O(N\log_2N)\)。但是呢，这样限制了缓存行同时出现的次数，如果超过了上限，需要替换掉已有的缓存，可能在一些场景下性能会降低。
还有一种方式，就是链表 (Chained directory format)。目录中保存最后一次访问的核心编号，然后每个核心的缓存里，保存了下一个保存了这个缓存行的核心编号，或者表示链表终止。这样存储空间也是 \(O(N\log_2N)\)，不过发送消息的延迟更长，因为要串行遍历一遍，而不能同时发送。类似地，可以用二叉树（Number-balanced binary tree format）来组织：每个缓存保存两个指针，指向左子树和右子树，然后分别遍历，目的还是加快遍历的速度，可以同时发送消息给多个核心。
2. 协议分析
下文结合实际的协议，分析缓存一致性协议是如何在硬件中实现的。
2.1 ACE 协议
Invalid: Invalid
spec中的定义如下：
Valid, Invalid: When valid, the cache line is present in the cache. When invalid, the cache line is not present in the cache. Unique, Shared: When unique, the cache line exists only in one cache. When shared, the cache line might exist in more than one cache, but this is not guaranteed. Clean, Dirty: When clean, the cache does not have responsibility for updating main memory. When dirty, the cache line has been modified with respect to main memory, and this cache must ensure that main memory is eventually updated.
大致理解的话，Unique 表示只有一个缓存有这个缓存行，Shared 表示有可能有多个缓存有这个缓存行；Clean 表示它不负责更新内存，Dirty 表示它负责更新内存。下面的很多操作都是围绕这些状态进行的。
文档中也说，它支持 MOESI 的不同子集：MESI, ESI, MEI, MOESI，所以也许在一个简化的系统里，一些状态可以不存在，实现会有所不同。
换位思考，作为协议的设计者，应该如何添加信号来实现缓存一致性协议？从需求出发，缓存一致性协议需要实现：
读或写 miss 的时候，需要请求这个缓存行的数据，并且更新自己的状态，比如读取到 Shared，写入到 Modified 等。
写入一个 valid && !dirty 的缓存行的时候，需要升级自己的状态，比如从 Shared 到 Modified。
需要 evict 一个 valid && dirty 的缓存行的时候，需要把 dirty 数据写回，并且降级自己的状态，比如 Modified -> Shared/Invalid。如果需要 evict 一个 valid && !dirty 的缓存行，可以选择通知，也可以选择不通知下一级。
收到 snoop 请求的时候，需要返回当前的缓存数据，并且更新状态。
需要一个方法来通知下一级 Cache/Interconnect，告诉它第一和第二步完成了。
首先考虑上面提到的第一件事情：读或写 miss 的时候，需要请求这个缓存行的数据，并且更新自己的状态，比如读取到 Shared，写入到 Modified 等。
AXI 已经有 AR 和 R channel 用于读取数据，那么遇到读或者写 miss 的时候，可以在 AR channel 上捎带一些信息，让下一级的 Interconnect 知道自己的意图是读还是写，然后 Interconnect 就在 R channel 上返回数据。
具体要捎带什么信息呢？“不妨”用这样一种命名方式：操作 + 目的状态，比如读 miss 的时候，需要读取数据，进入 Shared 状态，那就叫 ReadShared；写 miss 的时候，需要读取数据（通常写入缓存的只是一个缓存行的一部分，所以先要把完整的读进来），就叫 ReadUnique。这个操作可以编码到一个信号中，传递给 Interconnect。
再来考虑上面提到的第二件事情：写入一个 valid && !dirty 的缓存行的时候，需要升级自己的状态，比如从 Shared 到 Modified。
这个操作，需要让 Interconnect 把其他缓存中的这个缓存行数据清空，并且把自己升级到 Unique。根据上面的 操作 + 目的状态 的命名方式，可以讲其命名为 CleanUnique，即把其他缓存都 Clean 掉，然后自己变成 Unique。
接下来考虑上面提到的第三件事情：需要 evict 一个 valid && dirty 的缓存行的时候，需要把 dirty 数据写回，并且降级自己的状态，比如 Modified -> Shared/Invalid。
按照前面的 操作 + 目的状态 命名法，可以命名为 WriteBackInvalid。ACE 实际采用的命名是 WriteBack。
第四件事情：收到 snoop 请求的时候，需要返回当前的缓存数据，并且更新状态。
既然 snoop 是从 Interconnect 发给 Master，在已有的 AR R AW W B channel 里没办法做这个事情，不然会打破已有的逻辑。那不得不添加一对 channel：规定一个 AC channel 由 Interconnect 发送 snoop 请求，一个 C channel 让 Master 发送响应。这就相当于 TileLink 里面的 B channel（Probe 请求）和 C channel（ProbeAck 响应）。实际 ACE 和刚才设计的实际有一些区别，把 C channel 拆成了两个：CR 用于返回所有响应，CD 用于返回那些需要数据的响应。这就像 AW 和 W 的关系，一个传地址，一个传数据；类似地，CR 传状态，CD 传数据。
那么 AC channel 上要发送什么请求呢？回顾一下上面已经用到的请求类型：需要 snoop 的有 ReadShared，ReadUnique 和 CleanUnique，不需要 snoop 的有 WriteBack。那么直接通过 AC channel 把 ReadShared，ReadUnique 和 CleanUnique 这三种请求原样发送给需要 snoop 的 Cache 即可。Cache 在 AC channel 收到这些请求的时候，再做相应的动作。
第五件事情：需要一个方法来通知下一级 Cache/Interconnect，告诉它第一和第二步完成了。TileLink 添加了一个额外的 E channel 来做这个事情，ACE 更加粗暴：直接用一对 RACK 和 WACK 信号来分别表示最后一次读和写已经完成。关于 WACK 和 RACK 的讨论，详见 What's the purpose for WACK and RACK for ACE and what's the relationship with WVALID and RVALID? 。
这时候已经基本把 ACE 协议的信号和大体的工作流程推导出来了。从信号上来看，ACE 协议在 AXI 的基础上，添加了三个 channel：
AC: Coherent address channel, Input to master: ACADDR, ACSNOOP, ACPROT
CR: Coherent response channel, Output from master: CRRESP
CD: Coherent data channel, Output from master: CDDATA, CDLAST
ARSNOOP[3:0]/ARBAR[1:0]/ARDOMAIN[1:0] AWSNOOP[3:0]/AWBAR[1:0]/AWDOMAIN[1:0]/AWUNIQUE RRESP[3:2] RACK/WACK
ACE 协议还设计了一个 ACE-Lite 版本：ACE-Lite 只在已有 Channel 上添加了新信号，没有添加新的 Channel。因此它内部不能有 Cache，但是可以访问一致的缓存内容。
2.2 CHI 协议
2.2.1 介绍
CHI 协议是 AMBA 5 标准中的缓存一致性协议，前身是 ACE 协议。最新的 CHI 标准可以从 AMBA 5 CHI Architecture Specification 处下载。
相比 AXI，CHI 更加复杂，进行了分层：协议层，网络层和链路层。因此，CHI 适用于片上网络，支持根据 Node ID 进行路由，而不像 AXI 那样只按照物理地址进行路由。CHI 的地位就相当于 Intel 的环形总线。CHI 也可以桥接到 CCIX 上，用 CCIX 连接 SMP 的的多个 Socket，或者连接支持 CCIX 的显卡等等。
2.2.2 缓存行状态
Invalid: Invalid
UniqueDirty: Modified
UniqueDirtyPartial: 新增，可能有部分字节合法，在写回的时候，需要和下一级缓存或者内存中的合法缓存行内容进行合并
SharedDirty: Owned
UniqueClean: Exclusive
UniqueCleanEmpty: 新增，所有字节都不合法，但是本缓存占有该缓存行，如果要修改的话，不需要通知其他缓存
SharedClean: Shared
Invalid: Invalid
可以看到，比较特别的就是 UniqueDirtyPartial 和 UniqueCleanEmpty。CHI 标准在 4.1.1 章节给出了使用场景：如果一个 CPU 即将要写入一片内存，那么可以先转换到 UniqueCleanEmpty 状态中，把其他缓存中的数据都清空，这样后续写入的时候，不需要询问其他缓存，性能比较好。但此时因为数据还没写进去，所以就是 Empty，只更新状态，不占用缓存的空间。另一方面，如果 CPU 只写了缓存行的一部分字节，其他部分没有碰，那么引入 UniqueDirtyPartial 以后，可以把合并新旧缓存行数据这一步，下放到比较靠近内存的层级上，减少了数据搬运的次数。
2.2.3 CHI 网络节点
Request Node：发起 CHI 请求的节点，对应 CPU 的缓存，或者是网卡等外设 Home Node：管理 Request Node 来的请求，对应最后一级缓存 Subordinate Node：处理 Home Node 来的请求，对应内存或者显存等有内存的外设
在这种设计下，Node 之间可以互相通信，因此方便做一些新的优化。例如传统的缓存层次里，请求是一级一级下去，响应再一级一级上来。但是 CHI 可能是 Request Node 发给 Home Node 的请求，响应直接由 Subordinate Node 发送回 Request Node 了。
2.2.4 读请求
CHI 提供了复杂性的同时，也带来了很多的灵活性，也意味着潜在的性能优化的可能。例如在 CHI 中实现一个读操作，可能有很多种过程（CHI 标准第 2.3.1 章节）：
第二种是 Home Node 把响应拆成两份，一份表示读取结果，一份携带读取的数据（Separate data and response from Home）：
2.2.5 写请求
CHI 标准第 2.3.2 描述了写请求的流程。和读请求一样，写请求也有很多类型，下面进行介绍。与读请求不同的点在于，写入的时候，并不是直接把写入的地址和数据等一次性发送过去，而是先发一个写消息，对方回复可以发送数据了（DBIDResp），再把实际的数据传输过去（NCBWrData）。当然了，也可以中途反悔（WriteDataCancel）。
（全文完）
另外，由于微信群已经超过200人，添加小编的微信，拉你进入WX学习群。
最后的最后，感谢关注微信公众号《芯片验证日记》，我们一起好好学习天天向上！