第三章并行计算机系统互连.ppt

在各种并行计算机中 无论它是集中式 还是分布式多机系统 系统内部的处理器 存储模块以及磁盘阵列都需要网络将它们连接在一起 回顾上节课 问题 存储器主要有哪几种类型 各处理器如何与其互连 在各种并行计算机中 对于系统内部的处理器 如何将并行计算机中的处理器连接起来 处理器及I O设备如何通过网络访问共享存储器的各个存储模块 在并行计算机系统中采用的互连技术有 一 静态网络 StaticNetworks 指处理单元 功能部件 间有着固定连接的一类网络 在程序执行期间 这种点到点的链接保持不变 静态网络常用来实现集中式系统的子系统之间或分布式系统的多个计算节点之间的固定连接 二 动态网络 DynamicNetworks 在程序运行期间 可实时地重新组建网络连接的网络 它们常用于共享存储型多处理机中 一个处理器的静态组织方式可用一个图来表示图中的一个节点表示一个处理器边表示连接该边两端的处理器的通信路径 G V E V是节点 处理器 的有限集 E是节点间的边 通信路径 的有限集 定义1 网络中任意两节点间最短路径的最大值称为网络的直径 diameterofanetwork 直径越小越好 说明网络中任意两节点间的通信时间越少 它被用来确定并行算法的通信下限 定义2 当网络被切为相等的两半时 切口处的最少边数称为等分宽度 bisectionwidth对剖宽度 等分宽度越大 说明网络布线密度越大 通信的复杂性越小 它为消息传递量提供了下限值 平分宽度 2 直径 4 定义3 与节点连接的边数称为节点度 nodedegree 网络中各节点的节点度最好为一个常量 而不依赖于网络的大小 这样是因为处理器组织规模更容易扩大 定义4 如果从任意节点看网络都一样 则称网络为对称的 Symmetry 节点度 2该网络是对称的 1 网格网络 meshnetwork 该网络中的节点呈现为一个n维网格阵列 每个相邻节点才允许通信 2维网格是最常用的 一 静态互连网络 2维网格网络是并行机常用的一种结构 2维网格网络有很多变形情况 一 静态互连网络 2 二叉树网络 binarytreenetwork 该网络是由2k 1个节点组成的一个高度为k 1的完全二叉树 3 胖树网络 fattreenetwork 胖树的通道宽度从叶节点往根节点上行方向逐渐变宽 主处理器节点 4 超立方体网络 该网络可用递归方法来定义 Hypercubenetwork cube connectednetwork 5 带环立方体网络 Cube connectedcyclesnetwork 它是超立方体网络的一种变形 对k维超立方体做下列改变 将k维超立方体的每个节点由一个具有k个节点的环来代替 且环上的每个节点分别连接到超立方体各个维上 带环3维超立方体 6 金字塔网络 pyramidnetwork 它是树和2维网格的结合从每层看 它是一个2维网格从侧面看 它是一棵树 这是一棵高为2的金字塔网络 7 蝶式网络 butterflynetwork 设网络有k 1行 每行有2k个节点从0到k标记行号 从0到2k 1标记列号第 i j 节点 i 0 与两个节点相连 i j 与 i 1 j 相连 i j 与 i 1 m 相连 其中m为j表示的二进制数中第i位取反的值 K 3 001 001 000 001 000 101 与 8 混洗 交换网络 shuffle exchangenetwork 该网络包含n 2k个节点 分别标记为0 1 n 1有两种连接 交换链和混洗链 有向链 交换链 连接两个最低位 节点以二进制形式表示 不同的节点混洗链 从节点i到节点2 imod n 1 的连接 9 deBruijin网络该网络包含n 2k个节点 分别标记为0 1 n 1节点i 以二进制形式表示 通过两个有向边与其他节点 或自己 相连 指向把二进制形式表示的节点编号i的最左位移去后 右边补0得到的节点编号 指向把二进制形式表示的节点编号i的最左位移去后 右边补1得到的节点编号 二 动态互连网络 为了达到多用或通用的目的 有些系统需要采用动态互连网络 它能根据应用程序要求实现某种通信模式 动态互连网络不用固定连接 而是沿着连接通路使用开关 仲裁器以提供动态连接 常用的动态互连网络有 1 总线网络2 交叉开关网络3 多级互连网络 1 总线网络 busnetwork 总线 bus 在计算机系统内 用于连接各种功能部件 如 处理器 存储模块和I O设备等 并使它们之间构成信息传输的一条或多条公用线路 总线网络 在这种网络结构下 所有的处理器都并行地连接到公用总线上 这些入网节点都在时刻监视着总线上的活动 在任一节点上发出的信息都能同时被网络中所有其他节点检测到 但只有被访问节点才能接收此信息 总线只用于源 主部件 和目的 从部件 之间一回处理一次业务 在多个请求情况下 总线仲裁器根据请求的时机和它们的优先级别 决定哪个部件拥有总线控制权 一种总线连接的多处理机系统 2 交叉开关网络 crossbarswitchnetwork 它是一种具有多个纵向通路和横向通路的互连网络 其任一纵向通路可以与任一横向通路连接 通常用于多处理机系统 实现多台处理器 多个内存模块和多台I O设备之间的互连 交叉开关网络使处理器 I O设备能并行存取内存模块 因而信息传输的频带较宽 系统的效率较高 交叉开关网络也可看成是总线数目增多的一种极端情况 即总线数等于行相连的模块数在交叉开关网络中 每个输入可与一个或多个输出相连 但在输出端必须避免发生冲突在只允许一对一映射时 一个n n交叉开关网络可实现n 个不同的连接 映射 当n很大时 这种网络的结构十分复杂 成本也很大 3 多级互连网络 multistageinterconnectionnetwork