1、第八章第八章多处理机多处理机Computer Architecture并行计算机在未来将会发挥更大的作用并行计算机在未来将会发挥更大的作用?1.获得超过单处理器的性能，最直接的方法就是把获得超过单处理器的性能，最直接的方法就是把 多个处理器连在一起；多个处理器连在一起；2.自自1985年以来，体系结构的改进使性能迅速提高，年以来，体系结构的改进使性能迅速提高，这种改进的速度能否持续下去还不清楚，但通过这种改进的速度能否持续下去还不清楚，但通过 复杂度和硅技术的提高而得到的性能的提高正在复杂度和硅技术的提高而得到的性能的提高正在 减小；减小；3.并行计算机应用软件已有缓慢但稳定的发展。并行计算机
2、应用软件已有缓慢但稳定的发展。8.1 8.1 引引 言言Computer Architecture本章重点本章重点:中小规模的机器中小规模的机器 (处理器的个数处理器的个数128)（多处理机设计的主流）（多处理机设计的主流）8.1.1 并行计算机体系结构的分类并行计算机体系结构的分类1.按照按照Flynn分类法，可把计算机分成分类法，可把计算机分成 单指令流单数据流（单指令流单数据流（SISD）单指令流多数据流（单指令流多数据流（SIMD）多指令流单数据流（多指令流单数据流（MISD）多指令流多数据流（多指令流多数据流（MIMD）8.1 8.1 引引 言言Computer Architectu
3、re2.MIMD已成为通用多处理机体系结构的选择，原因已成为通用多处理机体系结构的选择，原因：(1)MIMD具有灵活性具有灵活性 高性能单用户机高性能单用户机 多道程序机器多道程序机器 (2)MIMD可以充分利用商品化微处理器在性能价格可以充分利用商品化微处理器在性能价格 比方面的优势。比方面的优势。8.1 8.1 引引 言言Computer Architecture3.按存储器的结构和互连策略，可按存储器的结构和互连策略，可把现有的把现有的MIMD机机器分为两类器分为两类（与多处理机系统中处理器个数的多少有关）（与多处理机系统中处理器个数的多少有关）(1)集中式共享存储器结构集中式共享存储器
4、结构 这类机器有时被称为这类机器有时被称为 SMP机器（机器（Symmetric shared-memory MultiProcessor）UMA机器（机器（Uniform Memory Access）8.1 8.1 引引 言言Computer Architecture CPU0Cache CPU1 Cache CPU2 Cache CPU3 Cache 存储器 I/O 适用于处理机数目不大情况。适用于处理机数目不大情况。8.1 8.1 引引 言言Computer Architecture(2)分布式存储器结构分布式存储器结构 每个结点包含：每个结点包含：处理器处理器 存储器存储器 IO 在许
5、多情况下，分布式存储器结构优于采用在许多情况下，分布式存储器结构优于采用 集中式共享存储器结构。集中式共享存储器结构。分布式存储器结构需要高带宽的互连。分布式存储器结构需要高带宽的互连。8.1 8.1 引引 言言Computer Architecture 互连网络 I/o 存储器 I/o 存储器 I/o 存储器 I/o 存储器 CPU0 Cache CPU1 Cache CPU2 Cache CPU3 Cache 存储器 I/o 存储器 I/o 存储器 I/o 存储器 I/o CPU4 Cache CPU5 Cache CPU6 Cache CPU7 Cache 适用于处理机数目较大情况。适用
6、于处理机数目较大情况。8.1 8.1 引引 言言Computer Architecture 分布式存储器结构的优点分布式存储器结构的优点(1)如果大多数的访问是针对本结点的局部存储器，如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；则可降低对存储器和互连网络的带宽要求；(2)对局部存储器的访问延迟低。对局部存储器的访问延迟低。主要缺点主要缺点 处理器之间的通信较为复杂，且各处理器之间处理器之间的通信较为复杂，且各处理器之间 访问延迟较大访问延迟较大（显式通信）（显式通信）;需要高带宽的互连。需要高带宽的互连。簇：簇：超结点超结点-每个结点有多个处理器每个结点有多
7、个处理器(2 8)8.1 8.1 引引 言言Computer Architecture8.1.2 通信模型和存储器的结构模型通信模型和存储器的结构模型1.两种地址空间的组织方案两种地址空间的组织方案 (1)物理上分离的多个存储器可作为一个逻辑上共物理上分离的多个存储器可作为一个逻辑上共 享的存储空间进行编址。享的存储空间进行编址。这类机器的结构被称为这类机器的结构被称为q分布式共享存储器结构分布式共享存储器结构 （DSM:Distributed Shared-Memory)q 可缩放共享存储器结构可缩放共享存储器结构 （SSM:Scalable Shared-Memory)q NUMA机器机器
8、 （NUMA:Non-Uniform Memory Access)8.1 8.1 引引 言言Computer Architecture (2)整个地址空间由多个独立的地址空间构成，它整个地址空间由多个独立的地址空间构成，它 们在逻辑上也是独立的，远程的处理器不能对们在逻辑上也是独立的，远程的处理器不能对 其直接寻址。其直接寻址。8.1 8.1 引引 言言 每一个处理器每一个处理器-存储器模块实际上是一个存储器模块实际上是一个单独的计算机，这种机器也称为多计算机。单独的计算机，这种机器也称为多计算机。Computer Architecture2.两种通信模型两种通信模型 共享地址空间的机器共享地
9、址空间的机器 利用利用 Load 和和 Store 指令中的地址隐含地指令中的地址隐含地 进行数据通讯。进行数据通讯。多个地址空间的机器多个地址空间的机器 通过处理器间显式地传递消息完成。通过处理器间显式地传递消息完成。8.1 8.1 引引 言言这种机器常称为这种机器常称为消息传递机器。消息传递机器。Computer Architecture 消息传递计算机通过传递消息来请求某些消息传递计算机通过传递消息来请求某些服务或传输数据，从而完成通信。服务或传输数据，从而完成通信。例：例：一个处理器要对远程存储器上的数据进行一个处理器要对远程存储器上的数据进行 访问或操作访问或操作 (1)发送消息，请
10、求传递数据或对数据进行操作；发送消息，请求传递数据或对数据进行操作；远程进程调用远程进程调用(RPC，remote process call)(2)目的处理器接收到消息以后，执行相应的操目的处理器接收到消息以后，执行相应的操 作或代替远程处理器进行访问，并发送一个作或代替远程处理器进行访问，并发送一个 应答消息将结果返回。应答消息将结果返回。8.1 8.1 引引 言言Computer Architecture 同步消息传递同步消息传递 请求处理器发送一个请求后一直要等到应答请求处理器发送一个请求后一直要等到应答 结果才继续运行。结果才继续运行。异步消息传递异步消息传递 发送方不先经请求就直接把
11、数据送往数据接发送方不先经请求就直接把数据送往数据接 受方。受方。3.通信机制的三个关键的性能指标：通信机制的三个关键的性能指标：1.通信带宽通信带宽 理想状态下的通信带宽受限于处理器、存储理想状态下的通信带宽受限于处理器、存储 器和互连网络的带宽。器和互连网络的带宽。8.1 8.1 引引 言言Computer Architecture2.通信延迟通信延迟通信延迟发送开销跨越时间传输延迟接收开销通信延迟发送开销跨越时间传输延迟接收开销理想状态下通信延迟应尽可能地小。理想状态下通信延迟应尽可能地小。3.通讯延迟的隐藏程度通讯延迟的隐藏程度 如何才能较好地将通信和计算或多次通信之如何才能较好地将通
12、信和计算或多次通信之 间重叠起来，以实现间重叠起来，以实现通讯延迟的隐藏通讯延迟的隐藏。通常的原则是：通常的原则是：只要可能就隐藏延迟只要可能就隐藏延迟。通信延迟隐藏是一种提高性能的有效途径，但它对通信延迟隐藏是一种提高性能的有效途径，但它对 操作系统和编程者来讲增加了额外的负担。操作系统和编程者来讲增加了额外的负担。8.1 8.1 引引 言言Computer Architecture4.不同通信机制的优点不同通信机制的优点 1.共享存储器通信的主要优点共享存储器通信的主要优点 (1)与常用的集中式共享存储器结构使用的通信机制与常用的集中式共享存储器结构使用的通信机制 兼容。兼容。(2)当处理
13、器通信活动方式复杂或动态变化时易于当处理器通信活动方式复杂或动态变化时易于 编程，同时在简化编译器设计方面也占有优势。编程，同时在简化编译器设计方面也占有优势。(3)当通信数据较小时，通信开销较低，带宽利用当通信数据较小时，通信开销较低，带宽利用 较好较好.(4)通过硬件控制的通过硬件控制的 Cache 减少了远程通信的频度，减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。减少了通信延迟以及对共享数据的访问冲突。8.1 8.1 引引 言言Computer Architecture2.消息传递通信机制的主要优点消息传递通信机制的主要优点 (1)硬件较简单。硬件较简单。(2)通信是显
14、式的，从而引起编程者和编译程序通信是显式的，从而引起编程者和编译程序 的注意，着重处理开销大的通信。的注意，着重处理开销大的通信。另外另外 在共享存储器上支持消息传递相对简单：在共享存储器上支持消息传递相对简单：将消息传递实现时转换成远端内存访问。将消息传递实现时转换成远端内存访问。在消息传递的硬件上支持共享存储器就非常困难：在消息传递的硬件上支持共享存储器就非常困难：所有对共享存储器的访问均要求操作系统提供地所有对共享存储器的访问均要求操作系统提供地 址转换和存储保护功能，址转换和存储保护功能，将存储器访问转换为消将存储器访问转换为消 息的发送和接收息的发送和接收。8.1 8.1 引引 言言
15、Computer Architecture8.1.3 并行处理面临的挑战并行处理面临的挑战 并行处理面临着两个重要的挑战：并行处理面临着两个重要的挑战：程序中有限的并行性程序中有限的并行性 相对较高的通信开销相对较高的通信开销8.1 8.1 引引 言言1.有限的并行性使机器要达到好的加速比十分困难有限的并行性使机器要达到好的加速比十分困难Computer Architecture例例 如果想用如果想用100个处理器达到个处理器达到80的加速比，的加速比，求原计算程序中串行部分所占比例。求原计算程序中串行部分所占比例。解解 Amdahl定律为定律为加速比加速比得出：得出：并行比例并行比例0.99
16、75 可以看出要用可以看出要用100个处理器达到个处理器达到80的加速比，串行计的加速比，串行计算的部分只能占算的部分只能占0.25%。1可加速部分比例可加速部分比例理论加速比理论加速比（1可加速部分比例）可加速部分比例）801并行比例并行比例100（1并行比例）并行比例）8.1 8.1 引引 言言Computer Architecture2.面临的第二个挑战主要是指多处理机中远程访面临的第二个挑战主要是指多处理机中远程访 问的较大延迟。问的较大延迟。在现有的机器中，处理器之间的数据通信在现有的机器中，处理器之间的数据通信 大约需要大约需要1001000个时钟周期。个时钟周期。8.1 8.1
17、引引 言言远程访问一个字的延迟时间远程访问一个字的延迟时间 计算机类型计算机类型 通信通信机制机制 互连网络互连网络 处理机处理机最大数量最大数量 典型远程存储器典型远程存储器访问时间（访问时间（ns）Sun Starfire servers SMP 多总线多总线 64 500 SGI Origin 3000 NUMA 胖超立方体胖超立方体 512 500 Cray T3E NUMA 3维环网维环网 2048 300 HP V series SMP 88交叉开关交叉开关 32 1000 HP AlphaServer GS SMP 开关总线开关总线 32 400 Computer Archite
18、cture8.1 8.1 引引 言言 例例8.2 假设有一台假设有一台32个处理器的多处理机，个处理器的多处理机，对远程存储器访问时间为对远程存储器访问时间为400 ns。除了通信以。除了通信以外，假设所有其他访问均命中局部存储器。外，假设所有其他访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处当发出一个远程请求时，本处理器挂起。处理器的时钟频率为理器的时钟频率为1 GHz，如果指令基本的，如果指令基本的IPC为为2（设所有访存均命中（设所有访存均命中Cache），求在没），求在没有远程访问的情况下和有有远程访问的情况下和有0.2%的指令需要远的指令需要远程访问的情况下，前者比后者
19、快多少程访问的情况下，前者比后者快多少?Computer Architecture8.1 8.1 引引 言言解解 没有远程访问时，机器的没有远程访问时，机器的CPI为为 1/基本基本IPC=1/2=0.5 有有0.2%远程访问的机器的实际远程访问的机器的实际CPI为为 CPI基本基本CPI远程访问率远程访问率远程访问开销远程访问开销 0.50.2%远程访问开销远程访问开销 远程访问开销为远程访问开销为 远程访问时间远程访问时间/时钟周期时间时钟周期时间400 ns/1 ns400个个时钟周期时钟周期 CPI0.50.2%4001.3 因此在没有远程访问的情况下的计算机速度是有因此在没有远程访问
20、的情况下的计算机速度是有0.2%远程访问的计算机速度的远程访问的计算机速度的1.3/0.5=2.6倍倍。Computer Architecture 问题的解决问题的解决 并行性不足：并行性不足：通过采用并行性更好的算法来解决通过采用并行性更好的算法来解决 远程访问延迟的降低：远程访问延迟的降低：靠体系结构支持和编程技术靠体系结构支持和编程技术 8.1 8.1 引引 言言Computer Architecture8.1 8.1 引引 言言3.在并行处理中，影响性能（负载平衡、同步和存在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：储器访问延迟等）的关键因素常依赖于：
21、应用程序的高层特性应用程序的高层特性 如数据的分配，并行算法的结构以及如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。在空间和时间上对数据的访问模式等。依据应用特点可把多机工作负载大致分成两类：依据应用特点可把多机工作负载大致分成两类：单个程序在多处理机上的并行工作负载单个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载Computer Architecture3.并行程序的计算通信比率并行程序的计算通信比率 反映并行程序性能的一个重要的度量反映并行程序性能的一个重要的度量 计算通信比率计算通信比率 随着处理数据规模的增大而增
22、加，随着处理数据规模的增大而增加，随着处理器数目的增加而降低。随着处理器数目的增加而降低。8.1 8.1 引引 言言Computer Architecture 多个处理器共享一个存储器。多个处理器共享一个存储器。当处理器规模较小时，这种机器十分经济。当处理器规模较小时，这种机器十分经济。支持对共享数据和私有数据的支持对共享数据和私有数据的 Cache 缓存。缓存。私有数据供一个单独的处理器使用，而共私有数据供一个单独的处理器使用，而共 享数据供多个处理器使用。享数据供多个处理器使用。共享数据进入共享数据进入Cache产生了一个新的问题：产生了一个新的问题：Cache的一致性问题的一致性问题8.
23、2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构Computer Architecture8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构 不一致产生的原因（不一致产生的原因（Cache一致性问题）一致性问题）IO操作操作 Cache中的内容可能与由中的内容可能与由IO子系统子系统输入输入/输出形成的存储器对应部分的内输出形成的存储器对应部分的内容不同。容不同。共享数据共享数据 不同处理器的不同处理器的Cache都保存有对应存储都保存有对应存储器单元的内容。器单元的内容。8.2.1 多处理机多处理机Cache一致性一致性由两个处理器（由两个处理器（A和和B）读写引起
24、的）读写引起的Cache一致性问题一致性问题 时间时间 事件事件 CPU A Cache 内容内容 CPU B Cache 内容内容 X单元存储器单元存储器内容内容 011 CPU A读读X 112 CPU B读读X 1113 CPU A将将0存入存入X 010Computer Architecture存储器是一致的存储器是一致的（非正式地定义）（非正式地定义）如果对某个数据项的任何读操作均可得到其最如果对某个数据项的任何读操作均可得到其最 新写入的值，则认为这个新写入的值，则认为这个存储系统是一致的。存储系统是一致的。满足条件满足条件 处理器处理器P对对X进行一次写之后又对进行一次写之后又对
25、X进行读，读和写进行读，读和写 之间没有其它处理器对之间没有其它处理器对X进行写，则读的返回值总进行写，则读的返回值总 是写进的值。是写进的值。一个处理器对一个处理器对X进行写之后进行写之后足够时间足够时间，另一处理器，另一处理器 对对X进行读，读和写之间无其它写，则读进行读，读和写之间无其它写，则读X的返回的返回 值应为写进的值。值应为写进的值。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构Computer Architecture 对同一单元的写是顺序化的，即任意两个处理器对对同一单元的写是顺序化的，即任意两个处理器对 同一单元的两次写，从所有处理器看来顺序都应是同一单元
26、的两次写，从所有处理器看来顺序都应是 相同的。相同的。足够时间？足够时间？简单处理方法：简单处理方法：所有的处理器均能看到写的结果所有的处理器均能看到写的结果 =直到所有的处理器均看到了写的结果，一次写直到所有的处理器均看到了写的结果，一次写 操作才算完成；操作才算完成；8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构Computer Architecture8.2.2 实现一致性的基本方案实现一致性的基本方案 在一致的多处理机中，在一致的多处理机中，Cache对共享数据提供对共享数据提供两种功能：两种功能：共享数据的迁移共享数据的迁移 降低了对远程共享数据的访问延迟。降低了对
27、远程共享数据的访问延迟。共享数据的复制共享数据的复制 不仅降低了访存的延迟，也减少了访问共不仅降低了访存的延迟，也减少了访问共 享数据所产生的冲突。享数据所产生的冲突。实现实现Cache一致性的目的：一致性的目的：确保上述两种功能实现过程中不会出现确保上述两种功能实现过程中不会出现Cache的不的不一致。一致。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构Computer Architecture实现方法：实现方法：Cache一致性协议一致性协议实现技术：实现技术：小规模多处理机不是采用软件而是采用小规模多处理机不是采用软件而是采用 硬件技术实现硬件技术实现Cache一致性。
28、一致性。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构Computer Architecture Cache一致性协议一致性协议:对多个处理器维护一致性的协议对多个处理器维护一致性的协议 协议实现基础：协议实现基础：跟踪共享数据块的状态跟踪共享数据块的状态 两类跟踪共享数据块状态的协议两类跟踪共享数据块状态的协议 目录目录 物理存储器中共享数据块的状态及相关信息均被物理存储器中共享数据块的状态及相关信息均被 保存在一个称为目录的地方。保存在一个称为目录的地方。监听监听 每个每个Cache除了包含物理存储器中块的数据拷贝之除了包含物理存储器中块的数据拷贝之 外，也保存着各个块的
29、共享状态信息。外，也保存着各个块的共享状态信息。Cache通常通常 连在共享存储器的总线上，各个连在共享存储器的总线上，各个Cache控制器通过控制器通过 监听总线来判断它们是否有总线上请求的数据块。监听总线来判断它们是否有总线上请求的数据块。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构3.两种协议两种协议 (1)写作废协议写作废协议 在一个处理器写某个数据项之前保证它对该数据项在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权，使别的拷贝作废。有唯一的访问权，使别的拷贝作废。例例 在写回在写回Cache的条件下，监听总线中写作废协议的实的条件下，监听总线中写作废协
30、议的实现。现。处理器行为处理器行为总线行为总线行为CPU A Cache内容内容CPU B Cache内容内容主 存主 存 X单 元 内单 元 内容容 0 CPU A 读读X Cache失效失效 0 0 CPU B 读读X Cache失效失效 0 0 0CPUA将将X单元单元写写1 作废作废X单元单元 1 0 CPU B 读读X Cache失效失效 1 1 1(2)写更新协议写更新协议 当一个处理器写某数据项时，通过广播使其它当一个处理器写某数据项时，通过广播使其它Cache中所有对应的该数据项拷贝进行更新。中所有对应的该数据项拷贝进行更新。例例 在写回在写回Cache的条件下，监听总线中写更
31、新协议的实的条件下，监听总线中写更新协议的实现。现。处理器行为处理器行为总线行为总线行为CPUA Cache内容内容CPUB Cache内容内容主存主存X单元内单元内容容 0 CPU A 读读XCach失效失效 0 0 CPU B 读读XCach失效失效 0 0 0CPUA将将X单单元写元写1广播写广播写X单单元元 1 1 1 CPU B 读读X 1 1 1 Computer Architecture(3)写更新和写作废协议性能上的差别写更新和写作废协议性能上的差别 对同一数据的多个写而中间无读操作的情况，对同一数据的多个写而中间无读操作的情况，写更新协议需进行多次写广播操作，而在写写更新协议
32、需进行多次写广播操作，而在写 作废协议下只需一次作废操作。作废协议下只需一次作废操作。对同一块中多个字进行写，写更新协议对每对同一块中多个字进行写，写更新协议对每 个字的写均要进行一次广播，而在写作废协个字的写均要进行一次广播，而在写作废协 议下仅在对本块第一次写时进行作废操作。议下仅在对本块第一次写时进行作废操作。从一个处理器写到另一个处理器读之间的延从一个处理器写到另一个处理器读之间的延 迟通常在写更新模式中较低。而在写作废协议迟通常在写更新模式中较低。而在写作废协议 中，需要读一个新的拷贝。中，需要读一个新的拷贝。*在基于总线的多处理机中，写作废协议成为绝大在基于总线的多处理机中，写作废
33、协议成为绝大多数系统设计的选择。多数系统设计的选择。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构Computer Architecture8.2.3 监听协议的基本实现过程监听协议的基本实现过程 小规模多处理机中实现写作废协议为例小规模多处理机中实现写作废协议为例 进行写操作时进行写操作时:1)获得总线控制权获得总线控制权 2)将要作废的数据块地址发在总线上将要作废的数据块地址发在总线上 3)其他处理器一直监听总线，若它们的其他处理器一直监听总线，若它们的Cache 中含有要作废的块，则作废该块中含有要作废的块，则作废该块*获得总线控制权的顺序性保证了写的顺序性获得总线控制
34、权的顺序性保证了写的顺序性(唯一访唯一访问权问权)8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构Computer Architecture进行读操作时进行读操作时:如果如果Cache命中，从命中，从Cache中获得数据中获得数据如果如果Cache不命中：不命中：(1)写直达写直达Cache，因为所有写的数据同时被写回因为所有写的数据同时被写回 主存，则从主存中总可以取到最新的数据值。主存，则从主存中总可以取到最新的数据值。(2)对于写回对于写回Cache，得到数据的最新值会困难一得到数据的最新值会困难一 些，因为些，因为最新值可能在某个最新值可能在某个Cache中，也可能中，
35、也可能 在主存中在主存中-同样需要使用监听机制，如果某同样需要使用监听机制，如果某 个处理器发现它有被读请求的块的被修改拷贝个处理器发现它有被读请求的块的被修改拷贝 则需提供该块数据，并阻止请求方对内存的访则需提供该块数据，并阻止请求方对内存的访 问。问。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构Computer Architecture8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构 在写回法在写回法Cache条件下的实现技术条件下的实现技术 Cache的标识（的标识（tag）用于实现监听。）用于实现监听。作废一个块只需将其有效位（作废一个块只需将其有效
36、位（valid）置）置 为无效。为无效。给每个给每个Cache块加一个特殊的状态位。块加一个特殊的状态位。状态：状态：共享共享（shared）专有专有（exclusive）clean dirty Cache块的拥有者块的拥有者：拥有唯一的：拥有唯一的Cache块副块副本的处理器。本的处理器。Computer Architecture8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构 在每个结点内嵌入一个在每个结点内嵌入一个Cache状态控制器。状态控制器。控制器根据来自处理器或总线的控制器根据来自处理器或总线的请求，改变所选择的数据块的状态。请求，改变所选择的数据块的状态。因为每
37、次总线操作均要检查因为每次总线操作均要检查Cache的地址的地址标识，这可能会影响标识，这可能会影响CPU对对Cache的访问。的访问。可通过下列两种技术之一来减少影响可通过下列两种技术之一来减少影响：复制标志位复制标志位采用多级包容采用多级包容Cache（许多系统采用）（许多系统采用）Computer Architecture通常结构：通常结构：存储器分布于各结点中，所有的结点通过网存储器分布于各结点中，所有的结点通过网 络互连。访问可以是本地的，也可是远程的。络互连。访问可以是本地的，也可是远程的。一般不支持一般不支持Cache一致性一致性,规定共享数据不规定共享数据不 进入进入Cache
38、，仅私有数据才能保存在，仅私有数据才能保存在Cache中。中。优点：优点：所需的硬件支持很少所需的硬件支持很少 (因为远程访问存取量仅是一个字因为远程访问存取量仅是一个字(或双字或双字)而而 不是一个不是一个Cache块块)8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构Computer Architecture缺点：缺点：(1)许多情况下编译器无法确切知道哪些数据当许多情况下编译器无法确切知道哪些数据当 前共享前共享;(2)当每次访问要从远程存储器取一个字时，不能有当每次访问要从远程存储器取一个字时，不能有 效利用共享数据的空间局部性效利用共享数据的空间局部性;(3)诸如预取
39、等延迟隐藏技术对于多个字的存取诸如预取等延迟隐藏技术对于多个字的存取 更为有效，比如针对一个更为有效，比如针对一个Cache块的预取。块的预取。8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构解决解决Cache一致性问题的关键：一致性问题的关键：寻找替代监听协议的一致性协议寻找替代监听协议的一致性协议:目录协议目录协议8.3.1 基于目录的基于目录的Cache一致性一致性目录协议目录协议 目录：目录：一种专用的数据结构，用于记录可一种专用的数据结构，用于记录可以进入以进入C
40、ache的每个数据块的状态、哪些的每个数据块的状态、哪些处理器有该块的副本以及是否修改过等信处理器有该块的副本以及是否修改过等信息。息。分布式目录分布式目录 如何将支持如何将支持Cache一致性的共享存储器模式扩展一致性的共享存储器模式扩展到可扩缩的大规模多处理机系统到可扩缩的大规模多处理机系统?Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构目录与存储器一起分布到各结点中，从目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同而对于不同目录内容的访问可以在不同的结点进行。的结点进行。存储块的共享状态信息在唯一的一个固存
41、储块的共享状态信息在唯一的一个固定单元中找到。这使一致性协议避免了定单元中找到。这使一致性协议避免了广播操作。广播操作。对每个结点增加目录表后的分布式存储对每个结点增加目录表后的分布式存储器多处理机的系统结构。器多处理机的系统结构。互连网络 I/o 存储器 I/o 存储器 I/o 存储器 I/o 存储器 CPU0 Cache CPU1 Cache CPU2 Cache CPU3 Cache 存储器 I/o 存储器 I/o 存储器 I/o 存储器 I/o CPU4 Cache CPU5 Cache CPU6 Cache CPU7 Cache 目 录 目 录 目 录 目 录 目 录 目 录 目 录
42、 目 录 Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构目录协议必须完成两种目录协议必须完成两种主要的操作：主要的操作：处理读失效处理读失效 处理对共享、干净（处理对共享、干净（clean）块的写）块的写 一个共享块的写失效处理可用这两个操作一个共享块的写失效处理可用这两个操作组合而成。组合而成。存储块的状态有三种：存储块的状态有三种：共享共享 在一个或多个处理器上具有这个在一个或多个处理器上具有这个块的副本，且存储器中的值是最新的块的副本，且存储器中的值是最新的（所有（所有Cache中的副本均相同）。中的副本均相同）。Compute
43、r Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构未缓冲未缓冲:所有处理器的所有处理器的Cache都没有该块的副本。都没有该块的副本。专有专有:仅有一个处理器上有该块的副本，且仅有一个处理器上有该块的副本，且已对该块进行了写操作，而主存中的副本仍是已对该块进行了写操作，而主存中的副本仍是旧的。这个处理器称为旧的。这个处理器称为该块的拥有者该块的拥有者。4.由于写作废操作的需要，还必须记录哪些处理器有该由于写作废操作的需要，还必须记录哪些处理器有该块的副本。块的副本。方法：方法：对每个主存块设置一个位向量对每个主存块设置一个位向量当该块被共享时，每个位指
44、出与之对应的处理当该块被共享时，每个位指出与之对应的处理器是否有该块的副本。器是否有该块的副本。当该块为专有时，可根据位向量来寻找其拥有当该块为专有时，可根据位向量来寻找其拥有者。者。Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构一个例子一个例子 本地结点、宿主结点以及远程结点的关系本地结点、宿主结点以及远程结点的关系 本地结点：本地结点：发出访问请求的结点发出访问请求的结点 宿主结点：宿主结点：包含所访问的存储单元及包含所访问的存储单元及其目录项的结点其目录项的结点 远程结点可以和宿主结点是同一个结远程结点可以和宿主结点是同一个结点
45、，也可以不是同一个结点。点，也可以不是同一个结点。CPUCache本地结点本地结点APCache远程结点远程结点C宿主结点宿主结点B(Home)副本副本目录目录存储器存储器宿主结点：宿主结点：存放有对应地址的存储器块和目录项的结点存放有对应地址的存储器块和目录项的结点 KComputer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构总结：总结：目录协议的目录协议的基本点基本点 在每个结点中增加了目录存储器用于存放目录。在每个结点中增加了目录存储器用于存放目录。存储器的每一块在目录中有对应的一项。存储器的每一块在目录中有对应的一项。每一个目录项主要由两
46、个字段构成：每一个目录项主要由两个字段构成：状态：状态：描述所对应的存储块的当前状态。描述所对应的存储块的当前状态。位向量：位向量：每一位对应于一个处理器，用于每一位对应于一个处理器，用于指出该处理器的指出该处理器的Cache中是否有该存储块的中是否有该存储块的副本。当处理器对某一块进行写操作时，副本。当处理器对某一块进行写操作时，只要根据位向量通知具有相应副本的处理只要根据位向量通知具有相应副本的处理器进行作废操作。器进行作废操作。位向量中记录的处理器集合称为位向量中记录的处理器集合称为共享集合共享集合。Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式
47、共享存储器体系结构 在基于目录的协议中，目录承担了一致性在基于目录的协议中，目录承担了一致性协议操作的主要功能。协议操作的主要功能。发往一个目录的消息会产生发往一个目录的消息会产生两种不同类型两种不同类型的动作：的动作：更新目录状态更新目录状态发送消息以完成所请求的操作发送消息以完成所请求的操作 目录可能接收目录可能接收三种不同的请求：三种不同的请求：读失效读失效写失效写失效数据写回数据写回8.3.2 目录协议及其实现目录协议及其实现Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构当一个块处于当一个块处于未缓冲状态未缓冲状态时，对该块发
48、出的时，对该块发出的请求及目录的处理操作为：请求及目录的处理操作为：读失效读失效将存储器数据送往请求方处理器，且将存储器数据送往请求方处理器，且该处理器成为该块的唯一共享结点，该处理器成为该块的唯一共享结点，本块的状态变成共享。本块的状态变成共享。写失效写失效将存储器数据送往请求方处理器，该将存储器数据送往请求方处理器，该块的状态变成专有，表示该块仅存在块的状态变成专有，表示该块仅存在唯一的有效副本。唯一的有效副本。其共享集合仅包含该处理器，指出该其共享集合仅包含该处理器，指出该处理器是其拥有者。处理器是其拥有者。Computer Architecture8.3 8.3 分布式共享存储器体系结
49、构分布式共享存储器体系结构当一个块处于当一个块处于共享状态共享状态时，其在存储器中的数据时，其在存储器中的数据是当前最新的，对该块发出的请求及其处理操作是当前最新的，对该块发出的请求及其处理操作为：为：读失效读失效将存储器数据送往请求方处理器，并将将存储器数据送往请求方处理器，并将其加入共享集合。其加入共享集合。写失效写失效将数据送往请求方处理器，对共享集合将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息。中所有的处理器发送写作废消息。将共享集合改为仅含有该处理器，该块将共享集合改为仅含有该处理器，该块的状态变为专有。的状态变为专有。Computer Architecture8.
50、3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构当某块处于当某块处于专有状态专有状态时，该块的最新值保存在共时，该块的最新值保存在共享集合所指出的唯一处理器（拥有者）中。享集合所指出的唯一处理器（拥有者）中。有三种可能的目录请求：有三种可能的目录请求：读失效读失效将将“取数据取数据”的消息发往拥有者处理器，的消息发往拥有者处理器，使该块的状态转变为共享。使该块的状态转变为共享。将数据送回宿主结点写入存储器，进而将数据送回宿主结点写入存储器，进而把该数据送回请求方处理器，将请求方把该数据送回请求方处理器，将请求方处理器加入共享集合。处理器加入共享集合。此时共享集合中仍保留原拥有者处理
