《计算机系统结构》PPT课件.ppt

第第8 8章章 多处理器系统多处理器系统 第第8 8章章 多处理器系统多处理器系统 第第8 8章章 多处理器系统多处理器系统 第第8 8章章 多处理器系统多处理器系统 指令级并行性的限制和超线程技术指令级并行性的限制和超线程技术 多处理器构成的系统结构多处理器构成的系统结构第第8 8 章章 多多处处理理器器系系统统 多处理器的多处理器的CacheCache一致性一致性 集群系统集群系统 多处理器系统的同步机制多处理器系统的同步机制 多处理器系统的程序并行性多处理器系统的程序并行性 曙光曙光50005000超级计算机超级计算机第第8 8章章 多处理器系统多处理器系统 第第8 8章章 多处理机系统多处理机系统Chapter 8 MultiprocessersChapter 8 Multiprocessers指令级并行性的限制和超线程技术指令级并行性的限制和超线程技术多处理器构成的系统结构多处理器构成的系统结构多处理器的多处理器的Cache一致性一致性多处理器系统的同步机制多处理器系统的同步机制集群系统集群系统多处理器系统的程序并行性多处理器系统的程序并行性曙光曙光5000超级计算机超级计算机本章小结本章小结第第8 8章章 多处理器系统多处理器系统 指令级并行性的限制和超线程技术指令级并行性的限制和超线程技术 指令级并行性的限制指令级并行性的限制 超线程技术超线程技术 限制单处理器发展的其它主要因素限制单处理器发展的其它主要因素 第第8 8章章 多处理器系统多处理器系统 8.1.1 8.1.1 8.1.1 8.1.1 指令级并行性的限制指令级并行性的限制指令级并行性的限制指令级并行性的限制 1.1.理想处理器理想处理器理想处理器理想处理器 2.2.理想处理器难以接近理想处理器难以接近理想处理器难以接近理想处理器难以接近（1 1）转移预测、重命名和相关性分析上依靠）转移预测、重命名和相关性分析上依靠）转移预测、重命名和相关性分析上依靠）转移预测、重命名和相关性分析上依靠静态的编译分析是不可能完美的，动态分静态的编译分析是不可能完美的，动态分静态的编译分析是不可能完美的，动态分静态的编译分析是不可能完美的，动态分析受窗口局限析受窗口局限析受窗口局限析受窗口局限 （2 2）错误的预测限制了指令的并行度）错误的预测限制了指令的并行度）错误的预测限制了指令的并行度）错误的预测限制了指令的并行度 （3 3）寄存器的数目有限）寄存器的数目有限）寄存器的数目有限）寄存器的数目有限（4 4）此外，每时钟周期发射指令数量、功能）此外，每时钟周期发射指令数量、功能）此外，每时钟周期发射指令数量、功能）此外，每时钟周期发射指令数量、功能单元及单元延迟、寄存器文件端口、功能单元及单元延迟、寄存器文件端口、功能单元及单元延迟、寄存器文件端口、功能单元及单元延迟、寄存器文件端口、功能单元队列、对转移发射的限制、对存储器单元队列、对转移发射的限制、对存储器单元队列、对转移发射的限制、对存储器单元队列、对转移发射的限制、对存储器并行访问的限制以及对指令提交的限制等并行访问的限制以及对指令提交的限制等并行访问的限制以及对指令提交的限制等并行访问的限制以及对指令提交的限制等都是影响指令级并行的因素。都是影响指令级并行的因素。都是影响指令级并行的因素。都是影响指令级并行的因素。第第8 8章章 多处理器系统多处理器系统 8.1.2 8.1.2 超线程（超线程（Hyper-ThreadingHyper-Threading）技术）技术 超线程技术是指在单处理器中采用的线程超线程技术是指在单处理器中采用的线程级并行技术，又称简单多线程技术。级并行技术，又称简单多线程技术。超线程有两种主要方法：细粒度超线程和超线程有两种主要方法：细粒度超线程和粗粒度超线程。粗粒度超线程。同时多线程（同时多线程（SMT）是超线程的一个改进）是超线程的一个改进版本，它使用多发射和动态调度机制在版本，它使用多发射和动态调度机制在开发线程级并行的同时开发指令级并行。开发线程级并行的同时开发指令级并行。第第8 8章章 多处理器系统多处理器系统 8.1.3 8.1.3 限制单处理器发展的其它主要因素限制单处理器发展的其它主要因素 尽管单处理器在提高指令集并行及采用超线程尽管单处理器在提高指令集并行及采用超线程尽管单处理器在提高指令集并行及采用超线程尽管单处理器在提高指令集并行及采用超线程并行技术方面做出了很大努力，但在如下几个并行技术方面做出了很大努力，但在如下几个并行技术方面做出了很大努力，但在如下几个并行技术方面做出了很大努力，但在如下几个方面受到局限：方面受到局限：方面受到局限：方面受到局限：（1 1）指令级并行约束及超线程技术的限制已）指令级并行约束及超线程技术的限制已）指令级并行约束及超线程技术的限制已）指令级并行约束及超线程技术的限制已经不太可能提高更多的并行性。经不太可能提高更多的并行性。经不太可能提高更多的并行性。经不太可能提高更多的并行性。（2 2）仅靠提高频率的办法，难以实现性能的）仅靠提高频率的办法，难以实现性能的）仅靠提高频率的办法，难以实现性能的）仅靠提高频率的办法，难以实现性能的突破。反而带来功耗和内存、突破。反而带来功耗和内存、突破。反而带来功耗和内存、突破。反而带来功耗和内存、I/OI/O速度平衡的问速度平衡的问速度平衡的问速度平衡的问题。题。题。题。（3 3）不断增加的单核芯片面积提高了生产成）不断增加的单核芯片面积提高了生产成）不断增加的单核芯片面积提高了生产成）不断增加的单核芯片面积提高了生产成本，并且使得设计和验证所花费的时间变得更本，并且使得设计和验证所花费的时间变得更本，并且使得设计和验证所花费的时间变得更本，并且使得设计和验证所花费的时间变得更长。长。长。长。（4 4）功耗与性能比问题日渐突出。）功耗与性能比问题日渐突出。）功耗与性能比问题日渐突出。）功耗与性能比问题日渐突出。第第8 8章章 多处理器系统多处理器系统 多核处理器结构多核处理器结构 多处理器结构多处理器结构 多处理器并行处理定量分析和所遇到的问题多处理器并行处理定量分析和所遇到的问题8.2 8.2 多处理器构成的系统结构多处理器构成的系统结构 第第8 8章章 多处理器系统多处理器系统 多核处理器是指在一个芯片上集成多个处理器多核处理器是指在一个芯片上集成多个处理器多核处理器是指在一个芯片上集成多个处理器多核处理器是指在一个芯片上集成多个处理器核心，即核心，即核心，即核心，即CMP(ChipMultiprocessorCMP(ChipMultiprocessor，CMPCMP单芯片多处理器单芯片多处理器单芯片多处理器单芯片多处理器)。这多个核心间联系非常紧。这多个核心间联系非常紧。这多个核心间联系非常紧。这多个核心间联系非常紧密，甚至共享密，甚至共享密，甚至共享密，甚至共享L1L1、L2L2和和和和L3CacheL3Cache等。等。等。等。CMPCMP通常可分为同构通常可分为同构通常可分为同构通常可分为同构CMPCMP和异构和异构和异构和异构CMPCMP 在存储层次上，在存储层次上，在存储层次上，在存储层次上，CMPCMP结构的互连采用共享二级结构的互连采用共享二级结构的互连采用共享二级结构的互连采用共享二级或三级或三级或三级或三级CacheCache的的的的CMPCMP结构，每个处理器核心拥结构，每个处理器核心拥结构，每个处理器核心拥结构，每个处理器核心拥有私有的一级或二级有私有的一级或二级有私有的一级或二级有私有的一级或二级CacheCache，且所有处理器核，且所有处理器核，且所有处理器核，且所有处理器核心共享下一级心共享下一级心共享下一级心共享下一级CacheCache。核间通信机制目前有两种，一种基于总线共享核间通信机制目前有两种，一种基于总线共享核间通信机制目前有两种，一种基于总线共享核间通信机制目前有两种，一种基于总线共享的的的的CacheCache结构，一种基于片上的互连结构。结构，一种基于片上的互连结构。结构，一种基于片上的互连结构。结构，一种基于片上的互连结构。8.2.1 8.2.1 多核处理器结构多核处理器结构第第8 8章章 多处理器系统多处理器系统 CMP在实际使用中具有如下优点：在实际使用中具有如下优点：（1）微处理器厂商一般采用现有的成熟）微处理器厂商一般采用现有的成熟单核处理器作为处理器核心，从而可缩单核处理器作为处理器核心，从而可缩短设计和验证周期，节省研发成本。短设计和验证周期，节省研发成本。（2）控制逻辑简单）控制逻辑简单,扩展性好扩展性好,易于实现。易于实现。（3）通过动态调节电压）通过动态调节电压/频率、负载优频率、负载优化分布等，可有效降低化分布等，可有效降低CMP功耗。功耗。（4）CMP采用共享采用共享Cache或者内存的方或者内存的方式，多线程的通信延迟较低。式，多线程的通信延迟较低。8.2.1 8.2.1 多核处理器结构多核处理器结构第第8 8章章 多处理器系统多处理器系统 这种结构的特性是：这种结构的特性是：（1）结构中的每个处理器取自己的指令）结构中的每个处理器取自己的指令并对自己的数据进行操作，即每个处理并对自己的数据进行操作，即每个处理器执行自己的指令流，很容易实现多线器执行自己的指令流，很容易实现多线程并行机制。程并行机制。（2）MIMD灵活性强；灵活性强；（3）MIMD结构中的众多处理器可以由结构中的众多处理器可以由同一种处理器来组成同一种处理器来组成8.2.2 8.2.2 多处理器结构多处理器结构8.2.2.1 MIMD8.2.2.1 MIMD计算机概述计算机概述第第8 8章章 多处理器系统多处理器系统 按照多处理器组成的规模，多处理器大按照多处理器组成的规模，多处理器大致可分为致可分为4个层次。个层次。（1）多核处理器）多核处理器（2）中小规模多处理器）中小规模多处理器（3）大规模多处理器）大规模多处理器（4）集群）集群商业集群和客户集群商业集群和客户集群8.2.2.1 MIMD8.2.2.1 MIMD计算机概述计算机概述第第8 8章章 多处理器系统多处理器系统 两种典型的结构：集中式共享存储器系统结两种典型的结构：集中式共享存储器系统结构和分布式存储器系统结构。构和分布式存储器系统结构。1集中式共享存储器系统集中式共享存储器系统8.2.2.2 MIMD8.2.2.2 MIMD计算机的基本结构计算机的基本结构第第8 8章章 多处理器系统多处理器系统 存储器存储器一级或多一级或多级级Cache图图8-3 集中式共享存储器的基本结构集中式共享存储器的基本结构处理处理器器I/O系统系统一级或多一级或多级级Cache处理处理器器一级或多一级或多级级Cache处理处理器器一级或多一级或多级级Cache处理处理器器第第8 8章章 多处理器系统多处理器系统 集中式共享存储器多处理器系统的优点是：集中式共享存储器多处理器系统的优点是：（1）可以与传统的单处理器系统软件兼）可以与传统的单处理器系统软件兼容。容。（2）程序设计容易。）程序设计容易。（3）通信开销小。）通信开销小。集中式共享存储器的结构组成的处理器不集中式共享存储器的结构组成的处理器不能太多，主要受到访存冲突和互联网络的能太多，主要受到访存冲突和互联网络的带宽和复杂性的限制带宽和复杂性的限制第第8 8章章 多处理器系统多处理器系统 2分布式存储器多处理器系统分布式存储器多处理器系统图图8-4分布式存储器多处理器的基本结构分布式存储器多处理器的基本结构处处理理器器+CacheI/O存储存储器器处处理理器器+CacheI/O存储存储器器处处理理器器+CacheI/O存储存储器器处处理理器器+CacheI/O存储存储器器处处理理器器+CacheI/O存储存储器器处处理理器器+CacheI/O存储存储器器处处理理器器+CacheI/O存储存储器器处处理理器器+CacheI/O存储存储器器互互连连网网络络第第8 8章章 多处理器系统多处理器系统 分布式存储器的主要优点是：分布式存储器的主要优点是：如果大部分访存是对节点内的本地存储如果大部分访存是对节点内的本地存储器进行的，这样做是增大存储器带宽的比器进行的，这样做是增大存储器带宽的比较经济的方法；较经济的方法；缩短了本地存储器访问的时延。缩短了本地存储器访问的时延。具有较好的扩展性。具有较好的扩展性。主要缺点是由于处理器不再共享单一集中主要缺点是由于处理器不再共享单一集中存储器，处理器间的数据通信在某种程度存储器，处理器间的数据通信在某种程度上变得更加复杂，且时延也更大。上变得更加复杂，且时延也更大。第第8 8章章 多处理器系统多处理器系统 分布式存储器有两种进行处理器之间通信分布式存储器有两种进行处理器之间通信的方式。的方式。一种是分布式共享存储器（一种是分布式共享存储器（DistributedShared-Memory，简称，简称DSM）系统，它）系统，它将物理上分开的存储器在逻辑上统一为一将物理上分开的存储器在逻辑上统一为一个地址空间，通过个地址空间，通过load和和store操作在统操作在统一的地址空间上隐式地传递数据。一的地址空间上隐式地传递数据。另一种是各个处理器都有自己的私有地址另一种是各个处理器都有自己的私有地址空间，它们在逻辑上分散，相互独立。数空间，它们在逻辑上分散，相互独立。数据通信往往通过显式地在处理器之间传递据通信往往通过显式地在处理器之间传递消息来完成。消息来完成。第第8 8章章 多处理器系统多处理器系统 GustafsonGustafson定律定律定律定律:扩展加速比扩展加速比=N+(1-N)*S其中，其中，其中，其中，N N表示处理器的数量，表示处理器的数量，表示处理器的数量，表示处理器的数量，S S表示程序中串行部分表示程序中串行部分表示程序中串行部分表示程序中串行部分的比例。的比例。的比例。的比例。虽然多处理器有利于程序级、进程级乃至线程级的虽然多处理器有利于程序级、进程级乃至线程级的虽然多处理器有利于程序级、进程级乃至线程级的虽然多处理器有利于程序级、进程级乃至线程级的并行处理，但存在着两个问题是并行开发所要面对并行处理，但存在着两个问题是并行开发所要面对并行处理，但存在着两个问题是并行开发所要面对并行处理，但存在着两个问题是并行开发所要面对的。一是程序可获得的并行度是有限的。二是执行的。一是程序可获得的并行度是有限的。二是执行的。一是程序可获得的并行度是有限的。二是执行的。一是程序可获得的并行度是有限的。二是执行模块之间的通信开销。这限制了多处理器系统的性模块之间的通信开销。这限制了多处理器系统的性模块之间的通信开销。这限制了多处理器系统的性模块之间的通信开销。这限制了多处理器系统的性价比的提高。价比的提高。价比的提高。价比的提高。要解决这两个问题，一是在软件中采用更好的并行要解决这两个问题，一是在软件中采用更好的并行要解决这两个问题，一是在软件中采用更好的并行要解决这两个问题，一是在软件中采用更好的并行算法来提高并行度。二是改进系统结构，如在硬件算法来提高并行度。二是改进系统结构，如在硬件算法来提高并行度。二是改进系统结构，如在硬件算法来提高并行度。二是改进系统结构，如在硬件上缓存共享数据，在确保存储器一致性的前提下，上缓存共享数据，在确保存储器一致性的前提下，上缓存共享数据，在确保存储器一致性的前提下，上缓存共享数据，在确保存储器一致性的前提下，如何使用如何使用如何使用如何使用CacheCache来减少远程访问频率。三是在软件来减少远程访问频率。三是在软件来减少远程访问频率。三是在软件来减少远程访问频率。三是在软件上重新构造数据来尽可能增加本地访问。此外，还上重新构造数据来尽可能增加本地访问。此外，还上重新构造数据来尽可能增加本地访问。此外，还上重新构造数据来尽可能增加本地访问。此外，还可以使用多线程或预取技术来减少时延的影响。可以使用多线程或预取技术来减少时延的影响。可以使用多线程或预取技术来减少时延的影响。可以使用多线程或预取技术来减少时延的影响。8.2.3 8.2.3 8.2.3 8.2.3 多处理器并行处理定量分析和所遇到的问题多处理器并行处理定量分析和所遇到的问题多处理器并行处理定量分析和所遇到的问题多处理器并行处理定量分析和所遇到的问题第第8 8章章 多处理器系统多处理器系统 8.3 8.3 多处理器的多处理器的CacheCache一致性一致性 对称式共享存储器系统和多处理器的对称式共享存储器系统和多处理器的CacheCache一致性一致性 分布式共享存储器系统和基于目录的分布式共享存储器系统和基于目录的CacheCache一致性一致性第第8 8章章 多处理器系统多处理器系统 8.3.1 8.3.1 8.3.1 8.3.1 对称式共享存储器系统和多处理器的对称式共享存储器系统和多处理器的对称式共享存储器系统和多处理器的对称式共享存储器系统和多处理器的CacheCacheCacheCache一致性一致性一致性一致性 对称式共享存储器系统对称式共享存储器系统 多处理器的多处理器的CacheCache一致性一致性 监听式协议实现多处理器的监听式协议实现多处理器的CacheCache一致性一致性第第8 8章章 多处理器系统多处理器系统 8.3.1.1 8.3.1.1 8.3.1.1 8.3.1.1 对称式共享存储器系统对称式共享存储器系统对称式共享存储器系统对称式共享存储器系统存储器存储器一级或多一级或多级级Cache图图8-5 对称式共享存储器的基本结构对称式共享存储器的基本结构处理处理器器一级或多一级或多级级Cache处理处理器器一级或多一级或多级级Cache处理处理器器一级或多一级或多级级Cache处理处理器器I/O系统系统存储器存储器存储器存储器存储器存储器互互连连网网络络第第8 8章章 多处理器系统多处理器系统 8.3.1.1 8.3.1.1 对称式共享存储器系统对称式共享存储器系统对对对对称称称称式式式式共共共共享享享享存存存存储储储储器器器器系系系系统统统统支支支支持持持持共共共共享享享享和和和和私私私私有有有有数数数数据据据据的的的的缓缓缓缓存存存存，私私私私有有有有数数数数据据据据被被被被单单单单个个个个处处处处理理理理器器器器使使使使用用用用，而而而而共共共共享享享享数数数数据据据据则则则则被被被被多多多多个个个个处处处处理理理理器器器器使使使使用用用用，基基基基本本本本上上上上是是是是通通通通过过过过读读读读写写写写共共共共享享享享数数数数据据据据完完完完成成成成处处处处理理理理器器器器之之之之间间间间的的的的通通通通信信信信。把把把把一一一一个个个个私私私私有有有有数数数数据据据据缓缓缓缓存存存存之之之之后后后后，支支支支该该该该数数数数据据据据的的的的访访访访问问问问就就就就可可可可以以以以在在在在CacheCache中中中中形形形形成成成成副副副副本本本本，这这这这样样样样做做做做除除除除了了了了会会会会减减减减少少少少访访访访问问问问时时时时延延延延和和和和降降降降低低低低对对对对存存存存储储储储器器器器带带带带宽宽宽宽的的的的要要要要求求求求外外外外，还还还还能能能能减减减减少少少少多多多多个个个个处处处处理理理理器器器器同同同同时时时时读读读读取取取取共共共共享享享享数数数数据据据据时时时时的的的的竞竞竞竞争争争争现现现现象象象象。然然然然而而而而，把把把把共共共共享享享享数数数数据据据据放放放放入入入入CacheCache又又又又出现了一个新的问题：出现了一个新的问题：出现了一个新的问题：出现了一个新的问题：CacheCache一致性。一致性。一致性。一致性。第第8 8章章 多处理器系统多处理器系统 8.3.1.2 8.3.1.2 多处理器的多处理器的CacheCache一致性一致性所所谓谓多多处处理理器器的的Cache一一致致性性问问题题，是是指指由由于于缓缓存存共共享享数数据据，两两个个不不同同的的处处理理器器所所保保存存的的存存储储器器视视图图可可能能是是通通过过各各自自的的Cache得得到到的的。因因此此，如如果果没没有有其其它它的的防防范范措措施施，则则会会导导致致两两个个处处理理器器分分别别得得到到两两个个不不同同的的值。值。解解决决多多处处理理器器的的Cache一一致致性性问问题题的的方方法法有有软件方法、总线监听法和目录表法。软件方法、总线监听法和目录表法。第第8 8章章 多处理器系统多处理器系统 8.3.1.2 8.3.1.2 多处理器的多处理器的CacheCache一致性一致性软件方法主要依靠编译程序进行分析，同时需要硬软件方法主要依靠编译程序进行分析，同时需要硬软件方法主要依靠编译程序进行分析，同时需要硬软件方法主要依靠编译程序进行分析，同时需要硬件机制的配合，使共享信息安排在主存中，而避免件机制的配合，使共享信息安排在主存中，而避免件机制的配合，使共享信息安排在主存中，而避免件机制的配合，使共享信息安排在主存中，而避免将它们存放到将它们存放到将它们存放到将它们存放到CacheCache中。这需要一种机制，使软件中。这需要一种机制，使软件中。这需要一种机制，使软件中。这需要一种机制，使软件能够对数据进行标记，并按时序进行调度。另外对能够对数据进行标记，并按时序进行调度。另外对能够对数据进行标记，并按时序进行调度。另外对能够对数据进行标记，并按时序进行调度。另外对于具有良好结构的循环级并行程序，且在循环中需于具有良好结构的循环级并行程序，且在循环中需于具有良好结构的循环级并行程序，且在循环中需于具有良好结构的循环级并行程序，且在循环中需要显式地复制数据，使用软件方法有可能大大降低要显式地复制数据，使用软件方法有可能大大降低要显式地复制数据，使用软件方法有可能大大降低要显式地复制数据，使用软件方法有可能大大降低访存开销。访存开销。访存开销。访存开销。软件方法的优点是不需要硬件提供很多支持，减少软件方法的优点是不需要硬件提供很多支持，减少软件方法的优点是不需要硬件提供很多支持，减少软件方法的优点是不需要硬件提供很多支持，减少了硬件的复杂性，降低了对互连网络通信量的要求。了硬件的复杂性，降低了对互连网络通信量的要求。了硬件的复杂性，降低了对互连网络通信量的要求。了硬件的复杂性，降低了对互连网络通信量的要求。其局限性在于编译器进行一致性处理的能力是很有其局限性在于编译器进行一致性处理的能力是很有其局限性在于编译器进行一致性处理的能力是很有其局限性在于编译器进行一致性处理的能力是很有限的，并且只能用于共享存储器的系统。限的，并且只能用于共享存储器的系统。限的，并且只能用于共享存储器的系统。限的，并且只能用于共享存储器的系统。第第8 8章章 多处理器系统多处理器系统 8.3.1.3 8.3.1.3 8.3.1.3 8.3.1.3 监听式协议实现多处理器的监听式协议实现多处理器的监听式协议实现多处理器的监听式协议实现多处理器的CacheCacheCacheCache一致性一致性一致性一致性监听式协议对于采用总线互连共享主存的监听式协议对于采用总线互连共享主存的多处理器系统，可利用总线的播送来实现。多处理器系统，可利用总线的播送来实现。它让各个处理器上的它让各个处理器上的Cache控制器对总线控制器对总线进行监视或监听，来确定它们是否含有总进行监视或监听，来确定它们是否含有总线或交换机上请求的数据块的副本，从而线或交换机上请求的数据块的副本，从而跟踪共享数据，以保证跟踪共享数据，以保证Cache一致性。监一致性。监听式协议使用硬件解决办法。听式协议使用硬件解决办法。有两种方法可以实现监听式协议：有两种方法可以实现监听式协议：写无效写无效协议和写更新或写广播协议。协议和写更新或写广播协议。第第8 8章章 多处理器系统多处理器系统 8.3.2 8.3.2 8.3.2 8.3.2 分布式共享存储器系统和基于目录的分布式共享存储器系统和基于目录的分布式共享存储器系统和基于目录的分布式共享存储器系统和基于目录的CacheCacheCacheCache一致性一致性一致性一致性 各个节点带有目录的分布式存储器多处理器各个节点带有目录的分布式存储器多处理器系统系统所谓目录式协议，是指把物理存储器的共享所谓目录式协议，是指把物理存储器的共享状态存放在一个地点，称之为目录。目录状态存放在一个地点，称之为目录。目录表中每项保存了每个表中每项保存了每个Cache数据块的使用数据块的使用情况。为了防止访问目录表成为瓶颈，需情况。为了防止访问目录表成为瓶颈，需要使目录随存储器分布。要使目录随存储器分布。第第8 8章章 多处理器系统多处理器系统 各个节点带有目录的分布式存储器多处理器系统各个节点带有目录的分布式存储器多处理器系统各个节点带有目录的分布式存储器多处理器系统各个节点带有目录的分布式存储器多处理器系统图图8-8 各个节点带有目录的分布式存储器多处理器系统的基本结构各个节点带有目录的分布式存储器多处理器系统的基本结构处理处理器器+CacheI/O存储存储器器处理处理器器+CacheI/O存储存储器器目录目录目录目录处理处理器器+CacheI/O存储存储器器处理处理器器+CacheI/O存储存储器器目录目录目录目录处理处理器器+CacheI/O存储存储器器处理处理器器+CacheI/O存储存储器器目录目录目录目录处理处理器器+CacheI/O存储存储器器处理处理器器+CacheI/O存储存储器器目录目录目录目录互互 连连 网网 络络第第8 8章章 多处理器系统多处理器系统 一般目录表中记录的一般目录表中记录的一般目录表中记录的一般目录表中记录的CacheCache数据块的状态主要有：数据块的状态主要有：数据块的状态主要有：数据块的状态主要有：共享：共享：共享：共享：该该该该CacheCache数据块具有正确的副本。数据块具有正确的副本。数据块具有正确的副本。数据块具有正确的副本。未缓存：未缓存：未缓存：未缓存：没有任何一个处理器含有该数据块的副本。没有任何一个处理器含有该数据块的副本。没有任何一个处理器含有该数据块的副本。没有任何一个处理器含有该数据块的副本。修改：修改：修改：修改：只有一个处理器拥有该只有一个处理器拥有该只有一个处理器拥有该只有一个处理器拥有该CacheCache数据块的正确数据块的正确数据块的正确数据块的正确副本并且对该块执行过写操作，因此其它存储器中副本并且对该块执行过写操作，因此其它存储器中副本并且对该块执行过写操作，因此其它存储器中副本并且对该块执行过写操作，因此其它存储器中与之对应的副本是无效的。这个处理器成为该块的与之对应的副本是无效的。这个处理器成为该块的与之对应的副本是无效的。这个处理器成为该块的与之对应的副本是无效的。这个处理器成为该块的所有者。所有者。所有者。所有者。无效：无效：无效：无效：由于某个处理器执行写操作，使得本处理器由于某个处理器执行写操作，使得本处理器由于某个处理器执行写操作，使得本处理器由于某个处理器执行写操作，使得本处理器含有该数据块的副本被标记为无效状态。含有该数据块的副本被标记为无效状态。含有该数据块的副本被标记为无效状态。含有该数据块的副本被标记为无效状态。第第8 8章章 多处理器系统多处理器系统 目录表的具体作法可分为目录表的具体作法可分为3种。种。（1）全映象目录表法。）全映象目录表法。（2）有限目录表法。）有限目录表法。（3）链式目录表法。）链式目录表法。目录式协议的实现要占据一些存储空间，比目录式协议的实现要占据一些存储空间，比监听式协议的开销略微偏高，但是可以用来监听式协议的开销略微偏高，但是可以用来扩展更多的处理器，很适合于分布式共享存扩展更多的处理器，很适合于分布式共享存储器系统。储器系统。监听式协议要求处理器在修改数据块时向所监听式协议要求处理器在修改数据块时向所有处理器广播有处理器广播Cache缺失的信息，这种方法缺失的信息，这种方法实现简单，但也限制了其扩展性。实现简单，但也限制了其扩展性。第第8 8章章 多处理器系统多处理器系统 8.4 8.4 多处理器系统的同步机制多处理器系统的同步机制 基本硬件原语基本硬件原语8.4.2 8.4.2 同步机制的实现同步机制的实现 多线程同步机制带来的问题多线程同步机制带来的问题第第8 8章章 多处理器系统多处理器系统 8.4.1 8.4.1 基本硬件原语基本硬件原语实实实实现现现现多多多多处处处处理理理理器器器器系系系系统统统统同同同同步步步步的的的的关关关关键键键键是是是是要要要要有有有有一一一一个个个个能能能能够够够够以以以以原原原原子方式对存储器执行读写操作的硬件原语集合。子方式对存储器执行读写操作的硬件原语集合。子方式对存储器执行读写操作的硬件原语集合。子方式对存储器执行读写操作的硬件原语集合。硬硬硬硬件件件件原原原原语语语语可可可可有有有有多多多多种种种种不不不不同同同同的的的的形形形形式式式式，但但但但都都都都必必必必须须须须支支支支持持持持原原原原子子子子方式的读写操作，并能够返回操作是否成功的信息。方式的读写操作，并能够返回操作是否成功的信息。方式的读写操作，并能够返回操作是否成功的信息。方式的读写操作，并能够返回操作是否成功的信息。这这这这些些些些硬硬硬硬件件件件原原原原语语语语是是是是构构构构造造造造多多多多种种种种不不不不同同同同的的的的用用用用户户户户层层层层同同同同步步步步操操操操作作作作的的的的基本构件，比如锁和屏障等。基本构件，比如锁和屏障等。基本构件，比如锁和屏障等。基本构件，比如锁和屏障等。一一一一般般般般来来来来说说说说，硬硬硬硬件件件件原原原原语语语语对对对对应应应应用用用用程程程程序序序序员员员员是是是是透透透透明明明明的的的的，而而而而是是是是由由由由系系系系统统统统程程程程序序序序员员员员用用用用这这这这些些些些硬硬硬硬件件件件原原原原语语语语构构构构建建建建一一一一个个个个同同同同步步步步库库库库来来来来支支支支持线程的同步机制。持线程的同步机制。持线程的同步机制。持线程的同步机制。第第8 8章章 多处理器系统多处理器系统 基本的硬件原语基本的硬件原语基本的硬件原语基本的硬件原语（1 1）原原原原子子子子互互互互换换换换。典典典典型型型型的的的的构构构构建建建建同同同同步步步步原原原原语语语语的的的的操操操操作作作作，它它它它将将将将一一一一个个个个寄寄寄寄存存存存器器器器中中中中的的的的值值值值与与与与一一一一个个个个存存存存储储储储器器器器中中中中的的的的值值值值进进进进行行行行互互互互换换换换。用用用用这这这这种种种种原原原原语语语语可可可可建建建建立立立立基基基基本本本本的的的的同同同同步步步步机机机机制制制制。例例例例如如如如可可可可建建建建立立立立一一一一个个个个简简简简单单单单的的的的锁锁锁锁（一一一一个个个个共共共共享享享享的的的的变变变变量量量量），其其其其中中中中0 0表表表表示示示示锁锁锁锁是是是是打打打打开开开开的的的的，1 1表表表表示示示示锁锁锁锁是是是是关关关关闭闭闭闭的的的的。如如如如果果果果某某某某个个个个处处处处理理理理器器器器要要要要访访访访问问问问存存存存储储储储器器器器，可可可可通通通通过过过过将将将将寄寄寄寄存存存存器器器器中中中中的的的的1 1与与与与存存存存储储储储器器器器中中中中的的的的锁锁锁锁的的的的值值值值交交交交换换换换，若若若若返返返返回回回回值值值值为为为为1 1，表表表表明明明明有有有有其其其其它它它它处处处处理理理理器器器器占占占占用用用用了了了了该该该该锁锁锁锁，不不不不能能能能访访访访问问问问；若若若若返返返返回回回回值值值值为为为为0 0，表表表表明明明明无无无无其其其其它它它它处处处处理理理理器器器器占占占占用用用用，并并并并已已已已被被被被该该该该处处处处理理理理器器器器占占占占用用用用，且且且且此此此此时时时时存存存存储储储储器器器器锁锁锁锁值值值值为为为为1 1，在在在在这这这这个个个个处处处处理理理理器器器器将将将将锁锁锁锁释释释释放放放放之之之之前前前前，其其其其它它它它处处处处理理理理器器器器无无无无法法法法占占占占用用用用。如如如如果果果果有有有有两两两两个个个个处处处处理理理理器器器器试试试试图图图图同同同同时时时时进进进进行行行行这这这这种种种种互互互互换换换换，这这这这就就就就发发发发生生生生了了了了竞竞竞竞争争争争。此此此此时时时时，只只只只能能能能有有有有一一一一个个个个处处处处理理理理器器器器首首首首先先先先执执执执行行行行互互互互换换换换并并并并得得得得到到到到返返返返回回回回值值值值0 0，而而而而另另另另一一一一个个个个处处处处理理理理器器器器执执执执行行行行互互互互换换换换时时时时得得得得到到到到返返返返回回回回值值值值1 1。应应应应用用用用互互互互换换换换原原原原语语语语实实实实现现现现同同同同步步步步的的的的关关关关键键键键是是是是这这这这种种种种操操操操作作作作具具具具有有有有原原原原子子子子性性性性：互互互互换换换换是是是是不不不不可可可可分分分分割割割割的的的的，两两两两个个个个同同同同时时时时进进进进行行行行的的的的互互互互换换换换操操操操作作作作将将将将被被被被排排排排序序序序进进进进行行行行，不不不不可可可可能能能能进进进进行行行行这这这这种种种种互互互互换换换换时时时时都都都都返返返返回回回回0 0值。值。值。值。第第8 8章章 多处理器系统多处理器系统 基本的硬件原语基本的硬件原语基本的硬件原语基本的硬件原语（2）测测试试并并置置位位（test-and-set）。这这是是许许多多早早期期的的多多处处理理器器系系统统采采用用的的同同步步操操作作。它它先先对对一一个个数数值值进进行行测测试试，若若该该数数值值通通过过了了检检测测则则执执行行设设置置。例例如如在在测测试试数数值值为为0时时将将其其设设置为置为1，这与前述原子互换类似。，这与前述原子互换类似。（3）读读取取并并加加1（fetch-and-increment）。它它返返回回存存储储器器中中的的值值并并以以原原子子操操作作的的方方式式使使存存储储器器中中的的值值加加1。若若用用0表表示示同同步步变变量量未未被被占占用用，则则可可以以像像使使用用原原子子互互换换一一样样得得到到类类似似的结果。当然，这类操作还有其它用途。的结果。当然，这类操作还有其它用途。第第8 8章章 多处理器系统多处理器系统 基本的硬件原语基本的硬件原语基本的硬件原语基本的硬件原语（4 4）读读读读取取取取并并并并更更更更新新新新（fetch-and-updatefetch-and-update）。这这这这是是是是一一一一种种种种新新新新型型型型的的的的同同同同步步步步原原原原子子子子操操操操作作作作，可可可可以以以以包包包包含含含含上上上上述述述述同同同同步步步步原原原原语语语语的的的的功功功功能能能能。这这这这一一一一对对对对指指指指令令令令包包包包括括括括一一一一条条条条专专专专门门门门的的的的装装装装载载载载指指指指令令令令，称称称称为为为为链链链链 接接接接 装装装装 载载载载（loadload linkedlinked）或或或或 上上上上 锁锁锁锁 装装装装 载载载载（loadloadlockedlocked）即即即即LLLL指指指指令令令令；还还还还包包包包括括括括一一一一条条条条称称称称为为为为条条条条件件件件存存存存储储储储（storestoreconditioncondition）即即即即SCSC指指指指令令令令。LLLL指指指指令令令令和和和和SCSC指指指指令令令令按按按按顺顺顺顺序序序序执执执执行行行行。如如如如果果果果LLLL指指指指令令令令指指指指定定定定的的的的存存存存储储储储单单单单元元元元的的的的地地地地址址址址值值值值在在在在对对对对应应应应的的的的SCSC指指指指令令令令执执执执行行行行之之之之前前前前被被被被改改改改变变变变了了了了，则则则则条条条条件件件件存存存存储储储储失失失失败败败败。如如如如果果果果处处处处理理理理