chap7-多处理机

7.1引言7.2对称式共享存储器体系结构7.3分布式共享存储器体系结构7.4互连网络7.5同步7.6同时多线程7.7多处理机实例第７章多处理机7.1.1并行计算机体系结构的分类1.按照Flynn分类法，可把计算机分成单指令流单数据流（SISD）单指令流多数据流（SIMD）多指令流单数据流（MISD）多指令流多数据流（MIMD）7.1引言第７章多处理机2.MIMD已成为通用多处理机体系结构的选择，原因：(1)MIMD(2)MIMD可以充分利用商品化微处理器在性能价格比方面的优势。3.根据系统中处理器个数的多少，可把现有的MIMD机器分为两类（每一类代表了一种存储器的结构和互连策略）(1)集中式共享存储器结构动画这类机器有时被称为SMP机器（Symmetricshared-memoryMultiProcessor）UMA机器（UniformMemoryAccess）7.1引言CPU0CPU1CPU2CPU3存储器I/O集中共享存储器计算机(2)分布式存储器结构动画每个结点包含：处理器存储器I／O在许多情况下，分布式存储器结构优于集中式共享存储器结构7.1引言互连网络I/o存储器I/o存储器I/o存储器I/o存储器CPU0CPU1CPU2CPU3存储器I/o存储器I/o存储器I/o存储器I/oCPU4CPU5CPU6CPU7分布共享存储器计算机分布式存储器结构的优点主要缺点处理器之间的通信较为复杂，且各处理器之间的访问延迟较大。需要高带宽的互连。簇：超结点如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；局部存储器的访问延迟低。7.1引言7.1.21.地址空间的组织方案（两种）(1)物理上分离的多个存储器作为一个逻辑上共享的存储空间进行编址。这类机器的结构被称为分布式共享存储器结构（DSM:DistributedShared-Memory)可缩放共享存储器结构（SSM:ScalableShared-Memory)NUMA机器（NUMA:Non-UniformMemoryAccess)7.1引言(2)整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。每一个处理器-存储器模块实际上是一个单独的计算机，这种机器也称为多计算机。7.1引言共享地址空间的机器利用Load和Store指令中的地址隐含地进行数据通讯。多个地址空间的机器通过处理器间显式地传递消息完成。(消息传递机器)2.两种通信模型7.1引言消息传递机器根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信。例如：一个处理器要对远程存储器上的数据进行访问或操作：(1)发送消息，请求传递数据或对数据进行操作；远程进程调用(RPC，RemoteProcessCall)(2)目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。7.1引言同步消息传递请求处理器发送一个请求后一直要等到应答结果才继续运行。异步消息传递发送方不先经请求就直接把数据送往数据接受方。3.通信机制的性能指标（3个）(1)通信带宽理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。7.1引言(2)通信延迟理想状态下通信延迟应尽可能地小。通信延迟＝发送开销+跨越时间+传输延迟+(3)通讯延迟的隐藏如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通讯延迟的隐藏。通常的原则：只要可能就隐藏延迟。通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。7.1引言4.不同通信机制的优点A.共享存储器通信的主要优点(1)与常用的集中式多处理机使用的通信机制兼容。(2)易于编程——与传统的编程模式一致(3)当通信数据较小时，通信开销较低，带宽利用较好。(4)通过硬件控制的Cache减少了远程通信的频度，7.1引言B.消息传递通信机制的主要优点(1)(2)通信是显式的，从而引起编程者和编译程序的注意，着重处理开销大的通信。在共享存储器上支持消息传递相对简单在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消7.1引言7.1.3并行处理面临的挑战并行处理面临着两个重要的挑战：。程序中有限的并行性相对较高的通信开销理论加速比可加速部分比例可加速部分比例）（11系统加速比=7.1引言例7.1如果想用100个处理器达到80的加速比，求原计算程序中串行部分所占比例。解动画演示2.第二个挑战：多处理机中远程访问的延迟较大在现有的机器中，处理器之间的数据通信大约需要50～10000个时钟周期。1.第一个挑战：有限的并行性使机器要达到好的加速比十分困难7.1引言机器通信机制互连网络处理机数量典型远程存储器访问时间SPARCCenter共享存储器总线≤201μsSGIChallenge共享存储器总线≤361μsCrayT3D共享存储器3维环网32－20481μsConvexExemplar共享存储器交叉开关＋环8－642μsKSR-1共享存储器多层次环32－2562-6μsCM-5消息传递胖树32－102410μsIntelParagon消息传递2维网格32－204810-30μsIBMSP-2消息传递多级开关2－51230-100μs远程访问一个字的延迟时间例一台32个处理器的计算机，对远程存储器访问时间为2000ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为10ns，如果指令基本的CPI为1.0(设所有访存均命中Cache)，求在没有远程访问的状态下与有0.5%的指令需要远程访问的状态下，前者比后者快多少?解有0.5%远程访问的机器的实际CPICPI＝基本CPI＋远程访问率×远程访问开销＝1.0＋0.5%×7.1引言远程访问开销＝远程访问时间/时钟时间＝2000ns/10ns＝200∴CPI＝1.0＋0.5%×200＝2.0它为只有局部访问的机器的2.0／1.0＝2倍，因此在没有远程访问的状态下的机器速度是有0.5%远程访问的机器速度的2倍。问题的解决并行性不足：采用并行性更好的算法远程访问延迟的降低：靠体系结构支持和编程技术7.1引言3.并行程序的计算／通信比率反映并行程序性能的一个重要的度量计算与通信的比率计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而降低。7.1引言7.2对称式共享存储器体系结构多个处理器共享一个存储器。当处理器规模较小时，这种机器十分经济。支持对共享数据和私有数据的Cache缓存私有数据供一个单独的处理器使用，而共享数据供多个处理器使用。共享数据进入Cache产生了一个新的问题Cache的一致性问题第七章多处理机(1)不一致产生的原因（Cache一致性问题）I／O操作Cache中的内容可能与由I／O子系统输入输出形成的存储器对应部分的内容不同。共享数据不同处理器的Cache都保存有对应存储器单元的内容。例两个处理器的读写7.2.1多处理机Cache一致性7.2对称式共享存储器体系结构(2)存储器的一致性（非正式定义）如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。What:返回给读操作的是什么值When:什么时候才能将已写入的值返回给读操作需要满足以下满足条件①处理器P对X进行一次写之后又对X进行读，读和写之间没有其它处理器对X进行写，则存储系统行为的两个不同方面7.2对称式共享存储器体系结构②一个处理器对X进行写之后，另一处理器对X进行读，读和写之间无其它写，则读X的返回值应为写③对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的。假设直到所有的处理器均看到了写的结果，一次写操作才算完成；允许处理器无序读，但必须以程序规定7.2对称式共享存储器体系结构在一致的多处理机中，Cache提供两种功能：共享数据的迁移降低了对远程共享数据的访问延迟。共享数据的复制不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突。小规模多处理机不是采用软件而是采用硬件技术实现Cache一致性。7.2.2实现一致性的基本方案7.2对称式共享存储器体系结构(1)Cache一致性协议对多个处理器维护一致性的协议。(2)关键：跟踪记录共享数据块的状态(3)共享数据状态跟踪记录技术目录物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方。监听（snooping）每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。7.2对称式共享存储器体系结构Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。(1)写作废协议在一个处理器写某个数据项之前保证它对该例：在写回Cache的条件下，监听总线中写作废协议的实现。7.2对称式共享存储器体系结构(2)写更新协议当一个处理器写某数据项时，通过广播使其它Cache例在写回Cache的条件下，监听总线中写更新协议的实现。处理器行为总线行为CPUACache内容CPUBCache内容主存X单元内容0CPUA读XCach失效00CPUB读XCach失效000CPUA将X单元写1广播写X单元111CPUB读X111(3)写更新和写作废协议性能上的差别主要来自：对同一数据的多个写而中间无读操作的情况，写更新协议需进行多次写广播操作，而在写对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写作废协议下仅在对本块第一次写时进行作废操作。从一个处理器写到另一个处理器读之间的延迟通常在写更新模式中较低。而在写作废协议中，需要读一个新的拷贝。7.2对称式共享存储器体系结构大多数多处理机系统都采用写作废协议7.2对称式共享存储器体系结构7.2.3监听协议及其实现基本实现技术小规模多处理机中实现写作废协议的关键利用总线进行作废操作：把要作废的地址放到总线上（一个放，多个读）写顺序化：由总线实现写直达Cache：因为所有写的数据同时被写回主存，则从主存中总可以取到最新的数据值。对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。7.2对称式共享存储器体系结构增加Cache中块的标志位状态：无效（invalid）——无副本共享（shared）——至少一个副本，clean独占（exclusive）——唯一副本，dirtyCache块的拥有者：拥有唯一的Cache块副本的处理器。因为每次总线任务均要检查Cache的地址位，这可能与CPU对Cache的访问冲突。可通过下列两种技术之一降低冲突：复制标志位采用多级包容Cache（许多系统采用）7.2对称式共享存储器体系结构监听协议举例为简单起见，对于对共享块的Writehit和Writemiss不加区分，都按Writemiss处理写作废，写回法7.2对称式共享存储器体系结构存储器分布于各结点中，所有的结点通过网络互连。访问可以是本地的，也可是远程的。可以不支持Cache一致性：规定共享数据不进入Cache，仅私有数据才能保存在Cache中。优点：所需的硬件支持很少(因为远程访问存取量仅是一个字(或双字)而不是一个Cache块)7.3分布式共享存储器体系结构第７章多处理机缺点：(1)实现透明的软件Cache一致性的编译机制能力有限。(2)没有Cache一致性，机器就不能利用取出同一块中的多个字的开销接近于取一个字的开销这个优点，这是因为共享数据是以Cache块为单位进行管理的。当每次访问要从远程存储器取一个字时，不能有效利用共享数据的空间局部性。(3)诸如预取等延迟隐藏技术对于多个字的存取更为有效，比如针对一个Cache块的预取。7.3分布式共享存储器体系结构解决Cache一致性问题的关键：寻找替代监听协议的一致性协议