第四章对称多处理机系统SMPRead.docx
《第四章对称多处理机系统SMPRead.docx》由会员分享，可在线阅读，更多相关《第四章对称多处理机系统SMPRead.docx（54页珍藏版）》请在冰点文库上搜索。
第四章对称多处理机系统SMPRead
第四章对称多处理机系统
第四章对称多处理机系统1
4.1引言2
4.2高速缓存一致性问题和存储一致性模型3
4.2.1高速缓存一致性问题3
4.2.2高速缓存一致性和存储系统一致性4
4.3侦听高速缓存一致性协议6
4.3.1基本高速缓存一致性协议6
4.3.2三态回写无效协议（MSI）8
4.3.3四态回写无效协议（MESI）9
4.3.4四态回写更新协议（Dragon）11
4.4基本高速缓存一致性协议的实现12
4.4.1正确性要求12
4.4.2基本的高速缓存一致性设计13
4.5多级高速缓存17
4.5.1维护包含性17
4.5.2层次高速缓存一致性的传播18
*4.6分事务总线19
4.6.1基本设计19
4.6.2支持多级高速缓存22
4.7同步问题23
4.7.1基本问题23
4.7.2互斥操作24
4.7.3点到点事件同步27
4.7.4全局事件同步28
4.8实例分析：
SGIChallenge29
4.8.1SGI处理器和主存子系统30
4.8.2SGII/O子系统30
4.9小结31
习题31
参考文献33
对称多处理机SMP（SymmetricMultiprocessor）是一类最主要的共享存储的并行计算机系统，一般利用系统总线作为互连网络实现通信，它在现今的并行服务器中几乎普遍被采用，且越来越多的出现在桌面上。
在本章中，首先讨论了基于总线的SMP机器设计的一些问题，主要包括高速缓存一致性问题、存储一致性模型、侦听高速缓存一致性协议；然后分别介绍了基于单级高速缓存和原子总线、多级高速缓存和分事务总线的高速缓存一致性协议的实现；最后，介绍了同步问题及一个具体实例SGIChallenge系统。
4.1引言
对称多处理机SMP（SymmetricMultiProcessor）结构在现今的并行服务器中几乎普遍采用，并且已经越来越多的出现在桌面上。
同时，SMP机器也越来越多的作为一个构造模块，用来构造更大规模的系统。
SMP机器为什么能得到如此广泛的应用呢？
让我们来看一下这种机器结构及具有的特性。
如图4.1所示，SMP系统使用商用微处理器（具有片上或外置高速缓存），它们经由高速总线（或交叉开关）连向共享存储器。
这种SMP结构具有以下一些特性：
①对称性：
系统中任何处理器均可以对称的存取任何存储单元和I/O设备；②单一物理地址空间：
所有处理器的存储单元按单一地址空间编址；③高速缓存及其一致性：
多级高速缓存可支持数据局部性，而其一致性可以由硬件来实现；④低通信延迟：
处理器间的通信用简单的读/写指令来完成。
图4.1SMP机器的结构图
这些特性使得对称多处理机具有一些优点。
例如,由于存在单一物理地址空间，只需要一个OS副本驻留在共享存储器中，所以OS可以按工作负载情况在多个处理器上调度进程，从而易于达到动态负载平衡和有效的利用系统资源。
这一点使得它作为对吞吐率要求很高的服务器是很有吸引力的。
另外，由于任何处理器可以用普通的读/写指令来高效的存取共享数据，并且共享数据在本地高速缓存间进行自动复制和移动，这一点，使得对并行编程具有很大吸
图4.2SMP机器的几种扩展的存储层次结构
引力。
SMP的许多优点，使得这种机器得到广泛应用。
但是，大多数的对称多处理机多是采用总线连接，因此可扩放性差，机器的规模一般较小。
然而，可扩放性对对称多处理机来说是很重要的。
下面，我们从扩展存储系统的组织结构方面，来看一下如图4.2所示的多处理机中的4种扩展存储层次结构，其中前三种是对称多处理机，而第四种不是。
在共享高速缓存的方法中（图4.2（a）），互连网络位于处理器和共享的一级高速缓存之间。
为了提高带宽，高速缓存和主存系统都是可以交叉存取的。
在80年代中期，这种方法常被用来连接一个主板上的多个处理器，现在这种方法可被用来实现单片多处理机（Multiprocessor-on-a-chip）。
然而，这种方法当多个对称处理器同时存取共享高速缓存时，对高速缓存的带宽要求很高，另外，对高速缓存数据的存取必须通过处理器和高速缓存间的互连网络，因此，使得高速缓存存取延迟变大。
所以，这种方法的可扩放性很差，只适用于机器规模很小的情况，通常只支持2到8个处理器。
在基于总线的共享内存方法中（图4.2（b）），互连网络是处理器的私有高速缓存和共享主存系统间的共享总线。
这种方法广泛的应用于小规模和中等规模的多处理机中，其处理器数目通常能达到20到30个。
现在，市场上卖的SMP基本上是这种形式的机器。
并且，在现代微处理器的设计中，对构成高速缓存一致的共享内存系统也进行支持。
例如，只要直接将几个IntelPentiumPro处理器，用一个共享总线连起来，不需要任何辅助逻辑就构成了一台对称多处理机。
同样，基于总线的共享内存方法的可扩放性也不是很好，主要受共享总线和内存系统的带宽限制。
在最后两种方法中（图4.2（c）,（d）），主要考虑到可扩放性问题。
舞厅（Dancehall）方法也把互连网络放在高速缓存和主存之间，但是互连网络是一个可扩放的点到点网络，内存被划分为许多逻辑模块，连到互连网络的不同连接点。
这种方法是对称的，所有的处理器到内存的距离是相同的。
缺点是所有内存存取要经过互连网络，当其规模较大时，内存存取延迟较大。
第四种方法是分布内存的方法，它不是对称的。
处理节点之间通过一个可扩放的互连网络相连，每个节点有本地内存，对本地内存的存取比对远地内存的存取快得多。
通过利用数据分布的局部性原理，大多数的高速缓存缺失（Miss，有人也称之为不命中）的存取几乎都能在本地内存中得到满足。
这种方法对设计可扩放多处理器最具吸引力。
当然，以上的这些方法也可组合起来进行设计，例如，一个分布式内存机器，其中每个节点又可以是一个对称多处理机。
在所有的情况下，高速缓存在减少平均数据存取时间，以及减少对互连网络和内存系统的带宽要求方面，均起着很重要的作用。
如果处理器发出的存取数据的请求，在高速缓存中得到满足，就可不出现在互连网络上。
除了共享高速缓存的方法，在所有方法中，每个处理器至少有一层高速缓存是私有的。
这就形成了高速缓存一致性问题。
造成这个问题的原因，主要是同一个内存块的拷贝可能同时出现在多个处理器的高速缓存中，多个处理器对这些拷贝的存取，可能会使这些拷贝的内容出现不一致的情况。
4.2高速缓存一致性问题和存储一致性模型
4.2.1高速缓存一致性问题
让我们先来看一下内存系统的基本性质。
一个内存系统应该能提供一组保存值的存储单元，当对一个存储单元执行读操作时，应该能返回最近向那个存储单元的写操作所写入的值。
我们在串行程序中，利用内存来将程序某一点计算出来的值，传递到该值使用点，实际上就是利用了以上的基本性质。
同样，运行在同一个处理器上的多个进程或线程利用共享地址空间进行通信，实际上也是利用了内存系统的这个性质。
一个读操作应返回最近的向那个位置的写操作所写的值，而不管是哪个线程写的。
当所有的线程运行在同一个处理器上时，它们通过相同的高速缓存层次来看到内存，因此在这种情况下，高速缓存不会引起问题。
当在共享内存的多处理器系统上运行一个具有多个进程的程序，我们希望不管这些进程是运行在同一个处理器上，还是在不同的处理器上，程序的运行结果都是相同的。
然而，这两个进程通过不同的高速缓存层次来看共享内存时，其中一个进程可能会看到在它的高速缓存中的新值，而另一个则可能会看到旧值，这就引起了高速缓存一致性（CacheCoherence）问题。
维护一致性有写直达WT（WriteThrough）和写回WB（WriteBack）两种高速缓存：
写直达高速缓存采用的策略是一旦高速缓存中的一个字被修改过，则在主存中要立即修改；而写回高速缓存的策略是对高速缓存的修改延迟到被修改的字从高速缓存中被替换或消除时，才真正修改主存。
造成高速缓存不一致性问题的主要原因有：
（1）由共享可写数据所造成的不一致：
图4.3显示三个带有私有高速缓存的处理器，其高速缓存通过总线与共享主存相连。
考虑主存中的一个位置u和以下的一系列处理器发出的访问u的指令：
首先，P1从主存中读u，从而P1的高速缓存中建立了一个u的拷贝；然后，P3从主存中读u，从而在P3的高速缓存中也建立了一个u的拷贝；接着，P3向主存写u，将u值从5改写为7。
下面我们根据采用的高速缓存类型分情况讨论：
①采用写直达高速缓存：
P3写u时，将直接更新主存，然后当P1再一次读u时（动作4），将读到无效值5，而不是主存中的当前值7；②采用写回高速缓存：
P3写u时，标记为脏（dirty），暂时把修改过的（脏的）值放在自己的高速缓存中，并不直接更新主存。
只有当u所在的块被从高速缓存中替换出去时，才将其值写回主存。
这样一来，不仅P1再次读时将读到旧值，而且P2读u（动作5）时，也从主存读到旧值5，而不是新值7。
最后，如果多个处理器对在写回高速缓存中的u写了一系列值，则最终主存中是哪个值，将取决于u所在高速缓存块被替换的次序，而与对u的写操作的发生次序无关。
图4.3一个引起高速缓存一致性问题的例子
（2）由绕过高速缓存的I/O所造成的不一致：
这种情况即使在单处理机中也会发生。
大多数的I/O传输，通过直接内存存取（DMA）设备在外围设备和内存间直接传输数据，而不通过处理器。
当DMA设备向内存的一个位置写时，如果不采取特别的措施，处理器将会看到以前就装入高速缓存中的旧值。
并且，如果采用写回高速缓存，DMA设备可能会从内存位置读取一个旧值，因为新值可能还在处理器的高速缓存中，没传播到内存中。
（3）由进程迁移所造成的不一致：
对于这种情况这儿就不详述了，读者可参阅习题4.1来学习之。
很明显，以上描述的内存行为，与我们直觉想象的内存应该表现的行为不一样。
实际上，内存系统应该给应用程序提供一个一致的外观。
此外，由于属于同一个并行应用的多个进程，就是通过读写共享变量来进行通信的，因此对共享变量读写操作会经常发生。
这样，一个体系结构如果能越有效地支持对共享变量的读写，则就有越多类型的并行应用能在这种体系结构上获得很好的性能。
基于这一点考虑，许多设计者采用硬件方法来实现一个共享的全局地址空间和一致的高速缓存。
4.2.2高速缓存一致性和存储系统一致性
在讨论实现一致的高速缓存的方法之前，我们需要更精确地给高速缓存一致性下一个定义。
前面，我们对于内存的直觉定义存在一些问题：
首先，在多处理机系统中，有多个处理器在同时运行，因此“最近”的意义就不能很好的定义；其次，由于光速极限原理，一个读操作有时不可能返回另一个处理器向那个位置写入的值。
实际上，如果我们只考虑内存中的单个位置，然后给所有对这个位置的读写操作加一些限制，就不会破坏编程人员对一致的内存系统的直觉。
事实上，只要保证下面两点就可以了：
①写传播（WritePropagation）：
一个处理器对一个位置所写入的值，最终对其它的处理器是可见的；②写串行化（WriteSerialization）：
对同一个位置的所有写操作（来自同一个或不同处理器）应该能串行化，也就是说，所有的处理器以相同的次序看到所有这些写操作。
下面，我们来精确定义一下多处理机存储系统一致性，它实际上隐含了以上两点。
（1）存储系统一致性：
一个多处理机的存储系统是一致的（Coherent），如果满足以下条件：
对于一个程序的任何执行结果，对每个内存位置都能构造一个对该位置的操作的假想串行序列，按照假想串行序列的执行结果与实际执行结果一样。
其中，①由任一进程所发出的操作，在假想串行序列中的次序，与该进程向存储系统实际发射的次序是一样的；②每个读操作返回的值，是在假想串行序列中最近的向那个位置的写操作所写的值。
高速缓存一致性是必要的，但实际上，我们期望存储系统能保证更多的东西，而不是仅仅保证“对每个位置的读操作，返回最近一个写操作所写的值”。
高速缓存一致性主要关心不同处理器上执行的对同一个内存位置的读写操作的次序，而我们有时候希望存储系统，能保证对不同内存位置的读写操作的次序。
我们来看如下一个例子：
P1
/*AssumeinitialvalueofA,B,andflagis0*/
A=1
B=1
Flag=1
P2
While（flag==0）;/*spinidle*/
PrintA
PrintB
在以上代码段中，程序员希望在处理器P1将共享变量flag的值赋为1之前，处理器P2在进行忙等待。
一旦P2发现flag的值变为1后，就退出循环，打印A和B的值。
程序员希望打印A和B的值均为1。
然而，假如只有高速缓存一致性，并不能保证打印出来的A和B值为1。
因为，flag和A或B是不同的内存位置，而高速缓存一致性只保证同一个内存位置的读写操作的次序，而不保证对不同内存位置的读写操作的顺序。
在共享地址空间中，编程为了保证对一个内存位置（如下例中的A）的存取操作的顺序，可以是通过对另一个位置（如上例中的flag）的存取，或者显式同步操作（Barrier）来建立的。
因为高速缓存一致性，仅仅保证了对同一个位置的操作的次序，它对不同位置的操作次序并没有作出规定，因此，只凭高速缓存一致性，我们不能正确推断程序的执行行为。
为了解决这个问题，我们进一步引入了存储一致性模型。
（2）存储一致性模型：
存储一致性模型对一个内存操作相对于其它“看起来好象执行了”（AppearToBePerformed）的内存操作的次序作了限制。
内存操作可作用于同一个或不同内存位置，也可以是由同一个或不同进程发出。
“看起来好象执行了”这句话说明，实际物理执行中可能不是这样，但效果是一样的。
这其实是向程序员做了一个保证，程序员可以据此来推断程序的行为。
例如，我们可能希望一个在多处理机上运行的多线程程序的执行结果，与在单处理机中的执行结果一样，只不过在多处理机情况下，多个线程可以在多个处理器能同时执行而已。
如果是这样，我们就能象推断在单处理机中程序的执行行为一样，来推断在多处理机中程序的执行行为了。
Lamport将这种直觉模型正规描述成以下顺序一致性SC（SequentialConsistency）[1]。
（3）Lamport顺序一致性：
一个多处理机系统是顺序一致的（SequentiallyConsistent），如果任意一次执行的结果都与所有处理器按某一顺序的次序执行的结果相同，并且在此顺序的次序中，各处理器的操作都按其程序所指定的次序出现。
图4.4描述了顺序一致性系统提供给编程人员的内存抽象。
多个处理器看起来好象共享一个单个的逻辑内存，实际上在真实的机器中，内存可能分布在多个处理器上，并且每个处理器可能具有私有的高速缓存。
每个处理器看起来好象是一次发射一个内存操作，并且按程序序原子执行；也就是说，一个内存操作看起来好象是等到前一个内存操作已经完成之后才发射。
此外，内存按照任意的调度次序来服务到来的请求。
图4.4顺序一致性模型提供给编程人员的内存抽象图
在第七章的7.3.3节，我们还将深入地讨论存储一致性模型。
4.3侦听高速缓存一致性协议
4.3.1基本高速缓存一致性协议
现在，基于总线的对称多处理机得到了广泛的应用。
这种类型的机器是通过高速共享总线将商用的微处理器与共享存储器连接起来，并且用硬件实现侦听高速缓存一致性协议，以保证高速缓存一致性。
侦听高速缓存一致性协议主要是利用了总线的特性。
总线是一组连接多个设备的线路，总线上的每个设备都能侦听到总线上出现的事务。
在侦听高速缓存一致性协议的实现中，所有高速缓存控制器都侦听总线上出现的事务，一旦发现与自己相关的事务就执行相应的动作来保证高速缓存一致性。
1.基本的侦听协议
侦听一致性协议（SnoopyCoherenceProtocol）牵涉到两个基本方面：
总线事务和与每个高速缓存块（也称之为高速缓存行）相关的状态转换图。
一个总线事务由仲裁，命令/地址和数据传输三个阶段组成。
在总线仲裁阶段，设备先发出总线请求信号，总线仲裁器在所有总线请求中选择一个设备，并将总线授予该设备。
一旦设备被授予总线，它就把读/写命令及地址放到命令和地址线上。
所有其它设备将进行侦听，只有其中一个设备会判断出该地址与它相关，并作出响应。
对于读事务来说，地址阶段后会跟着一个数据传输阶段；对于写事务来说，不同总线有不同的处理方法，主要取决于数据是在地址阶段就开始传输，还是等到地址阶段结束后才传输。
为简单起见，我们假设总线是原子的，即总线事务的各个阶段不能重叠，一次只能有一个事务出现在总线上。
下面，我们来看一下与每个高速缓存块相关的状态转换图。
对于每一个高速缓存块，除了标记（Tag）和数据外，还有一个与它相关的状态。
状态转换图实际上是一个有限状态机，它决定了高速缓存块在它的状态之间是如何转换的。
在单处理机中，当采用写直达且写不分配（Write-No-Allocate）的高速缓存时，只需要无效I（Invalidate）和有效V（Validate）两个状态。
开始时，所有的块都是无效的。
当处理器发生一个读缺失时，高速缓存控制器产生一个总线事务从主存中装入该块，并将该块状态置为有效；当处理器执行写操作时，高速缓存控制器产生一个总线事务去更新主存，如果所写的块在高速缓存中，且处于有效状态的话，则也更新高速缓存中块的内容，但不改变该块的状态。
当高速缓存中一个块被替换出去时，则将该块置为无效。
在多处理机系统中，一个块在每个处理器的高速缓存中都有一个状态，所有的这些状态都按照状态转换图来转换。
因此，假设n是系统中高速缓存的数目，则一个块的状态实际是可以看作是一个n维的向量。
由n个分布的有限状态机来控制高速缓存块的状态。
所有的有限状态机是相同的，但是同一个块在不同的高速缓存中的当前状态可能不一样。
每个高速缓存控制器都实现了一个有限状态机。
一般来说，在侦听高速缓存一致性协议中，每个高速缓存控制器接收的两方面输入：
处理器发出的内存请求和总线上侦听到的事务。
作为这些输入的响应，高速缓存控制器可能根据相应高速缓存块的当前状态及状态转换图来更新该块的状态，并且也可能要执行一些动作。
比如，作为对处理器发出的读请求的响应，高速缓存控制器可能要产生一个总线事务来获得数据，并返回给处理器。
有时候，高速缓存控制器也要参与到总线上侦听到的事务中去，并作出响应。
因此，侦听协议实际上是一组互相协作的有限状态机所代表的分布式算法，它由三部分组成：
①状态集合：
一个与本地高速缓存块相关联的状态集合；②状态转换图：
以当前状态和处理器请求，或观察到的总线事务作为输入，并输出该高速缓存块的下一个状态；③动作：
与每个状态转换相关的实际动作，这是由总线、高速缓存和处理器的具体设计来决定。
对同一个块的不同状态机不是独立操作的，而是由总线事务来协调的。
图4.5描述了一个简单使无效协议的状态转换图，该协议采用了写直达且写不分配的高速
图4.5一个简单使无效协议的状态转换图
缓存。
其中，每个高速缓存块有无效I（Invalid）和有效V（Valid）两个状态。
对于不在高速缓存中的块，可看作处于无效状态。
每个转换由一个输入和输出来表示。
输入表示引发该转换的条件，输出表示该转换产生的总线事务。
比如，当控制器看到一个处理器发出的读请求在高速缓存中缺失时，发出一个总线读（BusRd）事务，并在总线事务完成时，将该块状态变为有效状态；当控制器看到处理器发出写请求时，产生一个总线写（BusWr）事务来更新主存，但不改变块状态。
这个状态转换图与单处理机情况下的主要不同点是：
当高速缓存控制器在总线上侦听到一个总线写事务，并且在本地高速缓存中有该事务请求的内存块的拷贝时，就将本地高速缓存的拷贝状态置为无效状态，也就是说抛弃了本地拷贝。
这样一来，所有的高速缓存控制器相互合作保证在任意时刻只能有一个处理器对一个数据块进行写操作，但同时可以有多个处理器进行读操作，从而保证了高速缓存一致性。
2.侦听协议的类型
在侦听协议设计中，主要有两种设计选择：
①是写直达高速缓存，还是写回高速缓存；②是写无效WI（Write-Invalidate），还是写更新WU（Write-Update）协议。
以下我们讨论一下这两种设计选择。
我们将对写直达和写回分别进行分析：
在写直达方式下，主存总是与高速缓存中的最新值保持一致，但这种方式在每次高速缓存的写操作后，都需要更新主存从而需要额外的总线周期；在写回方式下，主存的更新要到发生替换时才进行，因此在高速缓存的写操作命中后的瞬间，高速缓存和主存是不一致的。
写回实际上尽量延迟写直达中对主存的更新，因此它只需占有较少的总线周期，故在存储器总线结构上采用写回高速缓存更经济。
另一个主要的选择是采用写无效还是写更新协议：
写无效协议在本地高速缓存中数据被更新后，使所有其他高速缓存中的相应数据拷贝无效，接下来由同一个处理器发出的对该内存块的写操作就不会在总线上引起任何通信；写更新协议则广播修改后的数据，以更新所有的高速缓存中的相应数据拷贝，因此当拥有该块拷贝的处理器接下来存取这个新数据时，存取延迟就很小。
另外，由于一个总线事务就能更新所有拥有该块的高速缓存中内容，因此如果该块有多个共享者，则能极大节约总线带宽。
具体例子可参看图4.6，其中主存数据X存在3个高速缓存中。
当某一处理器想要进行
图4.6采用写回高速缓存的写无效和写更新侦听协议
写操作时，首先必须获得对X访问的独占权，然后更新数据为X’并使其他处理器高速缓存中的相应数据拷贝无效；使用写回高速缓存时，主存的相应数据块也被置为无效。
4.3.2三态回写无效协议（MSI）
1.MSI协议
三态回写无效协议MSI（ModifiedSharedInvalid）协议是一种采用写回高速缓存的写无效侦听协议，与应用于SiliconGraphics4D系列机中的协议相似[2]。
为了区分高速缓存中块的不同，协议定义了以下三种状态：
①无效（I）状态：
它意味着该块在高速缓存中是无效的，或者该块还没有进入高速缓存；②共享（S）状态：
它意味着该块在高速缓存中没被修改过，主存中是最新的，在其它高速缓存中可能有也可能没有该块的最新拷贝；③修改过（M）状态：
也叫做脏状态，它意味着只有该高速缓存中有该块的最新拷贝，主存中的拷贝是过时的（Stale）。
在前一节中，我们讲过在侦听高速缓存一致性协议中，每个高速缓存控制器接收两方面输入：
处理器发出的请求和总线上侦听到的事务。
对于前者，处理器发出处理器读（PrRd）和处理器写（PrWr）两种类型的请求，并且读或写都有可能是对已经在高速缓存中的内存块、或者不在高速缓存中的内存块进行。
假如是对不在高速缓存中的内存块进行读或写，若缓存已满，则当前高速缓存中的一块就必须被新请求的块替换出去。
并且，若被替换出去的块处于M状态的话，则就必须将其内容写回到内存中。
对于后者，我们假设总线允许以下三种事务：
①总线读（BusRd）：
高速缓存控制器将地址放到总线上，并请求一个它不准备去修改的数据块，由主存或者另一个高速缓存提供数据。
②总线互斥读（BusRdX）：
高速缓存控制器将地址放到总线上，并请求一个它准备修改的互斥拷贝，由主存或者另一个高速缓存提供数据。
所有其他高速缓存中的拷贝必须被置为无效。
这种事务是由对某个不在缓存、或虽然在缓存但没有被标记为被修改过的块的写操作引起的。
一旦缓存获得互斥拷贝，写操作就能在缓存中执行，处理器可能会要求一个确认信号作为该事务的结果。
总线互斥读事务是唯一一个为了实现高速缓存一致性才引入的新事务。
③总线回写（BusWB）：
缓存控制器将主存块的地址和内容放到总线上，主存用该最新的内容来更新。
这种事务由缓存控制器的回写操作引起，处理器并不知道，也不期望得到响应。
为支持写回协议，除了改变缓存块的状态外，还需要一种新的动作，即高速缓存控制器能够中断已经出现在总线
升级会员 