第五章 多处理机系统

4 19 2020 1 多处理机系统 4 19 2020 2 多处理机系统的定义 P H Enslow对多处理机作了下列定义 包含两个或两个以上功能大致相同的处理器 所有处理器共享一个公共内存 所有处理器共享I O通道 控制器和外围设备 整个系统由统一的操作系统控制 在处理器和程序之间实现作业 任务 程序段 数组和数组元素等各级的全面并行 4 19 2020 3 多处理机的优点 很高的性能价格比 单处理机的性能价格比随其规模的增大而下降很高的可靠性 冗余度大 可维护性 可用性很高的处理速度 多个处理器并行运算很好的模块性 大量重复设置 结构灵活性 可扩充性 可重构性 4 19 2020 4 特性要求 进程恢复能力 多处理机系统使用的处理机结构应能反映进程和处理机是两个不同的实体 如果某处理机发生故障 另一台处理机应能检索到被中断的进程状态 使被中断的进程能继续运行 没有这个功能 系统的可靠性大大下降 大多数处理机把当前正在运行进程状态保存在内部寄存器中 如何使其他处理器在必要时能访问到进程状态 是恢复进程的关键之一 在不太损失速度的前提下 把通用寄存器与处理机本身分开是可能的 在系统内设置所有处理机共享的寄存器堆可以实现上述功能 4 19 2020 5 特性要求 有效的现场切换 现场切换操作是把当前进程状态保存起来 然后通过恢复新进程的状态切换到被选中的准备好运行的进程 切换操作可以在指令系统中设置一条专门指令来完成 该指令执行的结果是将当前进程状态或现场内容保存起来 然后到主存储器的缓冲区取另一个进程状态 该缓冲区称为交换包 4 19 2020 6 特性要求 大的物理地址空间和虚拟地址空间 多处理机系统内的处理机必须能支持大的物理地址空间 即直接寻址空间要大 这是因为进程需要访问大量数据 例如 Pentium地址线32根 直接寻址空间可达4GB 能满足需求 有了大的物理地址空间 还需要大的虚拟地址空间 把虚拟地址空间分段 便于模块共享以及地址界限的检查 4 19 2020 7 特性要求 高效率的同步原语 处理机设计时必须能提供作为同步原语基础的某种不可再分的操作 这些同步原语需要有互斥机构支持 当两个以上的进程并发地运行或相互交换数据时 需要互斥 互斥机构包含某种形式的读 修改 写存储周期和排队 信号灯 semaphore 是互斥机构的一种 每个信号灯有其队列 队列中的项是被挂起来的进程 信号灯操作是不可分操作 利用读 修改 写存储周期 测试和修改信号灯 队列操作也应是不可分的 4 19 2020 8 特性要求 处理机之间有高效率的通信机构 通信机构可用硬件实现 它有助于实现处理机之间的同步 在非对称多处理机系统中 不同的处理机之间经常需要交换服务请求 硬件通信机构作用更加明显 在处理机发生故障时 通过该机构发信号给其他正在运行的处理机 并启动诊断过程或纠错过程 在紧密耦合的多处理机系统内有共享存储器 采用软件方法实现多处理机之间的通信是可能的 每个处理机必须周期地检查位于共享存储器内的 信箱 缓冲区 检查是否有信息给它 4 19 2020 9 特性要求 指令系统 处理机的指令系统应能支持实现具有过程级并发功能的高级语言 为有效的处理数据结构提供充分条件 指令系统内应有过程连接 循环结构 参数处理 多维下标计算和地址界限检查等指令 还需包括产生和结束程序内部并行执行通路的指令 设置特权指令 4 19 2020 10 Flynn分类法 MichealFlynn 1972 提出指令流 数据流和多倍性概念 把不同的计算机分为四大类 下图 SISD Single InstructionSingle Data 单处理机结构 SIMD Single InstructionMulti Data 带分布存储器 MISD Multi InstructionSingle Data 搏动式阵列 MIMD Multi InstructionMulti Data 带共享存储器 4 19 2020 11 4 19 2020 12 1 并行性粒度 G小则粒度细 通信量大 2 并行性等级划分 作业级 任务级 子程序级 MIMD循环级 语句或指令级 SIMD 粗粒度通常采用MIMD 细粒度则采用SIMD 2 并行处理 是一种相对串行处理的信息处理方式 侧重并发性 4 19 2020 13 并行处理机 在单机系统里主要是采用时间重叠技术 把一件工作按功能分割为若干相互联系的部分 把每一部分指定给专门的部件完成 然后按时间重叠原则把各部分执行过程在时间上重叠起来 使所有部件依次分工完成一组同样的工作 并行处理机主要是通过资源重复技术来实现并行处理的 它属于单指令流多数据流 SIMD 计算机一类 4 19 2020 14 1 组成 通常由1个控制器 CU 多个处理器 PE m个存储模块 M 及1个互连网络 ICN 组成 一 基本结构 并行处理机工作原理 根据存储模块组成方式可有分布式和集中式两种 4 19 2020 15 基本结构的共同特点 并行处理机的两种基本结构的共同特点 重复设置许多个同样的处理单元PE ProcessElement 由ICN InterConnectionNetwork 按照一定的方式相互连接 在统一的控制部件CU ControlUnit 作用下 各PE对分配来的数据并行地完成同一条指令所规定的操作 4 19 2020 16 并行处理的特点 资源重复 它机利用众多的处理单元对向量所包含的各个分量同时进行运算 获得很高处理速度 连接模式 它的处理单元间是通过ICN来通信的 不同的连接模式确定了它的不同结构 专用性 它直接与一定的算法相联系 其效率取决于在多大程度上把计算问题归结为向量数组处理 复合性 整个系统是由三部分复合起来的一个多机系统 即多个处理单元组成阵列并行地处理向量 功能极强的控制部件实际上是一台标量处理机 系统的管理功能则由高性能单处理机担负 4 19 2020 17 2 分布式结构 存储模块由每个PE自带 3 集中式结构 各个PE共享m个存储模块 特点 ICN 是单向的 PE PE 工作流程 特点 ICN 是双向的 PE M 工作流程 比较 分布式每个PE有局部存储器 集中式共享存储器 ICN的作用不同 分布式PE PE 集中式PE M 4 19 2020 18 三 阵列处理机的常用并行算法 1 有限差分问题 应用 网格覆盖场 图像平滑化算法 结构 IN采用闭合螺旋线阵列 P189图 原理 实现 每个PE存储和计算一组结点 多次迭代 直到误差小于规定 效率 接近N倍 要扣除通讯开销 结点最大间距 n 1 4 19 2020 19 互连网络基本概念 并行计算机互连网络 基本功能 互连网络ICN主要完成结点与结点间的连接 连接和控制方式不同 连接效果不同 并行处理机互联网络ICN是实现并行处理机中各处理单元之间或处理单元与存储器之间的信息交换 互联网络的不同拓扑结构直接决定了并行处理机的结构 4 19 2020 20 结构特征 1 通信方式同步 异步 3 交换方式线路交换 分组交换 4 拓扑结构 2 控制策略集中 分散 4 19 2020 21 设计思路 根据应用需要 互连网络属性 选择合理的特征方式 考虑互连网络的性能因素 综合加以合理组合 目标 低成本 高灵活性 高连接度 低延时 适合VLSI 互连网络表示 入端的编码 x bn 1 b0 n log2N 互连函数为基于bn 1 b0的排列 组合 移位 取反等操作的结果 互连网络的连接特征一般用互连函数表示 一个互连网络的连接特征可对应多个互连函数 4 19 2020 22 1 立方体单级网络 交换互连网络 单级互连网络只能实现有限的几种连接 单级互连网络 出端编码与连接的入端结点的编码有一位相反 互连函数 互连特性 交换功能 互连函数可逆 互连函数个数 log28 3 最大连接度 log28 3 结点最大间距 log28 3 4 19 2020 23 出端编码与连接的入端结点的编码有一位相反 互连函数 Cube0 b2b1b0 0 1 2 3 4 5 6 7 Cube1 b2b1b0 0 2 1 3 4 6 5 7 Cube2 b2b1b0 0 4 1 5 2 6 3 7 注意 立方体坐标编号不能标错 4 19 2020 24 连接图 扩展成超立方体 有n log2N个互连函数 最大连接度 log2N 结点最大间距 log2N 应用 几种互连函数反复调用 任意结点间可连接 4 19 2020 25 2 PM2I单级网络 循环移数网络 出端编码与连接的入端结点编码相差2i 互连函数 PM2I i j j 2i modN n log2N 0 i n 1 PM2I i j j 2i modN 0 j N 1 共有2n个互连函数 2n 1种不同 连接图 0 顺环圆周连接 1 顺环内接n 2边形连接 2 顺环内接n 4边形连接 n 1 顺环内直径连接 4 19 2020 26 设n 8 则各互联循环为PM2 0 01234567 PM2 0 76543210 PM2 1 0246 1357 PM2 1 6420 7531 PM2 2 04 15 26 37 4 19 2020 27 互连特性 2n个互连函数只有一种函数可逆 其余均不可逆 最大连接度2n 1 互连函数个数2n 应用 几种互连函数混合 任意结点间可连接 实例 闭合螺旋结构为PM2I 0及PM2I n 2互连函数 4 19 2020 28 3 混洗交换单级网络 全混洗 二混洗 三混洗 全混洗互连函数 Shuffle bn 1bn 2 b1b0 bn 2 b1b0bn 1 全 0 或全 1 结点无法与其他结点连接 必须辅以交换互连函数 方可实现任意结点间连接 4 19 2020 29 最简单的交换互连函数为Cube0 因此混洗交换网络由全混洗和交换网络组合而成 交换互连函数 混洗交换互连函数 连接图 4 19 2020 30 4 总结 1 单级互连网络特性 任一单级互连网络可实现部分结点 一对或几对 间的连接 不能实现任意多对结点间的同时连接 单级互连网络含义 某些连接方法或拓扑结构 2 单级互连网络应用 利用单级互连网络的特性作为实际IN的拓扑结构 通过交换开关作为IN的可变因素 通过交换开关多次控制实现IN的结点间任意互连 4 19 2020 31 阵列机结构 阵列机系统是并行处理机最常见的结构形式 它是由大量的处理机按一定规则的几何形式构成阵列形式 最早阵列机是ILLIAC 它是由4个处理机阵列构成 每个阵列里由64个处理单元和1个控制部件组成 4 19 2020 32 阵列机结构 cont ILLIAC 阵列机结构 如图5 9所示 64个PE按矩形排列成8 8方阵 PE只与自己四边相邻的PE相连 任意二个不相邻PE的通信可以通过选择最短路径的算法 由软件来实现 每个PE包括处理机外 还有自身的附属存储器PEM和存储器逻辑部件MLU 同时还有包含I O在内的特殊总线结构互联 像这种阵列机结构又称闭合螺线结构 也是阵列机系统结构中最常见的一种结构形式 4 19 2020 33 阵列机结构 cont 阵列机的处理属于SIMD形式 单指令流多数据流 它最适合作向量数组运算 每个处理单元相当于一个向量数组元素的运算 包括定点和浮点的多种运算操作 对于是阵列机处理单元个数的倍数的向量数组运算尤为合适 如PE 64 则16 32 64 128 256 512 阵列向量数组就很方便地使阵列机发挥最佳效能 4 19 2020 34 阵列机结构 cont 阵列机中PE之间的互联通信是由互联寄存器来实现的 当PE执行互联指令时 由本PE的互联寄存器与相邻PE互联寄存器进行信息交换 4 19 2020 35 阵列机结构 cont 阵列机的操作分公共操作和本地操作 公共操作是指阵列机中的所有PE同时执行的操作 它一般由逻辑控制器来调度 本地操作是每个PE自己的操作 它由PE的指令译码 执行 像指令操作那样 阵列机的存储器有双重变址机构 除了逻辑控制器的公共变址外 还有每个PE自己的单独变址 这样既节省了公共数据和指令所占的存储空间 又增加各PE对存储器数据分配的灵活性 4 19 2020 36 阵列机结构 cont 一般 每个PE都配有状态寄存器 它标志了目前本PE处于活动状态还是处于屏蔽状态 运算结果是否有错 矩阵边缘处于何种连接等等各种状态信息 4 19 2020 37 阵列机算法 举例矩阵问题 矩阵运算是最适合阵列机运行的 如A B两个矩阵相加 只要把A和B居于相应位置的一对分量存放在同一个处理单元存储器内 当阵列机执行加法公共操作时 每个处理单元都将处于本结点的Ai和Bi两个矩阵元素进行加法运算 其和即为矩阵和的对应元素 4 19 2020 38 阵列机算法 cont 累加和问题 书上有详细的举例 请自学 4 19 2020 39 高性能计算机分三大类 PVP向量型超级计算机 如国防科技大学研制的银河I 1亿次 秒 银河II 10亿次 秒 MPP大规模并行处理超级计算机 如国防科技大学研制的银河III 130亿次 秒 中国科学院计算机技术研究所研制的曙光1000 25亿次 秒 中国江南计算机技术研究所研制的神威I 3840亿次 秒 Cluster集群计算机 中国科学院计算机技术研究所研制的曙光2000 II 1100亿次 秒 曙光3000 4030亿次 秒 清华大学研制的THNPSC 1 320亿次 秒 上海大学研制的自强2000 4500亿次 秒 4 19 2020 40 大规模并行处理机 MPP 1979年 美国NASA Goddard中心与Goodyear宇航公司合作研制一台用于处理遥感卫星图片的大规模SIMD阵列机获得成功 由于这台机器用了128 128 16384个可并行工作的微处理机 因此被定名为大规模并行处理机MPP MassivelyParallelProcessor MPP可对变长的操作数按位片进行算术运算 MPP有一个微程序控制器 能够十分灵活地定义向量 标量和I O操作的指令系统 整个MPP系统均用微处理器芯片和SRAM芯片组成 4 19 2020 41 大规模并行处理机 cont 阵列部件ARU ARrayUnit 由128 128个PE构成一个二维阵列 以SIMD方式工作 每个PE有一个1027位SRAM 有奇偶校验功能每个PE是位片式微处理机 与四周近邻相连 程序员可在平面 水平圆柱 垂直圆柱 开螺线 闭螺线等五种阵列拓扑中任选一种 增加了阵列机结构的灵活性 4 19 2020 42 大规模并行处理机 cont 在阵列中增加了4列冗余PE 使阵列的物理结构为132列 128行 阵列硬件出现故障时可旁路掉故障列方法 使阵列逻辑结构仍为128 128 每个PE内有一个串行加法器及用一个移位寄存器实现位串式加法 PE阵列的时钟周期为100ns 阵列控制器ACU是微程序控制器 对PE阵列处理进行管理 完成标量运算以及控制数据在PE阵列上移位 4 19 2020 43 大规模并行处理机 cont 程序和数据管理部件PDMU ProgramandDataManagementUnit 是一台后端小型计算机 其作用是管理阵列中的数据流 将程序装入控制器 进行系统的测试和诊断并提供程序开发手段等 MPP系统运行方式有两种 独立方式由用户在终端予以操作控制 在线方式由外接计算机予以控制 MPP与外接计算机之间的数据传输速率为6MB s 按高速数据方式运行时 数据通过128位外部接口传输 其速率可达320MB s 4 19 2020 44 多处理机的基本结构 常用的松散耦合和紧密耦合这两种形式松散耦合多处理机结构 互联常用通道或通信线路来实现 它们连接的频带较低 紧密耦合多处理机结构 通常是高速总线或高速开关实现机间互联 以共享存储器 4 19 2020 45 多处理机的基本结构 通道连接的多处理机结构 每台计算机是独立的 它们之间通过通道适配器连接 在进行通信时 发送的计算机可以把接受的计算机认为是自己的一个I O设备 从而能完成两个主存储器之间的数据传送 4 19 2020 46 多处理机的基本结构 cont 信息传输系统连接的多处理机结构 计算机模块通过一个信息传输系统连接起来 信息传输系统是耦合程度较低的 常用简单的分时总线及环形 星形等拓扑结构的系统 每个计算机模块可以是独立的计算机 它有处理单元 存储器 I O部件 而模块与信息传输系统则通过通道仲裁开关相连 通道仲裁开关的作用除使要通信的计算机模块与被通信的计算机模块在信息传输系统里连接起来外 还起到多个模块同时申请信息传输系统时 决定本模块是提出申请还是延缓提出申请 故称有仲裁作用 4 19 2020 47 多处理机的基本结构 cont 紧密耦合多处理机结构是真正的MPP 多个处理器通过互联网络 它是由高速开关来组成的 共享集中的主存储器 它由若干个存储模块组成 和多个输入输出设备 当某个处理机要访问主存储器 只需通过它的存储映象部件 MAP 就可以把全局的逻辑地址变换成局部的物理地址 即某一存储模块内的物理地址 互联网络不仅要提供高速的传输通路 而且具有选择有效路径 仲裁访问冲突等功能 对于输入输出设备的访问也与访问存储器一样 只是它们的界面通过输入输出处理机 IOP 来进行 4 19 2020 48 多处理机的互联网络 多处理机的主要特点是各台处理机共享一组存储器和I O设备 这种共享功能是通过两个互联网络实现的 一个是处理机和存储器模块之间的互联网络 另一个是处理机和I O子系统 I O接口和I O设备 之间的互联网络 互联网络可以采用不同的物理形式 一般可有四种基本结构 4 19 2020 49 1 总线结构 多处理机结构最简单互联系统是把所有功能模块 或部件 连接到一条公共通信通路上 如图5 16所示 公共通信通路也称为时分或公共总线 这种总线结构的特点是简单 容易实现 也容易扩展 重构 总线是一个无源部件 通信完全由发送和接收的总线接口控制 由于总线是共享资源 所以必须有总线请求和仲裁的机构 以避免发生总线冲突 4 19 2020 50 1 总线结构 cont 总线仲裁方法有静态的或动态的优先级方法 先进先出 FIFO 队列方法 串行优先链方法和总线控制器 或仲裁器 方法 当一个处理机要占用总线时 首先需测试总线状态是否 忙 busy 若是忙 则等待 等到空闲时 即不 忙 发出总线请求信号 经仲裁后 等到总线响应信号 才可以占用总线 与目的部件进行通信 在一个处理机占用总线进行通信过程中 哪怕比其优先级高的处理机需占用总线 也不能终止 中断 原来已在进行中的通信过程 4 19 2020 51 1 总线结构 cont 单总线结构简易而可靠 但总线接口线路出现任何一个故障会造成系统瘫痪 为了提高总线通信效率 设置在同一时间可进行多条总线通信 但增加了系统的复杂性 影响总线性能的因素有 总线上主控设备 即能掌握 占用总线的部件 数量 总线仲裁算法 控制集中程度 数据宽度 数据传输同步和错误检测等 4 19 2020 52 1 总线结构 cont 总线仲裁算法 静态优先级算法 给每一个设备一个唯一的优先级 固定时间片算法 把带宽分成固定长度的时间片 按循环方式顺序分配给每个设备 动态优先级算法 优先级予以动态调整 使每个设备均有机会占用总线 近期最少使用LRU 算法和旋转菊花链RDC算法 先来先服务算法 按照接受到的请求先后顺序予以处理 4 19 2020 53 2 交叉开关 当不断增加总线数目 使每个存储器模块有它自己单独可用的通路形成的互联网络称为无阻塞交叉开关 它的特点是开关和功能部件的接口非常简单 而且支持所有存储器模块同时通信 每个交叉点不仅能切换并行传播 而且必须能解决在同一存储器周期内访问同一个存储器模块的多个请求之间的冲突 通常用预设的优先级来处理冲突 4 19 2020 54 3 多端口存储器 如果把分布在交叉开关矩阵网络上的控制 转接 优先级仲裁等逻辑功能转移到存储器模块的接口上 就形成了多端口存储器系统 如图5 25所示 这种系统既适合单处理机 也适合于多处理机 4 19 2020 55 3 多端口存储器 cont 对于访问存储器的冲突 常用的解决方法是每个存储器端口分配一个永久优先级 而各个主控模块相对于某个存储器模块有一个优先级别序列 例如对于M0而言 其能接收主控模块的访问优先次序为P0 P1 I O0 I O1 对于M1而言 则为P0 P1 I O1 I O0 对于M3而言 则为P1 P0 I O1 I O0 对于M3而言 则为P1 P0 I O1 I O0 4 19 2020 56 4 多处理机的多级网络 由于开关过于复杂 对于大规模交叉开关用多个小规模交叉开关 串联 和 并联 组成多级交叉开关网络 以取代单级的大规模交叉开关 4 19 2020 57 多级互连网络 目标 完成某结点与其它任一结点的连接 同时完成多对结点的连接 方法 从时间性和空间性方面开发 1 循环互连网络 时间性 组成 DTRin DTRout MUX IN 结构 一个单级ICN MUX 特点 节省了设备 增加了时间 每个MUX可单独控制 4 19 2020 58 2 多级互连网络 空间性 组成 DTRin DTRout 交换开关 拓扑结构 ICN 交换开关 具有传送或播送功能 拓扑结构 不同级开关间连接方式 单级ICN的连接功能 控制方式 级控制 部分级控制 单元控制 DTRin DTRout PE或M 可为同一类型 4 19 2020 59 分类 根据拓扑结构进行分类 多级立方体网络多级混洗交换网络多级PM2I网络 4 19 2020 60 3 多级立方体网络 有STARAN 级控制和部分级控制 和间接二进制n立方体 单元控制 两种网络 以STARAN网络为例介绍 返回35页 返回下页 交换开关 二功能 直通和交换 拓扑结构 第i级为Cubei 为什么只有三级 4 19 2020 61 3 带宽问题 STARAN可同时多对结点连接 尚不能同时任意组合 4 例题 例1 编号0 F的PE间 要实现下列通信配对 7 D 6 C 5 F 4 E 3 9 2 8 1 B 0 A 画出互连网络结构图 写出控制方式级各开关状态 答 因需实现双向交换功能 选择STARAN的交换网络 级控制方式 可满足要求 因共有16个结点 编码需要4位 所以开关共4级 网络结构图如下页 返回下页 4 19 2020 62 转上页 拓扑结构 不同级完成地址不同位取反功能 注意 有交换开关的拓扑结构的实现 4 19 2020 63 4 多级混洗交换网络 网络 交换开关 四功能 允许实现一对多的连接 拓扑结构 不同级相同 均为全混洗结构 控制方式 级控制 部分级控制 单元控制 连接图 第n 1级靠近入端 返回下页 4 19 2020 64 并行存储器无冲突访问 一 访问需求 并行存取向量中各分量信息 可按行 列 对角线等方法存取 步长不一致 二 存在问题 存储器带宽限制 存储器带宽达不到向量带宽 访存方式 步长 不同 产生访存冲突 三 解决方法 1 采用多体交叉存储器 增加MEM带宽 2 对向量分组操作 解决MEM带宽小于向量带宽问题 4 19 2020 65 多处理机系统结构 并行处理机属SIMD结构 较适合向量处理 一 多处理机与并行处理机区别 多处理机属MIMD结构 可进行更高层次的并行处理 1 结构与通用性 SIMD 单指令流系统 并行操作相同 一个CU 控制 数据通讯简单 通用性较差 MIMD 多指令流系统 并行操作不同 多个CU 控制 数据通讯复杂 通用性较强 4 19 2020 66 2 程序并行性 SIMD 操作级并行 数据并行 识别 隐式识别和向量指令 支持 编译程序和硬件 MIMD 任务级并行 数据 功能并行 识别 显式指令 编译程序 OS和硬件等 支持 专用指令 OS对任务的分派和调度 3 任务派生 SIMD 向量指令表示及控制 隐式并行 效率低 MIMD 专用指令表示及控制 显式并行 效率高 4 19 2020 67 三 多处理机结构 1 紧耦合系统 TCS 特点 通过共享主存实现机间通讯 互连网络 实现PE PEM PE I O通道 PE 中断信号间的连接 4 19 2020 68 2 松耦合系统 LCS 特点 通过消息传送系统实现机间通讯 每个模块是一个独立的处理机 整个系统可看成是一个分布系统 互连网络 MTS有总线 环形 多级网络等种类 结构 有层次和非层次两种结构 4 19 2020 69 多处理机系统的存储器结构 在多处理机系统中 为了减少访存冲突 主存采用并行存储器结构 多个存储模块可采用低位交叉编址技术 也可采用高位交叉编址技术 能为某处理机进程放置大多数页面的存储器模块称为该处理机宿主存储器 图5 31所示 如果该处理器的现行进程全部活动页面在宿主存储器内 而且该存储器不包含其他处理机的页面 则处理机不会遇到存储冲突 4 19 2020 70 多处理机系统的存储器结构 cont 多处理机系统中常采用二维存储器结构 如图5 32所示 有n个同样容量的存储模块 排成l列 体 每一列有m个模块组成 各列之间按高位交叉编址 而列内各模块为按低位交叉编址 每列有一个列控制器连到互联网络 4 19 2020 71 多处理机系统的cache结构 当每个处理机都有自己专用的cache时 对应主存中某一个单元的数据 在各个cache中可能会出现相应的多个副本 当对其中某一个副本进行一次修改操作 就会产生cache中数据不一致性 无论cache采用 写回法 或 写直接法 都不能解决多个cache不一致问题 4 19 2020 72 静态一致性校验 只让该进程的独用信息 指令和操作数据 和共享的只读信息进入本处理机的cache 而对于共享的可写 即可修改 的信息不准进入cache 只可留在主存中 这种方法增加了互联网络和主存的竞争 因此 性能较差 减少竞争的方法是增加一个共享cache sc sharedcache 共享信息均在sc内 而取指令和独用数据则通过独用cache pc privatecache 其结构如图5 33所示 4 19 2020 73 动态一致性校验 基本思想是在若干个cache中使同一个信息 指令 数据 始终保持动态一致 一种方法是广播法 即当每个处理机每次写cache时 不仅写入自己的cache和共享的主存中 而且还把信息送到所有cache 如果其他cache有与自己cache相同的目标行 则也进行改写 4 19 2020 74 动态一致性校验 cont 另一种时目录法 在快速ram中构建一个目录表 如图5 34所示 它有两个部分 存在表 presenttable 是二维的 其中每一项P i c 表示第i块是在第c个cache中 修改表 modifiedtable 是一维的 其中每项M i 表示第i块是否被修改过 在每个cache中还有一个本地标志 可在地址变换表中设立 L k c 表示第c个cache中块k的状态 4 19 2020 75 多处理机系统的特点 1 结构灵活性相比并行处理机的专用性 多处理机系统是要把能并行处理的任务 数组 以及标量都进行并行处理 有较强的通用性 因此多处理机系统要能适应更多样化的算法 具有更灵活的结构 以实现各种复杂的机间互联模式 4 19 2020 76 多处理机系统的特点 cont 2 程序并行性在多处理机中 并行性存在于指令外部 即表现在多任务之间 为充分发挥系统通用性的优点 便要利用多种途径 算法 程序语言 编译 操作系统以至指令 硬件等 尽量挖掘各种潜在的并行性 4 19 2020 77 多处理机系统的特点 cont 3 并行任务派生多处理机是多指令流操作方式 一个程序当中就存在多个并发的程序段 需要专门的指令来表示它们的并发关系以及控制它们的并发执行 使一个任务正在执行时就能派生可与它并行执行的另一些任务 4 19 2020 78 多处理机系统的特点 cont 4 进程同步在多处理机系统里 同一时刻 不同的处理机执行不同的指令 由于执行时间互不相等 它们的工作进度不会也不必保持相同 因此当并发程序之间有数据交往或控制依赖时 就要采取特殊的同步措施 使它们包含的指令相互间仍保持程序要求的正确顺序 4 19 2020 79 多处理机系统的特点 cont 5 资源分配和任务调度多处理机执行并发任务 需要处理机的数目没有固定要求 各个处理机进入或退出任务以及所需资源变化的情况都要复杂的多 因此资源分配和任务调度的好坏将直接影响整个系统的效率 4 19 2020 80 算术表达式的并行算法 并行性的开发在算法 顺序处理机习惯采用循环及迭代算法 往往不适合用于多处理机 而采用直解法 有时能揭示更多的并行性 例如下列多项式E1 a bx cx2 dx3利用Horner法则 可得到E1 a x b x c x d 4 19 2020 81 算术表达式的并行算法 cont 这是顺序处理的典型算法 共需三个乘一加循环 六级运算 见图5 37 b 所示 它对于多处理并不合适 而采用前一式算法更加有效 只需四级运算即可 见图5 37 a 所示 图中P为所需处理机数目 Tp为运算级数 Sp为加速度 Sp T1 Tp EP Sp P 可见 Sp 1 即运算的加速总是伴随着效率的降低 4 19 2020 82 算术表达式的并行算法 cont 从算术表达式最直接的形式出发 利用交换律把相同运算集中在一起 再利用结合律把参加运算的操作数 称原子 配对 尽可能并行运算 最后利用分配律 平衡各分支运算的级数 使总级数减至最少 例如某多项式E2 a b c def g h需要7级运算 利用交换律和结合律改写为E2 a h b c g def 则需5级运算 再利用分配律 将上式改写为E2 a h bc bg ddef则仅需4级运算 如图5 38所示 4 19 2020 83 机间互连形式 1 总线形式 时间分配 最常见 PE PEM I O通道均连在总线上 采用分时或多路转换技术实现数据传递 是最简单的连接方式 总线仲裁算法 静态优先级算法 平等算法 动态优先级算法 先来先服务算法等 对外设一般采用优先级算法 对PE采用均等算法 实现方法 集中式 由总线控制器控制 分布式 中机构分散到各PE中 提高总线效率方法 改善传输介质和增加总线数量 总线互连方式不适宜连接过多的处理机 4 19 2020 84 2 交叉开关形式 空间分配 是总线形式的极端 总线数 PE数 PEM数 I O通道数 是一种全相联形式 控制 仲裁 转换机构均在开关中 改进 用一系列较小开关串联或并联 形成多级交叉开关 减少其复杂性 交叉开关方式不适宜连接过多的处理机 3 多端口存储器形式 将控制 仲裁 转换机构移到存储器中 每个端口与一个PE或I O通道相连 多端口存储器形式不适宜连接过多的处理机 4 19 2020 85 4 多级互连网络形式 是介于总线 N 与交叉开关 N2 中间的一种 Nlog2N 对互连网络I与O数不一致时 可采用榕树形网络 多级互连网络适宜于PE数较多的系统 a b交叉开关 a入b出 输入基于a编码 输出基于b编码 入端 出端受阻后 重新申请 性能受建立时间限制 设置缓冲器性能有所改善 适合于包交换网络 an bn互连网络 交叉开关为a b开关 由n级构成 比较 交叉开关时结点数为an bn 多级互连网络时结点数为a b n2 明显降低了复杂性 4 19 2020 86 程序并行性的分析 并行性的关键在算法 研究并行算法及程序设计 一直是多处理机系统的一个重要研究课题 其中相关问题是十分重要和难以解决的问题之一 4 19 2020 87 数据相关举例 假设有一个程序包含P1 P2 P3 Pi pj Pn等多个程序段 取最简单的形式 Pi和Pj都是一条语句 Pi在Pj之前执行 且只讨论Pi和Pj的直接相关关系 一般而言 Pi和Pj之间存在三种可能的数据相关情况 4 19 2020 88 数据相关举例 cont 1 如果Pi的左部变量也在Pj的右部变量集内 且Pj要从Pi取出算出的值 称 Pj数据相关 于Pi 如P1A B CP2C A EP2必须取P1算得的A值作为操作数 4 19 2020 89 数据相关举例 cont 2 如果Pj的左部变量也在Pi的左部变量集内 则称 Pi数据反相关 于Pj 如P1C A EP2A B D在P1未取用A值之前 A的值不能被P2所改变 4 19 2020 90 数据相关举例 cont 3 如果Pi的左部变量也在Pj的左部变量 则称 Pj数据数相关 于Pi 如P1A B DP2A A CP2存入它自己算得的值必须在P1存入之后 4 19 2020 91 3 数据相关避免 主要解决反相关和输出相关 由编译程序自动完成 重命名方法 S A B CT D A EU A A DV IFX 0THENG F A U AA A DV IFX 0THENG F AA 标量扩充方法 fori 1tondoifA i 0thenX B i elseX C i D i X 1 fori 1tondob i A i 0 X i B i whenb i X i C i whennotb i D i X i 1 存在数据相关 反相关 输出相关 控制相关 消除了数据反相关 输出相关 消除反相关 输出相关 4 19 2020 92 二 并行程序设计语言 1 开发方式 语言形成方式 扩充语言功能 重新设计并行语言 对语言的要求 灵活性 效率 程序设计方式 显式 隐式 2 扩展语言中三种并行结构 FORK JOIN 不同机器有不同形式 效果相同 FORKA 派生一个进程 当前进程继续 FORKA J FORKA功能外 地址J计数器 1 FORKA J N FORKA功能外 地址J计数器值为N JOINJ 地址J处计数器减1 当计数器值为零时 启动J 1处进程 否则 结束该进程 释放PE 4 19 2020 93 描述程序并行性的指令 并行程序的执行是一个不断地进行并行性任务的派生和汇合的过程 派生是在一个任务执行的同时 派生出可与它并行的一个或多个任务 分配给不同的处理机完成 这些任务可以是互不相同的 执行时间也不一样 要等它们全部完成以后在汇合起来 进入后继任务 后继任务可以是单任务 也可以是新的并行任务 若是并行任务 则又开始派生和汇合过程 依次类推 直至整个程序结束 4 19 2020 94 派生指令FORK 指令格式 FORKA功能 在遇到FORK指令时 执行该指令的原进程 并根据标记符A派生出该标记符所对应的新进程 即准备好启动新进程或恢复原来进程继续执行时的现场 若共享主存 则应该产生存储器指针 映像函数 访问权等信息 执行FORK指令的原程序 继续在分配给它的处理机上运行 将空闲处理机分配给FORK指令派生的新进程 如果所有处理机均忙 则让新进程进入排队等待 4 19 2020 95 汇合指令JOIN 指令格式 JOINN功能 JOIN指令有一个计数器 其初始值置为零 当执行JOIN指令时 计数器加上1 并与N比较 若比较结果表明计数器值等于N 说明是执行中的第N个进程经过JOIN指令 则允许该进程通过JOIN指令 在其所在处理机上继续执行后继指令 若计数器值小于N 则必须等待N个并行任务中尚未执行 或虽然执行但未结束的进程到达JOIN指令 现在执行JOIN指令的这个进程可以先结束 并把占用的处理机释放出来 分配给排队等待的其他任务 4 19 2020 96 例 3个PE并行处理8 8矩阵乘法 DO10J 0 610FORK20 60 派生处理第0 6列进程 J 7 当前进程处理第7列 20DO40I 0 7 处理0 7行 C I J 0DO30K 0 7 处理C I J 30C I J C I J A I K B K J 40CONTINUEJOIN6060 4 19 2020 97 块结构语言 把可并行执行的进程用cobegin coend括起来处理 最后一条语句执行完成后 方可执行后续语句 该语句可嵌套 可使用共享变量 但不允许修改 4 19 2020 98 parfor语句 parfor语句原语 4 19 2020 99 多处理机的操作系统 高效的多处理机的操作系统是多处理机系统软件的核心相同点是 资源分配和管理 存储器和数据保护 防止系统死锁 异常进程的终结和处理等 高效率地利用资源 合理的进程调度 使输入输出和处理机负载平衡 在出现故障时 使系统重新配置 适度降级运行 以提高系统可靠性 它自动地发掘硬件和运行中程序的并行性 通信方法 同步机构 布局和分配策略对操作系统的性能起决定性作用 4 19 2020 100 1 主从方式操作系统 有一台主处理机进行系统的集中控制 主处理机管理系统中所有处理机状态 并对所有从处理机分配任务 操作系统只运行在主处理机上 它把从处理机视作可调度的资源 从处理机经过自陷 trap 或管理调用指令向主处理机发出请求 主处理机中断当前程序 识别该请求并完成相应任务 由于只有主处理机执行管理程序 所以它不需要也不必考虑再入问题 并且也简化了系统控制表格的冲突和封锁等问题 4 19 2020 101 1 主从方式操作系统 cont 当主处理机出现故障时 整个系统崩溃 需要操作人员干预或重新启动 系统的硬件和软件比较简单 不太灵活 如果主处理机不能很快的为从处理机分配任务 则从处理机可能长时间空闲 系统利用率下降 本方式对工作负载固定 且从处理机能力比主处理机低的系统是适用的 例如异构型多处理机 用本方式操作系统就比较有效 4 19 2020 102 2 单独管理方式操作系统 每个处理机均有一个独立的管理程序 操作系统的内核 在运行 即每一个处理机都有同一个内核的副本为其本身服务 由于处理机之间可交互作用 因此 管理程序的某些代码必须是可重入的或为了给其它处理机提供拷贝而必须重复设置 每个管理程序都有一套自用表格 但仍有一些共享表格 从而带来共享表格访问冲突的问题 使进程调度的复杂性和开销增大 因此实现比较困难 4 19 2020 103 2 单独管理方式操作系统 cont 适应分布处理模块化结构特点 减少对控制专用处理机需求 有较高的可靠性 有较高的系统利用率 每个处理机有其自己的I O设备和文件 因此整个系统的I O结构有变动时 需要人工干预 有几台处理机共同负担整个系统的控制 所以当出现故障时 自动启动一台出故障的处理机相当困难 需要人工干预 4 19 2020 104 3 浮动管理控制方式操作系统 它属于上述两种方式的折衷 主处理机 可以从一台处理机向另一台处理机浮动 主控制程序也可以转移 或者几个处理机同时执行管理程序 担任主处理机时间也不固定 该方式可使各类资源的工作负载比较平衡 通过静态设置或动态控制的优先安排服务请求次序 由于若干台处理机可以同时执行同一个服务程序 因此管理程序的大多数代码必须是可重入的 4 19 2020 105 3 浮动管理控制方式操作系统 cont 由于存在多个管理程序 所以表格访问冲突和表格