《多处理机》PPT课件.ppt

第七章 多处理机,国防科技大学计算机学院,一个问题图书馆将一批新书上架，可以有多种方式。假定将书按类上架，而将书架依据在书库中的位置分成一些组。解决办法 若由一工人单独完成，不能在要求的时间内完成任务。若由多个工人完成，假定每次一人仅往书架上放一本书。可以采用两种不同的方式：,（1）将所有的书籍平均分配给每个人去完成。这种划分方法不是太有效，原因是每个工人为了将书上架必须走遍所有的书架。（2）将所有书架分成一些组，且平均分配给各个工人负责，同时将所有图书平均分配给每个工人去上架。如果工人发现一本书属于自己所负责的书架上，则将其放入书架。否则，将这本书传给所在书架对应的工人。这种分法对应的效率比较高。,结论将一个任务划分成一些子任务，并分配给多个工人去完成，工人们相互合作、并在需要时相互传递图书，这种协调的工作方式可较快地完成任务。并行计算就是严格地按照上述原理来完成的。,并行计算相关的两个概念 任务划分(task partitioning)将图书平均分配给所有工人为任务划分的一个例子。通信(communication)工人之间传递图书为子任务通信的例子。什么是并行计算？并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统，它是将多个处理器通过网络以一定的连接方式有序地组织起来。,并行计算的研究内容:(1)并行计算机设计(2)有效算法的设计(3)评价并行算法的方法(4)并行计算机语言(5)并行编程环境与工具(6)并行程序的可移植性(7)并行计算机的自动编程,并行计算的应用领域：(1)天气预报(2)卫星数据处理(3)石油数据处理（连续优化问题）(4)调度问题(5)VLSI设计（离散优化问题）(6),天气预报考虑3000*3000平方公里的范围，垂直方向的考虑高度为11公里。将3000*3000*11立方公里的区域分成0.13立方公里的小区域，则将近有1011个不同的小区域。另外还需考虑时间因素，将时间参数量化。假定考虑48小时天气预报。每一小区域的计算包括参数的初始化及与其它区域的数据交换。若每一小区域计算的操作指令为100条，则整个范围一次计算的指令为1011*100=1013，两天的计算次数将近100次，因此，指令总数为1015条。用一台10亿次/秒(PIII500)计算，大约需要280小时。,美国政府的HPCC计划公布的重大挑战性应用磁记录技术：研究静磁和交互感应以降低高密度磁盘的噪音新药设计：通过抑制人的免疫故障病毒蛋白酶的作用来研制治疗癌症与艾滋病的药物高速民航：用计算流体动力学来研制超音速喷气发动机催化作用：仿生催化剂计算机建模，分析合成过成中的酶作用燃料燃烧：通过化学动力学计算，揭示流体力学的作用，设计新型发动机海洋建模：对海洋活动与大气流的热交换进行整体海洋模拟,美国政府的HPCC计划公布的重大挑战性应用臭氧耗损：研究控制臭氧损耗过程中的化学与动力学机制数字解析：用计算机研究适时临床成像、计算层析术、磁共振成像 大气污染：对大气质量模型进行模拟研究，控制污染的传播，揭示其物理与化学机理蛋白质结构设计：对蛋白质组成的三维结构进行计算机模拟研究图像理解：实时绘制图像或动态密码破译：破译由长位数组成的密码，寻找该数的两个乘积因子,并行计算的应用分类（1）计算密集型（Compute-Intensive）这一类型的应用问题主要集中在大型科学工程计算与数值模拟（气象预报、地球物理勘探等）（2）数据密集型(Data-Intensive)Internet的发展，为我们提供了大量的数据资源，但有效地利用这些资源，需要进行大量地处理，且对计算机的要求也相当高，这些应用包括数字图书馆、数据仓库、数据挖掘、计算可视化。（3）网络密集型(Network-Intensive)通过网络进行远距离信息交互，来完成用传统方法不同的一些应用问题。如协同工作、遥控与远程医疗诊断等,7.1 引言7.2 多处理机的存储器体系结构7.3 互连网络 7.4 同步与通信7.5 并行化技术,单处理机的发展正在走向尽头？并行计算机在未来将会发挥更大的作用。获得超过单处理器的性能，最直接的方法就是把 多个处理器连在一起；2.自1985年以来，体系结构的改进使性能迅速提高，这种改进的速度能否持续下去还不清楚，但通过 复杂度和硅技术的提高而得到的性能的提高正在 减小；3.并行计算机应用软件已有缓慢但稳定的发展。,7.1 引 言,本章重点:中小规模的机器(处理器的个数100)（多处理机设计的主流）7.1.1 并行计算机体系结构的分类1.按照Flynn分类法，可把计算机分成,单指令流单数据流（SISD）单指令流多数据流（SIMD）多指令流单数据流（MISD）多指令流多数据流（MIMD）,2.MIMD已成为通用多处理机体系结构的选择，原因：(1)MIMD具有灵活性。(2)MIMD可以充分利用商品化微处理器在性能价格 比方面的优势。3.MIMD机器分为两类：（每一类代表了一种存储器的结构和互连策略）(1)集中式共享存储器结构 这类机器有时被称为UMA(uniform memory access)机器。,(2)分布式存储器结构 每个结点包含：在许多情况下，分布式存储器结构优于采用 集中式共享存储器结构。分布式存储器结构需要高带宽的互连。,处理器 存储器 IO,分布式存储器结构的优点(1)如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；(2)对局部存储器的访问延迟低。主要缺点 处理器之间的通信较为复杂，且各处理器之间访问 延迟较大。,1.两种地址空间的组织方案(1)物理上分离的多个存储器可作为一个逻辑上共享的 存储空间进行编址。这类机器的结构被称为分布式共享存储器(DSM)或可缩放共享存储器体系结构。DSM机器被称为NUMA(non-uniform memory access)机器。(2)整个地址空间由多个独立的地址空间构成，它们在 逻辑上也是独立的，远程的处理器不能对其直接寻 址。,7.1.2 通信模型和存储器的结构模型,每一个处理器-存储器模块实际上是一个单独的计算机，这种机器也称为多计算机。2.两种通信模型,共享地址空间的机器 利用Load和Store指令中的地址隐含地进行数据通信多个地址空间的机器 通过处理器间显式地传递消息完成(消息传递机器)消息传递机器根据简单的网络协议，通过传递消息来 请求某些服务或传输数据，从而完成通信。,例如：一个处理器要对远程存储器上的数据进行访问或操作(1)发送消息，请求传递数据或对数据进行操作；远程进程调用(RPC，remote process call)(2)目的处理器接收到消息以后，执行相应的操 作或代替远程处理器进行访问，并发送一个 应答消息将结果返回。,7.1.3 通信机制的性能 三个关键的性能指标：1.通信带宽 理想状态下的通信带宽受限于处理器、存储器和互 连网络的带宽。2.通信延迟 理想状态下通信延迟应尽可能地小。通信延迟 发送开销跨越时间传输延迟接收开销,3.通讯延迟的隐藏 如何才能较好地将通信和计算或多次通信之间重 叠起来，以实现通信延迟的隐藏。通常的原则是：只要可能就隐藏延迟。通信延迟隐藏是一种提高性能的有效途径，但 它对操作系统和编程者来讲增加了额外的负担。,1.共享存储器通信的主要优点(1)与常用的集中式多处理机使用的通信机制兼容。(2)当处理器通信方式复杂或程序执行动态变化时 易于编程，同时在简化编译器设计方面也占有 优势。(3)当通信数据较小时，通信开销较低，带宽利用 较好。(4)通过硬件控制的Cache减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。,7.1.4 不同通信机制的优点,2.消息传递通信机制的主要优点(1)硬件较简单。(2)通信是显式的，从而引起编程者和编译程序 的注意，着重处理开销大的通信。在共享存储器上支持消息传递相对简单，但在消 息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地 址转换和存储保护功能，即将存储器访问转换为消 息的发送和接收。,并行处理面临着两个重要的挑战：（可通过Amdahl定律解释）1.有限的并行性使机器要达到好的加速比十分困难。,程序中有限的并行性 相对较高的通信开销,7.1.5 并行处理面临的挑战,例7.1 如果想用100个处理器达到80的加速比，求原计算程序中串行部分所占比例。解：动画演示,面临的第二个挑战主要是指多处理机中远程访问 的较大延迟。在现有的机器中，处理器之间的数据通信大约需 要5010000个时钟周期。,远程访问一个字的延迟时间,例7.2 一台32个处理器的计算机，对远程存储器访问时间为2000ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为10ns，如果指令基本的CPI为1.0(设所有访存均命中Cache)，求在没有远程访问的状态下与有0.5%的指令需要远程访问的状态下，前者比后者快多少?解 有0.5%远程访问的机器的实际CPI为 CPI基本CPI远程访问率远程访问开销 1.00.5%远程访问开销,远程访问开销远程访问时间/时钟时间 2000ns/10ns200个时钟 CPI1.00.5%2002.0它为只有局部访问的机器的2.01.02倍，因此在没有远程访问的状态下的机器速度是有0.5%远程访问的机器速度的2倍。,问题的解决 并行性不足：通过采用并行性更好的算法来解决 远程访问延迟的降低：靠体系结构支持和编程技术,反映并行程序性能的一个重要的度量 计算与通信的比率 计算通信比率随着处理数据规模的增大而增 加；随着处理器数目的增加而降低。,7.1.6 并行程序的计算通信比率,7.2 多处理机的存储器体系结构,多个处理器共享一个存储器。当处理器规模较小时，这种机器十分经济。支持对共享数据和私有数据的Cache缓存。私有数据供一个单独的处理器使用，而共享数据供 多个处理器使用。共享数据进入Cache产生了一个新的问题：Cache的一致性问题,7.2.1 集中式共享存储器体系结构,1.多处理机的一致性(1)不一致产生的原因（Cache一致性问题）,IO操作Cache中的内容可能与由IO子系统输入输出形成的存储器对应部分的内容不同。共享数据不同处理器的Cache都保存有对应存储器单元的内容。,例 两个处理器Cache对应同一存储器单元产生出不同的值,(2)存储器是一致的（非正式地定义）如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。存储系统行为的两个不同方面,返回给读操作的是什么值 什么时候才能将已写入的值返回给读操作,满足条件 处理器P对X进行一次写之后又对X进行读，读和写之间没有其它处理器对X进行写，则 读的返回值总是写进的值。,一个处理器对X进行写之后，另一处理器对X进行 读，读和写之间无其它写，则读X的返回值应为写 进的值。对同一单元的写是顺序化的，即任意两个处理器 对同一单元的两次写，从所有处理器看来顺序都 应是相同的。假设 直到所有的处理器均看到了写的结果，一次写操 作才算完成；允许处理器无序读，但必须以程序 规定的顺序进行写。,2.实现一致性的基本方案 在一致的多处理机中，Cache提供两种功能。,共享数据的迁移 降低了对远程共享数据的访问延迟。共享数据的复制 不仅降低了访存的延迟，也减少了访问共享数据 所产生的冲突。,小规模多处理机不是采用软件而是采用硬件技术实现Cache一致性。,(1)Cache一致性协议 对多个处理器维护一致性的协议(2)关键：跟踪共享数据块的状态(3)共享数据状态跟踪技术 目录 物理存储器中共享数据块的状态及相关信息均被保 存在一个称为目录的地方。监听 每个Cache除了包含物理存储器中块的数据拷贝之 外，也保存着各个块的共享状态信息。,监听：Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。,3.两种协议(1)写作废协议 在一个处理器写某个数据项之前保证它对该数据项有 唯一的访问权。例：在写回Cache的条件下，监听总线中写作废协议的实现。,(2)写更新协议 当一个处理器写某数据项时，通过广播使其它Cache 中所有对应的该数据项拷贝进行更新。例:写回Cache条件下，监听总线中写更新协议的实现。,(3)写作废和写更新协议性能上的差别 对同一数据的多个写而中间无读操作的情况，写更 新协议需进行多次写广播操作，而在写作废协议下 只需一次作废操作。对同一块中多个字进行写，写更新协议对每个字的 写均要进行一次广播，而在写作废协议下仅在对本 块第一次写时进行作废操作。从一个处理器写到另一个处理器读之间的延迟通常 在写更新模式中较低。而在写作废协议中，需要读 一个新的拷贝。,在基于总线的多处理机中，写作废协议成为绝大多数系统设计的选择。4.监听协议的基本实现技术(1)小规模多处理机中实现写作废协议的关键利用总线进行作废操作 每个块的有效位使作废机制的实现较为容易。(2)写直达Cache，因为所有写的数据同时被写回主 存，则从主存中总可以取到最新的数据值。(3)对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存 中。,(4)在写回Cache条件下的实现技术 用Cache中块的标志位实现监听过程。给每个Cache块加一个特殊的状态位说明它是否 为共享。因为每次总线任务均要检查Cache的地址位，这 可能与CPU对Cache的访问冲突。可通过下列两种 技术之一降低冲突：复制标志位 采用多级包含Cache。,存储器分布于各结点中，所有的结点通过网络互连。访 问可以是本地的，也可是远程的。不支持Cache一致性：规定共享数据不进入Cache，仅私有数据才能保存在 Cache中。优点：所需的硬件支持很少(因为远程访问存取量仅是一个字(或双字)而 不是一个Cache块),7.2.2 分布式共享存储器体系结构,缺点：(1)实现透明的软件Cache一致性的编译机制能力有限(2)没有Cache一致性，机器就不能利用取出同一块中 的多个字的开销接近于取一个字的开销这个优点，这是因为共享数据是以Cache块为单位进行管理 的。当每次访问要从远程存储器取一个字时，不能 有效利用共享数据的空间局部性。(3)诸如预取等延迟隐藏技术对于多个字的存取更为有 效，比如针对一个Cache块的预取。,解决Cache一致性问题的关键：目录协议 目录：用一种专用的存储器所记录的数据结构，它 记录着可以进入Cache的每个数据块的访问状 态、该块在各个处理器的共享状态以及是否 修改过等信息。对每个结点增加目录表后的分布式存储器的系统结构。,(1)目录协议的基本点 在每个结点增加了目录存储器用于存放目录；存储器的每一块在目录中对应有一项；每一个目录项主要有状态和位向量两种成分。状态描述该目录所对应存储块的当前情况；位向量共有N位，其每一位对应于一个处理器的局部Cache，用于指出该Cache中有无该存储块的拷贝,共享 在一个或多个处理器上具有这个块的拷贝，且主存 中的值是最新值(所有Cache均相同)。未缓冲 所有处理器的Cache都没有此块的拷贝。专有 仅有一个处理器上有此块的拷贝，且已对此块进行 了写操作，而主存的拷贝仍是旧的。这个处理器称 为此块的拥有者。,(2)目录必须跟踪每个Cache块的状态。Cache块状态有三种：,(3)由于写作废操作的需要，还必须记录共享此块的 处理器信息。方法：对每个主存块设置一个位向量。当此块被共享时，每个位指出与之对应的处 理器是否有此块的拷贝。当此块为专有时，可根据位向量来寻找此块 的拥有者。(4)宿主结点 存放有存储器块和对应地址目录项的结点。,2.目录协议的基本实现技术 基于目录的协议中，目录承担了一致性协议操作的主要 功能。(1)发往一个目录的消息会产生两种不同类型的动作,更新目录状态 发送消息满足请求服务,(2)目录项可能接收到三种不同的请求,读失效 写失效 数据写回,读失效 将存储器数据送往请求方处理器，且本处理器成为此 块的唯一共享结点，本块的状态转换为共享。写失效 将存储器数据送往请求方处理器，此块成为专有。,(3)在各个状态下所接收到的请求和相应的操作 当一个块处于未缓冲状态时，对此块发出的 请求及处理操作为:,当一个块是共享状态时，存储器中的数据是其当前 最新值，对此块发出的请求及处理操作为:读失效 将存储器数据送往请求方处理器，并将其加入共享 集合。写失效 将数据送往请求方处理器，对共享集合中所有的处 理器发送写作废消息，且将共享集合置为仅含有此 处理器，本块的状态变为专有。,当某块处于专有状态时，本块的最新值保存在共 享集合指出的拥有者处理器中，从而有三种可能 的目录请求。读失效 将“取数据”的消息发往拥有者处理器，使该块的状 态转变为共享，并将数据送回目录结点写入存储器，进而把该数据返送请求方处理器，将请求方处理器加 入共享集合。,写失效 本块将有一个新的拥有者。数据写回 拥有者处理器的Cache要替换此块时必须将其写回，从而使存储器中有最新拷贝(宿主结点实际上成为拥有者)，此块成为非共享，共享集合为空。3.对基于目录的Cache一致性的多种改进,有限映射目录 链式结构目录,4.基于目录的Cache一致性协议是完全由硬件实现的。此外，还可以用软硬结合的办法实现。,