对称式存储器结构

大容量，多层级高速缓存的使用可以大量减少单个处理器对存储器带宽的要求。如果单个处理器对主存储器的带宽需求减少了，多个处理器就可以共享同一块存储器。80年代起，这个观点与统治地位初步显露的微处理器一起，促使很多设计者制造出小规模的，多个处理器通过一条总线共享同一块物理存储器的多处理器系统。因为这些处理器尺寸较小，并且大容量高速缓存有效减少了处理器对总线带宽的请求，所以在有充足存储器带宽存在的情况下，这种对称式多处理器结构会显得极为划算。这种多处理器系统的早期设计是能够把整个处理器和高速缓存子系统安在一块板上，这块板得插在总线底板上。后来90年代的这个设计已经能够在每块板上放置多达两个或者四个密度的处理器了，而且常常会使用多重总线与交叉存取用来支持更快的处理器。

2000年，IBM提出了可以在一块芯片上包含多个CPU用来做常规目的的运算。2005年，AMD和Intel相继在服务器市场发布双核处理器。2006年，Sun发布了8核处理器T1。4.8节会着重讲T1的设计与性能。之前第200页的图表4.1简单描绘了这种处理器。随着最近高性能处理器的出现，对存储器的需求超出了总线合理的带宽。结果，大多数最近的设计使用了小型交换机或者点对点网络。

这种对称式存储器结构的机器通常支持共享和私有数据的高速缓存。私有数据是被单个处理器使用的，而共享数据则是被多个处理器使用的，本质上是通过读写共享数据完成处理器之间的通信。把一个私有数据缓存之后，对该数据的访问就可以在高速缓存中进行，这样就减少了平均访问时间和对存储器带宽的请求。因为没有其他处理器使用这些数据，程序的行为与在单存储器机器中相同。当共享数据装载到高速缓存中时，会在多个高速缓存中形成副本。这样做除了会减少访问延迟和降低对存储器带宽的要求外，还能减少多个处理器同时读取共享数据时的竞争现象。然而，把数据放入高速缓存引入了一个新的问题：高速缓存一致性。

什么是多处理器的高速缓存一致性？

很不幸，高速缓存的引入带来了输入输出操作的一致性问题，这是因为从高速缓存得到的存储器视图可能会在毫无预知情况下与从输入输出子系统得到的存储器视图不同。

在多处理器中存在同样的问题，因为两个不同的处理器所保存的存储器视图是通过它们各自的高速缓存得到的。图表4.3说明了这个问题，并且解释了为什么两个不同的处理器对同一个位置会有不同的数值。这个问题通常被称为高速缓存一致性问题。

图4.3高速缓存一致性问题，两个处理器(A和B)对同一个存储器位置(x)执行读写操作。我们假设最初没有高速缓存含有该变量而且X的值为1，再假设使用写入直达的高速缓存；如果使用写回高速缓存则会增加一些较相似的复杂性。x值被A改写后，A的高速缓存和存储器中的副本都做了更新，但B的高速缓存则没有。如果B读入了X的数值，则会是1。

一般而言，如果在一个存储器系统中读取任何一个数据项的返回结果都是最近写入的数值，那么就可以认为该存储器是一致的。这个定义尽管直观地看是正确的，但是显得模糊而且太简略；实际情况要复杂得多。这个简单的定义包括了存储器系统行为的两个不同方面，它们对于编写正确的共享存储程序都是至关重要。第一个力一面叫高速缓存一致性，它定义了读操作可以返回什么样的数值，第二个方面叫存储器一致性，它定义了写入的数值什么时候才能被读操作返回。我们先看高速缓存一致性问题。

如果一个存储器系统满足如下条件，那么认为该存储器系统是一致的:

1.处理器P对地址X的写操作后面紧跟着处理器P对X的读操作，在这次读操作和写操作之问没有其他处理器对x进行写操作，这时读操作总是返回P写入的数值。

2.在其他处理器对X写操作后处理器P对X执行读操作，这两个操作之间有足够的间隔而且没有其他对X的写操作，这时读操作返回的是写入的数值。

3.对同个地址的写操作是串行执行的：也就是说，任何两个处理器对同一个地址的两个写操作在所有处理器看来都有相同的顺序。例如，如果向同一个地址中先后写入数值1和数值2，处理器决不会从该地址中先读出2再读出1。

第一个性质单单是为了保证程序的顺序，我们希望即使在单处理器中也要保证这性质。第二个性质定义了所谓的存储器一致性的概念：如果一个处理器对某个数据项执行读操作时，总是读入旧的数值，我们就认为这个存储器是非一致的。

写操作串行化的要求更加细致，但同样重要。如果没有把写操作串行化，而处理器P1写入地址X,紧跟着P2写入地址X，那后果会怎样呢？将写操作串化保证厂每个处理器都能在某个时间看到P2写入的结果。如果没有把写入串行化，就可能会有一些处理器先看到P2的写入结果再看到P1的写入结果，从而会不确定地保留P1写入的数值，避免这种情况最简单的方法是将写操作串行化，这样对同一个地址的写操作在所有处理器看来就具有相同的顺序。这个性质被称为写串行化。

虽然上述的三个性质足以保证一致性，但写入的数据什么时候可见也是很重要的。因为我们不能要求对X的读操作能立即看到由其他处理器写入X的值：例如，如果某个处理器对X的写操作只领先其他处理器对X的读操作很小的一段时问，那么无法保证该读操作能返回写入的数值，因为在这一刻写入的数据甚至可能还没有被处理器发送出去。存储器一致性模型定义了写入的数值必须在什么时候才能被读操作读出的问题，这个将会在4.6节讨论。

高速缓存一致性和存储器一致性是互补的：高速缓存一致性定义了对同一个存储器地址进行的读写操作行为。而存储器一致性定义了关于访问其他存储器地址的读写操作行为。到目前，做两个假设。第一，我们假设直到所有处理器都看到了写操作的效果之后一个写操作才算完成。第二，处理器不会因为其他存储器操作而改变写操作的顺序。这两种情况允许处理器重新安排读操作的顺序，但要强制处理器按照程序规定的顺序执行写操作。4.6节之前各节中的内容都是基于这个假设的，在4.6节中我们将会给出这个定义的准确含义，以及其他一些可供替代的选择。

严格执行一致性的基本方案

多处理器和输入输出的一致性问题在很多情况下是类似的，但还是具有一些不同的特征，这些特征会影响相应的解决方案。输入输出中，很少出现一个数据有多个副本的情况－－这是要尽量避免的，而多处理器系统中的情况恰恰相反，在多个处理器系统上运行的程序会要求在多个高速缓存中有同一个数据的副本。在支持高速缓存一致性的多处理器中，高速缓存提供共享数据的迁移和复制。

因为数据项可以被迁入本地高速缓存并以透明的方式使用，所以一致性的高速缓存要提供数据迁移。这样不但能减少访问远程共享数据项的延迟，而且可以减少对共享内存的带宽要求。

因为高速缓存在本地为被同时读取的共享数据做了备份，所以一致性的高速缓存也要为这些数据提供副本。而副本可以减少访问延迟和读取共享数据时的竞争现象。支持这种迁移和复制对于访问共享数据的性能来说是至关重要的。因此，小规模多处理器系统并没有通过在软件中避免出现不连贯的现象解决这个问题，而是通过在硬件上引入一个协议维护高速缓存的一致性来解决该问题。

这个用于维护多个处理器一致性的协议称为高速缓存一致性协议。实现高速缓存一致性协议的关键在于跟踪所有共享数据块的状态。广泛采用的有两类协议，它们采用不同的技术跟踪共享数据：

目录式－－把物理存储块的共享状态存放在一个地点，称之为目录。我们会在4.4节中讨论可扩展共享存储结构时集中讨论这个方法。4.8节将会介绍Sun T1的这种目录式设计，虽然它有一块中心物理存储器。

监听式－－每个含有物理存储器中数据块副本的高速缓存还要保留该数据块共享状态的副本，但是并不集中地保存状态。高速缓存通常放在共享存储总线上，所有的高速缓存控制器对总线进行监视或监听，来确定它们是否含有总线上请求的数据块的副本。本节集中讨论这种方法。

监听协议随着多处理器系统中越来越多地使用微处理器和连接到单一共享存储器的高速缓存而变得越来越流行，因为这种协议能使用已经存在的物理连接－－通往存储器的总线－－来查询高速缓存的状态。接下来一节我们通过实现一条共享总线来阐述监听式高速缓存一致性，但是，任何可以传播缓存缺失给一个处理器的传输介质都可以被用来实现监听式一致性方案。

监听协议

有两种方法可以保证上面所说的一致性。一种是在处理器写数据项之前保证该处理器能独占访问数据项。这种协议称为写无效协议，因为它在执行写操作时要使其他副本无效。而且这种协议是到目前为止在监听和目录方案中最常用的协议。独占访问确保写操作执行后不存在其他可读或可写的数据项副本：高速缓存中该数据项的所有其他副本都是无效的。

图4.4给出了一个基于监听总线的写无效协议的例子，其中使用写回高速缓存。为了说明它怎样保证一致性，考虑写操作后面紧跟其他处理器执行读操作的情况：由于写操作要求独占访问，执行读操作的处理器所保留的任何副本都被置为无效(协议正是由此得名的)。因此，执行读操作时，可能会发生高速缓存缺失然后要取回新的数据副本。对于写操作，我们要求执行写操作的处理器独占访问，这样就防止了任何其他处理器同时执行写操作的情况。如果两个处理器试图同时对同一个数据项执行写操作，它们中只有一个会在竞争中获胜(下面会给出如何确定谁能获胜)，这样另外一个处理器的副本就被置为无效。竞争失败的处理器要完成写操作，就必须首先取得新的数据副本，而这个副本中已经包含了更新后的数据。因此，这个协议强制执行写操作的串行化。

图4.4监听总线方式的写无效协议示例，使用写回式高速缓存。假设两个高速缓存最初都没有X，并且存储器中X的值为0。处理器和存储器中的内容是在处理器和总线活动全部完成后的数值。空格表明没有动作或没有存放副本。当B发生第二次缺失时，处理器A会应答，同时取消来自存储器的响应.然后，B的高速缓存和存储器中X的内容都得到更新。我们下面会看到，大部分协议都是这样做的，并且这样做的确能够简化协议。

还有另一种方法：写入数据项时更新该数据项所有的副本。这种类型的协议称为写更新或写广播协议。由于写更新协议必须给共享高速缓存广播所有的写操作，这消耗了大量带宽。由于这个原因，所有最新的多处理系统已经选择了实现写无效协议，本章的剩余部分仅集中讨论写无效协议。

基本实现技术

在小规模多处理器系统中实现写无效协议的关键是使用总线来完成无效操作。要实现无效操作，处理器只要取得总线控制权然后在总线上广播无效数据的地址即可。所有的处理器都要不断地监听总线来监测地址。处理器要检查各自的高速缓存中是否有总线上广播的地址。如果有，则高速缓存中相应的数据要置为无效。

总线所保证的串行访问也保证了写操作的串行化。因为当两个处理器竞争对同一个地址的写操作时，必然其中一个领先于另一个取得总线控制权。第一个取得总线控制权的处理器将把另一个处理器的副本置为无效，这样写操作就会严格地串行执行。要使用这个方案对共享数据项执行写操作，首先要取得总线控制权，否则无法完成。

除了要使执行写操作的高速缓存数据块的副本无效外，还需要在高速缓存缺失时对数据项进行定位。在写直达高速缓存中，查找数据项的最新值很容易，因为写入的数据总要送到存储器，故而可以在存储器中找到某个数据项的最新值。（写缓冲区引起的额外复杂性会在下一章中讨论。)在一个有充足内存带宽支持处理器写传输的设计中，使用写直达高速缓存可以简化高速缓存一致性。

然而，对于写回式高速缓存来说，要找出数据最新的值比较困难，因为数据项的最新值可能不在存储器中而在高速缓存中。幸运的是，写回式高速缓存能够使用同样的监听方案处理高速缓存缺失和写操作：所有处理器都要监听总线上的每个地址。如果一个处理器发现它留有被请求的高速缓存块的一个脏副本，它会对读操作做出响应，提供这个缓冲块，并中断对存储器的访问。因为写回式高速缓存对存储器带宽的要求较低，因此虽然有些复杂，多处理器系统还是倾向于使用这种方案。因而我们主要讨论使用写回式高速缓存的实现机制。

要跟踪一个缓存数据块是否共享，需要为每一个数据块再增加一个状态位，就如有效位和脏数据位一样。增加了标志该数据块是否被共享的状态位之后，执行写操作时就可以据此判定是否需要发送无效操作。当对共享的数据块执行写操作时，高速缓存会在总线卜发送一个无效操作并且把该块标记为私有。之后，那个处理器就不会再发送该数据块的无效操作了。拥有缓存块惟一一个副本的处理器通常称为该缓存块的所有者。