第7章多处理机

第7章多处理机 7 1多处理机的特点及主要技术问题7 2多处理机的硬件结构7 3程序并行性7 4多处理机的性能7 5多处理机的操作系统 本章重点 多处理机结构特点 程序并行性 并行任务的派生与汇合 本章难点 并行算法的研究思路 程序中并行任务的派生与汇合 7 1多处理机的特点及主要技术问题 多处理机具有两台以上的处理机 在操作系统控制下通过共享的主存或输入输出子系统或高速通讯网络进行通讯 多处理机属MIMD系统 一 多处理机与并行处理机的差别1 结构灵活性 并行处理机结构主要针对向量 数组处理设计 专用性强 互连形式简单 多处理机系统实现多作业 多任务并行 结构灵活 互连形式复杂 MIMD机结构上具有更大灵活性和更强的通用性 2 程序并行性 并行处理机是操作级并行 并行性存在于指令内部 识别比较容易 多处理机系统是作业级并行 存在于指令外部 较难识别 3 并行任务派生 并行处理机由指令反映数据间能否并行计算 并启动多个处理单元并行工作 多处理机系统需专用语句来指明 一个任务在执行时可派生另外的任务与之并行 4 进程同步 并行处理机的处理单元在同一控制器控制下执行同一条指令 工作显然同步 多处理机系统中处理可能执行不同指令 工作进度不一致 必须用同步机制来控制 5 资源分配和调度 并行处理机主要执行向量 数组运算 处理单元数目是固定的 并行处理机任务调度较易 用屏蔽手段就可以改变实际参加并行工作的处理单元数 多处理机系统需用的处理机数不固定 需解决好资源分配和任务调度 负荷平衡问题 尽可能提高系统硬件资源的利用率 防止系统死锁 二 多处理机存在的主要技术问题1 硬件上处理好处理机 I O通道 存储模块的互连问题 2 软件上最大限度开发系统的并行性 以实现多处理机各级的全面并行 3 确定任务粒度问题 即如何选择任务和子任务的大小 4 进程同步问题 5 任务分配 资源分配 防止死锁问题 6 当系统中某个处理机发生故障后的恢复问题 7 多处理机机数增多后 如何能给编程者提供良好的编程环境问题 7 2多处理机的硬件结构 7 2 1紧耦合和松耦合多处理机有紧耦合和松耦合两种 1 紧耦合多处理机紧耦合多处理机是通过共享主存实现处理机间通讯的 其通讯速率受限于主存频宽 各处理机与主存经互连网络连接 处理机数受限于互连网络带宽及各处理机访主存冲突的概率 为减少访主存冲突 主存采用模m交叉存取 处理机还可自带高速缓冲存储器Cache以减少访主存次数 184页图7 1是紧耦合多处理机的两种构形 它们的主要差别是处理机是否自带专用Cache 为了减少各处理机同时访问同一存储器模块的冲突 存储器模块数m应等于或略大于处理机数p 每台处理机自带局部存储器 不仅可以减少访主存信息量 降低访主存冲突概率 也可以减少处理机 存储器互连网络的冲突 如果再自带专用Cache就可以进一步减少这类冲突 处理机间通过中断信号互连网络 由一台处理机向另一台处理机发生中断信号来实现处理机间的进程同步 多数多处理机采用非对称互连 紧耦合多处理机常用于并行执行作业中的多个任务 以提高系统的速度性能 因此各处理机一般是同构形的 同构 异构 PE类型相同 不同 对称 非对称 每个PE与部分 全部的I O通道连接 常见结构 同构对称式和异构非对称式多机系统 互连网络 实现PE PEM PE I O通道 PE 中断信号间的连接 互连网络控制 分布式控制 消息传递机制 思考1 为什么每个PE可自带小容量局部存储器 思考2 为什么每个PE可自带一个Cache 系统规模 PE数量不能很多 为什么 通信与同步 通过共享存储器地址进行通信 通过共享地址或PPIN进行同步 1 松耦合多处理机松耦合多处理机中 每台处理机都有一个容量较大的局部存储器 用于存储经常用的指令和数据 以减少紧耦合系统中存在的访主存冲突 不同处理机间或者通过通道互连实现通讯 以共享某些外部设备 或者通过消息传送系统MTS来交换信息 各台处理机可带有自己的外部设备 消息传送系统常采用分时总线或环形 星形 树形等拓扑结构 松耦合多处理机较适合做粗粒度的并行计算 互连网络 实现结点 非PE与PSM 间互连 控制 分布式控制 消息传递机制 结点结构 是完整的处理机系统 当结点为多处理机系统时 构成了层次系统 7 2 2机间互连形式多处理机机间互连的形式是决定多处理机性能的一个重要因素 在满足高通讯速率 低成本的条件下 互连还应灵活多样 以实现各种复杂的乃至不规则的互连而不发生冲突 1 总线形式 时间分配 多个处理机 存储器模块和外围设备通过接口与公用总线相连 采用分时或多路转接技术传送 单总线方式结构简单 成本低 系统增减模块方便 但对总线的失效敏感 处理机机数增加会增大总线冲突概率 使系统效率急剧下降 1 提高总线形式的系统效率的办法一是用优质高频同轴电缆来提高总线的传输速率 二是用多总线方式来减少访总线的冲突概率 2 多种总线仲裁算法静态优先级算法为每个连到总线的部件分配一固定的优先级 固定时间片算法是把总线按固定大小时间片轮流提供给部件使用 动态优先级算法是总线上各部件优先级可根据情况按一定规则动态改变 先来先服务算法是按接收到访问总线请求的先后顺序来响应 2 环形互连形式构造一种逻辑总线 让各台处理机之间点点相连成环状 称环形互连 在这种多处理机上 消息的传递过程是由发送进程将信息送到环上 经环形网络不断向下一台处理机传递 直到此信息又回到发送者为止 发送信息的处理机拥有一个唯一的令牌 它是普通传送的信息中不会出现的特定标记 同时只能有一台处理机可持有这个令牌 发送者在发送信息时 环上其他处理机都处于接收信息的状态 优点 由于环形互连是点点连接 不是总线式连接 其物理参数容易得到控制 非常适合于有高通讯带宽的光纤通讯 有效带宽可以得到最充分的利用 缺点 信息在每个接口处都会有一个单位的传输延迟 当互连的处理机机数增加时 环中的信息传输延迟将增大 3 交叉开关形式 空间分配 单总线互连结构最简单 但争用总线最严重 交叉开关形式则不同于单总线 它用纵横开关阵列将横向的处理机P及I O通道与纵向的存储器模块M连接起来 如188页图7 7所示 交叉开关形式是总线形式的极端 总线数 PE数 PEM数 I O通道数 2 控制 仲裁 转换机构均在开关中 总线数等于全部相连的模块数 n i m 且m i n n个处理机和i个I O设备都能分到总线与m个存储器模块之一连通并行地通讯 改进 用一系列较小开关串联或并联 形成多级交叉开关 减少其复杂性 交叉开关方式不适宜连接过多的处理机 由于多处理机的通信模式不规则 因此 能实现N 种排列的全排列网络同样适用于多处理机的机间互连 4 多端口存储器形式将控制 仲裁 转换机构移到存储器中 每个存储器端口与一个PE或I O通道相连 多端口存储器形式不适宜连接过多的处理机 5 开关枢纽结构形式参照多端口存储器的思想 把互连结构的开关设置在各处理机或接口内部 组成分布式结构 则称为开关枢纽结构形式 每一台处理机通过它的开关枢纽与其他多台处理机连接组成各种有分布结构的多处理机 开关枢纽的选择 应使组成的多处理机有较佳的拓扑结构和良好的互连特性 特别是要适应处理机机数很多的情况 理想的拓扑结构应该是 所用开关枢纽数量少 每个开关枢纽的端口数不多 能以较短的路径把数量很多的处理机连接起来 实现快速而灵活的通讯 不改变模块本身的结构 就可使系统规模得到任意扩充 7 3程序并行性 多处理机的并行性既存在于指令内部 也存在于指令外部 因此 必须利用算法 程序语言 编译 操作系统及指令 硬件等多种途径来开拓 多处理机低层次的并行可通过向量化实现 系统高层次的任务和作业的并行主要靠算法 编译 语言和操作系统来开发 7 3 1并行算法为了简化讨论 以算术表达式的并行运算为例来说明并行算法的研究思路 算法必须适应具体的计算机结构 串行处理机上习惯采用的循环和迭代算法往往不适合于多处理机 采用直接解法有时反倒能揭示更多的并行性 例如 E1 a bx cx2 dx3 利用霍纳法可得到 E1 a x b x c x d 这是在单处理机上执行的典型算法 共需要3个乘加循环6级运算 但不适合于在多处理机上运行 因为它无法利用上其他的处理机 用3台处理机只需4级运算就够了 将这两式的运算过程表示为树形流程图分别为下图所示 运算的级数就是树的高度 用Tp代表 P为所需处理机的数目 称顺序运算的级数T1与P台处理机运算的级数Tp的比为加速比 用Sp代表 而Sp P Ep称为效率 可见 Sp 1时 会使Ep 1 即运算的加速总是伴随着效率的下降 既然可把运算过程表示成树形结构 那么 提高运算的并行性就是如何对树进行变换 减少运算的级数 即降低树高 树型结构可以用交换律 结合律 分配律来交换 方法 首先从算术表达式的最直接形式出发 利用交换律把相同的运算集中在一起 然后利用结合律把参加这些运算的操作数 称原子 配对 尽可能并行运算 从而组成树高最小的子树 最后再把这些子树结合起来 例如 表达式E2 a b c def g h 共需7级运算 利用交换律和结合律改写为E2 a h b c g def 则只需5级运算 利用分配律进一步降低树高 在恰当平衡各子树的级数的情况下往往能收到较好的效果 表达式运算并行性的识别 除了依靠算法外 还可以依靠编译程序 例如 给定算术表达式Z E A B C D F 利用普通的串行编译算法 产生三元指令组为 1 AB2 1C3 2D4 3E5 4F6 5Z 指令之间都是相关的 需5级运算 如用并行编译算法 则可得到能并行执行的三元指令组为 1 AB2 CD3 124 EF5 346 5Z可见 有了好的并行编译算法 算术表达式的预先变形也可以是不必要的 7 3 2程序并行性的分析任务间能否并行 除了算法外 很大程度还取决于程序的结构 程序中各类数据相关 是限制程序并行的重要因素 数据相关既可存在于指令之间 也可存在于程序段之间 假定一个程序包含P1 P2 Pi Pj Pn等n个程序段 其书写的顺序反映了该程序正常执行的顺序 为了便于分析 设Pi和Pj程序段都是一条语句 Pi在Pj之前执行 且只讨论Pi和Pj之间数据的直接相关关系 1 数据相关如果Pi的左部变量在Pj的右部变量集内 且Pj必须取出Pi运算的结果来作为操作数 就称Pj 数据相关 于Pi 例如 PiA B DPjC A E相当于流水中发生的 先写后读 相关 顺序串行运行的正确结果应当是 PiA新 B原 D原PjC新 A新 E原 B原 D原 E原 2 数据反相关如果Pj的左部变量在Pi的右部变量集内 且当Pi未取用其变量的值之前 是不允许被Pj所改变的 就称Pi 数据反相关 于Pj 例如 PiC A EPjA B D相当于流水线中发生的 先读后写 相关 顺序串行运行的正确结果应是 PiC新 A原 E原PjA新 B原 D原 3 数据输出相关如果Pi的左部变量也是Pj的左部变量 且Pj存入其算得的值必须在Pi存入之后 则称Pj 数据输出相关 于Pi 例如 PiA B DPjA C E按原执行顺序A新应为C E 可见 只要同步能保证Pi先写入之后Pj的再写入 这两个程序段可以并行 当然 交换串行是不行的 因为最后结果将使A新成了B D了 总结 两个程序段之间若有先写后读的数据相关 不能并行 只在特殊情况下可以交换串行 若有先读后写的数据反相关 可以并行执行 但必须保证其写入共享主存时的先读后写次序 不能交换串行 若有写 写的数据输出相关 可以并行执行 但同样需保证其写入的先后次序 不能交换串行 若同时有先写后读和先读后写两种相关 以交换数据为目的时 必须并行执行 且读写要完全同步 不许顺序串行和交换串行 若没有任何相关或仅有源数据相同时 可以并行 顺序串行和交换串行 7 3 3并行程序设计语言并行算法需要用并行程序来实现 并行程序设计语言的基本要求是 能使程序员在其程序中灵活方便地表示出各类并行性 能在各种并行 向量计算机中高效地实现 并行进程的特点是这些进程在时间上重叠地执行 一个进程未结束 另一个进程就开始 包含并行性的程序在多处理机上运行时 需要有相应的控制机构来管理 其中包括并行任务的派生和汇合 并行任务的派生是使一个任务在执行的同时 派生出可与它并行执行的其它一个或多个任务 分配给不同的处理机完成 并行任务的派生和汇合常用软件手段控制 首先要在程序中反映出并行任务的派生和汇合关系 例如 可在程序语言中用FORK语句派生并行任务 用JOIN语句对多个并发任务汇合 FORK和JOIN语句在不同机器上有不同的表示形式 现以M E Conway提出的形式为例 FORK语句的形式为FORKm 其中m为新进程开始的标号 执行FORKm语句时 派生出标号为m开始的新进程 具体为 准备好这个新进程启动和执行所必需的信息 如果是共享主存 则产生存储器指针 映象函数和访问权数据 将空闲的处理机分配给派生的新进程 如果没有空闲处理机 则让它们排队等待 继续在原处理机上执行FORK语句的原进程 与FORK语句配合 作为每个并发进程的终端语句JOIN的形式是JOINn 其中n为已派生出的并发进程个数 JOIN语句附有一个计数器 其初始值为0 每当执行JOINn语句时 计数器的值加1 并与n比较 若比较相等 表明这是执行中的第n个并发进程经过JOINn语句 于是允许该进程通过JOIN语句 将计数器清0 并在其处理机上继续执行后续语句 若比较结果 计数器的值仍小于n 表明此进程不是并发进程中的最后一个 可让现在执行JOIN语句的这个进程先结束 把它所占用的处理机释放出来 分配给正在排队等待的其它任务 如果没有排队等待的任务 就让该处理机空闲 例 算术表达式Z E A B C D F的计算为例 经并行编译得到如下程序 S1G A BS2H C DS3I G HS4J E FS5Z I J如果不加并行控制语句 这个程序仍然只是一个普通的串行程序 发挥不出多处理机的作用 利用FORK和JION语句实现这种派生和汇合关系 将程序改写为 FORK2010G A B 进程S1 JION2GOTO3020H C D 进程S2 JION230FORK40I G H 进程S3 JION2GOTO5040J E F 进程S4 JION250Z I J 进程S5 执行这个程序可用两台处理机 其执行过程见196页图7 17所示 假定A B两个8 8矩阵相乘 需要在多处理机上实现任务一级的并行 用FORTRAN语言书写的程序如下 DO10J 0 610FORK20J 720DO30I 0 7C I J 0DO40K 0 740C I J C I J A I K B K J 30CONTINUEJOIN8 设FORK语句在处理机1上执行 在循环执行7次FORK20语句时 派生出J 0 6共7个以20为标号的进程 让它们与J 7的进程并行 如果只有3台处理机 分配了J 0和J 1的进程后 其余J为2 6的5个进程就得排队等待 处理机1在结束循环后执行J 7的进程 整个程序在先后执行完8个进程才结束 资源时间图如下图所示 从表面上看 多处理机的每一个处理机和并行处理机的每一个处理单元求解矩阵乘完成的工作是一样的 但处理方式却有根本区别 第一 并行处理机的每一条指令要求8个处理单元对J 0 7的不同数组完全同步地运算 而在多处理机中 即使有8个处理机执行同一程序段 并不需要 也不会完全同步 更何况不同处理机执行的程序段还可以是毫不相同的 这是操作级并行与任务级并行的差别 第二 多处理机中可用的处理机数目对程序的书写没有影响 即程序对可用的处理机数目无固定要求 这是多处理机相对于并行处理机的重要优点之一 7 4多处理机的性能 7 4 1任务粒度与系统性能使用多处理机的主要目的是用多个处理机并发执行多个任务来提高解题速度 任务粒度的大小 会显著影响多处理机的性能和效率 任务粒度过小 辅助开销大 系统效率低 粒度过大 并行度低 性能不会很高 因此 要合理选择任务粒度的大小 并使其尽可能均匀 还要采取措施减少辅助开销 以保证系统性能随处理机数目的增大能有较大的提高 衡量任务粒度大小的一个依据是程序用于有效计算的执行时间E与处理机间的通讯等辅助开销时间C的比值 任务粒度还与系统的应用有关 图象及多目标跟踪因为机间通讯开销少 宜于细粒度处理 要求冗长计算才能得到结果的题目 宜于粗粒度处理 系统设计应使系统的应用能与应用问题的粒度取得较佳适配 7 4 2性能模型与分析通过建立多处理机若干不同的性能模型 来分析不同程序 并行算法及结构对多处理机性能的影响 为了简化模型 只考虑用于机间通讯方面的辅助开销 其他方面的辅助开销对性能的体现 可以通过对该模型适当增大任务粒度的办法来体现 假定一个应用程序含T个任务 在N台机处理机上运行 每个任务的执行时间为E 两个任务在同一台处理机上执行是不需要机间通讯的 但在不同处理机上执行 就可能要机间通讯 设每次通讯开销时间为C 1 N 2且计算与通讯不能重叠一个程序在双处理机上运行 如果将全部任务都分配给一台处理机 而让另一台处理机空闲 虽然没有并行 却不需要机间通讯 程序总的运行时间为R T E 如果将其中I个任务分配给第一台处理机 而余下的T I个任务分配给另一台处理机 则 R E max T I I C T I I其中 第1部分为执行时间 是取两台处理机执行时间中的大者 第2部分时间为通讯时间 R与I之间的关系如198页图7 19所示 图7 19 a 分别表示E C等于T 2 大于T 2和小于T 2时 总执行时间 总通讯时间与I的关系 可见E C的大小不影响总执行时间 只影响总通讯时间 图7 19 b 说明当E CT 2时 将任务均分给两台处理机 可使总运行时间R最少 2 N 2且计算与通讯不能重叠若将Ik个任务分配给第K台处理机 则 由于所以有 第2项为每台处理机上各个任务与其他处理机上各个任务之间两两通讯的总时间 N台处理机总运行时间最短的情况 或者是将所有任务集中分配于一台处理机上以免去通讯开销 或者是将任务尽可能平均分配给所有各处理机 对于平均分配的任务数T不是处理机数N的整数倍时 让大多数处理机分得T N个任务 一台处理机分配所剩全部不足T N个任务 余下的处理机空闲不分配任务 究竟是采用平均分配还是集中分配 可以通过计算这两种任务分配策略的总运行时间差来决定 结论 当E C T 2时 应采用平均分配策略 而当E C T 2时 因额外开销C较大 应采用集中分配策略 以上是假设所有任务的执行时间都相同的情况 因此 任务均匀分配给所有处理机 可使处理机总执行时间最少 实际上 各个任务的执行时间不一定相同 这时若采取不均匀分配任务 可以大大减少通讯开销 即在各处理机总的运行时间均衡的前提下 让各处理机所分配到的任务数尽可能地多或者尽可能的少 可以使系统因通讯开销减少而使总运行时间得以减少 3 额外开销与计算工作可以重叠推导过程见201页 对于N台处理机 当ET N C T T 2 1 1 N 时 辅助开销将被完全覆盖掉 如果N值很大 而让总运行时间最少时 就有N 2 E C T 即选择的最佳机数与可提供的任务数T成反比 4 机间通讯可以多路同时进行推导过程见201页 结论 增大并行度和增大通信链路带宽均可以缩短总运行时间 任务粒度相应可以取得小些 不过通信链路数的增大及通信链路带宽的提高 并不能降低通讯之外的其它辅助开销 同时将会显著提高系统的造价 因此 此时并行度大小主要取决于系统的性能价格比 所采用的机间通讯技术 互连结构以及为降低其它辅助开销所采取的措施 结论 随着多处理机机数的增加 解题时用于计算的那部分执行时间会减少 但调度 共享资源的竞争 同步 机间通讯等辅助开销会增大 而且这种增大的量可能比机数的线性增加还要大 就多处理机而言 结构设计者应考虑如何设计出一个使E C值尽可能高 且价格合理 处理机机数多 又能高效使用的多处理机 应深入展开对并行算法 并行语言 并行程序设计技术和如何减少额外开销等综合研究 7 5多处理机的操作系统 包含并行性的程序在多处理机上运行时 要有相应的控制机构来实现管理功能 它们主要是通过多处理机操作系统 用软件手段来实现的 多处理机操作系统有主从型 各自独立型及浮动型三类 7 5 1主从型操作系统主从型管理程序只在一个指定的处理机 主处理机 上运行 该主处理机可以是专门的执行管理功能的控制处理机 也可以是与其它从处理机相同的通用机 除执行管理功能外也能做其它方面的应用 1 优点系统硬件结构比较简单 整个管理程序只在一个处 理机上运行 除非某些需递归调用或多重调用的公用程序 一般都不必是可再入的 实现起来简单 经济 方便 是目前大多数多处理机操作系统所采用的方式 2 缺点对主处理机的可靠性要求很高 一旦发生故障 很容易使整个系统瘫痪 这时必须要由操作员干预才行 当大部分任务都很短时 由于频繁地要求主处理机完成大量的管理性操作 系统效率将会显著下降 3 适用场合主从型操作系统适合于工作负荷固定 且从处理机能力明显低于主处理机 或由功能相差很大的处理机组成的异构型多处理机 7 5 2各自独立型操作系统各自独立型将控制功能分散给多台处理机 共同完成对整个系统的控制工作 每台处理机都有一个独立的管理程序在运行 即每台处理机都有一个内核的副本按自身的需要及分配给它的程序需要来执行各种管理功能 1 优点很适应分布处理的模块化结构特点 减少对大型控制专用处理机的需求 某个处理机发生故障 不会引起整个系统瘫痪 有较高的可靠性 每台处理机都有其专用控制表格 使访问系统表 格 使访问系统表格的冲突较少 也不会有许