论文阅读，ProtoGen: Automatically Generating Directory Cache Coherence Protocols（三）
目录
C. An MSI Protocol for an Unordered Network
三、Comments对文献的想法 （强迫自己思考，结合自己的学科）
一、Article:文献出处（方便再次搜索）
（1）作者
- Nicolai Oswald，Vijay Nagarajan(爱丁堡大学)
- Daniel J. Sorin(杜克大学)
（2）文献题目
- ProtoGen: Automatically Generating Directory Cache Coherence Protocols from Atomic Specifications
（3）文献时间
- 2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture（ISCA）
（4）引用
- Oswald N, Nagarajan V, Sorin D J. ProtoGen: Automatically generating directory cache coherence protocols from atomic specifications[C]//2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA). IEEE, 2018: 247-260.
二、Data:文献数据（总结归纳，方便理解）
（1）背景介绍
教科书上的协议只有少量稳定状态，过于简化，无法适用于典型的多核处理器。具体而言，这些协议假设从一个稳定状态到另一个稳定状态的转换是原子的，即转换发生或看起来瞬间发生。只有简单的系统模型（例如核心连接到简单的原子总线和集中式一致性控制器）才能提供这种原子性，而高性能的多核处理器采用多跳互连网络和分布式目录协议。
（2）目的
在为多核处理器设计目录缓存一致性协议时，架构师面临多个挑战：
- 多核协议通常是并发的，这会导致瞬态一致性数量的大大增加。在一致性事务的每个步骤中，除了少数稳定状态，缓存通常会将块的状态更改为反映该步骤的不同瞬态状态。此外，在当前状态和请求状态之间的瞬态状态之外，通常还会由于其他缓存在此时间窗口内发出的一致性请求而产生瞬态状态。
- 在具有数十个状态的典型一致性协议中，架构师很容易犯错误，而这些微妙错误可能严重影响用户。架构师可能会忘记在某个特定状态下块可以接收到的一致性消息；可能会在处理某个特定状态下的块的传入消息时引入错误；可能会未能考虑到可能的情况，导致状态过少。
- 除了这些安全问题之外，协议还可能无法实现其最大性能，因为架构师在过于复杂的情况下可能会保守地限制并发。与其推理如何处理某个特定状态下的块接收到的某个消息，不如简单地将该请求暂停，直到块处于稳定状态。
传统的多核系统模型需要包含许多瞬态状态，从而增加了协议的复杂性。而协议生成的主要挑战，即如何在事务竞争时正确处理传入的一致性消息，关键在于利用目录协议中的事务串行化。
（3）结论
如何在事务竞争时正确处理传入的一致性消息？
通过为每个可以在缓存中达到稳定状态的目录转发请求分配唯一名称，ProtoGen使得目录能够将这个串行顺序传达给缓存。通过缓存和目录在竞争事务的顺序上达成一致，ProtoGen能够生成与该顺序一致的高并发和非阻塞的控制器操作。
- ProtoGen，是第一个可以根据目录一致性协议的SSP规范生成一个完整的目录协议的工具，其包括相同的稳定状态和所有必需的瞬态状态，以最大化协议并发性，同时保证安全性并防止死锁；
- 本文使用ProtoGen生成了高性能的MSI、MESI和MOSI协议，给定了SSP规范，并使用Mur模型检查器验证了生成的协议的安全性和无死锁性；
- 展示了ProtoGen的多样性，可以生成满足TSO内存一致性模型的TSO-CC协议。
（4）主要实现手段
4.1 系统模型和定义
假设：
- 假设协议使用著名的MOESIF状态的一个子集；
- 假设典型的一致性请求要么增加权限（使用“Get”或“Upgrade”），要么降低权限（使用“Put”）；
- 对拓扑、互连网络或点对点顺序是否强制执行都不做任何假设；
- 假设每个缓存块和每个directory entry都有状态，该状态由其coherence permission state和可能的auxiliary state组成。coherence permission state包括S（共享）和M（修改），它们反映了缓存访问块的能力或目录对块的了解。auxiliary state是指不描述任何权限的状态，但必须要能正确地在两个coherence permission state之间进行转换。目录条目的auxiliary state可能包括块的当前所有者的ID和当前共享块的缓存集合（共享者列表）。缓存块的辅助状态可能包括用于跟踪传入确认的计数器。
- 这些协议假设可能比必要的更保守，但我们尚未探索具有其他状态或请求类型的协议。
当一个核心需要执行一个无法由其缓存满足的访问（加载、存储或替换）时，其缓存将发起一个一致性事务，以获取所需的缓存块的适当一致性状态或将其替换出来。一个事务包括：
- 初始请求消息，如GetShared（GetS）、GetModified（GetM）或PutModified（PutM）；
- 零个或多个转发请求 - 例如由目录作为对传入请求的响应而发送的转发GetM或Invalidation消息；
- 一个或多个数据响应或确认。目录和缓存控制器都可以用数据和确认消息对传入的一致性消息进行响应。例如，如果一个目录收到一个处于I(nvalid)状态的块的GetS请求，它将回复Data；
- 对传入的一致性消息的状态转换。缓存可以改变其块的状态，目录可以改变其条目的状态；这些状态变化可以包括coherence permission state和auxiliary state。例如，如果目录收到来自缓存的一个处于I状态的块的GetS请求，它将改变目录条目的一致性权限状态和用于跟踪共享者的辅助状态。
从一个缓存的角度考虑一个事务，该缓存通过一个请求发起事务，称该事务为缓存的“own”事务。如果该缓存接收到属于另一个缓存发起的事务的消息，我们称之为“other”事务。类似地，我们将一致性消息称为“own”（例如，own GetM）和“other”（例如，other PutS）。
将每个事务视为开始或结束的coherence epoch，即一个缓存在一段时间内具有对一个块的一致性权限的窗口。例如，一个缓存发出一个GetS请求以开始自己的事务，当该事务完成时，它将在该缓存上开始一个Shared时期。这个时期将在以下情况下结束：(a) 缓存完成另一个事务以改变其权限，或者(b) 另一个缓存执行影响该缓存权限的事务。
coherence的定义：
一致性的常见定义，包含两个不变式：
- 首先，对于任何给定时间的内存位置，要么有一个单独的写要么没有，或多个读。这个不变式通常被称为SWMR（Single Writer, Multiple Readers）。
- 其次，一个时期开始时位置的值与其最后一次写入时位置的值相同。这个不变式通常被称为数据值不变式（data-value invariant）。
在逻辑时间中，这两个不变式合并成一个不变式，即对于每个内存位置来说是顺序一致性。
4.2 ProtoGen概述
ProtoGen是如何在无需原子系统模型（保证物理原子事务）的情况下，生成具有“瞬态”状态的完整协议？
为了理解ProtoGen的工作原理，首先考虑一个简单的协议，即，对于任何给定的内存块，一次只能有一个一致性事务处于活动状态。为这样的协议生成瞬态规范很简单，每个瞬态只对应于事务中的一个步骤。例如，发出GetS请求以从I状态过渡到S状态的缓存有一个单独的瞬态状态，我们将其称为IS，表示它已经发出了请求但尚未收到响应；一旦它收到Data响应，它将过渡到S状态。
ProtoGen面临的挑战是处理给定块的多个并发事务。当处于事务中的缓存接收到属于同一块的并发事务的转发请求时会发生什么？在上面的例子中，当发出GetS的缓存在状态IS时收到另一个缓存（通过目录）的Invalidation时会发生什么？在目录协议中，目录是串行化点，所以关键是让缓存能够推断出事务在目录中的排序。在这里，缓存可以推断出自己的GetS在目录中首先排序；否则目录就没有理由转发Invalidation。因此，通过简单地查看传入的转发请求，ProtoGen能够推断出排序。
但SSP可能被编写成使得同一个转发消息可能到达两个稳定状态。为了处理这个问题，ProtoGen预处理输入的SSP，以确保给定的转发请求只能到达一个稳定状态（如果输入的SSP对两个转发请求消息使用相同的名称，ProtoGen会为其中一个创建一个新的名称）。这个不变式使得缓存能够可靠地推断事务在目录中的序列化顺序，只需简单地查看传入的转发请求。
直观地说，ProtoGen为缓存和目录创建“瞬态”状态，使这些有限状态机始终遵守目录中事务的排序。
4.3 ProtoGen的输入，输出和限制
A. 输入
ProtoGen的主要输入是使用我们的领域特定语言（DSL）描述的稳定状态协议（SSP）的高级规范。该规范根据单个缓存块描述协议，因为所有块的行为是相同的，包括：
- 稳定的一致性权限状态列表，通常是MOESIF状态的子集；
- 每个缓存块和每个目录条目的稳定辅助状态；
- 访问（加载、存储、替换）列表及其触发的请求；
- 可以在每个稳定状态中到达的可能的一致性消息（请求、转发请求、响应和确认）列表；
- 作为传入一致性消息的结果，从一个稳定状态转换到另一个稳定状态的过渡，包括一致性权限和辅助状态。
DSL使设计人员能够定义任何机器（例如缓存和目录）的结构以及其架构行为规范。DSL支持标准数据类型，如bool、int和set，但也提供了协议特定的数据类型，比如Data（用于表示内存块中的实际数据）。每个机器都有两个预定义的内部变量：State（表示机器的状态）和ID（机器的ID）。DSL允许指定缓存和目录在内部访问和传入一致性消息时的行为。大多数事务由请求和响应组成，指定这些事务是直接的。然而，有两个值得讨论的规范问题。
- 首先，一些请求可能会导致多个可能的事务路径，这取决于其他缓存中块的状态。考虑S到M的转换，在该转换中，当一个缓存接收到对共享状态块的存储时，会请求对该块的修改访问。如果该块由请求者独占且没有在其他地方缓存，请求者将仅从目录接收一个响应以完成其事务。然而，如果该块由一个或多个其他缓存持有，请求者必须等待目录的响应（包含共享者计数）以及所有缓存的确认。
- 其次，某些事务需要发起缓存接收多种类型的消息才能完成事务。DSL允许用户指定多个消息必须到达。回到我们的例子，两个相关的消息是GetM_Ack（目录发送的带有计数的消息）和Inv_Ack（失效确认）。当前者到达时，DSL允许设置辅助状态acksExpected；当后者到达时，acksReceived被增加；当它们相等时，事务完成。
配置参数:
- 一个参数控制生成的协议是阻塞还是非阻塞。对于前者，当缓存和目录控制器接收到可能竞争的请求时，它们会阻塞，以性能为代价（同时仍然防止死锁）。对于后者，生成的协议尽可能避免阻塞，以增加"瞬态"的数量为代价。
- 另一个ProtoGen参数控制生成的协议是否允许加载或存储访问处于瞬态状态的块（例如，对于处于S和M之间的瞬态状态的块的加载），这个输入会影响生成的协议所保证的一致性不变性。允许对处于瞬态状态的缓存块进行访问可能会使协议无法在物理时间上强制执行SWMR，但与强制执行每个位置的顺序一致性相兼容。
B. 输出
ProtoGen为缓存和目录生成包括瞬态状态在内的有限状态机（FSMs）。这些FSMs使用相同的DSL表示，并可以转换为任何其他用于指定FSMs的格式。
C. 限制
首先，ProtoGen需要一个正确指定的SSP作为其输入；它无法自动“纠正”SSP中的错误。
其次，ProtoGen无法生成在SSP中未明确指定的新协议动作。例如，它无法推断如何实现原子读-修改-写操作，除非在SSP中明确指定；同样，它无法根据有序网络的SSP自动推断无序网络的协议。第三，ProtoGen不指定协议动作如何与互连网络进行交互；它要求用户手动定义虚拟通道并将消息分配给通道。最后，ProtoGen仅限于基于目录的协议。
4.4 ProtoGen示例
ProtoGen是一个工具，根据给定的SSP来生成高度并发的目录协议。本节通过逐步解释生成过程，并使用一个运行示例来说明每个步骤。
A. 预处理SSP
在生成任何瞬态状态之前，ProtoGen首先对SSP规范进行预处理，以确保一个给定的转发请求可以到达精确地一个稳定状态。如果在输入的SSP规范中，同一个转发请求可以到达两个稳定状态，ProtoGen会为其中一个转发请求创建一个新的名称。这是为了确保ProtoGen生成的缓存控制器在处理转发请求时能够正确地响应。
B. 生成初始状态集
ProtoGen通过状态集State Set来跟踪缓存块可能出现的稳定状态，并根据这些状态生成瞬态状态。值得注意的是，瞬态状态是缓存本地的，目录看不到瞬态状态。目录始终将缓存中的任何块视为处于稳定状态；它根据目录中看到的缓存块的状态将请求转发给缓存。因此，可以到达瞬态状态的转发请求集合由在目录中缓存块可以出现的可能稳定状态确定（当缓存块处于瞬态状态时）。
ProtoGen的关键挑战是生成能够正确响应处于瞬态状态的块的转发请求的缓存控制器。但是为了做到这一点，ProtoGen必须首先了解哪些转发请求可能会到达瞬态状态。举个例子：对于MSI协议，状态集最初分别为{I}，{S}和{M}，我们将它们分别称为I、S和M状态集。随着ProtoGen生成新的瞬态状态，它将它们添加到一个或多个状态集中。
C.在没有并发的情况下添加瞬态状态
在没有并发的情况下，ProtoGen接下来会添加非原子协议所需的瞬态状态。如果从稳定状态Si到稳定状态Sj的事务涉及发出一个请求并等待单个响应，ProtoGen将添加一个反映请求已经发出但尚未收到响应的瞬态状态。如果事务涉及多个响应，ProtoGen将为每个响应添加一个瞬态状态。
在MSI协议中，缓存可以发起五种事务类型：I → S，I → M，S → M，S → I和M → I。从I到S的事务将导致创建一个IS的瞬态状态，反映了缓存已向目录发出GetS请求并等待数据响应的情况。当从目录接收到数据时，缓存将从IS转换到S状态。
D.适应并发
如何对任何给定的瞬态状态进行处理？在状态集Si中任何状态的缓存，可以接收SSP指定的任何可以到达稳定状态Si的转发请求。如果消息到达该稳定状态，块的状态将立即根据SSP中指定的方式更改为一个稳定状态（或可能保持在Si中）。但是，如果失效请求到达瞬态状态IS会怎样呢？因为ProtoGen的预处理步骤确保任何类型的转发请求只能到达单个稳定状态，所以ProtoGen可以生成新的瞬态状态而不会引起混乱。
ProtoGen关键是知道转发请求可以到达哪个稳定状态，并因此推断目录中的事务顺序。考虑了两种可能的情况，即在缓存C0处于瞬态状态时转发请求到达的情况：
- case 1：其他事务被先排序。如果到达的转发请求是与状态Si相关联的请求，那么C0可以推断目录必须在自己的请求之前看到其他事务。此外，C0可以推断当其他事务到达目录时，目录必须看到C0处于状态Si，即C0必须：（a）立即响应该请求；（b）过渡到一个瞬态状态。
- case 2：其他事务被后排序。假设缓存C0已经发出从状态Si过渡到状态Sj的请求，并处于已发出请求但尚未收到响应的瞬态状态。如果到达的转发请求是与状态Sj相关联的请求，那么C0可以推断目录必须在其他事务之前看到自己的请求。此外，C0可以推断当其他事务到达目录时，目录必须看到C0处于状态Sj，这就是为什么它首先将其他事务转发给C0的原因。
E.为状态分配访问权限
对于协议中的每个状态，ProtoGen确定在该状态下允许哪些访问（加载、存储、替换）。对于稳定状态，这个分配在SSP中给出。对于瞬态状态，这个分配是瞬态状态的初始和最终稳定状态的函数（例如，从S到M的事务中的瞬态状态）。如果初始状态和最终状态都具有足够的权限来执行访问，则可以在瞬态状态中执行该访问。ProtoGen还有一个输入参数，确定是否允许在瞬态状态中进行加载和存储；当然，这样做可能会导致在物理时间上违反SWMR，但仍与每个位置的顺序一致性兼容。
F. 生成目录控制器
目录生成会面临一个独特的挑战，由于目录控制器是非阻塞的，目录中的并发性可能与系统中的缓存一样多（缓存的并发性受限于每个块的一次性事务限制）。具体而言，目录可以在任何状态下接收Put请求（PutS、PutM等）。例如，考虑一个处于状态S的块在缓存C0中向目录发出一个PutS请求。在该PutS到达目录之前，缓存C1发出一个GetM请求到达目录。GetM将目录状态更改为M，并且目录向C0发送一个无效化请求。稍后，C0的过时的PutS到达了目录，而目录已经处于状态M；这种情况在原子协议中是不可能的，因此不会出现在任何SSP规范中。此外，对于目录的每个Put和每个状态，都存在类似的情况。
由于在SSP中没有好的方式来指定这些情况（因为它们不会在SSP中出现），作者利用目录协议工作原理的知识：一个过时的Put请求在与目录的竞争中“丢失”，而目录知道发出该Put请求的缓存的epoch已经被另一个被排序在其Put之前的事务终结。对于使用常见MOESIF状态子集的协议，目录只需简单地确认任何过时的Put请求即可，以便发出Put的缓存可以完成其过时事务。
G. Put it All Together
ProtoGen首先对SSP进行预处理并初始化状态集合（步骤1）。然后，对于SSP中的每个稳态到稳态的转换，ProtoGen为每个转换中的中间步骤生成一个瞬态状态（步骤2）。然后，对于每个这些瞬态状态，ProtoGen执行步骤3中的过程以适应该瞬态状态中的可能并发性。作为该过程的一部分，ProtoGen可能会生成新的瞬态状态。ProtoGen在所有新生成的瞬态状态上重复步骤3，直到不再产生新的瞬态状态或达到挂起事务的限制。在生成所有状态之后，ProtoGen为每个状态分配访问权限（步骤4）。
（5）实验结果
作者使用ProtoGen生成了几个具有不同特性和不同系统模型假设的协议，并对其进行了实验评估。与传统的架构评估不同，传统评估旨在展示性能、功耗等方面的改进，而这个评估旨在展示ProtoGen能够成功生成与现有协议相同或在某些情况下甚至更好的协议。
A. Stalling Protocols
根据Sorin等人的入门手册生成了几个阻塞协议，包括并发MSI、MESI和MOSI协议的规范，所有这些协议都是阻塞的。并为每个协议开发了一个SSP（这些SSP比手册中的规范要简单得多），ProtoGen生成了这些协议的并发版本。对于这三个协议，ProtoGen生成的缓存控制器规范与手册中的规范完全相同，目录控制器也完全相同，除了MSI和MESI目录有一个微不足道的差异。所有的协议在三个缓存的情况下通过了SWMR和无死锁的Murϕ验证，这是Murϕ在不耗尽内存的情况下能处理的最大缓存数。
B. Non-Stalling Protocols
使用ProtoGen生成MSI、MESI和MOSI协议的非阻塞版本，以测试ProtoGen生成具有更高并发性的目录协议的能力。值得注意的是，生成的协议相当复杂，具有18-20个状态和46-60个转换。在手册中没有非阻塞的MESI和MOSI协议，因此无法进行比较。然而，手册中确实有一个非阻塞的MSI协议，我们将生成的协议与之进行比较。
可以观察到两个有趣的差异。首先，生成的协议更少地发生阻塞。尽管手册中的协议是“非阻塞”的，但在某些复杂情况下仍然会发生阻塞；而ProtoGen生成的协议不会发生阻塞，因为它具有额外的瞬态状态。其次，ProtoGen能够合并手册中保持分开的一些状态。
C. An MSI Protocol for an Unordered Network
设计一个用于点对点有序互连网络的MSI协议，这意味着如果节点A向节点B发送两条消息，它们会按照发送的顺序到达，这样可以通过消除可能发生的几种竞争条件，简化协议设计。
为了测试ProtoGen，开发了一个不依赖于点对点有序的MSI协议的SSP。该协议通过添加额外的“握手”消息来处理产生的竞争条件。ProtoGen根据SSP生成了并发协议，降低了复杂性。
D. TSO-CC
传统的协议设计旨在支持任何一致性模型，并因此保守地避免任何可能违反顺序一致性（SC）的行为，例如通过在物理时间上强制执行SWMR。相比之下，TSO-CC利用TSO的松散特性来避免共享者跟踪，从而打破了物理时间上的SWMR，但遵守了TSO。
作者使用ProtoGen生成具有并发性的完整协议。使用Banks等人的验证方法，验证了生成的协议正确完整地实施了TSO。这项研究的两个关键点是：首先，ProtoGen可以用于生成TSO-CC等非传统协议；其次，它展示了ProtoGen在转换复杂协议并使其适用于不同系统模型方面的实用性。
三、Comments对文献的想法 （强迫自己思考，结合自己的学科）
文献中主要讨论的是可行性，没有探讨性能方面的问题。对可行性方面的验证，主要验证了生成的MSI协议和非传统的TSO协议，对较为复杂的MOSI协议缺乏进一步的验证，文中提到的原因是MSI，MOSI，MESI常为阻塞式的协议，后两者没有非阻塞式的。
其次，文中花费了大量笔墨讲述ProtoGen如何处理瞬态收到并发请求时如何应对，emmm，但是太绕了，还没咋看明白，基础还是不行，回头再看下基础后回来应该会有不一样的感悟。
还有，关于cache一致性的两中国大类，基于目录和基于监听的一致性协议，以及内存一致性协议，有些知识点还是有点模糊，有必要整理一下，再写个博客，可能会更清楚一些。
四、Why:为什么看这篇文献 （方便再次搜索）
了解课题背景:
- 了解目录式cache一致性协议的实现
- 了解定会上关于cache一致性的发展
五、Summary:文献方向归纳 （方便分类管理）
directory-based cache coherence protocol
- design automation
- non-atomic transaction
- concurrency