第10章(CQReview)多处理机.

1/156▲第10章多处理机张晨曦刘依曹强（review）[e-mail]2/156▲10.1引言10.2对称式共享存储器系统结构10.3分布式共享存储器系统结构10.4同步10.5同时多线程10.6大规模并行处理机MPP10.7多处理机实例1：T110.8多处理机实例2：Origin20001.单处理机系统结构正在走向尽头？2.多处理机正起着越来越重要的作用。近几年来，人们确实开始转向了多处理机。Intel于2004年宣布放弃了其高性能单处理器项目，转向多核（multi-core）的研究和开发。IBM、SUN、AMD等公司并行计算机应用软件已有了稳定的发展。充分利用商品化微处理器所具有的高性能价格比的优势。3.本章重点：中小规模的计算机(处理器的个数＜32)（多处理机设计的主流）10.1引言4/156▲10.1引言1.Flynn分类法SISD、SIMD、MISD、MIMD2.MIMD已成为通用多处理机系统结构的选择，原因：MIMDMIMD可以充分利用商品化微处理器在性能价格比方面的优势。计算机机群系统（cluster）是一类广泛被采用的MIMD机器。10.1.1并行计算机系统结构的分类5/156▲10.1引言3.根据存储器的组织结构，把现有的MIMD机器分为两类：（每一类代表了一种存储器的结构和互连策略）集中式共享存储器结构动画最多由几十个处理器构成。各处理器共享一个集中式的物理存储器。这类机器有时被称为SMP机器（Symmetricshared-memoryMultiProcessor）UMA机器（UniformMemoryAccess）6/156▲10.1引言CPU0CPU1CPU2CPU3存储器I/O对称式共享存储器多处理机的基本结构7/156▲10.1引言分布式存储器多处理机动画存储器在物理上是分布的。每个结点包含：处理器存储器I／O互连网络接口在许多情况下，分布式存储器结构优于集中式共享存储器结构。8/156▲10.1引言互连网络I/o存储器I/o存储器I/o存储器I/o存储器CPU0CPU1CPU2CPU3存储器I/o存储器I/o存储器I/o存储器I/oCPU4CPU5CPU6CPU79/156▲10.1引言将存储器分布到各结点有两个优点如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；对本地存储器的访问延迟时间小。最主要的缺点处理器之间的通信较为复杂，且各处理器之间访问延迟较大。簇：超级结点每个结点内包含个数较少（例如2～8）的处理器；处理器之间可采用另一种互连技术（例如总线）相互连接形成簇。10/156▲10.1引言1.两种存储器系统结构和通信机制共享地址空间物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址。任何一个处理器可以访问该共享空间中的任何一个单元（如果它具有访问权），而且不同处理器上的同一个物理地址指向的是同一个存储单元。这类计算机被称为分布式共享存储器系统（DSM:DistributedShared-Memory)NUMA机器（NUMA:Non-UniformMemoryAccess)10.1.2存储器系统结构和通信机制11/156▲10.1引言把每个结点中的存储器编址为一个独立的地址空间，不同结点中的地址空间之间是相互独立的。整个系统的地址空间由多个独立的地址空间构成每个结点中的存储器只能由本地的处理器进行访问，远程的处理器不能直接对其进行访问。每一个处理器-存储器模块实际上是一台单独的计算机现在的这种机器多以集群的形式存在2.通信机制共享存储器通信机制共享地址空间的计算机系统采用12/156▲10.1引言处理器之间是通过用load和store指令对相同存储器地址进行读/写操作来实现的。消息传递通信机制多个独立地址空间的计算机采用通过处理器间显式地传递消息来完成消息传递多处理机中，处理器之间是通过发送消息来进行通信的，这些消息请求进行某些操作或者传送数据。13/156▲10.1引言例如：一个处理器要对远程存储器上的数据进行访问或操作：发送消息，请求传递数据或对数据进行操作；远程进程调用(RPC，RemoteProcessCall)目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。同步消息传递请求处理器发送一个消息后一直要等到应答结果才继续运行。异步消息传递数据发送方知道别的处理器需要数据，通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方。14/156▲10.1引言3.不同通信机制的优点共享存储器通信的主要优点与常用的对称式多处理机使用的通信机制兼容。易于编程，同时在简化编译器设计方面也占有优势。采用大家所熟悉的共享存储器模型开发应用程序，而把重点放到解决对性能影响较大的数据访问上。当通信数据量较小时，通信开销较低，带宽利用较好。可以通过采用Cache技术来减少远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。15/156▲10.1引言消息传递通信机制的主要优点硬件较简单。通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少。显式通信可以让编程者重点注意并行计算的主要通信开销，使之有可能开发出结构更好、性能更高的并行程序。同步很自然地与发送消息相关联，能减少不当的同步带来错误的可能性。16/156▲10.1引言可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。在共享存储器上支持消息传递相对简单。在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息的发送和接收。17/156▲10.1引言并行处理面临着两个重要的挑战程序中的并行性有限相对较大的通信开销10.1.3并行处理面临的挑战理论加速比可加速部分比例可加速部分比例）（11系统加速比=18/156▲10.1引言1.第一个挑战有限的并行性使计算机要达到很高的加速比十分困难。例10.1假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？解Amdahl定律为：－可加速部分比例）＋（理论加速比可加速部分比例加速比＝11－并行比例）＋（并行比例＝1100180由上式可得：并行比例＝0.997519/156▲10.1引言2.第二个挑战：多处理机中远程访问的延迟较大在现有的机器中，处理器之间的数据通信大约需要50～1000个时钟周期。主要取决于：通信机制、互连网络的种类和机器的规模在几种不同的共享存储器并行计算机中远程访问一个字的典型延迟20/156▲10.1引言机器通信机制互连网络处理机最大数量典型远程存储器访问时间（ns）SunStarfireserversSMP多总线64500SGIOrigin3000NUMA胖超立方体512500CrayT3ENUMA3维环网2048300HPVseriesSMP8×8交叉开关321000HPAlphaServerGSSMP开关总线3240021/156▲10.1引言例10.2假设有一台32台处理器的多处理机，对远程存储器访问时间为200ns。除了通信以外，假设所有其它访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器的时钟频率为2GHz，如果指令基本的CPI为0.5（设所有访存均命中Cache），求在没有远程访问的情况下和有0.2%的指令需要远程访问的情况下，前者比后者快多少?22/156▲10.1引言解有0.2%远程访问的机器的实际CPI为：CPI＝基本CPI＋远程访问率×远程访问开销＝0.5＋0.2%×远程访问开销远程访问开销为：远程访问时间/时钟周期时间＝200ns/0.5ns＝400个时钟周期∴CPI＝0.5＋0.2%×400＝1.3因此在没有远程访问的情况下的机器速度是有0.2%远程访问的机器速度的1.3/0.5=2.6倍。23/156▲10.1引言问题的解决并行性不足：采用并行性更好的算法远程访问延迟的降低：靠系统结构支持和编程技术3.在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：应用程序的高层特性如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。依据应用特点可把多机工作负载大致分成两类：单个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载24/156▲10.1引言4.并行程序的计算／通信比率反映并行程序性能的一个重要的度量：计算与通信的比率计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而减少。25/156▲多个处理器共享一个存储器。当处理机规模较小时，这种计算机十分经济。近些年，能在一个单独的芯片上实现2～8个处理器核。例如：Sun公司2006年T18核的多处理器支持对共享数据和私有数据的Cache缓存私有数据供一个单独的处理器使用，而共享数据则是供多个处理器使用。共享数据进入Cache产生了一个新的问题Cache的一致性问题10.2对称式共享存储器系统结构26/156▲10.2对称式共享存储器系统结构1.多处理机的Cache一致性问题允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致。例由两个处理器（A和B）读写引起的Cache一致性问题10.2.1多处理机Cache一致性…mCPUA（a）CPUA写入前存储器CPUB…………CacheA…pCPUA（b）CPUA将p写入X，p≠m存储器CPUB……………CacheA写入CacheBCacheBXXX的副本…mmmpX的副本28/156▲10.2对称式共享存储器系统结构2.存储器的一致性如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。存储系统行为的两个不同方面What:读操作得到的是什么值When:什么时候才能将已写入的值返回给读操作需要满足以下条件处理器P对单元X进行一次写之后又对单元X进行读，读和写之间没有其它处理器对单元X进行写，则P读到的值总是前面写进去的值。29/156▲10.2对称式共享存储器系统结构处理器P对单元X进行写之后，另一处理器Q对单元X进行读，读和写之间无其它写，则Q读到的值应为P写进去的值。对同一单元的写是串行化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度看来顺序都是相同的。(写串行化)在后面的讨论中，我们假设：直到所有的处理器均看到了写的结果，这个写操作才算完成；处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但必须以程序规定的顺序进行写。30/156▲10.2对称式共享存储器系统结构在一致的多处理机中，Cache提供两种功能：共享数据的迁移减少了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。共享数据的复制不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突。一般情况下，小规模多处理机是采用硬件的方法来实现Cache的一致性。10.2.2实现一致性的基本方案31/156▲10.2对称式共享存储器系统结构1.Cache一致性协议在多个处理器中用来维护一致性的协议。关键：跟踪记录共享数据块的状态两类协议（采用不同的技术跟踪共享数据的状态）目录式协议（directory）物理存储器中数据块的共享状态被保存在一个称为目录的地方。监听式协议（snooping）每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。32/156▲10.2对称式共享存储器系统结构Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线（它们一直在监听）来