多处理机曹强计算机学院武汉光电国家实验室信息存.ppt

《多处理机曹强计算机学院武汉光电国家实验室信息存.ppt》由会员分享，可在线阅读，更多相关《多处理机曹强计算机学院武汉光电国家实验室信息存.ppt（157页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1/156/156多处理机曹强计算机学院武汉光电国家实验室信息存 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望2 2/156/15610.1引言10.2对称式共享存储器系统结构10.3分布式共享存储器系统结构10.4同步10.5同时多线程10.6 大规模并行处理机MPP10.7多处理机实例1：T110.8多处理机实例2：Origin 20001.单处理机系统结构正在走向尽头？2.多处理机正起着越来越重要的作用。近几年来，人们确实开始转向了多处理机。Intel

2、于2004年宣布放弃了其高性能单处理器项目，转向多核（multi-core）的研究和开发。IBM、SUN、AMD等公司 并行计算机应用软件已有了稳定的发展。充分利用商品化微处理器所具有的高性能价格比的优势。3.本章重点：中小规模的计算机(处理器的个数32)（多处理机设计的主流）10.1 引 言4 4/156/15610.1 引 言1.Flynn分类法 SISD、SIMD、MISD、MIMD2.MIMD已成为通用多处理机系统结构的选择，原因：MIMD具有灵活性；MIMD可以充分利用商品化微处理器在性能价格比方面的优势。计算机机群系统（计算机机群系统（clustercluster）是一类广泛被采用

3、）是一类广泛被采用的的MIMDMIMD机器。机器。10.1.1 并行计算机系统结构的分类 5 5/156/15610.1 引 言3.根据存储器的组织结构，把现有的MIMD机器分为两类：（每一类代表了一种存储器的结构和互连策略）（每一类代表了一种存储器的结构和互连策略）集中式共享存储器结构 动画q最多由几十个处理器构成。最多由几十个处理器构成。q各处理器共享一个集中式的物理存储器。各处理器共享一个集中式的物理存储器。这类机器有时被称为这类机器有时被称为 qSMPSMP机器机器 （Symmetric shared-memory MultiProcessorSymmetric shared-memo

4、ry MultiProcessor）qUMAUMA机器机器（Uniform Memory AccessUniform Memory Access）6 6/156/15610.1 引 言对称式共享存储器多处理机的基本结构对称式共享存储器多处理机的基本结构7 7/156/15610.1 引 言分布式存储器多处理机 动画q存储器在物理上是分布的。存储器在物理上是分布的。q每个结点包含：每个结点包含：n处理器处理器n存储器存储器nI IO On互连网络接口互连网络接口q在许多情况下，分布式存储器结构在许多情况下，分布式存储器结构优于优于集中式共享存集中式共享存储器结构。储器结构。8 8/156/156

5、10.1 引 言9 9/156/15610.1 引 言q将存储器分布到各结点有两个将存储器分布到各结点有两个优点优点n如果大多数的访问是针对本结点的局部存储器，则如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；可降低对存储器和互连网络的带宽要求；n对本地存储器的访问延迟时间小。对本地存储器的访问延迟时间小。q最主要的最主要的缺点缺点n处理器之间的通信较为复杂，且各处理器之间访问处理器之间的通信较为复杂，且各处理器之间访问延迟较大。延迟较大。q簇：簇：超级结点超级结点 n每个结点内包含个数较少（例如每个结点内包含个数较少（例如2 28 8）的处理器；）的处理器；n

6、处理器之间可采用另一种互连技术（例如总线）相处理器之间可采用另一种互连技术（例如总线）相互连接形成簇。互连接形成簇。1010/156/15610.1 引 言1.两种存储器系统结构和通信机制共享地址空间 q物理上分离的所有存储器作为一个统一的共享逻辑物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址。空间进行编址。q任何一个处理器可以访问该共享空间中的任何一个任何一个处理器可以访问该共享空间中的任何一个单元（如果它具有访问权），而且不同处理器上的单元（如果它具有访问权），而且不同处理器上的同一个物理地址指向的是同一个存储单元。同一个物理地址指向的是同一个存储单元。q这类计算机被称为这类计算

7、机被称为 分布式共享存储器系统分布式共享存储器系统 （DSMDSM:Distributed Shared-Memory):Distributed Shared-Memory)NUMA NUMA机器机器 （NUMANUMA:Non-Uniform Memory Access):Non-Uniform Memory Access)10.1.2 存储器系统结构和通信机制 1111/156/15610.1 引 言把每个结点中的存储器编址为一个独立的地址空间，不同结点中的地址空间之间是相互独立的。q整个系统的地址空间由多个独立的地址空间构成整个系统的地址空间由多个独立的地址空间构成q每个结点中的存储器只

8、能由本地的处理器进行访问，每个结点中的存储器只能由本地的处理器进行访问，远程的处理器不能直接对其进行访问。远程的处理器不能直接对其进行访问。q每一个每一个处理器处理器-存储器存储器模块实际上是一台单独的计算机模块实际上是一台单独的计算机q现在的这种机器多以集群的形式存在现在的这种机器多以集群的形式存在2.通信机制 共享存储器通信机制q共享地址空间的计算机系统采用共享地址空间的计算机系统采用1212/156/15610.1 引 言q处理器之间是通过用处理器之间是通过用load和和store指令对相同存储器地指令对相同存储器地址进行读址进行读/写操作来实现的。写操作来实现的。消息传递通信机制q多个

9、独立地址空间的计算机采用多个独立地址空间的计算机采用 q通过处理器间显式地传递消息来完成通过处理器间显式地传递消息来完成q消息传递多处理机消息传递多处理机中，处理器之间是通过发送消息来中，处理器之间是通过发送消息来进行通信的，这些消息请求进行某些操作或者传送数进行通信的，这些消息请求进行某些操作或者传送数据。据。1313/156/15610.1 引 言例如：例如：一个处理器要对远程存储器上的数据进行访问或操作：一个处理器要对远程存储器上的数据进行访问或操作：n发送消息，请求传递数据或对数据进行操作；发送消息，请求传递数据或对数据进行操作；远程进程调用远程进程调用(RPC(RPC，Remote

10、Process Call)Remote Process Call)n目的处理器接收到消息以后，执行相应的操作或代替目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返远程处理器进行访问，并发送一个应答消息将结果返回。回。q同步消息传递同步消息传递 请求处理器发送一个消息后一直要等到应答结果才继续运行。请求处理器发送一个消息后一直要等到应答结果才继续运行。q异步消息传递异步消息传递 数据发送方知道别的处理器需要数据，通信也可以从数数据发送方知道别的处理器需要数据，通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方。据发送方来开始，数据可以不

11、经请求就直接送往数据接受方。1414/156/15610.1 引 言3.不同通信机制的优点 共享存储器通信的主要优点 q与常用的对称式多处理机使用的通信机制兼容。与常用的对称式多处理机使用的通信机制兼容。q易于编程，同时在简化编译器设计方面也占有优势。易于编程，同时在简化编译器设计方面也占有优势。q采用大家所熟悉的共享存储器模型开发应用程序，而采用大家所熟悉的共享存储器模型开发应用程序，而把重点放到解决对性能影响较大的数据访问上。把重点放到解决对性能影响较大的数据访问上。q当通信数据量较小时，通信开销较低，带宽利用较好。当通信数据量较小时，通信开销较低，带宽利用较好。q可以通过采用可以通过采用

12、Cache技术来减少远程通信的频度技术来减少远程通信的频度，减少，减少了通信延迟以及对共享数据的访问冲突。了通信延迟以及对共享数据的访问冲突。1515/156/15610.1 引 言消息传递通信机制的主要优点q硬件较简单。硬件较简单。q通信是显式的，因此更容易搞清楚何时发生通信以及通通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少。信开销是多少。q显式通信可以让编程者重点注意并行计算的主要通信开显式通信可以让编程者重点注意并行计算的主要通信开销，使之有可能开发出结构更好、性能更高的并行程序。销，使之有可能开发出结构更好、性能更高的并行程序。q同步很自然地与发送消息相关联，能减少不当

13、的同步带同步很自然地与发送消息相关联，能减少不当的同步带来错误的可能性。来错误的可能性。1616/156/15610.1 引 言可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。q在共享存储器上支持消息传递相对简单。在共享存储器上支持消息传递相对简单。q在消息传递的硬件上支持共享存储器就困难得多。在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息转换和存储保护功能，即将存储器访问转换为消息的发送和接收。的发送和接收。1717/156/15610.1 引 言

14、并行处理面临着两个重要的挑战程序中的并行性有限相对较大的通信开销10.1.3 并行处理面临的挑战 系统加速比系统加速比 =1818/156/15610.1 引 言1.第一个挑战有限的并行性使计算机要达到很高的加速比十分困难。例例10.110.1 假设想用假设想用100100个处理器达到个处理器达到8080的加速比，求原计算程的加速比，求原计算程 序中串行部分最多可占多大的比例？序中串行部分最多可占多大的比例？解解 AmdahlAmdahl定律为：定律为：由上式可得：由上式可得：并行比例并行比例0.99750.9975 1919/156/15610.1 引 言2.第二个挑战：多处理机中远程访问的

15、延迟较大在现有的机器中，处理器之间的数据通信大约需要501000个时钟周期。主要取决于：通信机制、互连网络的种类和机器的规模通信机制、互连网络的种类和机器的规模 在几种不同的共享存储器并行计算机中远程访问一个字的典型延迟 2020/156/15610.1 引 言机器 通信机制 互连网络 处理机最大数量 典型远程存储器访问时间（ns）Sun Starfire Sun Starfire servers servers SMP SMP 多总线多总线 64 64 500 500 SGI Origin 3000 SGI Origin 3000 NUMA NUMA 胖超立方体胖超立方体 512 512 5

16、00 500 Cray T3E Cray T3E NUMA NUMA 3 3维环网维环网 2048 2048 300 300 HP V series HP V series SMP SMP 8 88 8交叉开关交叉开关 32 32 1000 1000 HP AlphaServer GS HP AlphaServer GS SMP SMP 开关总线开关总线 32 32 400 400 2121/156/15610.1 引 言 例例10.210.2 假设有一台假设有一台3232台处理器的多处理机，对远程存储器台处理器的多处理机，对远程存储器访问时间为访问时间为200ns200ns。除了通信以外，假

17、设所有其它访问均命中局。除了通信以外，假设所有其它访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器的时部存储器。当发出一个远程请求时，本处理器挂起。处理器的时钟频率为钟频率为2GHz2GHz，如果指令基本的，如果指令基本的CPICPI为为0.50.5（设所有访存均命中（设所有访存均命中CacheCache），求在没有远程访问的情况下和有），求在没有远程访问的情况下和有0.2%0.2%的指令需要远程的指令需要远程访问的情况下，前者比后者快多少访问的情况下，前者比后者快多少?2222/156/15610.1 引 言解解 有有0.2%0.2%远程访问的机器的实际远程访问的机器的实际C

18、PICPI为：为：CPICPI基本基本CPICPI远程访问率远程访问率远程访问开销远程访问开销 0.50.50.2%0.2%远程访问开销远程访问开销 远程访问开销为：远程访问开销为：远程访问时间远程访问时间/时钟周期时间时钟周期时间200ns/0.5ns200ns/0.5ns400400个时钟周期个时钟周期 CPICPI0.50.50.2%4000.2%4001.31.3 因此在没有远程访问的情况下的机器速度是有因此在没有远程访问的情况下的机器速度是有0.2%0.2%远程访远程访问的机器速度的问的机器速度的1.3/0.5=2.61.3/0.5=2.6倍倍。2323/156/15610.1 引

19、言问题的解决q并行性不足：并行性不足：采用并行性更好的算法采用并行性更好的算法q远程访问延迟的降低：靠系统结构支持和编程技术远程访问延迟的降低：靠系统结构支持和编程技术 3.在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：应用程序的高层特性 如数据的分配，并行算法的结构以及在空间和如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。时间上对数据的访问模式等。依据应用特点可把多机工作负载大致分成两类：q单个程序在多处理机上的并行工作负载单个程序在多处理机上的并行工作负载q多个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载2424/15

20、6/15610.1 引 言4.并行程序的计算通信比率反映并行程序性能的一个重要的度量：计算与通信的比率计算与通信的比率计算通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而减少。2525/156/156多个处理器共享一个存储器。当处理机规模较小时，这种计算机十分经济。近些年，能在一个单独的芯片上实现28个处理器核。例如：例如：Sun公司公司 2006年年 T1 8核核的多处理器的多处理器支持对共享数据和私有数据的Cache缓存 私有数据供一个单独的处理器使用，而共享私有数据供一个单独的处理器使用，而共享数据则是供多个处理器使用。数据则是供多个处理器使用。共享数据进入Cache产生了一

21、个新的问题 CacheCache的一致性问题的一致性问题10.2 对称式共享存储器系统结构2626/156/15610.2 对称式共享存储器系统结构1.多处理机的Cache一致性问题允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致。例由两个处理器（由两个处理器（A和和B）读写引起的）读写引起的Cache一致性问题一致性问题 10.2.1 多处理机Cache一致性2828/156/15610.2 对称式共享存储器系统结构2.存储器的一致性 如果对某个数据

22、项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。存储系统行为的两个不同方面qWhat:What:读操作得到的是什么值读操作得到的是什么值qWhen:When:什么时候才能将已写入的值返回给读操作什么时候才能将已写入的值返回给读操作需要满足以下条件q处理器处理器P P对单元对单元X X进行一次写之后又对单元进行一次写之后又对单元X X进行读，进行读，读和写之间没有其它处理器对单元读和写之间没有其它处理器对单元X X进行写，则进行写，则P P读读到的值总是前面写进去的值。到的值总是前面写进去的值。2929/156/15610.2 对称式共享存储器系统结构q处理器处理器P P对单元

23、对单元X X进行写之后，另一处理器进行写之后，另一处理器Q Q对单元对单元X X进进行读，读和写之间无其它写，则行读，读和写之间无其它写，则Q Q读到的值应为读到的值应为P P写进写进去的值。去的值。q对同一单元的写是串行化的，即任意两个处理器对同对同一单元的写是串行化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度看来顺序都是一单元的两次写，从各个处理器的角度看来顺序都是相同的。相同的。(写串行化写串行化 )在后面的讨论中，我们假设：q直到所有的处理器均看到了写的结果，这个写操作才直到所有的处理器均看到了写的结果，这个写操作才算完成；算完成；q处理器的任何访存均不能改变写的顺序。就

24、是说，允处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但必须以程序规定的顺序许处理器对读进行重排序，但必须以程序规定的顺序进行写。进行写。3030/156/15610.2 对称式共享存储器系统结构在一致的多处理机中，Cache提供两种功能：共享数据的迁移 减少了对远程共享数据的访问延迟，也减少了减少了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。对共享存储器带宽的要求。共享数据的复制 不仅减少了访问共享数据的延迟，也减少了访问不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突。共享数据所产生的冲突。一般情况下，小规模多处理机是采用硬件的方法来实现

25、Cache的一致性。10.2.2 实现一致性的基本方案3131/156/15610.2 对称式共享存储器系统结构1.Cache一致性协议 在多个处理器中用来维护一致性的协议。关键：跟踪记录共享数据块的状态 两类协议（采用不同的技术跟踪共享数据的状态）q目录式协议目录式协议（directorydirectory）物理存储器中数据块的共享状态被保存在一个称物理存储器中数据块的共享状态被保存在一个称为目录的地方。为目录的地方。q监听式协议监听式协议（snoopingsnooping）n每个每个CacheCache除了包含物理存储器中块的数据拷贝之除了包含物理存储器中块的数据拷贝之外，也保存着各个块的

26、共享状态信息。外，也保存着各个块的共享状态信息。3232/156/15610.2 对称式共享存储器系统结构nCache通常连在共享存储器的总线上，当某个通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线需要访问存储器时，它会把请求放到总线上广播出去，其他各个上广播出去，其他各个Cache控制器通过监听总控制器通过监听总线（它们一直在监听）来判断它们是否有总线上线（它们一直在监听）来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。请求的数据块。如果有，就进行相应的操作。2.采用两种方法来解决Cache一致性问题。写作废协议 在处理器对某个数据项进行写入之

27、前，保证它拥在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。有对该数据项的唯一的访问权。(作废其它的副本作废其它的副本)例例 监听总线、写作废协议举例（采用写直达法）监听总线、写作废协议举例（采用写直达法）初始状态初始状态：CPU A、CPU B、CPU C都有都有X的副本。在的副本。在CPU A要对要对X进行写入时，需先作废进行写入时，需先作废CPU B和和CPU C中的副本，然后中的副本，然后再将再将p写入写入Cache A中的副本，同时用该数据更新主存单元中的副本，同时用该数据更新主存单元X。3434/156/15610.2 对称式共享存储器系统结构写更新协议 当一

28、个处理器对某数据项进行写入时，通过广播当一个处理器对某数据项进行写入时，通过广播使其它使其它CacheCache中所有对应于该数据项的副本进行更新。中所有对应于该数据项的副本进行更新。例例 监听总线、写更新协议举例（采用写直达法）监听总线、写更新协议举例（采用写直达法）假设：假设：3个个Cache都有都有X的副本。的副本。当当CPU A将数据将数据p写入写入Cache A中的副本时，将中的副本时，将p广播给所有的广播给所有的Cache，这些，这些Cache用用p更新其中的副本。更新其中的副本。由于这里是采用写直达法，所以由于这里是采用写直达法，所以CPU A还要将还要将p写入存储器中的写入存储

29、器中的X。如果采用写回法，则不需要写入存储器。如果采用写回法，则不需要写入存储器。3535/156/15610.2 对称式共享存储器系统结构3636/156/15610.2 对称式共享存储器系统结构写更新和写作废协议性能上的差别主要来自：q在对同一个数据进行多次写操作而中间无读操作的情在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作。协议只需一次作废操作。q在对同一在对同一CacheCache块的多个字进行写操作的情况下，写更块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要

30、进行一次广播，而写作新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。废协议仅在对该块的第一次写时进行作废操作即可。写作废是针对写作废是针对CacheCache块进行操作，而写更新则是针块进行操作，而写更新则是针对字（或字节）进行。对字（或字节）进行。q考虑从一个处理器考虑从一个处理器A A进行写操作后到另一个处理器进行写操作后到另一个处理器B B能能读到该写入数据之间的延迟时间。读到该写入数据之间的延迟时间。写更新协议的延迟时间较小。写更新协议的延迟时间较小。3737/156/15610.2 对称式共享存储器系统结构1.监听协议的基本实现技术实现监听

31、协议的关键有3个方面q处理器之间通过一个可以实现广播的互连机制相连。处理器之间通过一个可以实现广播的互连机制相连。通常采用的是总线。通常采用的是总线。q当一个处理器的当一个处理器的Cache响应本地响应本地CPU的访问时，如果它的访问时，如果它涉及到全局操作，其涉及到全局操作，其Cache控制器就要在获得总线的控控制器就要在获得总线的控制权后，在总线上发出相应的消息。制权后，在总线上发出相应的消息。q所有处理器都一直在监听总线，它们检测总线上的地址所有处理器都一直在监听总线，它们检测总线上的地址在它们的在它们的Cache中是否有副本。若有，则响应该消息，中是否有副本。若有，则响应该消息，并进行

32、相应的操作并进行相应的操作。10.2.3 监听协议的实现3838/156/15610.2 对称式共享存储器系统结构写操作的串行化：由总线实现 （获取总线控制权的顺序性）（获取总线控制权的顺序性）2.Cache发送到总线上的消息主要有以下两种：qRdMiss读不命中读不命中qWtMiss写不命中写不命中 需要通过总线找到相应数据块的最新副本，然后调入本地Cache中。q写直达写直达Cache：因为所有写入的数据都同时被写回主因为所有写入的数据都同时被写回主存，所以从主存中总可以取到其最新值。存，所以从主存中总可以取到其最新值。q对于对于写回写回Cache，得到数据的最新值会困难一些，因，得到数据

33、的最新值会困难一些，因为最新值可能在某个为最新值可能在某个Cache中，也可能在主存中。中，也可能在主存中。（后面的讨论中，只考虑写回法（后面的讨论中，只考虑写回法Cache）3939/156/15610.2 对称式共享存储器系统结构有的监听协议还增设了一条Invalidate消息，用来通知其他各处理器作废其Cache中相应的副本。q与与WtMiss的区别：的区别：Invalidate不引起调块不引起调块Cache的标识（tag）可直接用来实现监听。作废一个块只需将其有效位置为无效。给每个Cache块增设一个共享位q为为“1”：该块是被多个处理器所共享：该块是被多个处理器所共享q为为“0”：仅

34、被某个处理器所独占：仅被某个处理器所独占 块的拥有者：拥有该数据块的唯一副本的处理器。4040/156/15610.2 对称式共享存储器系统结构3.监听协议举例 在每个结点内嵌入一个有限状态控制器。q该控制器根据来自处理器或总线的请求以及该控制器根据来自处理器或总线的请求以及Cache块块的状态，做出相应的响应。的状态，做出相应的响应。每个数据块的状态取以下3种状态中的一种：q无效无效（简称（简称I）：）：Cache中该块的内容为无效。中该块的内容为无效。q共享共享（简称（简称S）：该块可能处于共享状态。）：该块可能处于共享状态。n在多个处理器中都有副本。这些副本都相同，在多个处理器中都有副本

35、。这些副本都相同，且与存储器中相应的块相同。且与存储器中相应的块相同。q已修改已修改（简称（简称M）：该块已经被修改过，并且还没写）：该块已经被修改过，并且还没写入存储器。入存储器。（块中的内容是最新的，系统中唯一的最新副本）（块中的内容是最新的，系统中唯一的最新副本）下面来讨论在各种情况下监听协议所进行的操作。响应来自处理器的请求q不发生替换的情况不发生替换的情况 写作废协议中（采用写回法），写作废协议中（采用写回法），Cache块的状态转换图块的状态转换图 4242/156/15610.2 对称式共享存储器系统结构q发生替换的情况发生替换的情况 写作废协议中（采用写回法），写作废协议中（采

36、用写回法），Cache块的状态转换图块的状态转换图 响应来自总线的请求q每个处理器都在监视总线上的消息和地址，当发现有与每个处理器都在监视总线上的消息和地址，当发现有与总线上的地址相匹配的总线上的地址相匹配的Cache块时，就要根据该块的状块时，就要根据该块的状态以及总线上的消息，进行相应的处理。态以及总线上的消息，进行相应的处理。写作废协议中（采用写回法），写作废协议中（采用写回法），Cache块的状态转换图块的状态转换图4444/156/15610.3 分布式共享存储器系统结构10.3.1 目录协议的基本思想广播和监听的机制使得监听一致性协议的可扩放性很差。寻找替代监听协议的一致性协议。（

37、采用目录协议）（采用目录协议）1.目录协议目录：一种集中的数据结构。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。4545/156/15610.3 分布式共享存储器系统结构q特点：特点：对于任何一个数据块，都可以快速地在唯一的对于任何一个数据块，都可以快速地在唯一的一个位置中找到相关的信息。这使一致性协议避免了一个位置中找到相关的信息。这使一致性协议避免了广播操作。广播操作。位向量：记录哪些Cache中有副本。q每一位对应于一个处理器。每一位对应于一个处理器。q长度与处理器的个数成正比。长度与处理器的个数成正比。

38、q由位向量指定的处理机的集合称为由位向量指定的处理机的集合称为共享集共享集S。分布式目录q目录与存储器一起分布到各结点中，从而对于不同目目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。录内容的访问可以在不同的结点进行。q 对每个结点增加目录后的分布式存储器多处理机对每个结点增加目录后的分布式存储器多处理机4747/156/15610.3 分布式共享存储器系统结构目录法最简单的实现方案：对于存储器中每一块都在目录中设置一项。目录中的信息量与MN成正比。其中：其中：qM：存储器中存储块的总数量存储器中存储块的总数量qN：处理器的个数处理器的个数q由于由于M=KN，K

39、是每个处理机中存储块的数量，所是每个处理机中存储块的数量，所以如果以如果K保持不变，则目录中的信息量就与保持不变，则目录中的信息量就与N2成正比。成正比。4848/156/15610.3 分布式共享存储器系统结构2.在目录协议中，存储块的状态有3种：未缓冲：该块尚未被调入Cache。所有处理器的Cache中都没有这个块的副本。共享：该块在一个或多个处理机上有这个块的副本，且这些副本与存储器中的该块相同。独占：仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，所以其内容是最新的，而存储器中该块的数据已过时。这个处理机称为该这个处理机称为该块的拥有者块的拥有者。4949/156/156

40、10.3 分布式共享存储器系统结构3.本地结点、宿主结点以及远程结点的关系 q本地结点：本地结点：发出访问请求的结点发出访问请求的结点 q宿主结点：宿主结点：包含所访问的存储单元及其目录项的结点包含所访问的存储单元及其目录项的结点 q远程结点远程结点可以和宿主结点是同一个结点，也可以不是可以和宿主结点是同一个结点，也可以不是同一个结点。同一个结点。CPUCache本地结点APCache远程结点C宿主结点B(Home)副本副本目录目录存储器存储器宿主结点：宿主结点：存放有对应地址的存储器块和目录项的结点存放有对应地址的存储器块和目录项的结点 K5151/156/15610.3 分布式共享存储器系

41、统结构4.在结点之间发送的消息本地结点发给宿主结点（目录）的消息 说明：括号中的内容表示所带参数。说明：括号中的内容表示所带参数。P P：发出请求的处理机编号：发出请求的处理机编号 K K：所要访问的地址：所要访问的地址qRdMiss（P，K）处理机处理机P读取地址为读取地址为A的数据时不命中，请求宿的数据时不命中，请求宿主结点提供数据（块），并要求把主结点提供数据（块），并要求把P加入共享集。加入共享集。qWtMiss（P，K）处理机处理机P对地址对地址A进行写入时不命中，请求宿主进行写入时不命中，请求宿主结点提供数据，并使结点提供数据，并使P成为所访问数据块的独占者。成为所访问数据块的独占

42、者。5252/156/15610.3 分布式共享存储器系统结构qInvalidate（K）请求向所有拥有相应数据块副本（包含地址请求向所有拥有相应数据块副本（包含地址K）的远程的远程Cache发发Invalidate消息，作废这些副本。消息，作废这些副本。宿主结点（目录）发送给远程结点的消息qInvalidate（K）作废远程作废远程Cache中包含地址中包含地址K的数据块。的数据块。qFetch（K）从远程从远程Cache中取出包含地址中取出包含地址K的数据块，并将的数据块，并将之送到宿主结点。把远程之送到宿主结点。把远程Cache中那个块的状态改为中那个块的状态改为“共享共享”。qFetc

43、h&Inv（K）5353/156/15610.3 分布式共享存储器系统结构q从远程从远程Cache中取出包含地址中取出包含地址K的数据块，并将之送的数据块，并将之送到宿主结点。然后作废远程到宿主结点。然后作废远程Cache中的那个块。中的那个块。宿主结点发送给本地结点的消息 DReply（D）qD表示数据内容。表示数据内容。q把从宿主存储器获得的数据返回给本地把从宿主存储器获得的数据返回给本地Cache。远程结点发送给宿主结点的消息 WtBack（K，D）q把远程把远程Cache中包含地址中包含地址K的数据块写回到宿主结点的数据块写回到宿主结点中，中，该消息是远程结点对宿主结点发来的该消息是远

44、程结点对宿主结点发来的“取数据取数据”或或“取取/作废作废”消息的响应。消息的响应。5454/156/15610.3 分布式共享存储器系统结构本地结点发送给被替换块的宿主结点的消息qMdSharer（P，K）用于当本地用于当本地Cache中需要替换一个包含地址中需要替换一个包含地址K的的块、且该块未被修改过的情况。这个消息发给该块的块、且该块未被修改过的情况。这个消息发给该块的宿主结点，请求它将宿主结点，请求它将P从共享集中删除。如果删除后从共享集中删除。如果删除后共享集变为空集，则宿主结点还要将该块的状态改变共享集变为空集，则宿主结点还要将该块的状态改变为为“未缓存未缓存”（U）。）。qWt

45、Back2（P，K，D）用于当本地用于当本地Cache中需要替换一个包含地址中需要替换一个包含地址K的的块、且该块已被修改过的情况。这个消息发给该块的块、且该块已被修改过的情况。这个消息发给该块的宿主结点，完成两步操作：宿主结点，完成两步操作：把该块写回；把该块写回；进行与进行与MdSharer相同的操作。相同的操作。5555/156/15610.3 分布式共享存储器系统结构在基于目录的协议中，目录承担了一致性协议操作的主要功能。q本地结点把请求发给宿主结点中的目录，再由目录控本地结点把请求发给宿主结点中的目录，再由目录控制器有选择地向远程结点发出相应的消息。制器有选择地向远程结点发出相应的消

46、息。q发出的消息会产生发出的消息会产生两种不同类型的动作：两种不同类型的动作：n更新目录状态更新目录状态n使远程结点完成相应的操作使远程结点完成相应的操作10.3.2 目录协议实例5656/156/15610.3 分布式共享存储器系统结构1.在基于目录协议的系统中，Cache块的状态转换图。响应本地Cache CPU请求 M MCPUCPU读不命中读不命中/发发 WtBack2WtBack2，发，发RdMissRdMissCPUCPU写不命中写不命中/发发MdSharerMdSharer，发发WtMissWtMissCPUCPU写命中写命中/发发InvalidateInvalidateS SC

47、PUCPU读命中读命中CPUCPU写命中写命中CPUCPU写不命中写不命中/发发WtBack2WtBack2，发，发WtMissWtMissCPUCPU读命中读命中CPUCPU读不命中读不命中/发发MdSharerMdSharer，发发RdMissRdMissI ICPUCPU写写/发发WtMissWtMissCPUCPU读读/发发RdMissRdMiss5757/156/15610.3 分布式共享存储器系统结构远程结点中Cache块响应来自宿主结点的请求的状态转换图 M MS SI IFetch&Inv/Fetch&Inv/发发WtBackWtBackFetch/Fetch/发发WtBack

48、WtBackInvalidateInvalidate5858/156/15610.3 分布式共享存储器系统结构2.目录的状态转换及相应的操作 如前所述：q目录中存储器块的状态有目录中存储器块的状态有3种种n未缓存未缓存n共享共享n独占独占q位向量位向量记录拥有其副本的处理器的集合。这个集合称记录拥有其副本的处理器的集合。这个集合称为为共享集合共享集合。q对于从本地结点发来的请求，目录所进行的操作包括：对于从本地结点发来的请求，目录所进行的操作包括：5959/156/15610.3 分布式共享存储器系统结构n向远程结点发送消息以完成相应的操作。这些向远程结点发送消息以完成相应的操作。这些远程结点

49、由共享集合指出；远程结点由共享集合指出；n修改目录中该块的状态；修改目录中该块的状态；n更新共享集合。更新共享集合。目录可能接收到3种不同的请求q读不命中读不命中q写不命中写不命中q数据写回数据写回 （假设这些操作是原子的）（假设这些操作是原子的）6060/156/156目录的状态转换及相应的操作目录的状态转换及相应的操作 10.3 分布式共享存储器系统结构E ERdMiss/RdMiss/S SWtMiss/WtMiss/发发Fetch&InvFetch&Inv，U UDReplyDReply，共享集，共享集PP发发DReplyDReply，共享集，共享集PPRdMiss/RdMiss/发发

50、FetchFetch，DReplyDReply，把，把P P加入共享集加入共享集WtMiss/WtMiss/发发InvalidateInvalidate，DReplyDReply，共享集，共享集PPWtBack/WtBack/共享集共享集 WtMiss/WtMiss/发发DReplyDReply，共享集共享集PPU U：未缓存（：未缓存（UncachedUncached）S S：共享（：共享（SharedShared）：只读）：只读E E：独占（：独占（ExclusiveExclusive）：可读写）：可读写 P P：本地处理器：本地处理器6161/156/15610.3 分布式共享存储器系统