Cache一致性模型.doc

第十章 Cache一致性模型 一、问题的提出 多处理机已经成为提高计算机系统的计算能力的一种方式。共享存储的多处理机是其中的一个子类。多个处理机通过通信子系统访问由多重存储模块组成的共享存储器。处理机和公用存储器之间的互连可以共享总线的方式实现，或者使用某种单级/多级的互连网络。 共享存储多处理机的主要优势在于其性价比较高，而对编程模型没有过高的要求。图1展示了一个典型的共享存储多处理机的结构。 ............... .................. （图1） 不难看出，这种系统组织方式存在以下三个主要问题： 存储器竞争：由于一个存储器模块一次只能处理一个存储器访问请求，如果多个处理机同时发出访问请求的话，就只能被串行处理。 通信竞争：即使请求被定向到不同的存储器模块，在互连网络上也存在同时通信的竞争问题。 反应延迟时间：对一个多处理机系统而言，其包含的处理机数目越多，互连网络的复杂性也就越高，从而增加了请求及应答数据在网络上的传输时间。 上述问题都增加了存储器访问时间，降低了处理机的执行速度。 单个处理机中的Cache有效地降低了存储器平均访问时间，存储器访问具有时间相关性和空间相关性的特点，cache能够处理大部分的存储器访问请求（通常能达到95%以上），由存储器处理的很少。这也是多处理机结构通常采用缓存技术解决上述问题的原因。在图2的多处理机组织结构中，每个处理机都有对应的cache。这种cache通常称作private cache（私有缓存），因为每个cache都隶属于一个或几个处理机；与之相对应的是shared cache（共享缓存）。 ................. ................ （图2） 很多多处理机系统都采用了私有缓存的组织方式。这些系统采用普通的总线作为互连网络。在这种情况下，cache的主要用处就是减少总线的竞争，降低存储器的平均访问延迟。 共享存储的多处理机的优点在于：在并行应用中，简化了进程间的共享代码和数据结构。举例来说，进程间通信可以通过改变共享变量的办法实现。这种方式不可避免地会造成在一个或多个cache中同时存在一个共享数据块的几个副本。如何保持多个副本之间的一致，这就是cache一致性问题。针对这个问题已经提出了很多解决方案。本文将就这些方案展开论述。其中既有基于硬件的cache一致性协议，也有基于软件实现的策略。通常说来，处理机数目比较多时，硬件的复杂性问题就比较突出，一般采用基于软件的解决办法。 二、问题的解决 （一）基于硬件的协议 基于硬件的协议主要有：监听总线协议（snoopy cache protocol）、基于目录的cache一致性协议（directory scheme）。相关问题还有采用什么样的cache一致性网络体系结构。它们都依赖于一定的cache一致性策略。我们首先来看一下不同的策略。 1．cache一致性策略 基于硬件的cache一致性协议不需要借助于软件机制。通常情况下，硬件机制检测到不一致性条件，根据某一基于硬件的协议采取相关措施。 数据被分为许多大小相等的块（block）。块是存储器和cache之间的数据传输单位。硬件协议允许一个块的任意多个副本同时存在。维护cache一致性的策略有以下几两种:write-invalidate（写无效）和write-update（写更新）。 写无效策略是这样实现的：读请求而言，如果存在块的一个副本，该请求就在本地被处理。当一个处理机修改更新了其私有cache中某一块的数据后，其它cache中的副本被置为无效。具体的实现细节和互连网络有关。此时关于如何处理memory中的副本，有两种方法。一种是write-through（写通过），同时更新memory中的副本，最终结果是一个cache中的副本和memory中的副本是有效的；另一种是write-back（写回），它使memory中的副本也失效，最终只有一个cache中的副本是有效的。同一个处理机对数据进行第二次更新时，就可以在其私有cache中直接进行了）。图3（a）（b）说明了这种策略是如何工作的。 (a) (b) 图3（a）中共有四个块X的副本（1个在主存中，3个在cache中）。图3（b）：处理机1修改了块X中的某一项（更