分布式存储器结构的优点课件

第八章第八章多处理机多处理机第八章Computer Architecture并行计算机在未来将会发挥更大的作用并行计算机在未来将会发挥更大的作用?1.获得超过单处理器的性能，最直接的方法就是把获得超过单处理器的性能，最直接的方法就是把多个处理器连在一起；多个处理器连在一起；2.自自1985年以来，体系结构的改进使性能迅速提高，年以来，体系结构的改进使性能迅速提高，这种改进的速度能否持续下去还不清楚，但通过这种改进的速度能否持续下去还不清楚，但通过复杂度和硅技术的提高而得到的性能的提高正在复杂度和硅技术的提高而得到的性能的提高正在减小；减小；3.并行计算机应用软件已有缓慢但稳定的发展。并行计算机应用软件已有缓慢但稳定的发展。8.1 8.1 引引 言言并行计算机在未来将会发挥更大的作用?8.1 引 言2Computer Architecture本章重点本章重点:中小规模的机器中小规模的机器(处理器的个数处理器的个数128)（多处理机设计的主流）（多处理机设计的主流）8.1.1并行计算机体系结构的分类并行计算机体系结构的分类1.按照按照Flynn分类法，可把计算机分成分类法，可把计算机分成单指令流单数据流（单指令流单数据流（SISD）单指令流多数据流（单指令流多数据流（SIMD）多指令流单数据流（多指令流单数据流（MISD）多指令流多数据流（多指令流多数据流（MIMD）8.1 8.1 引引 言言本章重点:8.1 引 言3Computer Architecture2.MIMD已成为通用多处理机体系结构的选择，原因已成为通用多处理机体系结构的选择，原因：(1)MIMD具有灵活性具有灵活性高性能单用户机高性能单用户机多道程序机器多道程序机器(2)MIMD可以充分利用商品化微处理器在性能价格可以充分利用商品化微处理器在性能价格比方面的优势。比方面的优势。8.1 8.1 引引 言言2.MIMD已成为通用多处理机体系结构的选择，原因：8.14Computer Architecture3.按存储器的结构和互连策略，可按存储器的结构和互连策略，可把现有的把现有的MIMD机机器分为两类器分为两类（与多处理机系统中处理器个数的多少有关）（与多处理机系统中处理器个数的多少有关）(1)集中式共享存储器结构集中式共享存储器结构这类机器有时被称为这类机器有时被称为SMP机器（机器（Symmetricshared-memoryMultiProcessor）UMA机器（机器（UniformMemoryAccess）8.1 8.1 引引 言言3.按存储器的结构和互连策略，可把现有的MIMD机器分为两5Computer Architecture适用于处理机数目不大情况。适用于处理机数目不大情况。8.1 8.1 引引 言言适用于处理机数目不大情况。8.1 引 言6Computer Architecture(2)分布式存储器结构分布式存储器结构每个结点包含：每个结点包含：处理器处理器存储器存储器IO 在许多情况下，分布式存储器结构优于采用在许多情况下，分布式存储器结构优于采用集中式共享存储器结构。集中式共享存储器结构。分布式存储器结构需要高带宽的互连。分布式存储器结构需要高带宽的互连。8.1 8.1 引引 言言(2)分布式存储器结构8.1 引 言7Computer Architecture适用于处理机数目较大情况。适用于处理机数目较大情况。8.1 8.1 引引 言言适用于处理机数目较大情况。8.1 引 言8Computer Architecture 分布式存储器结构的优点分布式存储器结构的优点(1)如果大多数的访问是针对本结点的局部存储器，如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；则可降低对存储器和互连网络的带宽要求；(2)对局部存储器的访问延迟低。对局部存储器的访问延迟低。主要缺点主要缺点处理器之间的通信较为复杂，且各处理器之间处理器之间的通信较为复杂，且各处理器之间访问延迟较大访问延迟较大（显式通信）（显式通信）;需要高带宽的互连。需要高带宽的互连。簇：簇：超结点超结点-每个结点有多个处理器每个结点有多个处理器(28)8.1 8.1 引引 言言 分布式存储器结构的优点8.1 引 言9Computer Architecture8.1.2通信模型和存储器的结构模型通信模型和存储器的结构模型1.两种地址空间的组织方案两种地址空间的组织方案(1)物理上分离的多个存储器可作为一个逻辑上共物理上分离的多个存储器可作为一个逻辑上共享的存储空间进行编址。享的存储空间进行编址。这类机器的结构被称为这类机器的结构被称为q分布式共享存储器结构分布式共享存储器结构（DSM:DistributedShared-Memory)q可缩放共享存储器结构可缩放共享存储器结构（SSM:ScalableShared-Memory)qNUMA机器机器（NUMA:Non-UniformMemoryAccess)8.1 8.1 引引 言言8.1.2 通信模型和存储器的结构模型8.1 引 言10Computer Architecture(2)整个地址空间由多个独立的地址空间构成，它整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对们在逻辑上也是独立的，远程的处理器不能对其直接寻址。其直接寻址。8.1 8.1 引引 言言每一个处理器每一个处理器-存储器模块实际上是一个存储器模块实际上是一个单独的计算机，这种机器也称为多计算机。单独的计算机，这种机器也称为多计算机。(2)整个地址空间由多个独立的地址空间构成，它8.11Computer Architecture2.两种通信模型两种通信模型共享地址空间的机器共享地址空间的机器利用利用Load和和Store指令中的地址隐含指令中的地址隐含地地进行数据通讯。进行数据通讯。多个地址空间的机器多个地址空间的机器通过处理器间显式地传递消息完成。通过处理器间显式地传递消息完成。8.1 8.1 引引 言言这种机器常称为这种机器常称为消息传递机器。消息传递机器。2.两种通信模型 共享地址空间的机器8.1 引 12Computer Architecture 消息传递计算机通过传递消息来请求某些消息传递计算机通过传递消息来请求某些服务或传输数据，从而完成通信。服务或传输数据，从而完成通信。例：例：一个处理器要对远程存储器上的数据进行一个处理器要对远程存储器上的数据进行访问或操作访问或操作(1)发送消息，请求传递数据或对数据进行操作；发送消息，请求传递数据或对数据进行操作；远程进程调用远程进程调用(RPC，remoteprocesscall)(2)目的处理器接收到消息以后，执行相应的操目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个作或代替远程处理器进行访问，并发送一个应答消息将结果返回。应答消息将结果返回。8.1 8.1 引引 言言 消息传递计算机通过传递消息来请求某些服务13Computer Architecture 同步消息传递同步消息传递请求处理器发送一个请求后一直要等到应答请求处理器发送一个请求后一直要等到应答结果才继续运行。结果才继续运行。异步消息传递异步消息传递发送方不先经请求就直接把数据送往数据接发送方不先经请求就直接把数据送往数据接受方。受方。3.通信机制的三个关键的性能指标：通信机制的三个关键的性能指标：1.通信带宽通信带宽理想状态下的通信带宽受限于处理器、存储理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。器和互连网络的带宽。8.1 8.1 引引 言言 同步消息传递8.1 引 言14Computer Architecture2.通信延迟通信延迟通信延迟发送开销跨越时间传输延迟接收开销通信延迟发送开销跨越时间传输延迟接收开销理想状态下通信延迟应尽可能地小。理想状态下通信延迟应尽可能地小。3.通讯延迟的隐藏程度通讯延迟的隐藏程度 如何才能较好地将通信和计算或多次通信之如何才能较好地将通信和计算或多次通信之间重叠起来，以实现间重叠起来，以实现通讯延迟的隐藏通讯延迟的隐藏。通常的原则是：通常的原则是：只要可能就隐藏延迟只要可能就隐藏延迟。通信延迟隐藏是一种提高性能的有效途径，但它对通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。操作系统和编程者来讲增加了额外的负担。8.1 8.1 引引 言言2.通信延迟8.1 引 言15Computer Architecture4.不同通信机制的优点不同通信机制的优点1.共享存储器通信的主要优点共享存储器通信的主要优点(1)与常用的集中式共享存储器结构使用的通信机制与常用的集中式共享存储器结构使用的通信机制兼容。兼容。(2)当处理器通信活动方式复杂或动态变化时易于当处理器通信活动方式复杂或动态变化时易于编程，同时在简化编译器设计方面也占有优势。编程，同时在简化编译器设计方面也占有优势。(3)当通信数据较小时，通信开销较低，带宽利用当通信数据较小时，通信开销较低，带宽利用较好较好.(4)通过硬件控制的通过硬件控制的Cache减少了远程通信的频度，减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。减少了通信延迟以及对共享数据的访问冲突。8.1 8.1 引引 言言4.不同通信机制的优点8.1 引 言16Computer Architecture2.消息传递通信机制的主要优点消息传递通信机制的主要优点(1)硬件较简单。硬件较简单。(2)通信是显式的，从而引起编程者和编译程序通信是显式的，从而引起编程者和编译程序的注意，着重处理开销大的通信。的注意，着重处理开销大的通信。另外另外 在共享存储器上支持消息传递相对简单：在共享存储器上支持消息传递相对简单：将消息传递实现时转换成远端内存访问。将消息传递实现时转换成远端内存访问。在消息传递的硬件上支持共享存储器就非常困难：在消息传递的硬件上支持共享存储器就非常困难：所有对共享存储器的访问均要求操作系统提供地所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，址转换和存储保护功能，将存储器访问转换为消将存储器访问转换为消息的发送和接收息的发送和接收。8.1 8.1 引引 言言2.消息传递通信机制的主要优点8.1 引 言17Computer Architecture8.1.3并行处理面临的挑战并行处理面临的挑战并行处理面临着两个重要的挑战：并行处理面临着两个重要的挑战：程序中有限的并行性程序中有限的并行性 相对较高的通信开销相对较高的通信开销8.1 8.1 引引 言言1.有限的并行性使机器要达到好的加速比十分困难有限的并行性使机器要达到好的加速比十分困难8.1.3 并行处理面临的挑战 程序中有限的并行性8.1 引18Computer Architecture例例 如如果果想想用用100个个处处理理器器达达到到80的的加加速速比比，求原计算程序中串行部分所占比例。求原计算程序中串行部分所占比例。解解Amdahl定律为定律为加速比加速比得出：得出：并行比例并行比例0.9975可以看出要用可以看出要用100个处理器达到个处理器达到80的加速比，串行计的加速比，串行计算的部分只能占算的部分只能占0.25%。1可加速部分比例可加速部分比例理论加速比理论加速比（1可加速部分比例）可加速部分比例）801并行比例并行比例100（1并行比例）并行比例）8.1 8.1 引引 言言例 如果想用100个处理器达到80的加速比，求原计19Computer Architecture2.面临的第二个挑战主要是指多处理机中远程访面临的第二个挑战主要是指多处理机中远程访3.问的较大延迟。问的较大延迟。在现有的机器中，处理器之间的数据通信在现有的机器中，处理器之间的数据通信大约需要大约需要1001000个时钟周期。个时钟周期。8.1 8.1 引引 言言面临的第二个挑战主要是指多处理机中远程访8.1 引 言20远程访问一个字的延迟时间远程访问一个字的延迟时间 计算机类型计算机类型通信通信机制机制互连网络互连网络处理机处理机最大数量最大数量典型远程存储器典型远程存储器访问时间（访问时间（ns）SunStarfireserversSMP多总线多总线64500SGIOrigin3000NUMA胖超立方体胖超立方体512500CrayT3ENUMA3维环网维环网2048300HPVseriesSMP88交叉开关交叉开关321000HPAlphaServerGSSMP开关总线开关总线32400远程访问一个字的延迟时间 计算机类型 通信机制 互连网络 处21Computer Architecture8.1 8.1 引引 言言例例8.2假设有一台假设有一台32个处理器的多处理机，个处理器的多处理机，对远程存储器访问时间为对远程存储器访问时间为400ns。除了通信以。除了通信以外，假设所有其他访问均命中局部存储器。当外，假设所有其他访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器发出一个远程请求时，本处理器挂起。处理器的时钟频率为的时钟频率为1GHz，如果指令基本的，如果指令基本的IPC为为2（设所有访存均命中（设所有访存均命中Cache），求在没有远），求在没有远程访问的情况下和有程访问的情况下和有0.2%的指令需要远程访的指令需要远程访问的情况下，前者比后者快多少问的情况下，前者比后者快多少?8.1 引 言 例8.2 假设有一台32个22Computer Architecture8.1 8.1 引引 言言解解没有远程访问时，机器的没有远程访问时，机器的CPI为为1/基本基本IPC=1/2=0.5有有0.2%远程访问的机器的实际远程访问的机器的实际CPI为为CPI基本基本CPI远程访问率远程访问率远程访问开销远程访问开销0.50.2%远程访问开销远程访问开销远程访问开销为远程访问开销为远程访问时间远程访问时间/时钟周期时间时钟周期时间400ns/1ns400个时钟周期个时钟周期CPI0.50.2%4001.3因此在没有远程访问的情况下的计算机速度是有因此在没有远程访问的情况下的计算机速度是有0.2%远程访问的计算机速度的远程访问的计算机速度的1.3/0.5=2.6倍倍。8.1 引 言解 没有远程访问时，机器的CPI为 1/23Computer Architecture问题的解决问题的解决并行性不足：并行性不足：通过采用并行性更好的算法来解决通过采用并行性更好的算法来解决远程访问延迟的降低：远程访问延迟的降低：靠体系结构支持和编程技术靠体系结构支持和编程技术8.1 8.1 引引 言言 问题的解决 8.1 引 言24Computer Architecture8.1 8.1 引引 言言3.在并行处理中，影响性能（负载平衡、同步和存储在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：器访问延迟等）的关键因素常依赖于：应用程序的高层特性应用程序的高层特性如数据的分配，并行算法的结构以及如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。在空间和时间上对数据的访问模式等。依据应用特点可把多机工作负载大致分成两类：依据应用特点可把多机工作负载大致分成两类：单个程序在多处理机上的并行工作负载单个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载8.1 引 言25Computer Architecture3.并行程序的计算通信比率并行程序的计算通信比率反映并行程序性能的一个重要的度量反映并行程序性能的一个重要的度量计算通信比率计算通信比率随着处理数据规模的增大而增加，随着处理数据规模的增大而增加，随着处理器数目的增加而降低。随着处理器数目的增加而降低。8.1 8.1 引引 言言3.并行程序的计算通信比率8.1 引 言26Computer Architecture多个处理器共享一个存储器。多个处理器共享一个存储器。当处理器规模较小时，这种机器十分经济。当处理器规模较小时，这种机器十分经济。支持对共享数据和私有数据的支持对共享数据和私有数据的Cache缓存。缓存。私有数据供一个单独的处理器使用，而共私有数据供一个单独的处理器使用，而共享数据供多个处理器使用。享数据供多个处理器使用。共享数据进入共享数据进入Cache产生了一个新的问题：产生了一个新的问题：Cache的一致性问题的一致性问题8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构 多个处理器共享一个存储器。8.2 对称式共享存储器体系27Computer Architecture8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构不一致产生的原因（不一致产生的原因（Cache一致性问题）一致性问题）IO操作操作Cache中的内容可能与由中的内容可能与由IO子系统子系统输入输入/输出形成的存储器对应部分的内输出形成的存储器对应部分的内容不同。容不同。共享数据共享数据不同处理器的不同处理器的Cache都保存有对应存储都保存有对应存储器单元的内容。器单元的内容。8.2.1多处理机多处理机Cache一致性一致性8.2 对称式共享存储器体系结构 不一致产生的原28由两个处理器（由两个处理器（A和和B）读写引起的）读写引起的Cache一致性问题一致性问题时间时间事件事件CPUACache内容内容CPUBCache内容内容X单元存储器单元存储器内容内容011CPUA读读X112CPUB读读X1113CPUA将将0存入存入X010由两个处理器（A和B）读写引起的Cache一致性问题 时间 29Computer Architecture存储器是一致的存储器是一致的（非正式地定义）（非正式地定义）如果对某个数据项的任何读操作均可得到其最如果对某个数据项的任何读操作均可得到其最 新写入的值，则认为这个新写入的值，则认为这个存储系统是一致的。存储系统是一致的。满足条件满足条件处理器处理器P对对X进行一次写之后又对进行一次写之后又对X进行读，读和写进行读，读和写之间没有其它处理器对之间没有其它处理器对X进行写，则读的返回值总进行写，则读的返回值总是写进的值。是写进的值。一个处理器对一个处理器对X进行写之后进行写之后足够时间足够时间，另一处理器，另一处理器对对X进行读，读和写之间无其它写，则读进行读，读和写之间无其它写，则读X的返回的返回值应为写进的值。值应为写进的值。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构存储器是一致的（非正式地定义）满足条件8.2 对称式共享30Computer Architecture对同一单元的写是顺序化的，即任意两个处理器对对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是同一单元的两次写，从所有处理器看来顺序都应是相同的。相同的。足够时间？足够时间？简单处理方法：简单处理方法：所有的处理器均能看到写的结果所有的处理器均能看到写的结果=直到所有的处理器均看到了写的结果，一次写直到所有的处理器均看到了写的结果，一次写操作才算完成；操作才算完成；8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构 对同一单元的写是顺序化的，即任意两个处理器对8.2 对31Computer Architecture8.2.2实现一致性的基本方案实现一致性的基本方案在一致的多处理机中，在一致的多处理机中，Cache对共享数据提供对共享数据提供两种功能：两种功能：共享数据的迁移共享数据的迁移降低了对远程共享数据的访问延迟。降低了对远程共享数据的访问延迟。共享数据的复制共享数据的复制不仅降低了访存的延迟，也减少了访问共不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。享数据所产生的冲突。实现实现Cache一致性的目的：一致性的目的：确保上述两种功能实现过程中不会出现确保上述两种功能实现过程中不会出现Cache的不的不一致。一致。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构8.2.2 实现一致性的基本方案 共享数据的迁移8.2 32Computer Architecture实现方法：实现方法：Cache一致性协议一致性协议实现技术：实现技术：小规模多处理机不是采用软件而是采用小规模多处理机不是采用软件而是采用硬件技术实现硬件技术实现Cache一致性。一致性。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构实现方法：Cache一致性协议8.2 对称式共享存储器体33Computer ArchitectureCache一致性协议一致性协议:对多个处理器维护一致性的协对多个处理器维护一致性的协议议协议实现基础：协议实现基础：跟踪共享数据块的状态跟踪共享数据块的状态两类跟踪共享数据块状态的协议两类跟踪共享数据块状态的协议 目录目录物理存储器中共享数据块的状态及相关信息均被物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。保存在一个称为目录的地方。监听监听每个每个Cache除了包含物理存储器中块的数据拷贝之除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。外，也保存着各个块的共享状态信息。Cache通常通常连在共享存储器的总线上，各个连在共享存储器的总线上，各个Cache控制器通过控制器通过监听总线来判断它们是否有总线上请求的数据块。监听总线来判断它们是否有总线上请求的数据块。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构 Cache一致性协议:对多个处理器维护一致性的343.两种协议两种协议(1)写作废协议写作废协议在一个处理器写某个数据项之前保证它对该数据项在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权，使别的拷贝作废。有唯一的访问权，使别的拷贝作废。例例在写回在写回Cache的条件下，监听总线中写作废协议的实的条件下，监听总线中写作废协议的实现。现。处理器行为处理器行为总线行为总线行为CPU A Cache内容内容CPU B Cache内容内容主主存存X单单元元内内容容0CPUA读读XCache失效失效00CPUB读读XCache失效失效000CPUA将将X单单元元写写1作废作废X单元单元10CPUB读读XCache失效失效1113.两种协议处理器行为总线行为CPU A Cache内35(2)写更新协议写更新协议当一个处理器写某数据项时，通过广播使其它当一个处理器写某数据项时，通过广播使其它Cache中所有对应的该数据项拷贝进行更新。中所有对应的该数据项拷贝进行更新。例例在写回在写回Cache的条件下，监听总线中写更新协议的实的条件下，监听总线中写更新协议的实现。现。处理器行为处理器行为总线行为总线行为CPUA Cache内容内容CPUB Cache内容内容主主存存X单单元元内内容容0CPUA读读XCach失效失效00CPUB读读XCach失效失效000CPUA将将 X单单元写元写1广广播播写写X单单元元111CPUB读读X111(2)写更新协议处理器行为总线行为CPUA Cache内容36Computer Architecture(3)写更新和写作废协议性能上的差别写更新和写作废协议性能上的差别 对同一数据的多个写而中间无读操作的情况，对同一数据的多个写而中间无读操作的情况，写更新协议需进行多次写广播操作，而在写写更新协议需进行多次写广播操作，而在写作废协议下只需一次作废操作。作废协议下只需一次作废操作。对同一块中多个字进行写，写更新协议对每对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写作废协个字的写均要进行一次广播，而在写作废协议下仅在对本块第一次写时进行作废操作。议下仅在对本块第一次写时进行作废操作。从一个处理器写到另一个处理器读之间的延从一个处理器写到另一个处理器读之间的延迟通常在写更新模式中较低。而在写作废协议迟通常在写更新模式中较低。而在写作废协议中，需要读一个新的拷贝。中，需要读一个新的拷贝。*在基于总线的多处理机中，写作废协议成为绝大在基于总线的多处理机中，写作废协议成为绝大多数系统设计的选择。多数系统设计的选择。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构(3)写更新和写作废协议性能上的差别8.2 对称式共享存37Computer Architecture8.2.3监听协议的基本实现过程监听协议的基本实现过程小规模多处理机中实现写作废协议为例小规模多处理机中实现写作废协议为例进行写操作时进行写操作时:1)获得总线控制权获得总线控制权2)将要作废的数据块地址发在总线上将要作废的数据块地址发在总线上3)其他处理器一直监听总线，若它们的其他处理器一直监听总线，若它们的Cache中含有要作废的块，则作废该块中含有要作废的块，则作废该块*获得总线控制权的顺序性保证了写的顺序性获得总线控制权的顺序性保证了写的顺序性(唯一访唯一访问权问权)8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构8.2.3 监听协议的基本实现过程8.2 对称式共享存储38Computer Architecture进行读操作时进行读操作时:如果如果Cache命中，从命中，从Cache中获得数据中获得数据如果如果Cache不命中：不命中：(1)写直达写直达Cache，因为所有写的数据同时被写回因为所有写的数据同时被写回主存，则从主存中总可以取到最新的数据值。主存，则从主存中总可以取到最新的数据值。(2)对于写回对于写回Cache，得到数据的最新值会困难一得到数据的最新值会困难一些，因为些，因为最新值可能在某个最新值可能在某个Cache中，也可能中，也可能在主存中在主存中-同样需要使用监听机制，如果某同样需要使用监听机制，如果某个处理器发现它有被读请求的块的被修改拷贝个处理器发现它有被读请求的块的被修改拷贝则需提供该块数据，并阻止请求方对内存的访则需提供该块数据，并阻止请求方对内存的访问。问。8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构进行读操作时:8.2 对称式共享存储器体系结构39Computer Architecture8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构在写回法在写回法Cache条件下的实现技术条件下的实现技术Cache的标识（的标识（tag）用于实现监听。）用于实现监听。作废一个块只需将其有效位（作废一个块只需将其有效位（valid）置）置为无效。为无效。给每个给每个Cache块加一个特殊的状态位。块加一个特殊的状态位。状态：状态：共享共享（shared）专有专有（exclusive）cleandirtyCache块的拥有者块的拥有者：拥有唯一的：拥有唯一的Cache块副块副本的处理器。本的处理器。8.2 对称式共享存储器体系结构 在写回法Cache条40Computer Architecture8.2 8.2 对称式共享存储器体系结构对称式共享存储器体系结构在每个结点内嵌入一个在每个结点内嵌入一个Cache状态控制器。状态控制器。控制器根据来自处理器或总线的控制器根据来自处理器或总线的请求，改变所选择的数据块的状态。请求，改变所选择的数据块的状态。因为每次总线操作均要检查因为每次总线操作均要检查Cache的地址的地址标识，这可能会影响标识，这可能会影响CPU对对Cache的访问。的访问。可通过下列两种技术之一来减少影响可通过下列两种技术之一来减少影响：复制标志位复制标志位采用多级包容采用多级包容Cache（许多系统采用）（许多系统采用）8.2 对称式共享存储器体系结构在每个结点内嵌入一个Cac41Computer Architecture通常结构：通常结构：存储器分布于各结点中，所有的结点通过网存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的。络互连。访问可以是本地的，也可是远程的。一般不支持一般不支持Cache一致性一致性,规定共享数据不规定共享数据不进入进入Cache，仅私有数据才能保存在，仅私有数据才能保存在Cache中。中。优点：优点：所需的硬件支持很少所需的硬件支持很少(因为远程访问存取量仅是一个字因为远程访问存取量仅是一个字(或双字或双字)而而不是一个不是一个Cache块块)8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构通常结构：存储器分布于各结点中，所有的结点通过网8.3 分布42Computer Architecture缺点：缺点：(1)许多情况下编译器无法确切知道哪些数据当许多情况下编译器无法确切知道哪些数据当前共享前共享;(2)当每次访问要从远程存储器取一个字时，不能有当每次访问要从远程存储器取一个字时，不能有效利用共享数据的空间局部性效利用共享数据的空间局部性;(3)诸如预取等延迟隐藏技术对于多个字的存取诸如预取等延迟隐藏技术对于多个字的存取更为有效，比如针对一个更为有效，比如针对一个Cache块的预取。块的预取。8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构缺点：8.3 分布式共享存储器体系结构43Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构解决解决Cache一致性问题的关键：一致性问题的关键：寻找替代监听协议的一致性协议寻找替代监听协议的一致性协议:目录协议目录协议8.3.1基于目录的基于目录的Cache一致性一致性目录协议目录协议目录：目录：一种专用的数据结构，用于记录可一种专用的数据结构，用于记录可以进入以进入Cache的每个数据块的状态、哪些的每个数据块的状态、哪些处理器有该块的副本以及是否修改过等信处理器有该块的副本以及是否修改过等信息。息。分布式目录分布式目录如何将支持如何将支持Cache一致性的共享存储器模式扩展一致性的共享存储器模式扩展到可扩缩的大规模多处理机系统到可扩缩的大规模多处理机系统?8.3 分布式共享存储器体系结构解决Cache一致性问题的关44Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构目录与存储器一起分布到各结点中，从目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同而对于不同目录内容的访问可以在不同的结点进行。的结点进行。存储块的共享状态信息在唯一的一个固存储块的共享状态信息在唯一的一个固定单元中找到。这使一致性协议避免了定单元中找到。这使一致性协议避免了广播操作。广播操作。对每个结点增加目录表后的分布式存储对每个结点增加目录表后的分布式存储器多处理机的系统结构。器多处理机的系统结构。8.3 分布式共享存储器体系结构目录与存储器一起分布到各结点45分布式存储器结构的优点课件46Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构目录协议必须完成两种目录协议必须完成两种主要的操作：主要的操作：处理读失效处理读失效处理对共享、干净（处理对共享、干净（clean）块的写）块的写一个共享块的写失效处理可用这两个操作一个共享块的写失效处理可用这两个操作组合而成。组合而成。存储块的状态有三种：存储块的状态有三种：共享共享在一个或多个处理器上具有这个在一个或多个处理器上具有这个块的副本，且存储器中的值是最新的块的副本，且存储器中的值是最新的（所有（所有Cache中的副本均相同）。中的副本均相同）。8.3 分布式共享存储器体系结构目录协议必须完成两种主要的操47Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构未缓冲未缓冲:所有处理器的所有处理器的Cache都没有该块的副本。都没有该块的副本。专有专有:仅有一个处理器上有该块的副本，且仅有一个处理器上有该块的副本，且已对该块进行了写操作，而主存中的副本仍是已对该块进行了写操作，而主存中的副本仍是旧的。这个处理器称为旧的。这个处理器称为该块的拥有者该块的拥有者。4.由于写作废操作的需要，还必须记录哪些处理器有该由于写作废操作的需要，还必须记录哪些处理器有该块的副本。块的副本。方法：方法：对每个主存块设置一个位向量对每个主存块设置一个位向量当该块被共享时，每个位指出与之对应的处理当该块被共享时，每个位指出与之对应的处理器是否有该块的副本。器是否有该块的副本。当该块为专有时，可根据位向量来寻找其拥有当该块为专有时，可根据位向量来寻找其拥有者。者。8.3 分布式共享存储器体系结构未缓冲:所有处理器的Cach48Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构一个例子一个例子本地结点、宿主结点以及远程结点的关系本地结点、宿主结点以及远程结点的关系本地结点：本地结点：发出访问请求的结点发出访问请求的结点宿主结点：宿主结点：包含所访问的存储单元及包含所访问的存储单元及其目录项的结点其目录项的结点远程结点可以和宿主结点是同一个结远程结点可以和宿主结点是同一个结点，也可以不是同一个结点。点，也可以不是同一个结点。8.3 分布式共享存储器体系结构一个例子49CPUCache本地结点本地结点APCache远程结点远程结点C宿主结点宿主结点B(Home)副本副本目录目录存储器存储器宿主结点：宿主结点：存放有对应地址的存储器块和目录项的结点存放有对应地址的存储器块和目录项的结点KCPUCache本地结点APCache远程结点C宿主结点B(50Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构总结：总结：目录协议的目录协议的基本点基本点在每个结点中增加了目录存储器用于存放目录。在每个结点中增加了目录存储器用于存放目录。存储器的每一块在目录中有对应的一项。存储器的每一块在目录中有对应的一项。每一个目录项主要由两个字段构成：每一个目录项主要由两个字段构成：状态：状态：描述所对应的存储块的当前状态。描述所对应的存储块的当前状态。位向量：位向量：每一位对应于一个处理器，用于每一位对应于一个处理器，用于指出该处理器的指出该处理器的Cache中是否有该存储块的中是否有该存储块的副本。当处理器对某一块进行写操作时，副本。当处理器对某一块进行写操作时，只要根据位向量通知具有相应副本的处理只要根据位向量通知具有相应副本的处理器进行作废操作。器进行作废操作。位向量中记录的处理器集合称为位向量中记录的处理器集合称为共享集合共享集合。8.3 分布式共享存储器体系结构总结：目录协议的基本点51Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构在基于目录的协议中，目录承担了一致性在基于目录的协议中，目录承担了一致性协议操作的主要功能。协议操作的主要功能。发往一个目录的消息会产生发往一个目录的消息会产生两种不同类型两种不同类型的动作：的动作：更新目录状态更新目录状态发送消息以完成所请求的操作发送消息以完成所请求的操作目录可能接收目录可能接收三种不同的请求：三种不同的请求：读失效读失效写失效写失效数据写回数据写回8.3.2目录协议及其实现目录协议及其实现8.3 分布式共享存储器体系结构在基于目录的协议中，目录承担52Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构当一个块处于当一个块处于未缓冲状态未缓冲状态时，对该块发出的时，对该块发出的请求及目录的处理操作为：请求及目录的处理操作为：读失效读失效将存储器数据送往请求方处理器，且将存储器数据送往请求方处理器，且该处理器成为该块的唯一共享结点，该处理器成为该块的唯一共享结点，本块的状态变成共享。本块的状态变成共享。写失效写失效将存储器数据送往请求方处理器，该将存储器数据送往请求方处理器，该块的状态变成专有，表示该块仅存在块的状态变成专有，表示该块仅存在唯一的有效副本。唯一的有效副本。其共享集合仅包含该处理器，指出该其共享集合仅包含该处理器，指出该处理器是其拥有者。处理器是其拥有者。8.3 分布式共享存储器体系结构当一个块处于未缓冲状态时，对53Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构当一个块处于当一个块处于共享状态共享状态时，其在存储器中的数据时，其在存储器中的数据是当前最新的，对该块发出的请求及其处理操作是当前最新的，对该块发出的请求及其处理操作为：为：读失效读失效将存储器数据送往请求方处理器，并将将存储器数据送往请求方处理器，并将其加入共享集合。其加入共享集合。写失效写失效将数据送往请求方处理器，对共享集合将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息。中所有的处理器发送写作废消息。将共享集合改为仅含有该处理器，该块将共享集合改为仅含有该处理器，该块的状态变为专有。的状态变为专有。8.3 分布式共享存储器体系结构当一个块处于共享状态时，其在54Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构当某块处于当某块处于专有状态专有状态时，该块的最新值保存在共时，该块的最新值保存在共享集合所指出的唯一处理器（拥有者）中。享集合所指出的唯一处理器（拥有者）中。有三种可能的目录请求：有三种可能的目录请求：读失效读失效将将“取数据取数据”的消息发往拥有者处理器，的消息发往拥有者处理器，使该块的状态转变为共享。使该块的状态转变为共享。将数据送回宿主结点写入存储器，进而将数据送回宿主结点写入存储器，进而把该数据送回请求方处理器，将请求方把该数据送回请求方处理器，将请求方处理器加入共享集合。处理器加入共享集合。此时共享集合中仍保留原拥有者处理器此时共享集合中仍保留原拥有者处理器（因为它仍有一个可读的副本）。（因为它仍有一个可读的副本）。8.3 分布式共享存储器体系结构当某块处于专有状态时，该块的55Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构写失效写失效该块将有一个新的拥有者。该块将有一个新的拥有者。给旧的拥有者处理器发送消息，要求它给旧的拥有者处理器发送消息，要求它将数据块送回宿主结点写入存储器，然将数据块送回宿主结点写入存储器，然后再从该结点送给请求方处理器。后再从该结点送给请求方处理器。把请求处理器加入共享者集合，使之成把请求处理器加入共享者集合，使之成为新的拥有者。该块的状态仍旧是专有。为新的拥有者。该块的状态仍旧是专有。8.3 分布式共享存储器体系结构写失效56Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构数据写回数据写回当一个块的拥有者处理器要从其当一个块的拥有者处理器要从其Cache中中把该块替换出去时，必须将该块写回其把该块替换出去时，必须将该块写回其宿主结点的存储器中，从而使存储器中宿主结点的存储器中，从而使存储器中相应的块中存放的数据是最新的（宿主相应的块中存放的数据是最新的（宿主结点实际上成为拥有者），该块的状态结点实际上成为拥有者），该块的状态变成非共享，其共享集合为空。变成非共享，其共享集合为空。8.3 分布式共享存储器体系结构数据写回57Computer Architecture8.3 8.3 分布式共享存储器体系结构分布式共享存储器体系结构对基于目录的对基于目录的Cache一致性的多种改进一致性的多种改进有限映射目录有限映射目录链式结构目录链式结构目录基于目录的基于目录的Cache一致性协议是完全由硬件实一致性协议是完全由硬件实现的。此外，还可以用软硬结合的办法实现。现的。此外，还可以用软硬结合的办法实现。8.3 分布式共享存储器体系结构对基于目录的Cache一致性58Computer Architecture8.4 8.4 同步同步同步机制通常是在硬件提供的同步指令的基同步机制通常是在硬件提供的同步指令的基础上，通过用户级软件例程来建立的。础上，通过用户级软件例程来建立的。8.4.1基本硬件原语基本硬件原语在多处理机中实现同步，所需的主要功能是：在多处理机中实现同步，所需的主要功能是：p一组能以原子操作的方式读出并修改存一组能以原子操作的方式读出并修改存储单元的硬件原语。它们能够自动读储单元的硬件原语。它们能够自动读修改单元。修改单元。p通常情况下，用户不直接使用基本的硬通常情况下，用户不直接使用基本的硬件原语，原语主要供系统程序员用来编件原语，原语主要供系统程序员用来编制同步库函数。制同步库函数。8.4 同步 同步机制通常是在硬件提供59Computer Architecture8.4 8.4 同步同步1)典型操作：原子交换典型操作：原子交换（atomicexchange）功能：功能：将一个存储单元的值和一个寄存器将一个存储单元的值和一个寄存器的值进行交换。的值进行交换。建立一个锁，锁值：建立一个锁，锁值：0：表示开（可用）表示开（可用）1：表示已上锁（不可用）表示已上锁（不可用）处理器上锁时，将对应于该锁的存储单元处理器上锁时，将对应于该锁的存储单元的值与存放在某个寄存器中的的值与存放在某个寄存器中的1进行交换。进行交换。如果返回值为如果返回值为0，存储单元的值此时已置，存储单元的值此时已置换为换为1，防止了其他进程竞争该锁。，防止了其他进程竞争该锁。8.4 同步 1)典型操作：原子交换（atomic ex60Computer Architecture8.4 8.4 同步同步2)测试并置定测试并置定（test_and_set）先测试一个存储单元的值，如果符合条件则先测试一个存储单元的值，如果符合条件则修改其值。修改其值。3)读取并加读取并加1（fetch_and_increment）它返回存储单元的值并自动增加该值。它返回存储单元的值并自动增加该值。4)使用指令对使用指令对LL(loadlinked或或loadlocked)的取指令的取指令SC(storeconditional)的特殊存指令的特殊存指令8.4 同步2)测试并置定（test_and_set）61Computer Architecture8.4 8.4 同步同步如果由如果由LL指明的存储单元的内容在指明的存储单元的内容在SC对其对其进行写之前已被其他指令改写过，则第二进行写之前已被其他指令改写过，则第二条指令条指令SC执行失败。执行失败。如果在两条指令间进行进程切换也会导致如果在两条指令间进行进程切换也会导致SC执行失败。执行失败。SC将返回一个值来指出该指令操作是否成将返回一个值来指出该指令操作是否成功：功：“1”：成功成功“0”：不成功不成功LL则返回该存储单元初始值。则返回该存储单元初始值。8.4 同步如果由LL指明的存储单元的内容在SC对其进行写62Computer Architecture8.4 8.4 同步同步例：例：实现对由实现对由R1指出的存储单元进行原子交换操作。指出的存储单元进行原子交换操作。try：ORR3,R4,R0/R4中为交换值。把该值送入中为交换值。把该值送入R3/MOVR2,#1LLR2,0（R1）/把单元把单元0（R1）中的值取到）中的值取到R2SCR3,0（R1）/若若0（R1）中的值与）中的值与R3中的值相中的值相/同，则置同，则置R3的值为的值为1，否则置为，否则置为0BEQZR3,try/存失败（存失败（R3的值为的值为0）则转移）则转移MOVR4,R2/将取的值送往将取的值送往R4最终最终R4和由和由R1指向的单元值进行原子交换，指向的单元值进行原子交换，在在LL和和SC之间如有别的处理器插入并修改了存之间如有别的处理器插入并修改了存储单元的值，储单元的值，SC将返回将返回0并存入并存入R3中，从而使这中，从而使这段程序再次执行。段程序再次执行。8.4 同步例：实现对由R1指出的存储单元进行原子交换操作63Computer Architecture8.4 8.4 同步同步LL/SC机制的一个优点机制的一个优点：用来构造别的同步原语：用来构造别的同步原语例如：例如：构造原子操作构造原子操作fetch_and_increment：try：LL R2,0（R1）DADDIUR2,R2,#1SCR2,0（R1）BEQZR2,try-?DADDIUR3,R2,#1SCR3,0（R1）8.4 同步 LL/SC机制的一个优点：用来构造别的同步64Computer Architecture8.4 8.4 同步同步采用多处理机的一致性机制来实现旋转锁采用多处理机的一致性机制来实现旋转锁旋转锁旋转锁(SPINLOCK)某一个时刻只有一个处理机可获得锁，某一个时刻只有一个处理机可获得锁，请求锁的处理机不停请求直到获得锁；请求锁的处理机不停请求直到获得锁；实现方法实现方法在存储器中保存锁变量，处理器可以不断地通在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求加锁，比如先交换，再测试返过一个原子操作请求加锁，比如先交换，再测试返回值从而知道锁的状况。释放锁的时候，处理器可回值从而知道锁的状况。释放锁的时候，处理器可简单地将锁置为简单地将锁置为“0”。适合于这样的场合：适合于这样的场合：锁被占用的时间很少，锁被占用的时间很少，8.4.2用一致性实现锁用一致性实现锁8.4 同步采用多处理机的一致性机制来实现旋转锁8.4.265Computer Architecture8.4 8.4 同步同步无无Cache一致性机制一致性机制在存储器中保存锁变量，处理器可以不断在存储器中保存锁变量，处理器可以不断地通过一个原子操作请求使用权。地通过一个原子操作请求使用权。比如：利用原子交换操作，并通过测试返比如：利用原子交换操作，并通过测试返回值而知道锁的使用情况。释放锁的时候，处回值而知道锁的使用情况。释放锁的时候，处理器只需简单地将锁置为理器只需简单地将锁置为0。例如，例如，用原子交换操作对旋转锁进行加锁，用原子交换操作对旋转锁进行加锁，R1中存放的是该旋转锁的地址。中存放的是该旋转锁的地址。DADDIUR2,R0,#1/MOVR2,#1lockit：EXCH R2,0（R1）BNEZR2,lockit8.4 同步 无Cache一致性机制66Computer Architecture8.4 8.4 同步同步支持支持Cache一致性一致性将锁调入将锁调入Cache，并通过一致性机制使锁值保持一，并通过一致性机制使锁值保持一致。致。优点：优点：可使可使“环绕环绕”的进程只对本地的进程只对本地Cache中的锁中的锁（副本）进行操作，而不用在每次请求占用锁（副本）进行操作，而不用在每次请求占用锁时都进行一次全局的存储器访问；时都进行一次全局的存储器访问；可利用访问锁时所具有的局部性，即处理器可利用访问锁时所具有的局部性，即处理器最近使用过的锁不久又会使用。最近使用过的锁不久又会使用。（减少为获得锁而花费的时间）（减少为获得锁而花费的时间）8.4 同步 支持Cache一致性67Computer Architecture8.4 8.4 同步同步改进旋转锁（获得第一条好处）改进旋转锁（获得第一条好处）只对本地只对本地Cache中锁的副本进行读取和检测，中锁的副本进行读取和检测，直到发现该锁已经被释放。然后，该程序立直到发现该锁已经被释放。然后，该程序立即进行交换操作，去跟在其他处理器上的进即进行交换操作，去跟在其他处理器上的进程争用该锁变量。程争用该锁变量。修改后的旋转锁程序：修改后的旋转锁程序：lockit：LD R2,0（R1）BNEZR2,lockitDADDIUR2,R0,#1/MOVR2,#1EXCHR2,0（R1）BNEZR2,lockit 8.4 同步 改进旋转锁（获得第一条好处）修改后的旋转锁68步骤步骤处理器处理器P0处理器处理器P1处理器处理器P2锁的状态锁的状态总线总线/目录操作目录操作1占有锁占有锁环绕测试环绕测试是否是否lock=0环绕测试环绕测试是否是否lock=0共享共享无无2将锁置为将锁置为0（收到作废命令）（收到作废命令）