第7章多处理机系统.ppt

第7章多处理机系统 7 1多处理机系统结构7 2多处理机系统控制7 3并行处理语言及算法7 4多处理机性能7 5多处理机系统实例 多处理机系统结构 多处理机硬件结构 紧耦合和松耦合 1 紧耦合多处理机紧耦合多处理机是通过共享主存来实现处理机间通信的 其通信速率受限于主存的频宽 但是 由于各处理机与主存经互连网络连接 系统中处理机数就受限于互连网络带宽及多台处理机同时访问主存发生冲突的概率 图7 1紧耦合多处理机的结构 带非对称I O子系统的多处理机 采用冗余连接的非对称I O子系统 2 松耦合多处理机 松耦合多处理机是通过消息传送系统连接的多处理机结构 机间互联形式 1 总线形式 多个处理机 存贮器模块和外围设备通过接口与公用总线相连 采用分时或多路转接技术传送 其中 单总线方式结构简单 成本低 系统上增减模块方便 但对总线的失效敏感 而且 处理机数增加会增大访问总线冲突的概率而导致系统效率急剧下降 虽然可以在处理机中设置局部存贮器和专用外围设备来减少访问总线的冲突 但这种单总线形式也只适用于处理机数较少的场合 IBMStretch和UNIVACLarg多处理机采用的就是单总线方式 2 环形互连形式 机间采用环形互连的多处理机 3 交叉开关形式 图7 7交叉开关形式 交叉开关中结点开关的结构 存储器组织 1 集中式共享存储器 三个特点 处理器数量不大 从而所有处理器可共享一个集中式存储器 处理器和存储器通过总线互连 采用大容量Cache 可使采用单一总线和单一存储器满足数目不多处理器对存储器的要求 每一处理器访问存储器的时间是相等的 多个处理器共享一个存储器当处理器规模较小时 这种机器十分经济支持对共享数据和私有数据的cache缓存私有数据供一个单独的处理器使用 而共享数据供多个处理器使用 共享数据进入cache 产生一个新的问题Cache一致性问题 多处理机cache的一致性 产生cache不一致的原因 I O操作Cache中的内容可能与由I O子系统输入输出形成的存储器对应部分的内容不同 共享数据不同处理器的Cache都保存有对应存储器单元的内容 存储器的一致性如果对某个数据项的任何读操作均可得到其最新写入的值 则认为这个存储系统是一致的 需满足以下条件 处理器P对X进行一次写之后又对X进行读 读和写之间没有其它处理器对X进行写 则读的返回值总是写进的值 一个处理器对X进行写之后 另一处理器对X进行读 读和写之间无其它写 则读X的返回值应为写进的值 对同一单元的写是顺序化的 即任意两个处理器对同一单元的两次写 从所有处理器看来顺序都应是相同的 实现一致性的基本方案 1 Cache一致性协议 对多个处理器维护一致性的协议 2 关键 跟踪记录共享数据块的状态 3 共享数据状态跟踪记录技术 目录物理存储器中共享数据块的状态及相关信息均被保存在一个称为目录的地方 监听 snooping 每个Cache除了包含物理存储器中块的数据拷贝之外 也保存着各个块的共享状态信息 2 分布式共享存储器 特点 存储器分布于各节点中 所有节点通过网络互连 访问可以是本地的 也可是远程的 可以不支持cache一致性协议 规定共享数据不进入cache 仅私有数据才保存在cache中 解决Cache一致性问题的关键 寻找替代监听协议的一致性协议 目录协议在每个结点增加目录存储器 用于存放目录 基于目录的Cache一致性及其实现 目录协议必须实现两种基本操作处理读失效 处理对共享 干净块的写目录必须跟踪记录每个存储块的状态必须记录哪些块有该处理器的拷贝 多处理机操作系统 1 主从式主从式操作系统由一台主处理机记录 控制其它从处理机的状态 并分配任务给从处理机 2 独立监督式独立监督式中 每一个处理机均有各自的管理程序 核心 3 浮动监督式每次只有一台处理机作为执行全面管理功能的 主处理机 但根据需要 主处理机 是可浮动的 即从一台切换到另一台处理机 多处理机系统控制 多处理机调度 1 什么是多处理机调度 将作业或任务分配给指定的处理机 并要求在指定的时间内完成 调度算法的一般目标是 使用最少的处理机 在最短的时间内完成并行程序的执行任务 在处理机器数目固定时 要改进处理机分配和进程调度算法 尽量减少并行程序的执行时间 2 多处理机调度方式 确定性调度 在调度之前必须知道所有有关信息 例如每个任务的执行时间和任务间的依赖关系 以便合理地把任务分派到处理机 不确定性调度 根据任务运行的动态行为 将任务分配到特定的处理机上 3 调度性能评价 评价多处理机调度性能的参数有 任务流时间 完成任务所需要的时间调度流时间 调度中所有任务流的时间平均流 平均流等于调度流时间除以任务数处理机的利用率 该处理机上任务流之和除以最大有效时间单位加速比 用于度量系统的速度 等于各处理机忙时间之和除以并行工作时间吞吐率 单位时间内系统完成的任务数 多处理机间进程通讯 第一种方法是在共享的地址空间进行通信 物理上分开的存储器能够作为逻辑上共享的地址空间进行寻址 利用地址空间通过load和store操作隐式地传递数据 第二种方法是在私有的地址空间进行通信 多个私有地址空间在逻辑上是分散的 并且不能被远程处理器寻址 数据通信通过显式地在处理器间传松消息来完成 如集群 就是使用消息传递的一类系统 多处理机系统死锁 死锁问题是由于各处理机为争夺全局范围内的资源而引发的 传统的狭义多处理机系统是利用系统内的多台处理器并行执行用户程序的若干个任务 任务至少包含有1个进程 如果一台处理器或处理机内运行多个进程 那么这种情况和单处理机完全相同 死锁是由于各并发进程为争夺本地资源而发生 死锁问题 预防 避免 检测与恢复 的解决办法可以套用单处理机做法 如果每台处理机只运行1个进程 系统死锁是由于各处理机为争夺全局范围内的资源而引发的 逻辑上 可以把这样的多机系统看成为单机多进程系统 因此单处理机环境中为解决死锁而讨论的资源分配 控制 使用策略在多处理机环境下继续有效 同步 运行在不同处理器上的进程之间需要通信以协调地完成一个任务 进程间的通信可以通过使用共享变量来实现信息交换 但对共享变量的访问要保证互斥访问 即 保证每次只有一个进程访问共享变量 同步机制的实现 硬件提供同步原语 用户层软件实现 关键的硬件功能 提供不可中断的指令 或实现原子地读和更新一个值的指令 并行处理语言及算法 并行处理面临的两个重要挑战 程序中有限的并行性相对较高的通信开销 系统加速比 问题的解决并行性不足 采用并行性更好的算法远程访问延迟的降低 靠体系结构支持和编程技术 并行程序设计语言 在多处理机系统中 必须用并行程序设计语言编写程序 或者把已经用串行语言编写的程序转换成并行语言程序之后 才能在多处理机系统上运行 把传统串行语言程序转换成并行语言程序的过程称为并行编译 有两种并行编译方式 全自动并行编译与半自动并行编译 全自动并行编译是方向 但实现起来很困难 半自动并行编译又称为交互式并行编译 程序员通过多次与机器对话 找到串行程序中可以并行执行的部分 并行程序设计语言 并行编译器生成代码的形式有多种 并行高级语言程序 并行中间语言程序 并行目标语言程序 多处理机的性能 引起峰值性能下降的原因是 1 因处理机间通信而产生的延迟 2 一台处理机与其它处理机同步所需的开销 3 当没有足够多任务时 一台或多台处理机处于空闲状态 4 由于一台或多台处理机执行无用的工作 5 系统控制和操作调度所需开销研究多处理机的目的 提前5年得到速度高10倍的机器 或用1 10的价格获得一台高性能的机器 如果设计得好 在某些适合进行并行处理得应用领域 可以达到 提前10年得到速度高100倍的机器或用1 100的价格获得一台高性能的机器 多处理机的性能 任务粒度与系统性能 衡量任务粒度大小的一个依据是程序用于有效计算的执行时间E与处理机间的通信等辅助开销时间C的比值 只有E C 的值较大时 开发并行性才能得到好处 如果最大并行度会带来最大的通信等辅助开销 倒不如增大任务粒度 降低并行度 来减少辅助开销 因此 为获得最佳的性能 必须对并行性和额外开销进行综合平衡 多处理机的性能 并行性在很大程度上依赖于R C比值 其中 R代表程序执行时间 C代表通信开销 通常 R C比值小 并行性低 R C比值大 并行性高如果把作业分解成较大的块 就能得到较大的R C值 但是所得到的并行性比最大可能的并行性要小得多 R C比值是衡量任务粒度 Granularity 大小的尺度在粗粒度 Coarsegrain 并行情况下 R C比值比较大 通信开销小在细粒度 Finegrain 并行情况下 R C比值比较小 通信开销大细粒度并行性需要的处理机多 粗粒度并行性需要的处理机少 细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务 在极端情况下 一个小任务只完成一个操作 性能模型 1 N 2且计算与通信不能重叠 一个程序在双处理机上运行 如果将全部任务都分配给一台处理机而让另一台处理机空闲 虽然没有并行 却不需要机间通信 程序总的运行时间R T E 如果将其中I个任务分配给一台处理机 而将余下的T I个任务分配给另一台处理机 则 性能模型与分析 1 N 2且计算与通信不能重叠 一个程序在双处理机上运行 如果将全部任务都分配给一台处理机而让另一台处理机空闲 虽然没有并行 却不需要机间通信 程序总的运行时间R T E 如果将其中I个任务分配给一台处理机 而将余下的T I个任务分配给另一台处理机 则 不同E C时 执行时间 通信时间和 总运行时间R与任务分配数I的关系 2 N 2且计算与通信不能重叠 若将Ik个任务分配给第k台处理机 则 由于 所以有 究竟是采用平均分配还是集中分配 可以通过计算这两种任务分配策略的总运行时间差来决定 为简单起见 设T是N的整数倍 则平均分配与集中分配二者总运行时间差为 若令其等于0 可得E C T 2 这说明 当E C T 2时 应采用平均分配策略 而当E C T 2时 因为额外开销C较大 应采用集中分配策略 否则并行执行的总运行时间反而会延长 进一步 可求得采用平均分配时 并行系统的加速比 由此得到一个重要的结论是 如果 加速比可接近于N 即当任务数T及处理机数N均较少 E C又较大时 并行系统的加速比是随处理机机数N的增加而接近线性地提高的 但当机数N增大到较大后 Sp就趋近于2E CT 只与E C及任务数T有关 而与机数N基本无关了 SP随N的变化趋势 T 20 E 100 不同C时SP与N的关系 在多处理机上并不是每个任务均需要与其他任务通信的 较常见的情况是 一个任务与其他任务通信且通信内容相同时 只需向每台处理机通信一次即可 这样 任务分配给N台处理机后 系统总运行时间为 T 20 E 10 不同C时SP与N的关系 当机数由N台增加到N 1台时 总运行时间的减少量为 令其大于等于0 有 可见 多处理机性能最佳时的机数N是E C的函数 当后 增大机数N 反而会使总运行时间延长 3 额外开销与计算工作可以重叠 假定额外工作被计算工作完全覆盖 则总运行时间为 当E C T 2时 虚直线与实曲线没有交点或仅在I T 2处有一个交点 执行时间完全覆盖了额外开销 当E C T 2时 虚直线与实曲线有两个交点 交点之纵坐标为最短总运行时间 横坐标为此时任务分配数I的最佳取值 在交点处为E T I C T I I 即I E C 其中 此时 总运行时间 加速比 SP肯定处于1 2之间 且在I T 2时 有最大值2 如果E C减小至1 SP T T 1 在T很大时 就会使SP 1 即双处理机的性能会降低成与单处理机的一样了 推广到N台处理机 当时 辅助开销将被完全覆盖掉 如果N值很大而让总运行时间最少时 就有 即选择的最佳机数与可提供的任务数T成反比 4 机间通信可以多路同时进行 现假设每台处理机均有通信链路与其他处理机通信 则通信操作就可以与任务本身的执行重叠进行 任何时刻 由于一台处理机只能与另一台处理机通信 即使链路数为N2 至多也只有N台处理机在并发通信 因此 这种系统总运行时间为 如果任务采取平均分配策略 则总运行时间R为 Origin2000分布共享存储器结构的大规模并行多处理机系统 采用超结点的模块结构 可以从1个处理器扩展到128个处理器 Origin2000采用超标量MIPSR10000处理器 运行Unix的64位IRIX操作系统 多处理机实例 Origin基于NUMA体系结构的每个结点可安装1个或2个MIPSR10000微处理器 第二级高速缓存 L2Cache 主存储器 目录存储器及Hub等 Hub用于连接微处理器 存储器 I O和路由器等 Origin存储器系统每个结点的主存储器容量 4GB结点的Hub内含4个接口和交叉开关 存储器最大传输率为780Mb sI O和路由器接口最大传输率 2 780Mbs 1 56Gb s Origin的路由器有6个端口 用于连接结点或其它路由器 Origin的路由器和互连网