中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 静态互连网络(1) 维线性阵列(1- D Linear Array): 并行机中最简单、最基本的互连方式, 每个节点只与其左、右近邻相连,也叫二近邻连接, N个节点用N-1条边串接之,内节点度为2,直径为N-1,对剖 宽度为1 ■当首、尾节点相连时可构成循环移位器,在拓扑结构上等同于 环,环可以是单向的或双向的,其节点度恒为2,直径或为 (双向环)或为N-1(单向环),对剖宽度为2 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 11 2021/2/19 静态互连网络（1） ▪ 一维线性阵列（1-D Linear Array）： ▪ 并行机中最简单、最基本的互连方式， ▪ 每个节点只与其左、右近邻相连，也叫二近邻连接， ▪ N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖 宽度为1 ▪ 当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于 环，环可以是单向的或双向的，其节点度恒为2，直径或为 （双向环）或为N-1（单向环），对剖宽度为2 N / 2
中国料学火计算机科学与波术系 niversity of Science and Technology of China D三PAT三NT口F 静态互连网绉(2) √N×√N二维网孔(2- D Mesh) 每个节点只与其上、下、左、右的近邻相连(边界节点除外), 节点度为4,网络直径为2N-),对剖宽度为 ■在垂直方向上带环绕,水平方向呈蛇状,就变成Iiac网孔了, 节点度恒为4,网络直径为-1,而对剖宽度为2N ■垂直和水平方向均带环绕,则变成了2-D环绕(2- D Torus) 节点度恒为4,网络直径为2N2,对剖宽度为2N () (a)2-D网孔 (b) Illiac网孔 (c)2-D环绕 国家高性能计算中心(合肥 2021/2/19 12
国家高性能计算中心（合肥） 12 2021/2/19 静态互连网络（2） ▪ 二维网孔（2-D Mesh）： ▪ 每个节点只与其上、下、左、右的近邻相连（边界节点除外）， 节点度为4，网络直径为 ，对剖宽度为 ▪ 在垂直方向上带环绕，水平方向呈蛇状，就变成Illiac网孔了， 节点度恒为4，网络直径为 ，而对剖宽度为 ▪ 垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus）， 节点度恒为4，网络直径为 ，对剖宽度为 2( N −1) N N −1 2 N 2 N / 2 2 N N N (a)2-D网孔 (b)Illiac网孔 (c)2-D环绕
中国料学火计算机科学与波术系 niversity of Science and Technology of China 静态互连网络(3) 二叉树: 除了根、叶节点,每个内节点只与其父节点和两个子节点相连。 节点度为3,对剖宽度为1,而树的直径为2ngM1-1) 如果尽量增大节点度为,则直径缩小为2,此时就变成了星形 网络,其对剖宽度为LN2」 传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通 路自叶向根逐渐变宽。 (a)二叉树 (b)星形连接 (c)二叉胖树 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 13 2021/2/19 静态互连网络（3） ▪ 二叉树： ▪ 除了根、叶节点，每个内节点只与其父节点和两个子节点相连。 ▪ 节点度为3，对剖宽度为1，而树的直径为 ▪ 如果尽量增大节点度为，则直径缩小为2，此时就变成了星形 网络，其对剖宽度为 ▪ 传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通 路自叶向根逐渐变宽。 2(log N −1) N / 2 (a)二叉树 (b)星形连接 (c)二叉胖树
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 静态互连网络(4) 超立方: 一个立方由N=2”个顶点组成,3-立方如图(a)所示;4立 方如图(b)所示,由两个3-立方的对应顶点连接而成。 n-立方的节点度为n,网络直径也是n,而对剖宽度为N2 如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示 的3-立方环,此时每个顶点的度为3,而不像超立方那样节点 度为n。 (a)3立方 (c)顶点代之以环 (d)3-立方环 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 14 2021/2/19 静态互连网络（4） ▪ 超立方 ： ▪ 一个n-立方由 个顶点组成，3-立方如图(a)所示；4-立 方如图(b)所示，由两个3-立方的对应顶点连接而成。 ▪ n-立方的节点度为n，网络直径也是n ，而对剖宽度为 。 ▪ 如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示 的3-立方环，此时每个顶点的度为3，而不像超立方那样节点 度为n。 n N = 2 N / 2 (a)3-立方 (b)4-立方 (c)顶点代之以环 (d)3-立方环
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 嵌 将网络中的各节点映射到另一个网络中去 用膨胀( Dilation)系数来描述嵌入的质量,它是指被 嵌入网络中的一条链路在所要嵌入的网络中对应所需的 最大链路数 如果该系数为1,则称为完美嵌入。 环网可完美嵌入到2-b环绕网中 超立方网可完美嵌入到2-D环绕网中 国家高性能计算中心(合肥 2021/2/19 15
国家高性能计算中心（合肥） 15 2021/2/19 嵌入 ▪ 将网络中的各节点映射到另一个网络中去 ▪ 用膨胀（Dilation）系数来描述嵌入的质量，它是指被 嵌入网络中的一条链路在所要嵌入的网络中对应所需的 最大链路数 ▪ 如果该系数为1，则称为完美嵌入。 ▪ 环网可完美嵌入到2-D环绕网中 ▪ 超立方网可完美嵌入到2－D环绕网中