计算机体系结构(张晨曦)第8章_PPT.

《计算机体系结构(张晨曦)第8章_PPT.》由会员分享，可在线阅读，更多相关《计算机体系结构(张晨曦)第8章_PPT.（29页珍藏版）》请在装配图网上搜索。

1、计算机系统结构www.GoioS第8章多处理机张晨曦刘依www. GotoSchool .netxzhang2(XX) 计算机系统结构www.GoioS8. 1引言8. 2对称式共享存储器系统结构8. 3分布式共享存储器系统结构8. 4同步8. 5同时多线程8. 6多处理机实例2/104计算机系统结构 www GoloS8.1引言1. 单处理机系统结构正在走向尽头？2. 多处理机正起着越来越垂要的作用近两年来.我们已经开始进入多处理机将起主要作用的新时期。期望：将来更加普及问题： 如何发挥其港在计算能力？（并行程序） 应用是否具有足够的并行性？并行计算机应用软件已有了稳定的发展（尽管缓慢）并行

2、处理已经成为重要和主流的技术。3. 本章霾点：中小规模的计算机（处理器的个数V128）（多处理机设计的主流）3/104计算机系统结构www.GotoS8. 1引言8.1.1并行计算机系统结构的分类1. Flynn分类法SISD、 SIMD、 MISD、 MIMD2. MIMD已成为通用多处理机系统结构的选择，原因： MIMD具有灵活性。 MIMD可以充分利用商品化微处理器在性能价格比 方面的优势。计算机机群系统（cluster）是一类广泛被采用 的MIMD计算机.5/104计算机系统结构www.GoloS8. 1引言3. 根据系统中处理器个数的多少，可把现有的MIMD计算 机分为两类：(每一类

3、代表了一种存储器的结构和互连策略)集中式共享存储器结构动画 最多由几十个处理器构成。 通过大容量的Cache和总线互连使各处理器共享一个 单独的物理存储器。这类计算机有时被称为口 SMP计算机(Symmetric shared-memory MultiProcessor)UMA计算机(Uniform Memory Access)5/104计算机系统结构www.GoloS8. 1引言7/1048. 1弓I言计算机系统结构 www GotoS分布式存储器结构动画 每个结点包含：处理器存储器 I/O互连网络接口 在许多情况下，分布式存储器结构优于集中式共宁存 储器结构。7/1048. 1弓I言计算机

4、系统结构 www GotoS8/104计算机系统结构www.GoloS8.1引言 分布式存储器结构的优点如果大多数的访问是针对本结点的局部存储器，则 可降低对存储器和互连网络的带宽要求。对局部存储器的访问延迟低。 最主要的缺点处理器之间的通信较为复杂，且各处理器之间访问 延迟较大。簇：超级结点每个结点内包含个数较少（例如28）的处理器；处理器之间可采用另一种互连技术（例如总线）相 互连接形成簇.9/104计算机系统结构www.GoloS8. 1引言8. 1.2通信模型和存储器的结构模型1. 地址空间的组织方案（两种）共享地址空间 物理上分离的多个存储器作为一个逻辑上共享的存 储空间进行编址。

5、任何一个处理器可以访问该共亨空间中的任何一个 单元（如果它具有访问权），而且不同处理器上的 同一个物理地址指向的是同一个存储单元。 这类机器的结构被称为分布式共享存储器结构（DSM: Distributed Shared-Memory） NUMA机器 （NUMA: Non-Uniform Memory Access）10/104计算机系统结构www.GotoS& 1引言整个地址空间由多个独立的地址空间构成，它们在 逻辑上也是独立的，远程的处理器不能对其直接寻址。 每一个处理器存储器模块实际上是一台单独的计算机 现在的这种机器多以集群的形式存在2. 两种通信机制共享地址空间的机器利用load和s

6、tore指令中的地址隐含地进行数据通信.多个地址空间的机器通过处理器间显式地传递消息来完成。(消息传递多处理机)11/104计算机系统结构www.GotoS8. 1引言 消息传递计算机通过传递消息來请求茱些戢务或传输数据, 从而完成通信。例如：一个处理器要对远程存储器上的数据进行访问或操作：发送消息，请求传递数据或对数据进行操作； 远程进程调用(RPC, Remote Process Call)目的处理器接收到消息以后，执行相应的操作或代替 远程处理器进行访问，并发送一个应答消息将结果返 回。 同步消息传递请求处理器发送一个请求后直要尊到应答结果才继续运行.12/104计算机系统结构R1引士w

7、ww.GoloSJ 异步消息传递发送方不经请求就直接把数据送往数据接收方。3. 通信机制的性能指标（3个）通信带宽理想状态下的通信带宽受限于处理器、存储器和互连网 络的带宽。通信延迟理想状态下通信延迟应尽可能地小。通信延迟=发送开销+跨越时间+传输延迟+接收开销 跨越时间：数字信号从发送方的线路端传送到接收方 的线路端所经过的时间.传输时间：全部的消息量除以线路带宽。13/104计算机系统结构www.GoloS81引言通信延迟的隐藏 如何才能较好地将通信和计算或多次通信之间重叠起 来，以实现通信延迟的隐藏。 通常的原则：只要可能就隐議延迟。 通信延迟隐藏是一种提高性能的有效途径，但它对操 作系

8、统和编程者来讲増加了额外的负拥.4. 不同通信机制的优点共享存储器通信的主要优点 与常用的对称式多处理机使用的通信机制兼容。易于编程，同时在简化编译器设计方面也占有优势。14/104计算机系统结构www.GotoS 当通信数据最较小时，通信开销较低，带宽利用较好 通过硬件控制的Cache减少了远程通信的频度，减少了 通信延迟以及对共享数据的访问冲突。消息传递通信机制的主要优点 硬件较简单. 通信是显式的，因此更容易搞清楚何时发生通信以及通 信开销是多少，以便编程者和编译程序设法减少通信开 销.15/104计算机系统结构www.GotoS& 1引言可在支持上面任何一种通信机制的硬件模型上建 立所

9、需的通信模式平台。在共享存储器上支持消息传递相对简单。在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址 转换和存储保护功能，即将存储器访问转换为消息 的发送和接收。16/1048. 1弓I言计算机系统结构 www GotoS8. 1.3并行处理面临的挑战并行处理面临着两个重要的挑战 程序中的并行性有限相对较高的通信开销系统加速比=（可加速部分比例）+疇|皺17/104计算机系统结构www.GoioS8. 1引言1. 第一个挑战有限的并行性使机器要达到好的加速比十分困难。例81假设想用100个处理器达到80的加速比，求原计算程 序中串行部分最多可占多大的比

10、例？解Amdahl定律为唱（i行比例）由上式可得，并行比例=0. 997518/104计算机系统结构www.GotoS8. 1引言2. 第二个挑战：多处理机中远程访问的延迟较大在现有的计算机中，处理器之间的数据通信大约 需要1001000个时钟周期。主要取决于：通信机制、互连网络的种类和计算机的规模在几种不同的共享存储器并行计算机中远程访问 一个字的典型延迟19/104计算机系统结构www.GotoS8. 1引言计算机类型通信 机制直连网络处理机 最大数屋典型远程存储器 访问时间(ns )Sun Starfire serversSMP多总线64500SGI Origin 3000NUMA胖超立

11、方体512500Cray T3ENUMA3维环网2048300HP V seriesSMP8X8交叉开关321000HP AlphaServer GSSMP开关总线3240020/104计算机系统结构www.GotoS& 1引言例8. 2假设有一台32个处理器的多处理机，对远程存储器 访问时间为400ns除了通信以外，假设所有其他访问均命中局 部存储器。当发出一个远程请求时，本处理器挂起。处理器的 时钟频率为1GHz,如果指令基本的PC为2 （设所有访存均命中 Cache）,求在没有远程访问的情况下和有0.2%的指令需要远程 访问的情况下，前者比后者快多少？21/104& 1引言计算机系统结构

12、www.GotoS解 没有远程访问时，机器的CPI为1/基本IPC=l/2=0. 5 有0. 2%远程访问的机器的实际CPI为CPI =基本CPI+远程访问率X远程访问开销=0.5+0. 2%X远程访问开销远程访问开销为远程访问时间/时钟周期时间=400ns/lns=400个时钟周期 CPI=0. 5+0. 2%X400 = l. 3因此在没有远程访问的情况下的计算机速度是有0. 2%远程 访问的计算机速度的1. 3/0. 5=2.6倍。22/104计算机系统结构www.GotoS8. 1引言问题的解决 并行性不足：采用并行性更好的算法 远程访问延迟的降低：靠系统结构支持和编程技术3. 在并行

13、处理中，影响性能（负载平衡、同步和存储器 访问延迟等）的关键因素常依赖于：应用程序的高层特性如数据的分配，并行算法的结构以及在空间和 时间上对数据的访问模式尊.依据应用特点可把多机工作负载大致分成两类： 单个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载23/104计算机系统结构www.GoloS8. 1引言4. 并行程序的计算/通信比率反映并行程序性能的一个重要的度量：计算与通信的比率计算/通信比率随着处理数据规模的増大而增加: 随着处理器数目的増加而降低。24/104计算机系统结构www.GotoS8.2对称式共享存储器系统结构多个处理器共享一个存储器、当处理机规模较小时

14、，这种计算机十分经济。教材中图8. 1是这种计算机的一个简单示意图.支持对共享数据和私有数据的Cache缓存私有数据供一个单独的处理器使用，而共享数据 则是供多个处理器使用。 共享数据进入Cmche产生了一个新的问题Cache的一致性问题25/104计算机系统结构www.GotoS&2对称式共亭存储器系统结构8. 2. 1多处理机Cache致性1. 不一致产生的原因（Cache致性问题） I / 0操作Cache中的内容可能与由I/O子系统输入/输出形 成的存储器对应部分的内容不同。共享数据不同处理器的Cache都保存有对应存储器单元的内容。例两个处理器的读写26/104由两个处理器（A和B）

15、读写引起的Cache致性问题时间爭件CPU A Cache 内容CPU B Cache内容X单元存储器 内容011CPU A读X112CPU B读X1113CPU A将0存入X010计算机系统结构 www GotoS8.2对称式共享存储器系统结构27/104计算机系统结构 www GotoS8.2对称式共手存储器系统结构2. 存储器的一致性（非正式定义）如果对某个数据项的任何读操作均可得到其 最新写入的值，则认为这个存储系统是一致的。存储系统行为的两个不同方面 What:读操作得到的是什么值When:什么时候才能将已写入的值返回给读操作需要满足以下条件处理器P对单元X进行一次写之后又对单元X进

16、行读， 读和写之间没有其他处理器对单元X进行写，则P读 到的值总是前面写进去的值。28/104计算机系统结构www.GotoS&2对称式共享存储器系统结构处理器P对单元X进行写之后，另一处理器Q对单元X进 行读，读和写之间无其他写，则Q读到的值应为卩写进 去的值。 对同一单元的写是顺序化的，即任意两个处理器对同 一单元的两次写，从各个处理需的角度看米顺序都是 相同的.（写顺序化）在后面的讨论中，我们假设： 直到所有的处理器均看到了写的结果，这个写操作才 算完成； 处理器的任何访存均不能改变写的顺序。就是说，允 许处理器对读进行重排序，但必须以程序规定的顺序 进行写.29/104计算机系统结构w

17、ww.GotoS&2对称式共亭存储器系统结构8. 2. 2实现一致性的基本方案在一致的多处理机中，Cache提供两种功能：共享数据的迁移降低了对远程共享数据的访问延迟，也减少了 对共享存储器带宽的要求。共享数据的复制不仅降低了访存的延迟，也减少了访问共享数 据所产生的冲突。一般情况下，小规模多处理机采用硬件的方法来 实现Czche的一致性。30/104计算机系统结构 www GotoS8.2对称式共宰存储器系统结构1 Cache致性协议在多个处理器中用来维护一致性的协议。关键：跟踪记录共享数据块的状态 两类协议（采用不同的共享数据状态跟踪技术）-j 目录法（directory）物理存储器中共享

18、数据块的状态及相关信息均被 保存在一个称为目录的地方.监听法（snooping）每个Cache除了包含物理存储器中块的数据副本 之外，也保存着各个块的共享状态信息。31/104计算机系统结构 www GotoS8.2对称式共享存储器系统结构 Cache通常连在共享存储器的总线上，各个Cache 控制器通过监听总线来判断它们是否有总线上请 求的数据块。2.两种更新协议（维持一致性要求）写作废协议在处理器对某个数据项进行写入之前，保证它拥 有对该数据项的唯一的访问权.（作废其他副本）32/104计算机系统结构www.GolQS&2对称式共享存储器系统结构例在写回Cache、监听总线的情况下.写作废

19、协议的实现处理器行为总线行为CPU ACache内容CPU BCache内容主存单元x 的内容0CPU A 读XCache失效00CPU B 读XCache失效000CPU A将1写入单元X作废X单元i0CPU B 读 XCache失效i1133/104计算机系统结构www.GolQS&2对称式共享存储器系统结构写更新协议当一个处理器对某数据项进行写入时，通过广播 使其他Cache中所有对应于该数据项的副本进行更新。例 在写回Cache、监听总线的情况下，写更新协议的实现。处理器行为总线行为CPU ACache内容CPU B Cache内容主存单元X 的内容0CPU A 读XCache失效00

20、CPU B 读XCache失效000CPU A将1写入单元X对单元X进 行写广播111CPU B 读X11134/104计算机系统结构www.GotoS8.2对称式共享存储器系统结构写更新和写作废协议性能上的差别主要来自： 在对同一个数据进行多次写操作而中间无读操作的情 况下，写更新协议需进行多次写广播操作，而写作废 协议只需一次作废操作。 在对同-Cache块的多个字进行写操作的情况下，写更 新协议对于每一个写操作都要进行一次广播，而写作 废协议仅在对该块的第一次写时进行作废操作即可.写作废是针对Cache块进行操作，而写更新则是针 对字（或字节进行. 考虑从一个处理器A进行写操作后到另一个

21、处理器B能 读到该写入数据之间的延迟时间。写更新协议的延迟时间较小。35/104计算机系统绪构www.GoloS&2对称式共辜存储器系统结构8. 2. 3监听协议及其实现1. 小规模多处理机中实现写作废协议的关键利用总线进行作废操作：把要作废的地址放到总线上（一个放，多个读）写操作的顺序性：由总线实现（获取总线控制权的顺序性）写直达Cache：因为所有写的数据同时被写回主存， 所以从主存中总可以取到最新的数据值。对于写回Cache,得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。37/104计算机系统结构www.GotoS8.2对称式共亨存储器系统结构2. 在写回

22、法Czche条件下的实现技术 Cache的标识(tag)用于实现监听。作废一个块只需将其有效位(valid)置为无效。 给每个Cache块加一个特殊的状态位。状态： 共享 (shared) 至少一个副本，clean 专有(exclusive)唯一副本，dirtyCache块的拥有者：拥有唯一的Cache块副本 的处理器。37/104计算机系统结构www.GotoS&2对称式共宇存储器系统结构在每个结点内嵌入一个Cache状态控制器。控制器根据来自处理器或总线的请求，改变所 选择的数据块的状态.因为每次总线操作均要检查Cache的地址标识， 这可能会影响CPU对Cache的访问。可通过下列两 种

23、技术之一来减少影响: 复制标志位采用多级包容Cache (许多系统采用)38/104计算机系统结构www.GotoS8.3分布式共享存储器系统结构存储器分布于各结点中，所有的结点通过网络互 连。访问可以是本地的，也可是远程的。可以不支持C/h6致性：规定共享数据不进入 Cache,仅私有数据才能保存在Cache中。优点：所需的硬件支持很少（因为远程访问存取量仅是一个字（或双字）而不是一 个Cache块）如何将支持Cache致性的共享存储器模式扩展 到可扩缩的大规模多处理机系统？39/104计算机系统绣构www.GotoS&3分布式共李存储器系统结构解决Cache致性问题的关键：寻找替代监听协议

24、的一致性协议。（采用目录协议）8. 3. 1基于目录的Cache致性1. 目录协议目录：一种专用的数据结构，用于记录可以进入 Cache的每个数据块的状态、哪些处理器有该块的 副本以及是否修改过等信息，分布式目录40/104计算机系统结构www.GotoS8. 3分布式共手存储器系统结构u 目录与存储器一起分布到各结点中，从而对于不同目 录内容的访问可以在不同的结点进行。 特点：存储块的共享状态信息可以在唯一的一个固定单元中找到。这使一致性协议避免了广播操作。 对每个结点增加冃录表后的分布式存储器名处理机的 系统结构.41/104计算机系统结构www.GotoS&3分布式共亭存储器系统结构42

25、/104计算机系统结构www.GotoS8. 3分布式共亭存储器系统结构2. 目录协议必须完成两种主要的操作：处理读失效 处理对共享、干净(clean)块的写个共享块的写失效处理可用这两个操作组合而成。3. 目录必须跟踪记录每个Cache块的状态存储块的状态有三种：a共享在一个或多个处理器上具有这个块的副本，且存 储器中的值是最新的(所有Cache中的副本均相同).43/104计算机系统结构www.GotoS8.3分布式共享存储器系统结构 未缓冲所有处理器的Cache都没有该块的副本。 专有仅有一个处理器上有该块的副本，且已对该块 进行了写操作，而主存中的副本仍是旧的。这个处 理器称为该块的拥

26、有者。4. 由于写作废操作的需要，还必须记录哪些处理器有该 块的副本。方法：对每个主存块设置一个位向量当该块被共享时，每个位指岀与之对应的处理器是 否有该块的副本.当该块为专有时，可根据位向量来寻找其拥有者。44/104计算机系统结构www.GotoS8. 3分布式共亭存储器系统结构假设：对于本地Cmche中非“专有”状态Czche块 的写入操作总会产生写失效，处理器封锁直到写 操作完成。5一个例子本地结点、宿主结点以及远程结点的关系 本地结点：发出访问请求的结点 宿主结点：包含所访问的存储单元及其目录项的结点 远程结点可以和宿主结点是同一个结点，也可以不是 同一个结点。45/1041 K存储

27、器宿主结点B(Home)计算机系统结构www.GotoS8. 3分布式共亭存储器系统结构宿主结点：存放有对应地址的存储器块和目录项的结点计算机系统结构www.GoloS8.3分布式共李存储器系统结构响应访问请求时，要将宿主结点中相应的值返回给请求结点。数据写回在两种情况下发生：Cache中某个块被替换时必须写回到其宿主结点的存 储器。响应宿主结点发出的取数和取数/作废消息时也要写 回。47/104计算机系统结构www.GoloS8.3分布式共李存储器系统结构总结：目录协议的基本点在每个结点中增加了目录存储器用于存放目录。存储器的每一块在目录中有对应的一项。每一个目录项主要由两个字段构成：状态：

28、描述所对应的存储块的当前状态.位向邀：每一位对应于一个处理器，用于指出该处 理器的Cache中是否有该存储块的副本。当处理器对 某一块进行写操作时，只要根据位向屋通知具有相 应副本的处理器进行作废操作。位向毎中记录的处理器集合称为共享集合.48/104计算机系统结构www GotoS8.3分布式共享存储器系统结构8. 3.2目录协议及其实现在基于目录的协议中，目录承担了一致性协议操作 的主要功能。发往一个目录的消息会产生两种不同类型的动作： 更新目录状态 发送消息以完成所请求的操作目录可能接收三种不同的请求： 读失效 写失效 数据写回49/104计算机系统结构www.GoloS&3分布式共亭存储器系统结构1.当一个块处于未缓冲状态时，对该块发出的请求及目 录的处理操作为：读失效 将存储器数据送往请求方处理器，且该处理器成为 该块的唯一共享结点，本块的状态变成共享。写失效 将存储器数据送往请求方处理器，该块的状态变成 专有，表示该块仅存在唯一的有效副本。 其共享集合仅包含该处理器，指出该处理器是其拥 有者。50/104