一致性整体抽象

coherence protocol是通过保证如下的两点invariants，来实现一致性的；

• SWMR invariant, 对于任何一个地址，任何时刻，都只会有一个core写，可能会有多个core读；
• Data-value invariant， 当前读到的数据，是上一次写入的数据；

        为了实现这些变量，我们将一个存储系统（cache/llc/memory）和一个coherence controller(状态机)关联在一起；这些存储系统和状态机，构成了一个分布式系统，在这个系统中controller之间互相交换信息，确保每个地址都保证了SWMR和data-value invariant;

状态机之间，交换什么信息，是由一致性协议决定的；

如上图所示，coherence controller主要由如下几个职责：

• 在core这一侧：
  • 接收core的loads和store指令；
  • 返回load的value to core；
  • 如果load/store产生了cache miss， 则cache controller会发送一致性请求，来获取改访问地址的读写权限；
  • 这个一致性请求，会通过interconnect发往一个或者多个cache controller；
  • 具体发送的什么一致性请求，以及怎样会响应，这个是根据采用什么一致性协议决定的；
• 在network side：
  • 每个cache controller通过interconnection network与其他controller进行通信；
  • 每个controller接收一致性请求，返回一致性响应；

        memory处的coherence controller， 称之为memory controller；这个memory controller一侧与interconnection Network交互，一侧与memory交互；其是被动的一个组件，只能接收请求，返回响应；

        至于状态机，这个对每一个cacheline都有一个独立的状态机，根据一致性请求，跳转不同的状态；

一致性协议设计空间概述

        文章中的比较简单的，用于举例的一致性我们就直接跳过了，直接讲常用的一致性协议是从哪些方面考虑问题的；

        一致性协议，主要从states, transactions, events, transitions 4个方面来考虑；

STATE

        

• STABLE STATES

        在一个单核系统中，cacheline的状态只有valid和invalid, 在此基础上，我们可以加上dirty的标志，用于标志当前这个数据相较于memory中的数据而言，是否是新的。例如，对于write-back的L1 Cache, 其中的dirty cacheline就表示它的值比L2 cache的数据更新；

        在多个参与者的系统中，我们也可以只是用这两三个状态，但是这样的效率太低，我们通常需要区分不同类型的valid状态；例如，我们用如下4个状态，其中，exclusive和ownership是多核系统所独有的；

1. Validity， 表示拥有该地址的数据，可以读，但是如果想要写的话，还需要拥有exclusive的状态；
2. dirtiness，表示当前这个controller的数据是最新的，他需要负责最后将这个数据写入到memory中；
3. exclusivity, 表示整个系统中，只有它有这个cacheline的copy, 其他人都没有；
4. Ownership, 标记为owner的cache controller， 需要响应其他核发送过来的一致性请求。在大多数的一致性协议中，某个cacheline在系统中只能由一个controller是ownership的。拥有O态的cacheline, 最好不要因为空间不够而被evict;

        在这里，我们先讨论一些比较稳定的，常用的状态，后面我们还会讲下，基于这些状态，而时刻不同产生的瞬间状态；

        许多一致性协议，都是用经典的MOESI模型中的一些子状态，MSI是其中最基本的状态, O态和E态是可选的；

• M(odify): 当前cacheline是valid的，exclusive的，owned的，其数据可能是dirty的（为什么是可能？我觉得因为core可以直接修改状态）。整个系统中，只有这个controller有该cacheline, 因此，它要负责响应其他核发送的一致性请求；
• S(hared): 当前cacheline是valid的，但是不是exclusive的，也不是dirty的，更不是owned的。这个cacheline只是read-only的一个copy。 其他cache可能也有S态的该条cacheline;
• I(nvalid)： invalid；

        在MSI的基础上，增加O/E态，是可以做很多优化的，这写优化，我们在描述snooping /directory protocols时再描述，此处我们仅描述完整的状态；

• O(wned): 当前cacheline是valid的，owned, 数据可能是dirty的（可能的原因同上），但不是exclusive的，也就是说，其他的cache可能也有该cacheline, 但是它们中的cacheline都是read-only的copy; 当前这个cache, 需要负责处理所有的一致性请求；
• E(xclusive)： 当前cacheline是valid， exclusive， clean的。当前cache有该cacheline的read-only copy。其他cache是没有该cacheline的，当前cache中的数据，与memory中的数据，是保持一致的。

        

        MOESI状态的venn diagram如上图所示，从图中，我们可以清晰的看到各个状态之间的关系：

• All states besides I are valid
• M, O, and E are ownership states.
• Both M and E denote exclusivity, in that no other caches have a valid copy of the block.
• Both M and Oindicate that the block is potentially dirty.

• Transient State

        到目前为止，我们只讨论了当cacheline没有当前一致性活动时出现的稳定状态，并且在提到协议（例如，“具有 MESI 协议的系统”）时仅使用这些稳定状态。但是，当从一种稳定状态，跳转到另外一种稳定状态时，可能会存在瞬间状态；

        我们用XYz表示当前正在从X状态转换成Y状态，z表示促发这个转换完成的事件；例如，IMd，表示一个cacheline之前是I态，一旦data到来，将变为M态；

• LLC/Memory state

       之前我们只讨论了cache中的stable state, 实际上，在LLC/Memory中，也有对应的状态描述；但是在这一侧，状态的描述需要看站在谁的角度；

         a. 站在cache的角度

        在我们认为最常见的这种方法中，LLC 和内存中的块状态是缓存中该块状态的聚合。 例如，如果一个块在所有缓存中都处于 I 状态，则该块的 LLC/内存状态为 I。如果一个块在一个或多个缓存中处于 S 状态，则 LLC/内存状态为 S。如果一个块在单个缓存中处于 M 状态，则 LLC/内存状态为 M。

         b. 站在memory的角度

        在这种方法中，LLC/内存中块的状态对应于内存控制器对该块的权限（而不是缓存的权限）。例如，如果一个块在所有缓存中都处于 I 状态，则该块的 LLC/内存状态为 O（不是 I，如在以缓存为中心的方法中那样），因为 LLC/内存的行为类似于该块的所有者。如果一个块在一个或多个缓存中处于 S 状态，则 LLC/内存状态也是 O，出于同样的原因。但是，如果一个块在单个缓存中处于 M 或 O 状态，则 LLC/内存状态为 I，因为 LLC/内存有该块的无效副本。

• Maintaining Block State

        整个系统必须维护cache/llc/memory之间的cacheline状态转换；

        对于cache和LLC而言，只需要增加几个bit用于表示各个状态。coherence protocol可能会有更多的瞬间状态，but need maintain these states only for those blocks that have pending coherence transactions.实现层面，为了维护这些瞬间状态，是通过往MSHR（或者其他相似的结构）中增加一些状态bit，来跟踪这些pending的transaction;

        对于memory, 更大的总容量似乎会带来重大挑战。 然而，许多当前的多核系统维护一个 inclusive LLC，这意味着 LLC 维护缓存在系统中任何位置的每个块的副本（甚至是“独占”块）。 使用 inclusive LLC，内存不需要明确表示一致性状态。 如果一个块驻留在 LLC 中，则它在内存中的状态与它在 LLC 中的状态相同。 如果块不在 LLC 中，则其在内存中的状态隐含无效，因为 inclusive LLC 的缺失意味着该块不在任何缓存中。

TRANSACTIONS

       大多数协议都有一组相似的transaction，因为coherence-controller的基本目标是相似的。 例如，几乎所有协议都有一个transaction来获得对cacheline的shared（read-only）access。 在表 6.4 中，我们列出了一组常见transaction，并且对于每个transaction，我们描述了发起transaction的请求者的目标。 这些transaction都是由响应来自其相关core的请求的coherence-controller发起的。 在表 6.5 中，我们列出了core可以向其coherence-controller发出的请求，以及这些core请求如何引导coherence-controller启动一致性事务。

     

   虽然大多数的一致性协议，transaction是相似的，但是coherence controller之间如何进行交互，以及controller如何处理这些transaction, 还是很不一样的；

• snooping protocols中，cache controller通过向系统中的所有cache controller广播 GetS 请求来启动 GetS 事务，并且当前是cacheline所有者的controller响应带有包含所需数据的消息给请求者。 相反，
• directory protocols中，cache controller通过向特定的预定义cache controller发送单播 GetS 消息来启动 GetS 事务，该控制器可以直接响应，也可以将请求转发到将响应的另一个coherence controller给请求者。

    

 

MAJOR PROTOCOL DESIGN OPTIONS

       有许多种方式可以设计一个一致性协议。即使是states和transaction相同，也可能实现不同的协议。 协议的设计决定了每个cache controller上可能发生的event和transition； 与state和transaction不同，没有办法提供独立于协议的可能event或transition的列表。

        尽管一致性协议有巨大的设计空间，但有两个主要的设计决策会对协议的其余部分产生重大影响，我们接下来将讨论它们。 

Snooping vs. Directory

        snooping和directory是两类经典的一致性协议。这里我们简单对比一下两者的主要特点和区别；

•  snooping protocol

        此种方式的主要特点是，cache controller通过向all other coherence controllers广播请求消息来发起对cacheline的请求，然后每个coherence controller各自做正确的事情。

        例如，如果有人是该cacheline的ownner, 则它就需要返回data response；snooping protocol依赖于interconnect将关播请求按照"一定的顺序"发送到其他的core, 大多数的snoop协议，都假定请求是按照顺序到达的，但是更宽松的顺序也是可以实现的；

• Directory protocol

        此种方式的特点是，通过将cacheline requeset 单播到作为该块所在的memory controller来发起对块的请求。memory controller维护一个目录，该目录保存有关 LLC/内存中每个块的状态，例如当前所有者的身份或当前共享者的身份。 当对块的请求到达该home节点时，memory controller会查找该块的目录状态。

         例如，如果请求是 GetS，则memory controller查找目录状态以确定owner是谁。 如果 LLC/内存是所有者，则memory controller通过向请求者发送数据响应来完成事务。 如果cache controller是owner，则memory controller将请求转发给owner cache； 当owner cache接收到转发的请求时，它通过向请求者发送数据响应来完成事务。

        监听与目录的选择涉及权衡取舍。 snoop协议在逻辑上很简单，但它们无法扩展到大量内核，因为广播无法扩展。directory协议是可扩展的，因为它们是单播的，但许多事务需要更多时间，因为当 home 不是所有者时，它们需要发送额外的消息。 此外，协议的选择会影响互连网络（例如，经典的监听协议需要请求消息的总顺序）。

invalidate vs. update

        另一个design需要在coherence protocol中考虑的点是，当core将数据写入cacheline时，需要做什么，这个实现独立于snoop or directory, 也有两种实现方式；

• Invalidate protocol

        当某个核想要将数据写入某条cacheline时，他会发起coherence transaction, 将其他cache的该cacheline的copy全部invalid。 

        一旦副本失效，请求者就可以写入块，而另一个core不可能读取块的旧值。 如果另一个core希望在其副本失效后读取该块，它必须启动一个新的一致性事务来获取该块，并且它将从修改它的core的cache中获得一个副本，从而保持一致性。

• Update protocol

        当某个核想要将数据写入某条cacheline时，它会发起coherence transaction来更新所有其他cache中，该cacheline的数据，使所有人都看到它刚刚写入的新的数据；

        同样的，在做出这个决定时需要权衡取舍。 Update protocol减少了core读取新写入块的延迟，因为core不需要启动并等待 GetS 事务完成。 但是，Update protocol通常比Invalidate protocol消耗更多的带宽，因为更新消息大于无效消息（地址和新值，而不仅仅是地址）。 此外，Update protocol使许多memory consistency model的实现变得非常复杂。 例如，当多个cache必须对一个块的多个副本应用多个更新时，保持写入原子性（第 5.5 节）变得更加困难。 由于Update protocol的复杂性，它们很少被实现； 在本入门书中，我们将重点介绍更为常见的无效协议。