第六章 并行处理机.ppt

1 第六章并行处理机 2 并行处理机 并行处理机 ParallelProcessor 也称为阵列处理机 ArrayProcessor 通过重复设置大量相同的处理单元PE ProcessingElement 将它们按一定方式互连成阵列 在单一控制部件CU ControlUnit 控制下 对各自所分配的不同数据并行执行同一组指令规定的操作 操作级并行的SIMD计算机 3 6 1并行处理机的结构和特点 并行处理机按存储器的分布方式可分为两类 分布式存储器结构各PE均有局部存储器PEMi 集中式共享存储器结构各PE无局部存储器PEMi 均通过互连网络共享主存 并行处理机的特点 通过资源重复 解决向量 阵列类的计算问题 体现了并行性中的同时性 缺点是专用性强 处理单元的时间利用率低 系统造价较高 但提高速度的潜力大 并行处理机的实际速度还要受标量运算的影响 4 分布式存储器结构 5 集中式共享存储器结构 6 6 2SIMD计算机的互连网络 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络 用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接 在SIMD计算机中 处理单元与处理单元或存储分体之间要通过互连网络进行信息交换 7 互连网络的作用 用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接 互连网络已成为并行处理系统的核心组成部分 互连网络对整个计算机系统的性能价格比有着决定性的影响 8 具有本地存储器 私有高速缓存 共享存储器和共享外围设备的一般处理机系统的互连结构 9 互连网络的特性 互连网络通常是用有向边或无向边连接有限个结点的组成互连网络的主要特性有 网络规模 网络中结点的个数结点度 与结点相连接的边数称为结点度 包括入度和出度 进入结点的边数叫入度 从结点出来的边数则叫出度距离 两个结点之间相连的最少边数网络直径 网络中任意两个结点间距离的最大值 用结点间的连接边数表示结点间的线长 两个结点间连线的长度 用米 公里等表示对称性 从任何结点看到拓扑结构都是一样的网络称为对称网络 对称网络比较易实现 编程也较容易 10 互连网络在传输方面的主要性能参数 频带宽度 Bandwidth 互连网络传输信息的最大速率 传输时间 Transmissiontime 消息长度 频宽飞行时间 Timeofflight 第一位信息到达接收方所花费的时间 发送方开销 Senderoverhead 处理器把消息放到互连网络的时间 接收方开销 Receiveroverhead 处理器把消息从网络取出来的时间 一个消息的总时延可以用下面公式表示 总时延 发送方开销 飞行时间 消息长度 频宽 接收方开销 11 例题假设一个网络的频宽为10Mb S 发送方开销为230us 接收方开销为270us 如果两台机器相距100米 现在要发送一个1000字节的消息给另一台机器 试计算总时延 如果两台机器相距1000公里 那么总时延为多大 解 光的速度为299792 5KM S 信号在导体中传递速度大约是光速的50 相距100米时总时延为 12 相距1000公里时的总时延为 13 互连网络的表示方法 1 互连函数表示法 为反映互连网络的连接特征 常用函数的形式进行描述 称为互连函数 它反映的是从输入端到输出端的映象关系 设用x表示具有N个输入端的网络输入序号 则输出端的序号用函数f x 表示 设x是一个n位的二进制数 即x bn 1bn 2 b1b0 其中n log2N 则f x 因函数的不同 而有不同的表达式 例如 交换互连函数f x f bn 1bn 2 b1b0 bn 1bn 2 b1b0全混洗互连函数f x f bn 1bn 2 b1b0 bn 2 b1b0bn 1 14 互连网络的表示方法 2 输入输出对应表示法 3 循环函数表示法 15 互联函数的表示方式 续 4 图形法 星型网络结构 16 基本的单级互连网络 恒等置换交换置换立方体置换PM2I置换换洗交换网络蝶形互连函数ILLIAC网 17 恒等置换 也称为直通互连 是指输出端与相同序号的输入端对应连接 其互连函数为 f x f bn 1bn 2 b1b0 bn 1bn 2 b1b0其示意如下所示 左边表示输入端 右边表示输出端 18 交换置换 交换置换 Exchange 实现输入端与地址中某一位取反的输出端连接 Exchange bn 1bn 2 b1b0 bn 1bn 2 b1b0 01234567 01234567 19 立方体置换 如果设N 8 则n log2N 3 其互连关系在空间表示一个立方体 如右图所示 立方体 Cube 互连函数 Cube0 b2b1b0 b2b1b0Cube1 b2b1b0 b2b1b0Cube2 b2b1b0 b2b1b0 20 21 Cube交换互连示意图 22 PM2I置换 共有2n个互连函数 PM2 i j j 2imodNPM2 i j j 2imodN网络直径为 23 PM2I单级网络 续 当N 8时 有n log2N 2n 6个互联函数PM2 0 01234567 PM2 0 76543210 PM2 1 0246 1357 PM2 1 6420 7531 PM2 2 04 15 26 37 PM2 2 40 51 62 73 24 PM2I单级网络 续 25 混洗交换单级网络 包含两个函数 混洗 交换shuffle pn 1pn 2 p1p0 pn 2 p1p0pn 1网络直径为2n 1 26 混洗Shuffle 27 N 8时全混交换互连网络连接图 1 2 3 4 5 6 7 0 28 蝶形单级网络 互连函数Butterfly pn 1pn 2 p1p0 p0pn 2 p1pn 1即将二进制的最高位和最低位相互交换位置 29 30 31 ILLIAC网 32 特点 闭合螺线阵列任意单元的最短距离不超过7步一般来讲 个处理单元组成的阵列中 任意两个处理单元之间的最短距离不会超过步ILLIAC网相当于度为4的环 33 多级互联网络 能够实现结点到结点之间的任意互连是互连网络的一种基本功能 多级互连网络采用多个相同的或不同的互连网络直接连接起来 属于组合逻辑线路 一个时钟周期就能够实现任意结点到结点之间的互连 多级互连网络采用的关键技术 交换开关交换开关之间的拓扑连接对交换开关的不同控制方式 34 交换开关 一个a b交换开关有a个输入和b个输出 最常用的二元开关 a b 2 每个输入可与一个或多个输出相连 但是在输出端必须避免发生冲突 一对一和一对多映射是容许的 但不容许有多对一映射 只容许一对一映射时称为置换连接 称这种开关为n n交叉开关 具有直通和交换两种功能的交换开关称为二功能开关 用一位控制信号控制 具有所有四种功能的交换开关称为四功能开关 用两位控制信号控制 35 36 拓扑结构 前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构 通常采用前面介绍的互连函数实现拓扑结构实际上 从结点的输出到第一级交换开关的输入 以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接 37 控制方式 对各个交换开关进行控制的方式通常有三种控制方式级控制 同一级交换开关使用同一个控制信号控制 单元级控制 每个交换开关分别控制 部分级控制 例如 第i级使用i 1个控制信号控制 38 1 多级立方体网络 采用二功能开关 直连 交换 第i级交换单元处于交换状态时 实现的是Cubei互连函数 采用三种不同的控制方式 可以构成三种不同的互连网络 采用级控制可以构成STARAN交换网 采用部分级控制 可以构成STARAN移数网 采用单元控制可以构成间接二进制n方体网 39 40 2 多级混洗交换网络 又称omega网交换开关 四功能 允许实现一对多的连接 拓扑结构 不同级相同 均为全混洗结构 控制方式 级控制 部分级控制 单元控制连接图 第n 1级靠近入端 41 42 3 多级PM2I网络 包含n级的PM2I网络 第i级的每个入单元j都有3根连线分别通往j j 2imodN和j 2imodN可转化为强化数据交换网络 AugmentedDataManipulator 控制线多 成本较高 43 多级PM2I网络 三级PM2I互连网络 44 全排列网络 定义 所有入端 出端的连接均不发生冲突的网络 又称非阻塞型网络 即 N入 N出有N 种排列 互连网络要求 全排列网络 非阻塞型网络 非阻塞型网络 Non BlockingNetwork 灵活性好 连线多 控制复杂 成本高STARAN omega等网络属于阻塞型网络 阻塞型网络 BlockingNetwork 同时实现两对或多对入端与出端之间连接时 都有可能因争用数据传送路径而发生冲突 45 6 3共享主存构形阵列处理机中并行存储器的无冲突访问 访问需求并行存取向量中各分量信息 可按行 列 对角线等方法存取 步长不一致 存在问题存储器带宽限制 存储器带宽达不到向量带宽 访存方式 步长 不同 产生访存冲突 46 传统模m 取2的整数次幂 的访存储冲突问题 1 一维数组 连续访问m 4个元素访问 无冲突按2变址 冲突 存储器实际频宽降低一半解决方案 M应取质数 避免冲突 只要变址跳距与m互质 47 2 n n二维数组方阵 同时访问某一行 主对角线或次对角线上的所有元素 无冲突同时访问某一列 冲突 降低成1 4 48 错位存放 m为大于每次访问的元素数n的一个质数 二维数组各元素在行 列上分别错开一定的体号来存放 原则 质数m 22P 1则二维数组同一列上相邻各元素错开体号距离 1 2P二维数组同一行上相邻各元素错开体号距离 2