静态互连网络与动态互连网络 *静态互连网络 米 处理单元间有着固定连接的一类网络，在程序执行期间， 这种点到点的链接保持不变 米 典型的静态网络有一维线性阵列、二维网孔、树连接、超 立方网络、立方环、洗牌交换网、蝶形网络等 *动态网络 *用交换开关构成的，可按应用程序的要求动态地改变连接 组态 *典型的动态网络包括总线、交叉开关和多级互连网络等。 18 2021/9/1
* 静态互连⽹络 * 处理单元间有着固定连接的⼀类⽹络，在程序执⾏期间， 这种点到点的链接保持不变 * 典型的静态⽹络有⼀维线性阵列、⼆维⽹孔、树连接、超 立⽅⽹络、立⽅环、洗牌交换⽹、蝶形⽹络等 * 动态⽹络 * 用交换开关构成的，可按应用程序的要求动态地改变连接 组态 * 典型的动态⽹络包括总线、交叉开关和多级互连⽹络等。 18 2021/9/1 静态互连网络 与动态互连网络
静态互连网络（1) *一维线性阵列（1-D Linear Array): * 并行机中最简单、最基本的互连方式， *每个节点只与其左、右近邻相连，也叫二近邻连接， *N个节点用N-1条边串接之，内节点度为2，直径为N-1,对 剖宽度为1 * 当首、尾节点相连时可构成循环移位器，在拓扑结构上等 同于环，环可以是单向的或双向的，其节点度恒为2，直 径或为N2(双向环)或为N-1（单向环)，对剖宽度为2 19 2021/9/1
* ⼀维线性阵列（1-D Linear Array）： * 并⾏机中最简单、最基本的互连⽅式， * 每个节点只与其左、右近邻相连，也叫⼆近邻连接， * N个节点用N-1条边串接之，内节点度为2，直径为N-1，对 剖宽度为1 * 当首、尾节点相连时可构成循环移位器，在拓扑结构上等 同于环，环可以是单向的或双向的，其节点度恒为2，直 径或为 （双向环）或为N-1（单向环），对剖宽度为2 19 2021/9/1 静态互连网络（1） ëN / 2û ……
静态互连网络(2) √Wx√W二维网孔(2-D Mesh) * 每个节点只与其上、下、左、右的近邻相连（边界节点除 外)，节点度为4，网络直径为2(N-),对剖宽度为N * 在垂直方向上带环绕，水平方向呈蛇状，就变成，lac网孔 了，节点度恒为4，网络直径为-1，而对剖宽度为2N * 垂直和水平方向均带环绕，则变成了2-D环绕(2-D Torus), 节点度恒为4，网络直径为2/2，对剖宽度为2N (a)2-D网孔 (b)I2biac网孔 (c)2-D环绕 2021/9/1
* ⼆维⽹孔（2-D Mesh）： * 每个节点只与其上、下、左、右的近邻相连（边界节点除 外），节点度为4，⽹络直径为 ，对剖宽度为 * 在垂直⽅向上带环绕，⽔平⽅向呈蛇状，就变成Illiac⽹孔 了，节点度恒为4，⽹络直径为 ，⽽对剖宽度为 * 垂直和⽔平⽅向均带环绕，则变成了2-D环绕（2-D Torus）， 节点度恒为4，⽹络直径为 ，对剖宽度为 20 2021/9/1 静态互连网络（2） 2( N -1) N N -1 2 N 2ë N / 2û 2 N N ´ N (a)2-D网孔 (b)Illiac网孔 (c)2-D环绕
静态互连网络(3) 二叉树： 除了根、叶节点，每个内节点只与 其父节点和两个子节点相连。 *节点度为3，对剖宽度为1，而树的 直径为21ogN1-) 《《。对 *如果尽量增大节点度为N1,则直径 (a)二叉树 (6)星形连接 缩小为2，此时就变成了星形网络， 其对剖宽度为LN12] *传统二叉树的主要问题是根易成为 通信瓶颈。胖树节点间的通路自叶 不不不 向根逐渐变宽。 (c)二叉胖树 21 2021/9/1
* ⼆叉树： * 除了根、叶节点，每个内节点只与 其⽗节点和两个⼦节点相连。 * 节点度为3，对剖宽度为1，⽽树的 直径为 * 如果尽量增⼤节点度为N-1，则直径 缩小为2，此时就变成了星形⽹络， 其对剖宽度为 * 传统⼆叉树的主要问题是根易成为 通信瓶颈。胖树节点间的通路自叶 向根逐渐变宽。 21 2021/9/1 静态互连网络（3） 2(élog Nù -1) ëN / 2û (a)二叉树 (b)星形连接 (c)二叉胖树
静态互连网络(4) 超立方： *一个n-立方由N=2”个顶，点组成， 3-立方如图(a)所示；4立方如图 (b)所示，由两个3立方的对应顶 点连接而成。 (a)3-立方 (6)4-立方 *n-立方的节点度为n,网络直径也 是n,而对剖宽度为N/2。 米 如果将3立方的每个顶，点代之以 一个环就构成了如图(d)所示的3 立方环，此时每个顶点的度为3， (c)顶点代之以环 (d)3-立方环 而不像超立方那样节，点度为。 22 2021/9/1
* 超立⽅ ： * ⼀个n-立⽅由 个顶点组成， 3-立⽅如图(a)所示；4-立⽅如图 (b)所示，由两个3-立⽅的对应顶 点连接⽽成。 * n-立⽅的节点度为n，⽹络直径也 是n ，⽽对剖宽度为 。 * 如果将3-立⽅的每个顶点代之以 ⼀个环就构成了如图(d)所示的3- 立⽅环，此时每个顶点的度为3， ⽽不像超立⽅那样节点度为n。 22 2021/9/1 静态互连网络（4） n N = 2 N / 2 (a)3-立方 (b)4-立方 (c)顶点代之以环 (d)3-立方环