7.4 互连网络 互连网络是将集中式系统或分布式系统中的结点连 接起来所构成的网络。

Presentation on theme: "7.4 互连网络 互连网络是将集中式系统或分布式系统中的结点连 接起来所构成的网络。"— Presentation transcript:

1 7.4 互连网络 互连网络是将集中式系统或分布式系统中的结点连 接起来所构成的网络。
第７章 多处理机 7.4 互连网络 互连网络是将集中式系统或分布式系统中的结点连 接起来所构成的网络。 在拓扑上，互连网络为输入和输出两组结点之间提 供一组互连或映象。 本节介绍：构造多处理机的互连网络

2 7.4.1 互连网络的性能参数 1. 互连网络的拓扑结构 (1) 静态网络 由点和点直接相连而成，这种连接方式在 程序执行过程中不会改变。
7.4 互连网络 互连网络的性能参数 1. 互连网络的拓扑结构 (1) 静态网络 由点和点直接相连而成，这种连接方式在 程序执行过程中不会改变。 (2) 动态网络 用开关通道实现，可动态地改变结构， 使其与用户程序中通信要求匹配。

3 网络中任意两个结点间最短路径长度的最大值。 (4) 等分宽度 在将某一网络切成相等两半的各种切法中， 沿切口的最小通道边数。
7.4 互连网络 2. 性能参数 (1) 网络规模：结点数 (2) 结点度：与结点相连接的边的数目。 入度：进入结点的通道数 出度：从结点出来的通道数 (3) 网络直径 网络中任意两个结点间最短路径长度的最大值。 (4) 等分宽度 在将某一网络切成相等两半的各种切法中， 沿切口的最小通道边数。

4 从其中的任何一个结点看，拓扑结构都是一样的。 (5) 路由 在网络通信中对路径的选择与指定。
7.4 互连网络 对称网络 从其中的任何一个结点看，拓扑结构都是一样的。 (5) 路由 在网络通信中对路径的选择与指定。 3. 互连函数 如果把互连网络的N个入端和N个出端各自用 整数0，1，…，N-1代表，则互连函数表示互连的 出端号和入端号的一一对应关系。

5 f(x0)=x1,f(x1)=x2,……,f(xj)=x0 j+1称为该循环的周期。 (2) 置换 指对象的重新排序。对于n个对象来说，
7.4 互连网络 4. 几种数据路由功能 (1) 循环 若把互连函数f(x)表示为： (x0,x1,x2,……,xj) 则代表对应关系为： f(x0)=x1,f(x1)=x2,……,f(xj)=x0 j+1称为该循环的周期。 (2) 置换 指对象的重新排序。对于n个对象来说， 有n!种置换。

6 例如 置换π=(a,b,c)(d,e)表示了置换映射： f(a)=b,f(b)=c,f(c)=a,f(d)=e和f(e)=d。
7.4 互连网络 例如 置换π=(a,b,c)(d,e)表示了置换映射： f(a)=b,f(b)=c,f(c)=a,f(d)=e和f(e)=d。 这里循环(a,b,c)周期为3，循环(d,e)周期为2。 (3) 均匀混洗 n=8（对象个数）的均匀混洗所对应的映射与其逆过程 对n=2k个对象均匀混洗，可用k位二进制数 x=(xk-1,…,x1,x0) 表示定义域中的每个对象 均匀混洗将x映射到f(x)，得到：f(x)=( xk-2,…,x1,x0,xk-1) （将x循环左移1位）

7

8 7.4 互连网络 (4) 超立方体路由功能 例 一个三维二进制立方体网络

9 分别根据结点的二进制地址（C2 C1 C0）中的某一位来确定
7.4 互连网络 有三种路由功能: 分别根据结点的二进制地址（C2 C1 C0）中的某一位来确定 根据最低位C0路由 根据中间位C1路由 根据最高位C2路由 一个n维超立方体共有n种路由功能，分别由n位地 址中的每一位求反位值来确定。将x=(xk-1,…,x1,x0)映 射到f(x)，得到f(x)=( xk-1, …, xk,…,x1,x0)。

10

11 (5) 广播和选播 广播 一对全体的映射。 选播 一个子集到另一子集(多对多)的映射。 5. 影响互连网络性能的因素 (1) 功能特性
7.4 互连网络 (5) 广播和选播 广播 一对全体的映射。 选播 一个子集到另一子集(多对多)的映射。 5. 影响互连网络性能的因素 (1) 功能特性 网络如何支持路由、中断处理、同步、请 求／消息组合和一致性。

12 单位消息通过网络传送时最坏情况下的时间延迟。 (3) 带宽 通过网络的最大数据传输率，用MB／s表示。 (4) 硬件复杂性
7.4 互连网络 (2) 网络时延 单位消息通过网络传送时最坏情况下的时间延迟。 (3) 带宽 通过网络的最大数据传输率，用MB／s表示。 (4) 硬件复杂性 诸如导线、开关、连接器、仲裁和接口逻辑等 的造价。 (5) 可扩展性 在增加机器资源使性能可扩展的情况下，网络 具备模块化可扩展的能力。

13 7.4.2 静态连接网络 1. 线性阵列 一种一维的线性网络，其中N个结点用N-1个链 路连成一行。 内部结点度：2 端结点度：1
7.4 互连网络 7.4.2 静态连接网络 1. 线性阵列 一种一维的线性网络，其中N个结点用N-1个链 路连成一行。 内部结点度：2 端结点度：1 直径：N-1 等分宽度b=1

14 用一条附加链路将线性阵列的两个端点连接起 来而构成的。可以单向工作，也可以双向工作。
7.4 互连网络 2. 环和带弦环 (1) 环 用一条附加链路将线性阵列的两个端点连接起 来而构成的。可以单向工作，也可以双向工作。 结点度：2 双向环的直径：N／2 单向环的直径：N

15 增加的链路愈多，结点度愈高，网络直径就愈小。
7.4 互连网络 (2) 带弦环 增加的链路愈多，结点度愈高，网络直径就愈小。

16 7.4 互连网络 全连接网络 结点度: N-1 直径最短，为1

17 数幂的结点之间都增加一条附加链而构成的。
7.4 互连网络 3. 循环移数网络 通过在环上每个结点到所有与其距离为2的整 数幂的结点之间都增加一条附加链而构成的。 结点数: 16 结点度: 7 直径: 2

18 如果｜j-i｜=2 r，r=0,1,2,…,n-1，网络规模 N=2n，则结点i与结点j连接。这种循环移数网络的结
7.4 互连网络 如果｜j-i｜=2 r，r=0,1,2,…,n-1，网络规模 N=2n，则结点i与结点j连接。这种循环移数网络的结 点度为d=2n-1，直径D=n／2。

19 4. 树形和星形 (1) 一棵5层31个结点的二叉树 一般说来，一棵k层完全平衡的二叉树有 N=2k-1个结点。
7.4 互连网络 4. 树形和星形 (1) 一棵5层31个结点的二叉树 一般说来，一棵k层完全平衡的二叉树有 N=2k-1个结点。 最大结点度是3，直径是2(k-1)。 (2) 星形 一种2层树 结点度较高，为d=N-1 直径较小，是一常数2

20 7.4 互连网络

21 7.4 互连网络 5. 胖树形

22 部结点度为2k ，网络直径为k(n-1)。边结 点和角结点的结点度分别为3或2。 (2) 环形网
7.4 互连网络 6. 网格形和环网形 (1) 一个3×3网格形网络 一般说来，N=nk 个结点的k维网络的内 部结点度为2k ，网络直径为k(n-1)。边结 点和角结点的结点度分别为3或2。 (2) 环形网 可看做是直径更短的另一种网格 环形网沿阵列每行和每列都有环形连接 一个n×n二元环网 结点度为4 直径为2*[n/2」

23 7.4 互连网络

24 一般说来，一个n-立方体由N=2n 个结点组成， 它们分布在n维上，每维有两个结点。 例 8个结点的3-立方体 4-立方体
7.4 互连网络 7. 超立方体 一种二元n-立方体结构 一般说来，一个n-立方体由N=2n 个结点组成， 它们分布在n维上，每维有两个结点。 例　8个结点的3-立方体 4-立方体 一个n-立方体的结点度等于n，也就是网络的 直径。

25 7.4 互连网络

26 环形、网络形、环网形、二元n-立方体(超立方 体)等网络都是k元n-立方体网络系统的拓扑同构体。 参数n: 立方体的维数
7.4 互连网络 8. k元n-立方体网络 环形、网络形、环网形、二元n-立方体(超立方 体)等网络都是k元n-立方体网络系统的拓扑同构体。 参数n: 立方体的维数 k: 基数或者说是沿每个方向的结点数(多重性)。 N=kn, (n=logkN) K元n-立方体的结点可用基数为k的n位地址 A=a0a1a2…an-1来表示，其中ai代表第i维结点的位置。 按照惯例，低维k元n-立方体称为环网，而高维二 元n-立方体则称为超立方体。

27 7.4 互连网络 例　一种4元3-立方体网络

28 7.4.3 动态连接网络 1. 动态互连网络的三个主要操作特征 定时 开关 控制 2. 根据级间连结方式，动态互连网络分为 (1) 单级网络
7.4 互连网络 动态连接网络 1. 动态互连网络的三个主要操作特征 定时 开关 控制 2. 根据级间连结方式，动态互连网络分为 (1) 单级网络 也称循环网络 (2) 多级网络 由一级以上的开关元件构成。 这类网络可以把任一输入与任一输出相连。

29 阻塞网络 如果同时连接多个输入输出对时,可能会引 起开关和通信链路使用上的冲突。 大多数多级网络都是阻塞网络。 非阻塞网络
7.4 互连网络 阻塞网络 如果同时连接多个输入输出对时,可能会引 起开关和通信链路使用上的冲突。 大多数多级网络都是阻塞网络。 非阻塞网络 如果多级网络通过重新安排连接方式可以 建立所有可能的输入输出之间的连接。

30 3. 几类主要的开关网络 (1) 总线系统 优点：价格较低 带宽较窄 缺点：容易产生故障 总线研制中的重要问题 总线仲裁 中断处理
7.4 互连网络 3. 几类主要的开关网络 (1) 总线系统 优点：价格较低 带宽较窄 缺点：容易产生故障 总线研制中的重要问题 总线仲裁 中断处理 一致性协议 总线事务的处理

31 一种总线连接的多处理机系统

32 提供源(处理器)和目的(存储器)之间点对点 的连接通路。 交叉点开关网络中n对处理器可以同时传送 数据。 交叉开关网络的带宽和互连特性最好。
7.4 互连网络 (2) 交叉开关网络 单级无阻塞置换网络 每个交叉点是一个可以打开或关闭的开关， 提供源(处理器)和目的(存储器)之间点对点 的连接通路。 交叉点开关网络中n对处理器可以同时传送 数据。 交叉开关网络的带宽和互连特性最好。 一种交叉开关网络

33 7.4 互连网络

34 ② 多端口存储器结构是一个折衷方案，它介于低 成本低性能的总线系统和高成本高带宽的交叉 开关系统之间。 ③ 缺点
7.4 互连网络 (3) 多端口存储器 ① 主要思想 将所有交叉点仲裁逻辑和跟每个存储器模 块有关的开关功能移到存储器控制器中。 ② 多端口存储器结构是一个折衷方案，它介于低 成本低性能的总线系统和高成本高带宽的交叉 开关系统之间。 ③ 缺点 十分昂贵 不能扩展 当系统配置很大时，需要大量的互连电缆和连接器。

35 用于多处理机系统的多端口存储器结构

36 (4) 多级网络 多级网络可用于构造大型多处理机系统。 ① 一种通用多级网络 各种多级网络的区别就在于所用开关模 块和级间连接模式的不同。
7.4 互连网络 (4) 多级网络 多级网络可用于构造大型多处理机系统。 ①　一种通用多级网络 各种多级网络的区别就在于所用开关模 块和级间连接模式的不同。

37 由a×b开关模块和级间构成的通用多级互连网络结构

38 7.4 互连网络 ②　Omega网络 2×2开关四种可能的连接方式

39 一个16×16 Omega网络