《计算机体系结构(张晨曦)第8章_PPT》由会员分享,可在线阅读,更多相关《计算机体系结构(张晨曦)第8章_PPT(104页珍藏版)》请在金锄头文库上搜索。
1、1/104第8章 多处理机张晨曦 刘依www.GotoS2/1048.1引言8.2对称式共享存储器系统结构8.3分布式共享存储器系统结构8.4同步8.5同时多线程8.6多处理机实例3/1048.1 引 言1. 单处理机系统结构正在走向尽头? 2. 多处理机正起着越来越重要的作用。近两年来,我们已经开始进 入多处理机将起主要作用的新时期。期望:将来更加普及问题:q如何发挥其潜在计算能力? (并行程序)q应用是否具有足够的并行性? 并行计算机应用软件已有了稳定的发展。 (尽管缓慢) 并行处理已经成为重要和主流的技术。 3.本章重点:中小规模的计算机(处理器的个数128) (多处理机设计的主流)4/
2、1048.1 引 言wFlynn分类法SISD、SIMD、MISD、MIMDwMIMD已成为通用多处理机系统结构的选择,原因:MIMD具有灵活性。MIMD可以充分利用商品化微处理器在性能价 格比方面的优势。计算机机群系统(cluster)是 一类广泛被采用的MIMD计算机。8.1.1 并行计算机系统结构的分类 5/1048.1 引 言w根据系统中处理器个数的多少,可把现有的MIMD计算 机分为两类:(每一类代表了一种存储器的结构和互 连策略)集中式共享存储器结构 动画q最多由几十个处理器构成。q通过大容量的Cache和总线互连使各处理 器共享一个单独的物理存储器。 这类计算机有时被称为 qSM
3、P计算机(Symmetric shared-memory MultiProcessor)qUMA计算机(Uniform Memory Access) 6/1048.1 引 言对称式共享存储器多处理机的基本结构7/1048.1 引 言分布式存储器结构 动画q每个结点包含:n处理器n存储器nIOn互连网络接口q在许多情况下,分布式存储器结构优于集 中式共享存储器结构。8/1048.1 引 言9/1048.1 引 言q分布式存储器结构的优点n如果大多数的访问是针对本结点的局部存储器,则可降低对存储器和互连网络的带宽要求。n对局部存储器的访问延迟低。q最主要的缺点n处理器之间的通信较为复杂,且各处理器
4、之间访问延迟较大。q簇:超级结点 n每个结点内包含个数较少(例如28)的处理器;n处理器之间可采用另一种互连技术(例如总线)相互连接形成簇。 10/1048.1 引 言w地址空间的组织方案(两种)共享地址空间 q物理上分离的多个存储器作为一个逻辑 上共享的存储空间进行编址。q任何一个处理器可以访问该共享空间中 的任何一个单元(如果它具有访问权),而且不同 处理器上的同一个物理地址指向的是同一个存储单 元。q这类机器的结构被称为分布式共享存储器结构(DSM: Distributed Shared-Memory)NUMA机器 (NUMA: Non-Uniform Memory Access)8.1
5、.2 通信模型和存储器的结构模型 11/1048.1 引 言整个地址空间由多个独立的地址空间构成, 它们在逻辑上也是独立的,远程的处理器不能对其 直接寻址。 q每一个处理器-存储器模块实际上是一台单 独的计算机q现在的这种机器多以集群的形式存在w两种通信机制 共享地址空间的机器 利用load和store指令中的地址隐含地进行 数据通信。多个地址空间的机器 通过处理器间显式地传递消息来完成。(消息传递多处理机) 12/1048.1 引 言q消息传递计算机通过传递消息来请求某些服务或传输数据,从而完成通信。例如:一个处理器要对远程存储器上的数据进行访问或操作:n发送消息,请求传递数据或对数据进行操
6、作;远程进程调用(RPC,Remote Process Call)n目的处理器接收到消息以后,执行相应的操作或代替远程处理器进行访问,并发送一个应答消息将结果返回。q同步消息传递 请求处理器发送一个请求后一直要等到应答结果才继续运行。13/1048.1 引 言q异步消息传递 发送方不经请求就直接把数据送往数据接 收方。 w通信机制的性能指标(3个)通信带宽理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。 通信延迟理想状态下通信延迟应尽可能地小。通信延迟发送开销跨越时间传输延 迟接收开销 q跨越时间:数字信号从发送方的线路端传 送到接收方的线路端所经过的时间。q传输时间:全部的消息量除
7、以线路带宽。14/1048.1 引 言通信延迟的隐藏q如何才能较好地将通信和计算或多次通信 之间重叠起来,以实现通信延迟的隐藏。q通常的原则:只要可能就隐藏延迟。q通信延迟隐藏是一种提高性能的有效途径 ,但它对操作系统和编程者来讲增加了额外的负担。w不同通信机制的优点 共享存储器通信的主要优点 q与常用的对称式多处理机使用的通信机制 兼容。q易于编程,同时在简化编译器设计方面也 占有优势。15/1048.1 引 言q当通信数据量较小时,通信开销较低,带 宽利用较好。q通过硬件控制的Cache减少了远程通信的频 度,减少了通信延迟以及对共享数据的访问冲突。消息传递通信机制的主要优点q硬件较简单。
8、q通信是显式的,因此更容易搞清楚何时发 生通信以及通信开销是多少,以便编程者和编译程序设 法减少通信开销。 16/1048.1 引 言可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。q在共享存储器上支持消息传递相对简单。q在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能,即将存储器访问转换为消息的发送和接收。 17/1048.1 引 言并行处理面临着两个重要的挑战程序中的并行性有限相对较高的通信开销8.1.3 并行处理面临的挑战 系统加速比 =18/1048.1 引 言w第一个挑战有限的并行性使机器要达到好的加速比十分
9、困难。 例8.1 假设想用100个处理器达到80的加速比,求原计算程 序中串行部分最多可占多大的比例?解 Amdahl定律为由上式可得,并行比例0.9975 19/1048.1 引 言w第二个挑战:多处理机中远程访问的延迟较大在现有的计算机中,处理器之间的数据通信 大约需要1001000个时钟周期。主要取决于:通信机制、互连网络的种类和计算机的 规模 在几种不同的共享存储器并行计算机中远程 访问一个字的典型延迟 20/1048.1 引 言计算机类型 通 信 机 制 互连网络 处理 机 最大 数量 典型远程存 储器 访问时间 (ns) Sun Starfire servers SMP 多总线 6
10、4 500 SGI Origin 3000 NUMA 胖超立方体 512 500 Cray T3E NUMA 3维环网 2048 300 HP V series SMP 88交叉开关 32 1000 HP AlphaServer GS SMP 开关总线 32 400 21/1048.1 引 言例8.2 假设有一台32个处理器的多处理机,对远程存储器访问时间为400 ns。除了通信以外,假设所有其他访问均命中局部存储器。当发出一个远程请求时,本处理器挂起。处理器的时钟频率为1 GHz,如果指令基本的IPC为2(设所有访存均命中Cache),求在没有远程访问的情况下和有0.2%的指令需要远程访问的
11、情况下,前者比后者快多少?22/1048.1 引 言解 没有远程访问时,机器的CPI为 1/基本IPC=1/2=0.5有0.2%远程访问的机器的实际CPI为 CPI基本CPI远程访问率远程访问开销0.50.2%远程访问开销远程访问开销为 远程访问时间/时钟周期时间400 ns/1 ns400个时钟周期 CPI0.50.2%4001.3因此在没有远程访问的情况下的计算机速度是有0.2%远程访问的计算机速度的1.3/0.5=2.6倍。23/1048.1 引 言问题的解决q并行性不足: 采用并行性更好的算法q远程访问延迟的降低:靠系统结构支持 和编程技术 w在并行处理中,影响性能(负载平衡、同步和存
12、储器 访问延迟等)的关键因素常依赖于:应用程序的高层特性如数据的分配,并行算法的结 构以及在空间和时间上对数据的访问模式等。依据应用特点可把多机工作负载大致分成 两类:q单个程序在多处理机上的并行工作负载q多个程序在多处理机上的并行工作负载24/1048.1 引 言w并行程序的计算通信比率反映并行程序性能的一个重要的度量:计算与通信的比率计算通信比率随着处理数据规模的增大而增加;随着处理器数目的增加而降低。25/104多个处理器共享一个存储器。当处理机规模较小时,这种计算机十分经济 。教材中图8.1是这种计算机的一个简单 示意图。 支持对共享数据和私有数据的Cache缓存私有数据供一个单独的处
13、理器使 用,而共享数据则是供多个处理器使用。 共享数据进入Cache产生了一个新的问题Cache的一致性问题8.2 对称式共享存储器系统结构26/1048.2 对称式共享存储器系统结构w不一致产生的原因(Cache一致性问题)IO操作Cache中的内容可能与由IO子 系统输入/输出形成的存储器对应部分的内容不同。共享数据不同处理器的Cache都保存有对应存储 器单元的内容。例 两个处理器的读写8.2.1 多处理机Cache一致性27/1048.2 对称式共享存储器系统结构由两个处理器(A和B)读写引起的Cache一致性问题 时间 事件 CPU A Cache 内容 CPU B Cache 内容
14、 X单元存 储器 内容 011 CPU A读X 112 CPU B读X 1113 CPU A将0 存入X 01028/1048.2 对称式共享存储器系统结构w存储器的一致性(非正式定义)如果对某个数据项的任何读操作均 可得到其最新写入的值,则认为这个存储系统是 一致的。存储系统行为的两个不同方面qWhat: 读操作得到的是什么值qWhen: 什么时候才能将已写入的值返回 给读操作需要满足以下条件q处理器P对单元X进行一次写之后又对单 元X进行读,读和写之间没有其他处理器对单元X进 行写,则P读到的值总是前面写进去的值。 29/1048.2 对称式共享存储器系统结构q处理器P对单元X进行写之后,
15、另一处理器 Q对单元X进行读,读和写之间无其他写,则Q读到的 值应为P写进去的值。q对同一单元的写是顺序化的,即任意两个 处理器对同一单元的两次写,从各个处理器的角度看 来顺序都是相同的。(写顺序化 )在后面的讨论中,我们假设:q直到所有的处理器均看到了写的结果,这 个写操作才算完成;q处理器的任何访存均不能改变写的顺序。 就是说,允许处理器对读进行重排序,但必须以程序 规定的顺序进行写。 30/1048.2 对称式共享存储器系统结构在一致的多处理机中,Cache提供两种功能:共享数据的迁移降低了对远程共享数据的访问 延迟,也减少了对共享存储器带宽的要求。共享数据的复制不仅降低了访存的延迟,也
16、减 少了访问共享数据所产生的冲突。一般情况下,小规模多处理机采用硬件的方法来 实现Cache的一致性。 8.2.2 实现一致性的基本方案31/1048.2 对称式共享存储器系统结构wCache一致性协议在多个处理器中用来维护一致性的协议 。关键:跟踪记录共享数据块的状态 两类协议(采用不同的共享数据状态跟踪技 术)q目录法(directory)物理存储器中共享数据块的状态 及相关信息均被保存在一个称为目录的地方。q监听法(snooping)n每个Cache除了包含物理存储 器中块的数据副本之外,也保存着各个块的共 享状态信息。32/1048.2 对称式共享存储器系统结构nCache通常连在共享存储器的总线上,各个Cache控制器通过监听总线来判断它们