论文部分内容阅读
【摘 要】本文首先简单介绍cache的工作原理，分析产生cache不一致的三个原因，再简单介绍并比较两种目前普遍使用的一致性协议：侦听协议和目录协议。接着我们在本文中主要提出一种新的一致性协议框架，这种协议能够将系统性能从正确性中独立出来。我们将这种综合性能的协议称之为基于令牌的Cache一致性协议。该协议Cache一致性是通过显式交换令牌和令牌计数的方式来实现的。
【关键词】共享存储；cache；一致性；令牌
在计算机经过多年发展的今天，单处理机的性能开发已经到了极限，而共享存储多处理机系统作为一种新的高端的技术，已经无可厚非的成为了主流。即使是低端的服务器也至少拥有两个处理器，而高端系统通常拥有十几个甚至几十个处理器。按照目前的趋势发展下去，多核或多处理机系统将取代单处理机系统而遍布市场，消费者也不太可能去购买一台单处理机的系统。
1.一致性相关概念
1.1一致性问题 在多处理机系统中，如果不同处理机中的进程需要共享某些数据，那么同一数据就可能有多个副本分别存放在各个Cache中，当某个Cache中的数据被更新后，而其他Cache中的相同数据副本并未作相应修改，造成了同一数据多个版本共存的现象。这就是所谓的Cache一致性问题。
1.2一致性协议 共享存储多处理机系统采用了一些高速缓存一致性协议（cache coherence protocols）来协调cache跟主存的内容一致性，使其作为一个整体给处理机提供一个单一的地址空间。这种cache-memory结构给处理器提供的一致性视图称为“存储一致性模型”，其通常作为系统结构指令集设计的一个部分[1]。cache一致性协议维护着这种模型的一个全局统一性，虽然目前多处理器系统已经是很普遍了，但在为其设计cache一致性协议方面却没有一个统一的看法，目前来说有两大主流的cache一致性协议：侦听协议和目录协议。事实上，大部分的争论都是围绕这两类协议而展开的。
2.高速缓存的工作原理
2.1基本原理
在由主存和cache组成的存儲器层次结构中， 主存是多处理机共享的， 而cache是每个处理机私有的。主存和cache都以块为单位进行划分， 以映射的方式来检索。在主存和cache之间， 是以块为单位进行搬送。
当处理机发出一个访问指令来访问主存的一个地址时， 如果包含这个地址在内的模块在cache中， 该cache可以使用。如果不在cache中，这时，必须把这个模块从主存搬到cache中， 叫做块搬送。如果cache已满， 则必须按一定的置换算法挑出一个模块搬出cache到主存。
2.2写控制方式
cache的写控制有两种： 写直达方式和写回方式。
2.2.1写直达方式是指处理机把数据写入cache的同时，也写入主存。这种方式控制简单是一优点， 但如果写命令多， 访问主存次数也会很多， 这样就不能充分发挥cache的优势。影响整个系统的性能。
2.2.2写回方式是当cache不命中时， 把所有要置换出的块都写回主存去， 这又叫简单写回方式。而如果只把修改过的块， 在被替换掉时写回主存， 这时就要在cache目录中设一位标志， 指示该模块是否被修改过。这种方式叫做标志写回方式。简单写回方式会产生多余的块交换， 使总交换时间变长， 而标志写回方式中， 必须在cache目录中增加标志位， 致使检索开销增加。
3.产生高速缓存不一致的三个原因
3.1共享可写数据（Sharing of writable data）引起的不一致
处理机 P1 将一个新的数据X’写入高速缓冲器中时，如果采用写通过策略，则立即将此复本写回共享存储器，在这种情况下，两个高速缓存中的两份复本 X 与 X’就不一致了；如果采用写回策略 ，也会产生不一致性。只用当高速缓存器中修改的数据被替换或变成无效时，主存储器内容才被更新，如图3.1所示。
3.2进程迁移（Process migration）引起的不一致
如果采用写回策略，包含共享变量 X 的进程从处理机 P1 迁移到处理机P2 时，将会出现不一致性；如果采用写通过策略时，进程从处理机 P2 迁移到处理机 P1 时，也会出现不一致性。如图3.2所示。
图 3.1 共享可写数据引起的不一致性
图 3.2进程迁移后引起的不一致性
3.3 I/O操作（I/O operation）引起的不一致
绕过高速缓存的 I/O 操作也会引起不一致性问题。当 I/O 处理机将一个新的数据X’写入主存储器时，绕过采用写通过策略的高速缓存，则在共享缓存 C1 和共享存储器之间产生了不一致性。当绕过高速缓存直接从共享存储器中输出数据时，采用写回策略的高速缓存也会产生不一致性。例如以DMA方式传送数据，DMA控制器直接对主存进行操作（读或写），但此时各个高速缓冲中可能有相应数据的复本，就会造成内存与高速缓存之间的不一致。如图3.3所示。
图3.3 绕过高速缓存的 I/O 操作引起的不一致性
4.解决高速缓存一致性问题的方法
解决cache一致性问题的方法大体有两种：软件控制法和硬件控制法。[5]
4.1软件控制法
cache一致性问题可以采用软件来解决，包括主流的通过编译进行事先分析的办法、利用OS来保证cache数据一致性的方法、以及其它一些模仿硬件控制法来实现一致性的软件控制方法等。
Hakan Grahn和Per Stenstrom对软件实现硬件控制法中的基于目录的一致性协议进行了详细的分析和比较之后得出，用软件实现可以达到用硬件实现性能的63%到97%，而事实上，一些现实因素会影响软件实现的的性能，导致其具有一些局限。例如，为了维护一致性以及由于不统一的分布式节点的中断导致读取不平衡的开销，以及由于某些处理器比其它处理器处理更多的涉及一致性的重要操作，使软件控制需要同步操作的开销[2]。 4.2硬件控制法
硬件控制法是目前使用较为广泛的解决cache一致性问题的方法，主要有侦听总线协议和目录协议，此外，还有用于单cache存储结构（cache-only memory architecture，COMA）的数据传播机制协议（data diffusion machine，DDM）以及基于SCI的协议等[3]。
5.一种新的可供选择的协议：令牌协议
5.1 令牌协议介绍
令牌协议允许竞争发生，但是它利用一种称为正确性基底（correctness substrate）的机制保证所有情况下系统能够正确的运行。该正确性基底确保：
（1）为保证共享变量（也就是内存块或其在Cache中的拷贝）的一致性，所有处理器适当地读写共享变量；
（2）避免饥饿：所有处理器最终能够获得需要共享变量。
正确性基底
正确性基底利用令牌计数方式来执行共享变量一致性保证，并且其利用永久性请求（persistent request）策略防止“饥饿”发生。这两种机制使得在系统中传输共享变量而不必考虑（竞争）访问该变量的顺序，允许处理器仅仅适时读或者写共享变量，但保证无论在何种情况下，某个对共享变量的（永久性）请求能够最终成功实现。
① 通过令牌计数保证一致性：
基于令牌协议的共享内存多处理器系统为共享内存中的每一个内存块（block）设置固定数目（例如T个）的令牌。当一个处理器拥有至少一个令牌才能够读取共享变量。当一个处理器拥有（某内存块的）全部令牌才能写共享变量。
在系统初始化期间，系统为每一个内存块设置T个令牌（T大于或者等于系统处理器数目）。最初，内存块宿主模块（block’s home memory module）拥有每个内存块的T个令牌。稍后，这些令牌能够被Cache和一致性消息（coherent message）拥有。
只要正确性基底保证不能创建或销毁令牌，确保当有处理器正在读共享变量时，该共享变量便不能被改写，确保当处理器Cache拥有某共享变量的令牌时就一定拥有对应共享变量。
根据拥有共享变量令牌数的不同，可以直接对分别应到传统一致性协议中共享变量的Modify、Share、Invalid不同状态：
基于令牌的正确性基底通过直接令牌计数方式执行这些规定。正确性基底通过归纳法来维持这些规定。系统初始状态满足这些规定，所有令牌和共享变量的传输满足这些规定。因此，安全性能够得到保证而不需考虑非稳定协议状态间的交互，数据响应，应答消息，总线互联下的顺序访问，或系统的层次性。
令牌一致性协议以目录协议相似的方式满足存储一致性模型。上述的“单写者”或者“多读者无写者”保证具有和传统目录协议相同的特性。
② 优化的令牌计数：
与上述四条规定相关的一个问题就是共享变量必须连同令牌一起传递，哪怕从拥有共享变量的Cache中收集令牌也不例外。这样在有的情况下会导致带宽利用率低下。为防止带宽利用率低下的情况发生，正确性基底实际上允许传递不携带共享变量的令牌（类比于基于目录协议的无数据无效应答消息）。为使这种优化（即允许传递不携带共享变量的令牌）生效，正确性基底设置一个独立的拥有者令牌（Owner Token），添加一个有效数据位，同时要保证共享变量的一致性，允许在传输携带有非拥有者令牌（non-owner token）的一致性消息时，该消息中可以省略共享变量拷贝；但是传输携带有拥有者令牌的一致性消息时，该消息中必须包含有效数据。这样能够防止所有处理器同时丢弃共享变量的情况发生。同时拥有拥有者令牌和其他少于T-1个非拥有者令牌（non-owner token）的情况对应我们熟悉的占有（Owned）状态。
令牌可以存放在处理器Cache中，或者共享内存中，或者一致性消息中。（我们假设互联设备提供可靠的消息传递）。因为我们不需跟踪哪个处理机拥有令牌而仅仅需要令牌的数目，所以这些令牌可以存放在2+「」（取上整）个二进制位中。
5.2一致性实现过程
我们可以从以下三个方面来利用这种自由：首先，我们定义永久性请求来防治饥饿的发生。其次，我们定义瞬时性请求（transient request），该请求允许高性能协议将这个请求发送给正确性基底，然后正确性基底将请求的共享变量和令牌发送给发起请求的处理器。最后，这种自由使得我们能够创造更多的高性能一致性协议。
5.2.1瞬时性请求的实现：
瞬时性请求很快，而且成功的机会很大。但是，其仍然可能由于以下原因而失败：因为竞争而不能获得请求块；不充分的接受者；被正确性基底忽略。高性能协议可以探测到某个瞬时性请求还没有被满足，因为请求者没有获得足够的令牌（一个令牌以读某共享变量，所有T个令牌以写共享变量）。高性能协议可以重发该瞬时性请求或者什么都不做（因为瞬时性请求一直不被满足的话，最终会超时失败从而发起一个永久性请求）。
5.2.2永久性请求的实现：
当申请共享变量在Cache缺失后的10倍于平均缺失时间内没有被满足，处理器便调用一个永久性请求。正确性基底通过位于宿主存储模块中的裁决状态机（arbiter state machine）来实现永久性請求。正确性基底将永久性请求指向其请求共享变量的宿主节点。裁决状态机通过告知系统中所有的节点来（最多）激活一个永久性请求。系统中每个节点通过一个应答消息响应（避免竞争）同时通过硬件表记录下所有已经激活的永久性请求。当一个永久性请求处于激活状态，那么所有的节点必须将所有令牌（和共享变量，如果其有拥有者令牌的话）向前传送给请求者。所有节点还必须将后来到达本节点的的令牌（和共享变量，如果其有拥有者令牌的话）向前传送给请求者，因为该永久性请求会一直保持直到请求者显式解除激活（deactivate）请求。一旦请求者得到满足，其便发送一条消息给宿主存储模块的裁决状态机，状态机随即告知系统中所有节点以解除激活。所有节点收到该告知后立即从硬件表中删除该永久性请求记录条目，并且反馈一条应答消息给裁决状态机。
6.总结
本文的主要工作是介绍一种新的一致性协议框架-令牌协议。在第五章中我们详细介绍了令牌协议的工作原理及运用的一种机制-正确性基底，通过令牌计数方式解决了共享变量在高速缓存中不一致性的难题。并且根据实际系统的需要（防止带宽利用率低下）进一步提出了优化的令牌计数策略。
总体而言，本文在解决共享存储器系统高速缓存不一致性问题上做了很多有益的工作，涉及到产生原理到具体实现的很多方面，为以后进一步进行类似的研究积累了很多宝贵的经验。
【关键词】共享存储；cache；一致性；令牌
在计算机经过多年发展的今天，单处理机的性能开发已经到了极限，而共享存储多处理机系统作为一种新的高端的技术，已经无可厚非的成为了主流。即使是低端的服务器也至少拥有两个处理器，而高端系统通常拥有十几个甚至几十个处理器。按照目前的趋势发展下去，多核或多处理机系统将取代单处理机系统而遍布市场，消费者也不太可能去购买一台单处理机的系统。
1.一致性相关概念
1.1一致性问题 在多处理机系统中，如果不同处理机中的进程需要共享某些数据，那么同一数据就可能有多个副本分别存放在各个Cache中，当某个Cache中的数据被更新后，而其他Cache中的相同数据副本并未作相应修改，造成了同一数据多个版本共存的现象。这就是所谓的Cache一致性问题。
1.2一致性协议 共享存储多处理机系统采用了一些高速缓存一致性协议（cache coherence protocols）来协调cache跟主存的内容一致性，使其作为一个整体给处理机提供一个单一的地址空间。这种cache-memory结构给处理器提供的一致性视图称为“存储一致性模型”，其通常作为系统结构指令集设计的一个部分[1]。cache一致性协议维护着这种模型的一个全局统一性，虽然目前多处理器系统已经是很普遍了，但在为其设计cache一致性协议方面却没有一个统一的看法，目前来说有两大主流的cache一致性协议：侦听协议和目录协议。事实上，大部分的争论都是围绕这两类协议而展开的。
2.高速缓存的工作原理
2.1基本原理
在由主存和cache组成的存儲器层次结构中， 主存是多处理机共享的， 而cache是每个处理机私有的。主存和cache都以块为单位进行划分， 以映射的方式来检索。在主存和cache之间， 是以块为单位进行搬送。
当处理机发出一个访问指令来访问主存的一个地址时， 如果包含这个地址在内的模块在cache中， 该cache可以使用。如果不在cache中，这时，必须把这个模块从主存搬到cache中， 叫做块搬送。如果cache已满， 则必须按一定的置换算法挑出一个模块搬出cache到主存。
2.2写控制方式
cache的写控制有两种： 写直达方式和写回方式。
2.2.1写直达方式是指处理机把数据写入cache的同时，也写入主存。这种方式控制简单是一优点， 但如果写命令多， 访问主存次数也会很多， 这样就不能充分发挥cache的优势。影响整个系统的性能。
2.2.2写回方式是当cache不命中时， 把所有要置换出的块都写回主存去， 这又叫简单写回方式。而如果只把修改过的块， 在被替换掉时写回主存， 这时就要在cache目录中设一位标志， 指示该模块是否被修改过。这种方式叫做标志写回方式。简单写回方式会产生多余的块交换， 使总交换时间变长， 而标志写回方式中， 必须在cache目录中增加标志位， 致使检索开销增加。
3.产生高速缓存不一致的三个原因
3.1共享可写数据（Sharing of writable data）引起的不一致
处理机 P1 将一个新的数据X’写入高速缓冲器中时，如果采用写通过策略，则立即将此复本写回共享存储器，在这种情况下，两个高速缓存中的两份复本 X 与 X’就不一致了；如果采用写回策略 ，也会产生不一致性。只用当高速缓存器中修改的数据被替换或变成无效时，主存储器内容才被更新，如图3.1所示。
3.2进程迁移（Process migration）引起的不一致
如果采用写回策略，包含共享变量 X 的进程从处理机 P1 迁移到处理机P2 时，将会出现不一致性；如果采用写通过策略时，进程从处理机 P2 迁移到处理机 P1 时，也会出现不一致性。如图3.2所示。
图 3.1 共享可写数据引起的不一致性
图 3.2进程迁移后引起的不一致性
3.3 I/O操作（I/O operation）引起的不一致
绕过高速缓存的 I/O 操作也会引起不一致性问题。当 I/O 处理机将一个新的数据X’写入主存储器时，绕过采用写通过策略的高速缓存，则在共享缓存 C1 和共享存储器之间产生了不一致性。当绕过高速缓存直接从共享存储器中输出数据时，采用写回策略的高速缓存也会产生不一致性。例如以DMA方式传送数据，DMA控制器直接对主存进行操作（读或写），但此时各个高速缓冲中可能有相应数据的复本，就会造成内存与高速缓存之间的不一致。如图3.3所示。
图3.3 绕过高速缓存的 I/O 操作引起的不一致性
4.解决高速缓存一致性问题的方法
解决cache一致性问题的方法大体有两种：软件控制法和硬件控制法。[5]
4.1软件控制法
cache一致性问题可以采用软件来解决，包括主流的通过编译进行事先分析的办法、利用OS来保证cache数据一致性的方法、以及其它一些模仿硬件控制法来实现一致性的软件控制方法等。
Hakan Grahn和Per Stenstrom对软件实现硬件控制法中的基于目录的一致性协议进行了详细的分析和比较之后得出，用软件实现可以达到用硬件实现性能的63%到97%，而事实上，一些现实因素会影响软件实现的的性能，导致其具有一些局限。例如，为了维护一致性以及由于不统一的分布式节点的中断导致读取不平衡的开销，以及由于某些处理器比其它处理器处理更多的涉及一致性的重要操作，使软件控制需要同步操作的开销[2]。 4.2硬件控制法
硬件控制法是目前使用较为广泛的解决cache一致性问题的方法，主要有侦听总线协议和目录协议，此外，还有用于单cache存储结构（cache-only memory architecture，COMA）的数据传播机制协议（data diffusion machine，DDM）以及基于SCI的协议等[3]。
5.一种新的可供选择的协议：令牌协议
5.1 令牌协议介绍
令牌协议允许竞争发生，但是它利用一种称为正确性基底（correctness substrate）的机制保证所有情况下系统能够正确的运行。该正确性基底确保：
（1）为保证共享变量（也就是内存块或其在Cache中的拷贝）的一致性，所有处理器适当地读写共享变量；
（2）避免饥饿：所有处理器最终能够获得需要共享变量。
正确性基底
正确性基底利用令牌计数方式来执行共享变量一致性保证，并且其利用永久性请求（persistent request）策略防止“饥饿”发生。这两种机制使得在系统中传输共享变量而不必考虑（竞争）访问该变量的顺序，允许处理器仅仅适时读或者写共享变量，但保证无论在何种情况下，某个对共享变量的（永久性）请求能够最终成功实现。
① 通过令牌计数保证一致性：
基于令牌协议的共享内存多处理器系统为共享内存中的每一个内存块（block）设置固定数目（例如T个）的令牌。当一个处理器拥有至少一个令牌才能够读取共享变量。当一个处理器拥有（某内存块的）全部令牌才能写共享变量。
在系统初始化期间，系统为每一个内存块设置T个令牌（T大于或者等于系统处理器数目）。最初，内存块宿主模块（block’s home memory module）拥有每个内存块的T个令牌。稍后，这些令牌能够被Cache和一致性消息（coherent message）拥有。
只要正确性基底保证不能创建或销毁令牌，确保当有处理器正在读共享变量时，该共享变量便不能被改写，确保当处理器Cache拥有某共享变量的令牌时就一定拥有对应共享变量。
根据拥有共享变量令牌数的不同，可以直接对分别应到传统一致性协议中共享变量的Modify、Share、Invalid不同状态：
基于令牌的正确性基底通过直接令牌计数方式执行这些规定。正确性基底通过归纳法来维持这些规定。系统初始状态满足这些规定，所有令牌和共享变量的传输满足这些规定。因此，安全性能够得到保证而不需考虑非稳定协议状态间的交互，数据响应，应答消息，总线互联下的顺序访问，或系统的层次性。
令牌一致性协议以目录协议相似的方式满足存储一致性模型。上述的“单写者”或者“多读者无写者”保证具有和传统目录协议相同的特性。
② 优化的令牌计数：
与上述四条规定相关的一个问题就是共享变量必须连同令牌一起传递，哪怕从拥有共享变量的Cache中收集令牌也不例外。这样在有的情况下会导致带宽利用率低下。为防止带宽利用率低下的情况发生，正确性基底实际上允许传递不携带共享变量的令牌（类比于基于目录协议的无数据无效应答消息）。为使这种优化（即允许传递不携带共享变量的令牌）生效，正确性基底设置一个独立的拥有者令牌（Owner Token），添加一个有效数据位，同时要保证共享变量的一致性，允许在传输携带有非拥有者令牌（non-owner token）的一致性消息时，该消息中可以省略共享变量拷贝；但是传输携带有拥有者令牌的一致性消息时，该消息中必须包含有效数据。这样能够防止所有处理器同时丢弃共享变量的情况发生。同时拥有拥有者令牌和其他少于T-1个非拥有者令牌（non-owner token）的情况对应我们熟悉的占有（Owned）状态。
令牌可以存放在处理器Cache中，或者共享内存中，或者一致性消息中。（我们假设互联设备提供可靠的消息传递）。因为我们不需跟踪哪个处理机拥有令牌而仅仅需要令牌的数目，所以这些令牌可以存放在2+「」（取上整）个二进制位中。
5.2一致性实现过程
我们可以从以下三个方面来利用这种自由：首先，我们定义永久性请求来防治饥饿的发生。其次，我们定义瞬时性请求（transient request），该请求允许高性能协议将这个请求发送给正确性基底，然后正确性基底将请求的共享变量和令牌发送给发起请求的处理器。最后，这种自由使得我们能够创造更多的高性能一致性协议。
5.2.1瞬时性请求的实现：
瞬时性请求很快，而且成功的机会很大。但是，其仍然可能由于以下原因而失败：因为竞争而不能获得请求块；不充分的接受者；被正确性基底忽略。高性能协议可以探测到某个瞬时性请求还没有被满足，因为请求者没有获得足够的令牌（一个令牌以读某共享变量，所有T个令牌以写共享变量）。高性能协议可以重发该瞬时性请求或者什么都不做（因为瞬时性请求一直不被满足的话，最终会超时失败从而发起一个永久性请求）。
5.2.2永久性请求的实现：
当申请共享变量在Cache缺失后的10倍于平均缺失时间内没有被满足，处理器便调用一个永久性请求。正确性基底通过位于宿主存储模块中的裁决状态机（arbiter state machine）来实现永久性請求。正确性基底将永久性请求指向其请求共享变量的宿主节点。裁决状态机通过告知系统中所有的节点来（最多）激活一个永久性请求。系统中每个节点通过一个应答消息响应（避免竞争）同时通过硬件表记录下所有已经激活的永久性请求。当一个永久性请求处于激活状态，那么所有的节点必须将所有令牌（和共享变量，如果其有拥有者令牌的话）向前传送给请求者。所有节点还必须将后来到达本节点的的令牌（和共享变量，如果其有拥有者令牌的话）向前传送给请求者，因为该永久性请求会一直保持直到请求者显式解除激活（deactivate）请求。一旦请求者得到满足，其便发送一条消息给宿主存储模块的裁决状态机，状态机随即告知系统中所有节点以解除激活。所有节点收到该告知后立即从硬件表中删除该永久性请求记录条目，并且反馈一条应答消息给裁决状态机。
6.总结
本文的主要工作是介绍一种新的一致性协议框架-令牌协议。在第五章中我们详细介绍了令牌协议的工作原理及运用的一种机制-正确性基底，通过令牌计数方式解决了共享变量在高速缓存中不一致性的难题。并且根据实际系统的需要（防止带宽利用率低下）进一步提出了优化的令牌计数策略。
总体而言，本文在解决共享存储器系统高速缓存不一致性问题上做了很多有益的工作，涉及到产生原理到具体实现的很多方面，为以后进一步进行类似的研究积累了很多宝贵的经验。