计算机体系结构(张晨曦)第8章-PPT

第8章多处理机8.1引言8.2对称式共享存储器系统结构8.3分布式共享存储器系统结构8.4同步8.5同时多线程8.6多处理机实例8.1引言1.单处理机系统结构正在走向尽头？2.多处理机正起着越来越重要的作用。近两年来，我们已经开始进入多处理机将起主要作用的新时期。期望：将来更加普及问题：如何发挥其潜在计算能力？（并行程序）应用是否具有足够的并行性？并行计算机应用软件已有了稳定的发展。（尽管缓慢）并行处理已经成为重要和主流的技术。3.本章重点：中小规模的计算机(处理器的个数＜128)（多处理机设计的主流）8.1引言1.Flynn分类法SISD、SIMD、MISD、MIMD2.MIMD已成为通用多处理机系统结构的选择，原因：MIMDMIMD可以充分利用商品化微处理器在性能价格比方面的优势。计算机机群系统（cluster）是一类广泛被采用的MIMD计算机。8.1.1并行计算机系统结构的分类8.1引言3.根据系统中处理器个数的多少，可把现有的MIMD计算机分为两类：（每一类代表了一种存储器的结构和互连策略）集中式共享存储器结构动画最多由几十个处理器构成。通过大容量的Cache和总线互连使各处理器共享一个单独的物理存储器。这类计算机有时被称为SMP计算机（Symmetricshared-memoryMultiProcessor）UMA计算机（UniformMemoryAccess）8.1引言CPU0CPU1CPU2CPU3存储器I/O对称式共享存储器多处理机的基本结构8.1引言分布式存储器结构动画每个结点包含：处理器存储器I／O互连网络接口在许多情况下，分布式存储器结构优于集中式共享存储器结构。8.1引言互连网络I/o存储器I/o存储器I/o存储器I/o存储器CPU0CPU1CPU2CPU3存储器I/o存储器I/o存储器I/o存储器I/oCPU4CPU5CPU6CPU78.1引言分布式存储器结构的优点如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求。对局部存储器的访问延迟低。最主要的缺点处理器之间的通信较为复杂，且各处理器之间访问延迟较大。簇：超级结点每个结点内包含个数较少（例如2～8）的处理器；处理器之间可采用另一种互连技术（例如总线）相互连接形成簇。8.1引言1.地址空间的组织方案（两种）共享地址空间物理上分离的多个存储器作为一个逻辑上共享的存储空间进行编址。任何一个处理器可以访问该共享空间中的任何一个单元（如果它具有访问权），而且不同处理器上的同一个物理地址指向的是同一个存储单元。这类机器的结构被称为分布式共享存储器结构（DSM:DistributedShared-Memory)NUMA机器（NUMA:Non-UniformMemoryAccess)8.1.2通信模型和存储器的结构模型8.1引言整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。每一个处理器-存储器模块实际上是一台单独的计算机现在的这种机器多以集群的形式存在2.两种通信机制共享地址空间的机器利用load和store指令中的地址隐含地进行数据通信。多个地址空间的机器通过处理器间显式地传递消息来完成。（消息传递多处理机）8.1引言消息传递计算机通过传递消息来请求某些服务或传输数据，从而完成通信。例如：一个处理器要对远程存储器上的数据进行访问或操作：发送消息，请求传递数据或对数据进行操作；远程进程调用(RPC，RemoteProcessCall)目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。同步消息传递请求处理器发送一个请求后一直要等到应答结果才继续运行。8.1引言异步消息传递发送方不经请求就直接把数据送往数据接收方。3.通信机制的性能指标（3个通信带宽理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。通信延迟理想状态下通信延迟应尽可能地小。通信延迟＝发送开销＋跨越时间＋传输延迟＋接收开销跨越时间：数字信号从发送方的线路端传送到接收方的线路端所经过的时间。传输时间：全部的消息量除以线路带宽。8.1引言通信延迟的隐藏如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通信延迟的隐藏。通常的原则：只要可能就隐藏延迟。通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。4.不同通信机制的优点共享存储器通信的主要优点与常用的对称式多处理机使用的通信机制兼容。易于编程，同时在简化编译器设计方面也占有优势。8.1引言当通信数据量较小时，通信开销较低，带宽利用较好。通过硬件控制的Cache减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。消息传递通信机制的主要优点硬件较简单。通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少，以便编程者和编译程序设法减少通信开销。8.1引言可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。在共享存储器上支持消息传递相对简单。在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息的发送和接收。8.1引言并行处理面临着两个重要的挑战程序中的并行性有限相对较高的通信开销8.1.3并行处理面临的挑战理论加速比可加速部分比例可加速部分比例）（11系统加速比=8.1引言1.第一个挑战有限的并行性使机器要达到好的加速比十分困难。例8.1假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？解Amdahl定律为－可加速部分比例）＋（理论加速比可加速部分比例加速比＝11－并行比例）＋（并行比例＝1100180由上式可得，并行比例＝0.99758.1引言2.第二个挑战：多处理机中远程访问的延迟较大在现有的计算机中，处理器之间的数据通信大约需要100～1000个时钟周期。主要取决于：通信机制、互连网络的种类和计算机的规模在几种不同的共享存储器并行计算机中远程访问一个字的典型延迟8.1引言计算机类型通信机制互连网络处理机最大数量典型远程存储器访问时间（ns）SunStarfireserversSMP多总线64500SGIOrigin3000NUMA胖超立方体512500CrayT3ENUMA3维环网2048300HPVseriesSMP8×8交叉开关321000HPAlphaServerGSSMP开关总线324008.1引言例8.2假设有一台32个处理器的多处理机，对远程存储器访问时间为400ns。除了通信以外，假设所有其他访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器的时钟频率为1GHz，如果指令基本的IPC为2（设所有访存均命中Cache），求在没有远程访问的情况下和有0.2%的指令需要远程访问的情况下，前者比后者快多少?8.1引言解没有远程访问时，机器的CPI为1/基本IPC=1/2=0.5有0.2%远程访问的机器的实际CPI为CPI＝基本CPI＋远程访问率×远程访问开销＝0.5＋0.2%×远程访问开销远程访问开销为远程访问时间/时钟周期时间＝400ns/1ns＝400个时钟周期∴CPI＝0.5＋0.2%×400＝1.3因此在没有远程访问的情况下的计算机速度是有0.2%远程访问的计算机速度的1.3/0.5=2.6倍。8.1引言问题的解决并行性不足：采用并行性更好的算法远程访问延迟的降低：靠系统结构支持和编程技术3.在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：应用程序的高层特性如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。依据应用特点可把多机工作负载大致分成两类：单个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载8.1引言4.并行程序的计算／通信比率反映并行程序性能的一个重要的度量：计算与通信的比率计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而降低。多个处理器共享一个存储器。当处理机规模较小时，这种计算机十分经济。教材中图8.1是这种计算机的一个简单示意图。支持对共享数据和私有数据的Cache缓存私有数据供一个单独的处理器使用，而共享数据则是供多个处理器使用。共享数据进入Cache产生了一个新的问题Cache的一致性问题8.2对称式共享存储器系统结构8.2对称式共享存储器系统结构1.不一致产生的原因（Cache一致性问题）I／O操作Cache中的内容可能与由I／O子系统输入/输出形成的存储器对应部分的内容不同。共享数据不同处理器的Cache都保存有对应存储器单元的内容。例两个处理器的读写8.2.1多处理机Cache一致性8.2对称式共享存储器系统结构由两个处理器（A和B）读写引起的Cache一致性问题时间事件CPUACache内容CPUBCache内容X单元存储器内容011CPUA读X112CPUB读X1113CPUA将0存入X0108.2对称式共享存储器系统结构2.存储器的一致性（非正式定义）如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。存储系统行为的两个不同方面What:读操作得到的是什么值When:什么时候才能将已写入的值返回给读操作需要满足以下条件处理器P对单元X进行一次写之后又对单元X进行读，读和写之间没有其他处理器对单元X进行写，则P读到的值总是前面写进去的值。8.2对称式共享存储器系统结构处理器P对单元X进行写之后，另一处理器Q对单元X进行读，读和写之间无其他写，则Q读到的值应为P写进去的值。对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度看来顺序都是相同的。(写顺序化)在后面的讨论中，我们假设：直到所有的处理器均看到了写的结果，这个写操作才算完成；处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但必须以程序规定的顺序进行写。8.2对称式共享存储器系统结构在一致的多处理机中，Cache提供两种功能：共享数据的迁移降低了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。共享数据的复制不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。一般情况下，小规模多处理机采用硬件的方法来实现Cache的一致性。8.2.2实现一致性的基本方案8.2对称式共享存储器系统结构1.Cache一致性协议在多个处理器中用来维护一致性的协议。关键：跟踪记录共享数据块的状态两类协议（采用不同的共享数据状态跟踪技术）目录法（directory）物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。监听法（snooping）每个Cache除了包含物理存储器中块的数据副本之外，也保存着各个块的共享状态信息。8.2对称式共享存储器系统结构Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。2.两种更新协议（维持一致性要求）写作废协议在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。(作废其他副本)8.2对称式共享存储器系统结构处理器行为总线行为CPUACache内容CPUBCache内容主存单元X的内容0CPUA读XCache失效00CPUB读XCache失效000CPUA将1写入单元X作废X单元10CPUB读XCache失效111例在写回Cache、监听总线的情况下，写作废协议的实现8.2对称式共享存储器系统结构写更新协议当一个处理器对某数据项进行写入时，通过广播使其他Cache中所有对应于该数据项的副本进行更新。例在写回Cache、监听总线的情况下，写更新协议的实现。处理器行为总线行为CPUACache内容CPUBCache内容主存单元X的内容0CPUA读XCache失效00CPUB读