多核系统内存一致性和cache一致性入门教程(连载：第六章 Cache一致性协议)
2012-11-11 21:01阅读：
新浪博客
第六章
在这一章，我们将回到在第二章中介绍的cache一致性这个话题。为了理解cache一致性在支持内存一致性在支持内存一致性中的作用，我们在第二章定义了cache一致性的概念，但是我们没有深入的说明cache一致性协议是如果工作的以及是如何实现的。这章我们将从一般意义上讨论cache一致性，在下面的两章中，我们将进一步讲述两种特定类型的协议。我们从6.1章开始，这一章中我们将展示cache一致性协议如何的实现的全景图，接着在6.2节，我们将说明如何详细描述这些协议，在6.3节中我们将展示一个简单的、明确的一致性协议的例子，在 6.4pan >节中，我们将探索一下协议的设计空间。
1、单个写操作者、多个读操作者（Single-Writer,Multiple-Reader，SWMR）不变式。对于任何一个给定的内存A，在任何一个给定的时间内，只有一个core可以对A进行写操作（该core同时也可以进行读取操作）或者任意多个core可以仅仅进行读操作；
2、值不变式（Date-Value Invariant）。对于一个给你的内存单元，该内存单元的值在一个阶段开始的时候的值和这个内存单元的上一次读写阶段结束的时候的值相同。
为了实现好这些不变式，我们将每个存储单元——每个cache和LLC/内存——和一个被称为控制器的有限状态机相关联。这些一致性控制器的集合构成了一个分布式系统。在这个系统中，控制器们彼此交换数据来保证对于每个块而言，SWMR和值不变式在所有时间都可以维持。这些状态机之间的相互作用详细定义了cache一致性协议。
一致性协议有很多职责。Cache中的一致性控制器我们称之为cache控制器。如图6.1所示。Cache控制器必须同时向两个请求的源头提供服务。在core这一侧，cache控制器和core连接。Cache控制器从core接收load和store请求并且向core返回读取的内容。Cache miss导致控制器通过发出一致性请求（比如，只读许可的请求）来启动一次一致性事务，这个请求包含了core访问的内存地址所在的块。这个一致性请求被通过互联网络发送到一个或者更多的一致性控制器。一次事务包括一个请求和其他为了满足该请求而进行交换的消息（比如，从其他一致性控制器发送到请求者的数据应答消息）。传输的类型和作为每个事务的一部分而发送的消息类型取决于一致性协议的具体实现。
图6.1 cache控制器
在cache控制器的网络侧，cache控制器通过互联网络和系统的其他部分互联在一起。控制器接收它必须处理的一致性请求和一致性应答。和core侧相同，对于接收到的一致性消息的处理取决于协议的具体实现。
在LLC/memory上的控制器，我们称之为内存控制器，如图6.2中介绍。内存控制和cache控制器类似，除了内存控制只有网路侧的接口。这样，它就不能发起一致性请求（代表load和store）或者接受一致性应答。其他代码，比如IO设备，的行为可以和cache控制器的行为相同，也可以和内存控制器的行为相同，或者上述二者的行为，这取决于系统的具体需求。
每一个一致性控制器都实现了一个有限状态机并且根据当前块的状态接收和处理事件（比如，接收的一致性消息），从逻辑上讲这些状态机是独立的，但是每个块的状态机是相同的。对于一个block为B类型为E的事件（比如，从core到cache控制器的store请求），一致性控制器采取的动作（比如，为了获取读写权限而发送的请求）是E和B的状态的函数。在采取了上述这些动作之后，控制器可能会改变B的状态。
为了简单起见，表格6.1中的例子是故意不完整的，但是它展示了为了捕获一致性控制的行为而引入的表格描述方法。为了描述一致性协议，我们只需要完整的描述cache控制器和内存控制器的表格。
表6.1
详细描述的表格化描述方法。这是一个cache一致性控制器的不完整的详细描述。表格中的每个单元指定了要采取的措施和该block的下一个状态。
一致性协议的不同取决于控制器的详细描述的不同。这个不同包括一个block的状态的集合、事务、时间和状态变迁。在6.4节，我们通过探索这些方面的每个选项来描述一致性协议的设计空间，但是，我们先介绍一个简单的、明确的协议。
每个cache块可以处于两个一致性状态中的一个：I（无效状态）和V（有效状态）。在LLC/内存中的每个块也可能处于两个一致性状态中的一个：I和V。在LLC/内存中状态I表示所有cache以I状态保存该block，状态V表示一个cache以V状态保存这个block。同时也存在单一的中间状态，IVD ，该状态将在下面讨论。当系统启动后，所有的cache块和LLC/内存块处于I状态。每个core可以向自己的cache控制器发起load和store请求；当需要为另一个块腾出空间的时候，cache控制器将会产生一个替换块（Evict Block）事件。由于load和store产生的cache miss将发起cache一致性事务，依此来获得该cache块的有效拷贝，具体细节将在下面讨论。和本书中的所有协议一样，我们假定一个回写的cache，也就是说，当一个写操作在cache中命中，会将需要写入的内容仅仅保存在（本地）cache中，并且直到cache替换事件的应答过程中才将整个cache块写入LLC/内存中。
有两种类型的一致性事务，这些一致性事务使用三种类型的总线消息实现：Get消息用于请求一个数据块，DataResp用于传输块存储的数据和put用于将block中的数据写入内存控制器。在load和store引起的cache miss的情况下，cache控制器通过发送Get消息和等待Get消息对应的DataResp消息出现在总线上的方式Get事务。在cache替换事件处理过程中，cache控制器向内存控制器发送一个带有完整数据块的Put消息。
我们在表6.3中描述在稳定的一致性状态之间的事务。我们使用“Own”和“Other”两个前缀来区分事务是由一个给定的cache控制器还是来至于其他cache控制器。需要注意的是，如果一个给定的cache控制器拥有一个处于V状态的block，另一个cache控制器通过Get消息（标注为Other-Get），用于数据块的cache必须（使用DateResp消息，这里没有显示）对该消息进行应答并且将自己的状态转换为I。
表6.2和6.3更为详细的描述了这些协议。表格中带有阴影的单元表示不可能的事务。例如，对于一个在cache中处于V状态的cache块，cache控制器在总线上永远也不应该看到来自自己的类型为put的请求（因为，它应该已经变迁到了I状态）。
图6.3： 在cache控制器中稳定状态之间的状态变迁。
中间状态IVD对应于一个处于I状态、在变迁到V状态之前正在等待数据（通过DataResp消息）的状态。中间状态出现在两个稳定的状态的变迁过程不是原子的情况。在这个简单的协议中，独立的消息的发送和接收都是原子的，但是从内存控制器取一个block的数据需要发送Get消息和接收DataResp消息，在两个消息之间存在一个间隔。IVD状态表明协议正在等待DataResp消息。我们将在6.4.1节中更为深入的讨论中间状态。
这个协议在很多地方是经过简化的并且低效的，但是展示这个协议的目的是理解如何描述协议。我们将在本书中使用这种方法描述不同类型的cache一致性协议。
表格6.2： cache控制的详细描述。表格中带阴影的单元表示不可能的状态，空白的单元表示这个事件将被忽略。
表格6.3： 内存控制的详细描述
[1] 译者注：对于一个支持共享多主总线（在我们的系统模型中，每个cache控制器和LLC/内存控制器都是一个主设备）而言，系统中必须提供总线仲裁器，当系统中的某个主设备想要获取总线，需要先向总线仲裁器发起请求，待仲裁器发起应答请求后，该主设备才可以使用总线，只要该设备不释放总线，其他设备就无法获取总线，这样也就保证了共享总线上的事务的原子属性。如果一个主设备向仲裁器发起请求，而此时总线正在被其他主设备占用，该主设备只能处于等待状态。当多个主设备同时想仲裁器发起请求，总线仲裁器需要使用仲裁算法对于所有请求进行仲裁，最终保证只有一个主设备获取中线，其他主设备必须处于等待状态，这样共享总线也就具有了全局顺序的属性。在wishbone总线中，系统使用CYC_O/CYC_I信号申请总线的使用权，使用GNT_O/GNT_I信号作为主设备是否获得总线的应答信号。
6.1 全景图
Cache一致性协议的目的是通过保持2.3节中介绍的不变式来维持cache一致性，这里在重新陈述一下：1、单个写操作者、多个读操作者（Single-Writer,Multiple-Reader，SWMR）不变式。对于任何一个给定的内存A，在任何一个给定的时间内，只有一个core可以对A进行写操作（该core同时也可以进行读取操作）或者任意多个core可以仅仅进行读操作；
2、值不变式（Date-Value Invariant）。对于一个给你的内存单元，该内存单元的值在一个阶段开始的时候的值和这个内存单元的上一次读写阶段结束的时候的值相同。
为了实现好这些不变式，我们将每个存储单元——每个cache和LLC/内存——和一个被称为控制器的有限状态机相关联。这些一致性控制器的集合构成了一个分布式系统。在这个系统中，控制器们彼此交换数据来保证对于每个块而言，SWMR和值不变式在所有时间都可以维持。这些状态机之间的相互作用详细定义了cache一致性协议。
一致性协议有很多职责。Cache中的一致性控制器我们称之为cache控制器。如图6.1所示。Cache控制器必须同时向两个请求的源头提供服务。在core这一侧，cache控制器和core连接。Cache控制器从core接收load和store请求并且向core返回读取的内容。Cache miss导致控制器通过发出一致性请求（比如，只读许可的请求）来启动一次一致性事务，这个请求包含了core访问的内存地址所在的块。这个一致性请求被通过互联网络发送到一个或者更多的一致性控制器。一次事务包括一个请求和其他为了满足该请求而进行交换的消息（比如，从其他一致性控制器发送到请求者的数据应答消息）。传输的类型和作为每个事务的一部分而发送的消息类型取决于一致性协议的具体实现。
图6.1 cache控制器
在cache控制器的网络侧，cache控制器通过互联网络和系统的其他部分互联在一起。控制器接收它必须处理的一致性请求和一致性应答。和core侧相同，对于接收到的一致性消息的处理取决于协议的具体实现。
在LLC/memory上的控制器，我们称之为内存控制器，如图6.2中介绍。内存控制和cache控制器类似，除了内存控制只有网路侧的接口。这样，它就不能发起一致性请求（代表load和store）或者接受一致性应答。其他代码，比如IO设备，的行为可以和cache控制器的行为相同，也可以和内存控制器的行为相同，或者上述二者的行为，这取决于系统的具体需求。
每一个一致性控制器都实现了一个有限状态机并且根据当前块的状态接收和处理事件（比如，接收的一致性消息），从逻辑上讲这些状态机是独立的，但是每个块的状态机是相同的。对于一个block为B类型为E的事件（比如，从core到cache控制器的store请求），一致性控制器采取的动作（比如，为了获取读写权限而发送的请求）是E和B的状态的函数。在采取了上述这些动作之后，控制器可能会改变B的状态。
6.2 一致性协议的描述方式
我们通过详细描述一致性控制的方式来描述一致性协议。我们有很多种方式来描述控制器，但是为了特定的一致性控制器的行为，出现了表格方式的描述方式。如表6.1所示，我们可以使用一个表格描述控制器，这个表格的行对应于block的状态，列对应于事件。我们使用“状态/事件”这种描述方式表格中每个单元所代表的状态变迁，对于block B对于事件E的状态变迁包括了两部分：（a）当E发生的时候采取的动作，（b）block B的下一个状态。我们使用“动作/下一个状态”的方式来描述状态的变迁。以表格6.1所示的状态变迁为例，如果从core接收到一个对于block B的store请求，并且block B处于只读状态，这样表格显示控制器的状态变迁将是采取如下操作：（a）[对BLOCK B]发送获取读写请求的一致性请求；将block B的状态变迁到RW。为了简单起见，表格6.1中的例子是故意不完整的，但是它展示了为了捕获一致性控制的行为而引入的表格描述方法。为了描述一致性协议，我们只需要完整的描述cache控制器和内存控制器的表格。
| 事件 |
||||
| 来自core的load请求 |
来自core的store请求 |
获得块的读写状态的一致性请求 |
||
| 状态 |
不可读也不可写（N） |
发送获取只读权限的一致性请求/RO |
发送获取读写权限的一致性请求/RW |
<没有动作> |
| 只读（RO） |
从cache中返回数据给core |
发送获取读写权限的一致性请求/RW |
<没有动作>/N |
|
| 可读写（RW） |
从cache中返回数据给core/RO |
向cache中写入数据 |
将block中数据发送到请求者/N |
|
一致性协议的不同取决于控制器的详细描述的不同。这个不同包括一个block的状态的集合、事务、时间和状态变迁。在6.4节，我们通过探索这些方面的每个选项来描述一致性协议的设计空间，但是，我们先介绍一个简单的、明确的协议。
6.3 简单的一致性协议的例子
为了便于理解一致性协议，我们先描述一个简单的协议。我们的系统模型是2.1节中描述的基线系统，但是，我们将互联网络限制为共享总线：一组共享的线，这样每个core可以发送消息，同时所有的core和LLC/内存控制器都可以观察到这个请求。 [1]每个cache块可以处于两个一致性状态中的一个：I（无效状态）和V（有效状态）。在LLC/内存中的每个块也可能处于两个一致性状态中的一个：I和V。在LLC/内存中状态I表示所有cache以I状态保存该block，状态V表示一个cache以V状态保存这个block。同时也存在单一的中间状态，IVD ，该状态将在下面讨论。当系统启动后，所有的cache块和LLC/内存块处于I状态。每个core可以向自己的cache控制器发起load和store请求；当需要为另一个块腾出空间的时候，cache控制器将会产生一个替换块（Evict Block）事件。由于load和store产生的cache miss将发起cache一致性事务，依此来获得该cache块的有效拷贝，具体细节将在下面讨论。和本书中的所有协议一样，我们假定一个回写的cache，也就是说，当一个写操作在cache中命中，会将需要写入的内容仅仅保存在（本地）cache中，并且直到cache替换事件的应答过程中才将整个cache块写入LLC/内存中。
有两种类型的一致性事务，这些一致性事务使用三种类型的总线消息实现：Get消息用于请求一个数据块，DataResp用于传输块存储的数据和put用于将block中的数据写入内存控制器。在load和store引起的cache miss的情况下，cache控制器通过发送Get消息和等待Get消息对应的DataResp消息出现在总线上的方式Get事务。在cache替换事件处理过程中，cache控制器向内存控制器发送一个带有完整数据块的Put消息。
我们在表6.3中描述在稳定的一致性状态之间的事务。我们使用“Own”和“Other”两个前缀来区分事务是由一个给定的cache控制器还是来至于其他cache控制器。需要注意的是，如果一个给定的cache控制器拥有一个处于V状态的block，另一个cache控制器通过Get消息（标注为Other-Get），用于数据块的cache必须（使用DateResp消息，这里没有显示）对该消息进行应答并且将自己的状态转换为I。
表6.2和6.3更为详细的描述了这些协议。表格中带有阴影的单元表示不可能的事务。例如，对于一个在cache中处于V状态的cache块，cache控制器在总线上永远也不应该看到来自自己的类型为put的请求（因为，它应该已经变迁到了I状态）。
图6.3： 在cache控制器中稳定状态之间的状态变迁。
中间状态IVD对应于一个处于I状态、在变迁到V状态之前正在等待数据（通过DataResp消息）的状态。中间状态出现在两个稳定的状态的变迁过程不是原子的情况。在这个简单的协议中，独立的消息的发送和接收都是原子的，但是从内存控制器取一个block的数据需要发送Get消息和接收DataResp消息，在两个消息之间存在一个间隔。IVD状态表明协议正在等待DataResp消息。我们将在6.4.1节中更为深入的讨论中间状态。
这个协议在很多地方是经过简化的并且低效的，但是展示这个协议的目的是理解如何描述协议。我们将在本书中使用这种方法描述不同类型的cache一致性协议。
|
来自CPU的事件 |
来自总线的事件 |
|||||||
|
自己事务的消息 |
来自其他核的事务的消息 |
|||||||
| Load或store |
替换block |
Own-Get |
Own-Get的DataResp |
Own-Put |
Other-Get |
Other-Get的DataResp |
Other-Put |
|
| I |
发送Get消息/ IVD |
|||||||
| IVD |
暂停load和store操作 |
暂停替换 |
拷贝数据到cache中，执行load或store操作 |
|||||
| V |
执行load和store操作 |
发送Put消息（带数据）/I |
发送DataResp消息/I |
|||||
| 状态 |
总线事件 |
|
| Get |
Put |
|
| I |
向请求者发送在DataResp消息中的数据块/V |
|
| V |
更新内存中的block/I |
|
[1] 译者注：对于一个支持共享多主总线（在我们的系统模型中，每个cache控制器和LLC/内存控制器都是一个主设备）而言，系统中必须提供总线仲裁器，当系统中的某个主设备想要获取总线，需要先向总线仲裁器发起请求，待仲裁器发起应答请求后，该主设备才可以使用总线，只要该设备不释放总线，其他设备就无法获取总线，这样也就保证了共享总线上的事务的原子属性。如果一个主设备向仲裁器发起请求，而此时总线正在被其他主设备占用，该主设备只能处于等待状态。当多个主设备同时想仲裁器发起请求，总线仲裁器需要使用仲裁算法对于所有请求进行仲裁，最终保证只有一个主设备获取中线，其他主设备必须处于等待状态，这样共享总线也就具有了全局顺序的属性。在wishbone总线中，系统使用CYC_O/CYC_I信号申请总线的使用权，使用GNT_O/GNT_I信号作为主设备是否获得总线的应答信号。