第六章 并行处理技术(6.1—6.4).ppt

计算机系统结构 第6章并行处理技术 本章学习要求 理解并行处理机的结构和工作原理 了解并行处理机与流水处理机的差别 熟练掌握基本的单级互连网络及其互连函数表示 理解循环互连网络的实现 熟练掌握多级网络 全排列网络的画法 本章学习要求 了解多处理机的特点及主要技术 掌握并行算法研究思路 程序并行性分析结论 任务的派生和汇合 理解多处理机任务粒度 通信开销对性能的影响 了解多处理机操作系统 并行处理技术 是获取高性能计算的重要手段通过资源的重复设置以实现性能的改善 其发展是没有极限的有双重含义 同时性 Simultaneity 和并发性 Concurrency 6 1并行处理技术的基本概念 并行处理的目的 提高速度对于一个固定规模的问题 采用并行计算技术可以使求解时间更少现在的微型机也开始借助于流水线技术 多核技术等并行计算技术来提高系统的速度 扩大问题求解规模由于器件本身的限制 任何单处理器的速度不能超过某个上限要突破这个上限 必须采用并行计算技术 6 1并行处理技术的基本概念 数据处理过程中可能存在若干个可以同时进行处理的部分 用一个处理部件按时间顺序先后处理它们 称串行处理用若干个处理部件同时处理这些部分 称并行处理并行性概念同时性并发性 6 1并行处理技术的基本概念 并行处理相对于串行处理而言 着重开发计算过程中的并发事件 用并行性粒度G来描述 所有处理器处理时间的总和 所有处理器通信时间的总和 6 1并行处理技术的基本概念 粒度细 表明处理器间通信时间长 粒度粗 表明处理器之间通信量小 性能较好 程序执行过程分个5级别 作业级 任务级 程序级 指令级 指令内操作级 粗粒度级别 细粒度级别 主要由多处理机或多计算机系统实现 开发手段 软件 在单处理机实现 开发手段 硬件 如流水技术 6 1并行处理技术的基本概念 并发性开发的途径有 时间重叠 多个处理过程在时间上错开 重叠使用同一部件 以赢得速度 如指令流水执行方式 资源重复 通过设置多套功能部件 利用空间上的并行性提高指令执行速度资源共享 利用软件的方法 让多个任务在时间上轮流使用一套资源 以提高资源的利用率 6 2SIMD并行计算机 阵列处理机 并行处理机 ParallelProcessor 的一个重要特点是处理机有并列的多个处理单元 每个单元的组成都相同或相似 并行处理机内部有数十 数百甚至更多个处理单元 每个单元可以有自己的运算器 存储器 寄存器组或别的硬件设备 阵列机 ArrayProcessor 作为并行处理机 在差分 乘法 矩阵和向量运算等领域用之甚多 6 2SIMD并行计算机 阵列处理机 阵列机的处理单元被画成 阵列 的样子 处理单元作为这个这个阵列的节点 通过一个环形的网络把节点连接起来了 网络同时也把控制器CU和各节点连接起来 CU通过网络向各个处理单元 广播 共享资源 阵列机属于SIMD 6 2SIMD并行计算机 阵列处理机 阵列处理机由一个控制器 CU N个处理单元 PE M个存储器模块 M 和一个互连网络 IN 组成 由CU控制将指令广播给系统中的各个PE 所有活跃的PE将以同步方式执行相同的指令 单指令流 它们从相应的存储模块中取得自己所需的数据对象 多数据流 ILLIAC IV阵列机处理单元内部方块图 RGA RGB RGR RGS RGX RGM AU LU SU ADA PEM 累加寄存器64b存放第1操作数 操作数寄存器64b存放第2操作数 被乘数寄存器64b兼互连寄存器 通用寄存器64b中间寄存器 PE单元存储器 容量2048 64b访问时间350ns 变址寄存器64bADA的地址修改 MAR MLU 存储器逻辑控制器 模式寄存器8b指示标志位 PEM地址寄存器11b 算术运算器 逻辑运算器 移位运算器 地址加法器 PE DFS ILLIAC说明 ILLIAC IV阵列机 RGA RGB RGR RGS RGX RGM AU LU SU ADA CDC B6700 PEM IOS 标量ALU CUB CDB 64 MBL 64 CU 64 ICL 200 1024总线 2048X64b 13 管理系统资源完成编译汇编进行作业调度 BIOM 阵列控制计算机CU 输入输出系统 阵列PE共64个 PE 变址 16b 模式 8b acc gr dr nr buffer 6 2SIMD并行计算机 阵列处理机 图6 1阵列处理机两种结构 a 分布存储器的阵列机 b 共享存储器的阵列机 6 2SIMD并行计算机 阵列处理机 阵列机的主要特点它采用资源重复方法它是以某一类算法为背景的专用机器阵列机的研究必须以并行算法的研究密切结合从处理单元来看 由于都是相同的 故阵列机是同构的并行处理机 6 4SIMD计算机的互联网络 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络 用来实现计算机系统中结点之间的相互连接 节点 处理器 存储模块或其他设备 互连网络在系统中的位置 如图所示 在拓扑上 互连网络为输入结点到输出结点之间的一组互连或映象 6 4SIMD计算机的互联网络 互连网络在系统中的位置 6 4SIMD计算机的互联网络 可以从4个不同的方面来描述互连网络通信工作方式 有同步和异步两种 同步系统 使用一个统一的时钟 SIMD阵列处理机就属于这一种类型 异步系统 没有统一的时钟 系统中的各个处理机都是独立地工作 控制策略 有集中式和分散式两种集中控制方式 有一个全局的控制器接收所有的通信请求 并由它设置互连网络的开关连接 分散控制方式 不存在全局的控制器 通信请求的处理和开关的设置由互连网络分散地进行 6 4SIMD计算机的互联网络 交换方法 有线路交换和分组交换两种 线路交换 源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接 分组交换 把信息分割成许多组 又称为包 将它们分别送入互连网络 这些数据包可以通过不同的路径传送 到达目的结点后再拼合成原来的数据 结点之间不存在固定连接的物理通路 7 1互连网络的基本概念 拓扑结构 有静态和动态两种 静态拓扑结构 在各结点之间有专用的连接通路 且在运行过程中不能改变 动态拓扑结构 可根据需要设置互连网络中的开关 从而对结点之间的连接通路进行重新组合 实现所要求的通信模式 6 4SIMD计算机的互联网络 SIMD系统互连网络的设计目标 1 结构不要过分复杂 以降低成本 2 互连要灵活 以满足算法和应用的需要 3 处理单元间信息交换所需传送步数要尽可能少 以提高速度性能 4 能用规整单一的基本构件组合而成 或经多次通过或多级连接来实现复杂的互连 使模块性好 以便于VLSI实现并满足系统的可扩展性 6 4SIMD计算机的互联网络 三 互连网络的分类 6 4 2互联函数 互连函数互连函数是反映互连网络连接特性的一组定义 如果把互连网络的N个入端和N个出端 N 2n 各自用0 1 N 1的整数编号表示 则互连函数就是表示互连网络的出端号和入端号的一一对应关系 如入端号的二进制表示为xn 1xn 2 x2x1 则与此入端相连接的出端可用互连函数f xn 1xn 2 x2x1 表示 恒等置换函数 6 4 2互联函数 2 方体 Cube N个节点的立方体单级网络共有n log2N种互连函数 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 K 0 K 1 K 2 6 4 2互联函数 3 全混洗单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 6 4 2互联函数 4 交换单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 6 4 2互联函数 5 蝶式单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 6 4 2互联函数 6 子蝶式单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 K 0 K 1 K 2 6 4 2互联函数 7 移位单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 6 4 2互联函数 8 PM2I单级网络 PM2 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 6 4 2互联函数 8 PM2I单级网络 PM2 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 0 1 2 3 4 5 6 7 6 4 2互联函数 8 PM2I单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 PM2 0 0 1 2 3 4 5 6 7 6 4 2互联函数 8 PM2I单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 PM2 1 0 1 2 3 4 5 6 7 6 4 2互联函数 8 PM2I单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 0 1 2 3 4 5 6 7 PM2 1 6 4 2互联函数 8 PM2I单级网络 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 000 0 PM2 2 0 1 2 3 4 5 6 7 阵列计算机ILLIAC 采用PM2 0和PM2 n 2构成ILLIAC 阵列机的互连网络 6 4 3互联网络分类与结构参数 Fig 6 17互连网络的分类 互连网络通常可以分为两大类 静态互连网络各结点之间有固定的连接通路且在运行中不能改变的网络 动态互连网络由交换开关构成 可按运行程序的要求动态地改变连接状态的网络 下面介绍几种静态互连网络 其中 N表示结点的个数 静态互连网络 6 4 4静态互连网络 静态互联网络的参数 1 结点度 与结点相连接的边 链路或通道 数 表示节点所需要的I O端口数 一个网络的度是这个网络中各结点的度的最大值 结点度反映了网络中结点之间的连接能力 结点度 入度 出度其中入度是进入结点的通道数 出度是从结点出来的通道数 2 距离 网络中两个结点之间的拓扑距离用这两个结点之间相连的最少边数表示 3 网络直径 网络中任意两个结点间距离的最大值 即最远两个结点之间的距离 4 网络规模 指网络中的结点数 表示该网络功能连结部件的多少 5 带宽总和 指网络中各链路的传输带宽的总和 它代表了网络在理想状况下的传输能力 即每个结点的处理器同时与其它直接连接的结点进行通信时的网络传输能力 6 等分 bisection 带宽 当某一网络被切成相等的两半时 沿切口的边数 通道数 的最小值称为通道等分宽度 用b表示 静态互联网络的参数 6 4 4静态互连网络 1 线性阵列一种一维的线性网络 其中N个结点用N 1个链路连成一行 端结点的度 1其余结点的度 2直径 N 1等分宽度b 1 6 4 4静态互连网络 对称结点的度 2双向环的直径 N 2单向环的直径 N 2 环和带弦环环 用一条附加链路将线性阵列的两个端点连接起来而构成 可以单向工作 也可以双向工作 6 4 4静态互连网络 带弦环 增加的链路愈多 结点度愈高 网络直径就愈小 3 循环移数网络 通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成 N 16结点度 7直径 2 6 4 4静态互连网络 全连接网络结点度 15直径最短 为1 6 4 4静态互连网络 树形和星形一棵5层31个结点的二叉树一般说来 一棵k层完全平衡的二叉树有N 2k 1个结点 最大结点度 3直径 2 k 1 星形结点度较高 为N 1 直径较小 是一常数2 可靠性比较差 只要中心结点出故障 整个系统就会瘫痪 6 4 4静态互连网络 6 4 4静态互连网络 胖树形 6 4 4静态互连网络 网格形和环网形网格形一个3 3的网格形网络一般来说 N nk个结点的k维网络的内部结点度是2k 网络直径为k n 1 闭合螺旋 环形网 可看作是直径更短的另一种网格 将环形和网格形组合在一起 并能向高维扩展 沿阵列的每行和每列都有环形连接 一个n n二元环网结点度 4直径 2 n 2 6 4 4静态互连网络 6 4 4静态互连网络 立方体一种二元n维立方体结构一般来说 一个二元n维立方体由N 2n个结点组成 它们分布在n维上 每维有两个结点 例8个结点的3维立方体4维立方体为实现一个n维立方体 只要把两个 n 1 维立方体中相对应的结点用链路连接起来即可 共需要2n 1条链路 n维立方体中结点的度都是n 直径也是n 6 4 4静态互连网络 6 4 5动态互联网络 1 动态互连网络的三个参量由交换开关构成 可按运行程序的要求动态地改变连接状态的网络 动态互连网络用三个参量来描述 1 交叉开关 2 连接模式 或拓扑结构 3 控制方式 6 4 5动态互联网络 1 交叉开关交叉开关是一种有源的开关元件 它可根据控制信号 工作在各种不同的状态 实现输入端和输出端的不同连接 常用的交叉开关有2 2 4 4 8 8 2 2交叉开关的4种工作状态直连交换上播下播 a 直连 b 交叉 c 上播 c 下播 6 4 5动态互联网络 2 连接模式也称网络拓扑结构 它是多级互连网络的各级开关之间链路的连接模式 连接模式实现的互连函数不同 就构成各种不同的互连网络 3 控制方式 指网络中各级开关的控制方式 级控方式 同一级开关用一个信号来控制 所有开关都处于一种工作状态单元控制 每一个开关都有单独的控制信号部分级控方式 用i 1个控制信号来控制第i级的所有开关 其中 0 i n 1 单级混洗 交换网络n 3的混洗网络拓扑形状如下图绿线所示 可以看出它不是一个连通图 所以还需要增加一个交换函数 Cube0 图中红线所示 才能构成完整的单级混洗 交换网络 8个处理单元的混洗交换互连网络连接图 6 4 5动态互联网络 该网络由PM2I函数定义 PM2I函数共有n对成员 分别是PM2 0 PM2 1 PM2 n 1 PM2I函数定义 PM2 i的功能是对入端结点编号加或减2i 然后再作模N运算PM2 i j j 2imodNPM2 i j j 2imodN其中j 0 N 1 i 0 n 1 例如 当N 8时 PM2 0 0 0 20 1 PM2 0 1 1 20 2 PM2 0 7 7 20 0 PM2 1 0 0 21 2 N 8的PM2 1 j 函数开关状态如右图所示 其连接规律是把各入端结点编号加上相同的增量21 modN 获得出端结点编号 2 单级加减2i网 PM2I网 移数网 N 8的PM2 i网络拓扑形状如下图所示 可以看出它包含多个强连通子图 即除去若干边以后仍能保证任何一对结点互相可达 所以这2n个函数并不是实现互连网的最小集合 实际应用中为了降低造价 人们往往取它们的一个子集来构造互连网 性质1 对相同的i值 PM2 i与PM2 i函数的传送路径相同 方向相反 右图中所有箭头反向即为PM2 1的拓扑形状 性质2 PM2 n 1 PM2 n 1 根据性质2 我们知道单级PM2I网络实际上只能实现2n 1种不同的置换 2 单级加减2i网 PM2I网 移数网 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 PM2 0互连循环函数 01234567 及连接图 PM2 1互连循环函数 0246 1357 及连接图 PM2 2互连循环函数 04 15 26 37 及连接图 6 4 5动态互联网络 3 多级互联网络 交叉开关是一种单级互联网络 输入端的数据经过一个开关元件就被输出 这种网络的设备量较大 解决的办法是采用多级网络 即用多个开关元件构成多级的开关阵列 降低互联网络的成本 在MIMD和SIMD计算机都使用多级互连网络 相邻各级开关之间都有固定的级间连接 如图 6 4 5动态互联网络 3 基本的多级互连网络 1 多级立方体网络 STARAN网络 间接二进制n方体网络 交换网络 移数网络 2 多级混洗交换网络 omega网络或 网络 3 基准网络 4 全排列网络 6 4 5动态互联网络 1 STARRAN网络 2 间接二进制n方体网络共同点 第i级交换开关处于交换状态时 实现的是Ci互连函数 且都采用二功能交换开关 即直连和交换 差别 STARAN网络采用级控制 称交换网络 和部分级控制 其中可实现移数功能的称移数网络 而间接二进制n方体网络采用单元控制 6 4 5动态互联网络 1 STARAN网络STARAN网络的特点 网络规模 N个节点的网络由n log2N级构成 每级开关的编号从输入端到输出端依次为K0 K1 Kn 1 每级的交换开关数为N 2个 每个开关都是2功能的 即直连和交换 拓扑结构 N个节点的网络共有n 1级拓扑结构 其编号从输入端到输出端依次为C0 C1 Cn C0为恒等置换 C1 Cn为逆混洗置换STARAN网络的控制方式 级控制和部分级控制STARAN网络的典型应用 交换网络和移数网络 6 4 5动态互联网络 1 STARAN网络 交换网络 STARAN网络用作交换网络时 采用级控制方式工作 实现的是交换函数的功能 交换函数是将一组元素首尾对称地进行交换 A B C D E F G H I J K L 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 C0 C1 C2 C3 K0 K1 K2 表6 1三级STARAN交换网络实现的入出端连接及所执行的交换函数功能 ki为第i级控制信号 除F 000 实现恒等置换外 其他7种实现分组交换置换 如F 101 实现的置换可表示为 01234567 01 23 45 67 10 32 54 76 1032 5476 2301 6745 23016745 54761032 入端排列 分成4组 每组二元交换 分成二组 每组四元交换 分成一组 每组八元交换 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 01234567 F 000 F 001 F 010 F 011 F 100 F 101 F 110 F 111 可以发现 F f2f1f0 001的交换置换就是Cube0置换 F f2f1f0 010的交换置换就是Cube1置换 F f2f1f0 100的交换置换就是Cube2置换 也就是说 fi实现Cubei置换 例如 当F f2f1f0 011 3级STARAN网络实现的交换置换为 E X2X1X0 Cube1 Cube0 X2X1X0 X2X1X0记为Cube0 Cube1 6 4 5动态互联网络 1 STARAN网络 移数网络 当STARAN网络采用部分级控制时 实现的是移数函数的功能 故称为移数网络 表6 2三级移数网络能实现的入出端连接及移数函数功能 6 4 5动态互联网络 2 间接二进制n方体网络网络规模 N个节点的网络由n log2N级构成 每级开关的编号从输入端到输出端依次为K0 K1 Kn 1 每级的交换开关数为N 2个 每个开关都是2功能的 直连和交换 拓扑结构 N个节点的网络共有n 1级拓扑结构 其编号从输入端到输出端依次为C0 C1 Cn C0为恒等置换 C1 Cn 1为子蝶式置换 Cn为逆混洗置换控制方式 单元控制典型应用 交换置换 移数置换等 6 4 5动态互联网络 2 间接二进制n方体网络的拓扑结构 A B C D E F G H I J K L 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 C0 C1 C2 C3 K0 K1 K2 6 4 5动态互联网络 2 多级混洗交换网络 omega网络或 网络 网络规模 N个节点的网络由n log2N级构成 每级开关的编号从输入端到输出端依次为Kn 1 Kn 2 K0 每级的交换开关数为N 2个 每个交换开关都是4功能的 即直连 交换 上播和下播 拓扑结构 N个节点的网络共有n 1级拓扑结构 其编号从输入端到输出端依次为Cn Cn 1 C0 C0为恒等置换 C1 Cn为全混洗置换 控制方式 单元控制典型应用 恒等置换 移数置换等各种函数的变形置换 可完成数组按行 列 对角线 子块等无冲突访问 6 4 5动态互联网络 2 多级混洗交换网络 omega网络或 网络 A B C D E F G H I J K L 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 C3 C2 C1 C0 K2 K1 K0 N 8个节点的 网络的拓扑结构 6 4 5动态互联网络 2 多级混洗交换网络 omega网络或 网络 网络的寻径算法 设网络输入端地址编号为S sn 1sn 2 s1s0 输出端地址编号为D dn 1dn 2 d1d0 从输入端开始 每一级开关状态由终端地址所对应位控制 若终端地址某位为0 则对应级上开关的输入端与上输出端相连 若某位为1 则对应级上开关的输入与下输出端相连 6 4 5动态互联网络 A B C D E F G H I J K L 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 C3 C2 C1 C0 K2 K1 K0 2 多级混洗交换网络 omega网络或 网络 6 4 5动态互联网络 3 基准网络网络规模 N个节点的网络由n log2N级构成 每级开关的编号从输入端到输出端依次为K0 K1 Kn 1 每级的交换开关数为N 2个 每个开关都是2功能的 直连和交换 拓扑结构 N个节点的网络共有n 1级拓扑结构 其编号从输入端到输出端依次为C0 C1 Cn C0和Cn为恒等置换 C1为逆混洗置换 C2 Cn 1为子逆混洗置换 控制方式 单元控制 可采用终端地址标记的寻径算法典型应用 6 4 5动态互联网络 3 基准网络 A B C D E F G H I J K L 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 N 8的基准网络的拓扑结构 6 4 5动态互联网络 4 全排列网络 课堂练习题1 编号为0 1 15的16个处理器用单级互连网络互连 当互连函数分别为 Cube3PM2 3PM2 0ShuffleShuffle Shuffle 时 第13号处理器各连至哪一个处理器 分析 编号为0 1 15的16个处理器 其号可用4位二进制码P3P2P1P0表示 第13号处理器二进制编号为1101Cube3实现将处理器号为P3P2P1P0与处理器号为P3P2P1P0的数据进行交换 PM2 3实现将j号处理器数据送至第 j 23mod16 处理器上 PM2 0实现将j号处理器数据送至第 j 20mod16 处理器上 Shuffle实现将处理器号为P3P2P1P0的信息送至处理器号为P2P1P0P3的处理器上 Shuffle Shuffle 实现将处理器号为P3P2P1P0的信息送至处理器号为P1P0P3P2的处理器上 解答 1 第1101处理器连至0101处理器号上 即第5号处理器上 2 第13号处理器数据送至第 13 23mod16 处理器上 即第5号处理器上 3 第13号处理器数据送至第 13 20mod16 处理器上 即第12号处理器上 4 第1101处理器连至1011处