11互联网络5-1.ppt

1、1,第五章 互连网络,互连网络是现代计算机系统中的一个核心部分和关键部件。对整个计算机系统的性能有着决定性影响。随着系统规模、通信要求和线路复杂性的增加,其重要性在不断增长。已经成为计算机组织和系统结构中独立的研究内容。,5.3 路由选择和信息传递方式 5.4 流量控制策略和通信模式,5.1 互连网络的相关概念 5.2 互连网络的结构,2,5.1 互连网络的相关概念,一、互连网络的组成,1、互连网络(IN)定义 由开关元件按照一定拓扑结构和控制方式构成的网络，实现多个节点对之间的相互连接。 互连网络已成并行计算机系统中重要的核心部件。,根据需要，有PP及PM的连接形式,3,2、互连网络(IN)

2、 的特性 *特性1：同时实现多个端口对的互连及通信。,*特性2：具有多种并行端口对的互连方式.,*互连网络与总线比较： 互连网络 : 强调多个节点对之间的互连及通信。 总 线 : 多个设备或单元所共享的公共通道(分时),理论上有N!种端口对互连排列方式,4,2、互连网络要素：开关元件、互联结构、控制方式。 互联结构：网络合理布局关键因素，反映系统结构特征。用有向图或无向图表示，节点对应开关元件或处理机。边对应通信链路。 开关元件：网络中最基本模块，在不同系统和控制中，开关元件所处的物理位置和工作状态不同。 控制方式：网络中各种开关的控制方法 3 、互连网络的特征,1) 拓扑结构 静态 动态 2

3、) 控制策略 集中式 分散式 3) 定时方式 同步 异步 4) 交换方法 线路交换 分组交换,5,互连网络的特征,1) 拓扑结构: 分静态和动态两种。 静态网:各节点间有专用通信线路（链路），运行间不改变或重新组合。又称直接网络 (节点通过链路直接连接) 组成：由链路、结构及网络节点组成。 结构: 线性、环形、树形、 立方体等。,6,动态网: 链路可通过设置网络中开关重新组合。节点与节点的连接由程序或控制信号动态地改变，又称间接网络(节点与交换开关连接)。 组成：由链路、结构、开关及节点组成。 结构: 总线、环状、 开关、(单)多级。,动态网:,7,互连网络的特征,2)控制策略: 集中控制:全

4、局控制器接收所有通信请求，设置互连网络的开关连接。 分散控制: 通信请求和开关设置由互连网络分散地进行。 3)定时方式 ： 同步系统：系统使用一个集中的统一时钟. 异步系统：无统一时钟，节点根据各自情况独立工作。 4)交换方法: 线路交换和分组交换。 线路交换：源结点和目的结点间的物理通路在整个数据传送期间一直保持连接。 分组交换：信息分割成组(包)，各组(包)通过多个不同路径传分别送入互连网络。传送不存在一个实际连接的固定通路。,8,5.1.2 互连网络的描述,根据输入与输出结点之间的对应关系，有以下表示方法： 函数表示法 变量x表示输入，函数f(x)表示输出，建立输入与输出端的一一对应关系

5、。 自变量和函数常用二进制、十进制表示。互连函数反映网络输入数组和输出数组之间对应的排列关系，也称排列函数。 输入输出对应表示法 图形表示法 用图形表示输入端 与输出端之间的一一对应关系 循环表示法：如(0 4)(1 5)(2 6)(3 7),9,互连函数 数的排列：N个数的每一种有确定次序的放置方法叫做一个N排列。一般有N！种放置方法。 网络排列：N输入、N输出端网络中，输入端和输出端的放置方法分别为一种排列。 置换：把一个N排列变成另一个N排列的变换叫N阶置换。表示输入端和输出端的连接关系. 复杂的置换方式可用少量基本的互联函数表示,10,基本的互联函数,恒等函数:输入端与输出端一一对应,

6、且编号相同。,Xn-1 Xn-2Xk X0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：,(0)(1)(2)(3)(4)(5)(6)(7),11,交换函数,交换函数:函数形式为,主要用于超立方体互联网络中。,超立方体由n个交换函数组成。 K=1,二进制地址编码下，,某一位的输入与输出端编号相反。,0kn,12,当n=3，结点数N8时，可得到3立方体互连函数： 互连函数变换图形,交换函数,典型的立方体网络结构图,(0 1) (2 3 ) (4 5) (6 7),(0 2)(1 3 ) (4 6) (5 7),(0 4)(1 5) (2 6) (3 7),13,均匀洗牌函数,把输

7、入端二进制地址循环左移一位。表示为： 逆均匀洗牌函数: 输入端二进制地址循环右移一位。函数：,(0)(1 2 4)(3 6 5)(7),将输入端分成数目相等的两半，前一半和后一半按序一个隔一个，从头依次与输出端相连，类似洗牌方式。,14,均匀洗牌函数,均匀洗牌函数,逆均匀洗牌函数,均匀洗牌与开关多级组合起来可构成Omega网络,15,蝶式函数,蝶式函数: 输入二进制地址的最高位和最低位互换位置，定义为： N=8的蝶式函数变换图形,均匀洗牌，蝶式函数不能单独实现任意结点间互连。它们与交换函数多级组合是构成复杂多级网络的基础,例如 : 均匀洗牌函数与Cube0的组合,(0)(2)(1 4) (3

8、6)(5)(7),16,反位序函数,反位序函数: 输入端二进制地址的位序颠倒过来求得相应输出端的地址。其互连函数表示如下： 对于N=8的情况，图形见图5.4（b）,17,PM2I移数函数,移数函数的一般形式为： 如k=2 PM2I函数（加减2i）是一种特殊移数函数，将输入端数组的十进制编号循环移动特定的位置向输出端传输。 N个结点的移数函数表示为： 如i=1 设 N为结点数。n=log2 N ； 0 xN1，0in1， 共有2n个互连函数,(0 2 4 6)(1 3 5 7),18,N=8的PM2I函数的变换图形。,(a) PM2： (0 1 2 3 4 5 6 7),(b) PM21： (0

9、 2 4 6) (1 3 5 7),(c) PM2+2： (0 4)(1 5)(2 6)(3 7),实质为1,2,4 个环型网,移数函数可构成环型网(单向环网、双向环网)、方格网、移数网,19,课堂练习,设PM2I网络有8个结点，写出所有PM2I函数的输入输出对表示，画出PM21、PM22互连网络的连接图。,20,【例 】设PM2I网络有8个结点，写出所有PM2I函数的，画出PM21、PM22互连网络的连接图。,解 N=8，则n =3，所以i=0,1,2;j=0,1,7。 根据公式 6个PM2I函数如下： PM2：(0 1 2 3 4 5 6 7) PM2：(7 6 5 4 3 2 1 0)

10、PM21：(0 2 4 6)(1 3 5 7) PM21：(6 4 2 0)(7 5 3 1) PM2 2：(0 4)(1 5)(2 6)(3 7) PM2 2 ：(4 0)(5 1)(6 2)( 7 3),PM2,PM2,21,PM21：(0 2 4 6)(1 3 5 7),PM21互连网络的连接图。,22,(c) PM22：(0 4)(1 5)(2 6)(3 7) (4 0)(5 1)(6 2)(7 3),PM22互连网络的连接图,23,【例】Illiac 阵列计算机：采用PM20和PM2n/2四个移数网络构成处理器的连接。16个结点的Illiac 网络表示,PM22：(0 4)(1 5)

11、(2 6) (3 7) (4 8)(5 9)(6 10)(7 11) (8 12)(9 13)(10 14)(11 15) (0 12)(1 13)(2 14) (3 15),PM2+0:( 0 1 2 15 ) PM2-0:( 15 14 13 0 ),24,5.1.3互连网络的特性参数,主要特性参数有： 网络规模: 结点度: 距离 网络直径 结点间线长 等分宽度 对称性,25,网络规模：网络中结点个数，表示该网络所能连接的部件多少。 结点度：与结点相连接的边数(通道数)。进结点的边数叫入度，出结点的边数叫出度。 结点度=出度+入度 距离：两个结点之间相连的最少边数。 网络直径：网络中结点间

12、距离的最大值，可用结点间的连接边数表示。 结点间线长：结点间连线的长度，用米、公里等表示。,互连网络的特性参数,26,等分宽度:把N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。反映网络内部传输带宽。 线等分宽度：传输带宽与通道宽度w(位)的乘积，Bbw。反映网络最大流量。 对称性：从任何结点，拓扑结构都相同的网络称为对称网络。对称网络容易编程和实现。结点上的负载量分布均匀。,互连网络的特性参数,27,5.2.1 静态互连网络 静态网络： 指各节点（处理单元）间有着固定或专用的连接通路的网络。在程序执行中，节点到节点的链接保持（或网络）保持不变。 静态网络中

13、，每个开关元件固定地与一个结点相连，或分散在每个节点的内部（看不到开关元件），直接实现两结点之间的通信。 一般是简单的、通信模式可预测的网络系统。,5.2 互连网络的结构,互连网络可分为静态和动态互连网络。,28,静态互连网络,从不同的角度对静态互连网络进行分类 1）按通路类型 共享（总线型）通路： 非共享通路： 2) 按拓扑维数 所谓维数 n ，指网络画在n维空间时才能保证各条链路不会相交。 3) 按网络形状 总线型、线型、 环型、立方体型、树型、全连接等。 4) 按度数,29,典型的静态网络,N个结点的线形网（规模），有N-1条链路，距离的最大值为N-1（直径），度为2，等分宽度为1。 一

14、维，不对称（？）。 简单，N很大时，通信效率很低。,1.线形网,30,2.环形网,N个结点的环，有双向环和单向环。 双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。 单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。,31,3.带弦环,图为（12个结点）带弦双向环 结点度为3：链路数为18，直径4（红色结点），度为3，不对称，等分宽度为2。 结点度为4：链路数为24，直径3（红色结点），度为4，对称，等分宽度为8。,32,4.全链接 全链接中的每个结点和其他结点之间都有单一的直接链路。带弦环的一种特殊情形。 下图中8个结点的全链接：,28条链路，直径1，度为7，对称，等分

15、宽度16。,全连接网络是最复杂的拓扑结构，每个结点同其他 结点都连接，直径为1，度数是(N-1)。,33,5.树形,4层的二叉树,K层完全二叉树有N = 2K - 1个结点，中间层结点的结点度为3，直径为2（K - 1）。不对称，等分度为1。树形网是一种容易扩展的系统结构。 根部结点和连到根部链路上的负载量较大，为系统的瓶颈。,34,树形的扩展：,带环树,两种结构可以缓解根结点的瓶颈问题。,35,6.星形,星形实际上是一种二层树（如右图）。 N个结点的星形网络，有N - 1条链路，直径为2，最大结点度为N - 1，非对称（？），等分宽度为1。,36,7.网格,N个结点的rr网格，有2N - 2

16、r条链路， 直径为2（r-1)，结点度为4，非对称，等分宽度为r。,二维环形拓扑结构,37,网格的变形-Illiac 网：,N个结点的rr网格 2N条链路（？），直径为r-1，结点度为4。,-网格结构扩充性好，易在VLSI芯片上实现。,每行尾与下一行的头，每列尾与下一列的头相接-网格卷绕。,38,网格的变形-搏动式阵列（Systolic Array）,39,8.超立方体,0维-立方体,1维-立方体,2维-立方体,3维-立方体,4维-立方体,n-立方体由N = 2n个结点构成。直径为n，结点度为n，对称。结点度随维数线性增加。,特点： 相邻的结点编号只差一位,40,9.带环立方体（CCC）,一个

17、带环n-立方体，由N = 2n个结点环构成，每个结点环是一个有n个结点的环，结点总数为n 2n个。直径通常为2n，结点度为3，对称。,带环3-立方体,41,静态网络特性比较,42,5.2.2 动态互连网络,动态网络(dynamic Networks)通常由交换开关构成互联网络的，可按运行程序的要求改变网络的连接状态。 特点： 网络中开关元件可以控制（有源）。 链路可通过设置开关的状态来重构。 网络边界上的开关元件可与处理机相连。 有总线网络、多级网络和交叉开关网络等。,43,1 总线系统,总线是一组公用通信通路，通过导线和插座把各台处理机、存储模块和外围设备与总线连接起来。总线是一组公用通信通

18、路，通过导线和插座把各台处理机、存储模块和外围设备与总线连接起来。 组成：处理机、存储模块、局部Catch、I/O部件和外围设备等。总线结构在并行处理机系统有重要地位。,44,总线系统一般特点,处理机、存储模块和外围设备均与总线相连，分时工作。价格低。 每台处理机都能访问公共总线，有局部catch。 处理机通过请求访问全局存储器。多请求下总线仲裁逻辑将总线分配给一个请求。 局部Catch数据修改和通信执行“一致性协议” 存在总线和共享存储器两大瓶颈。 主要问题：总线仲裁、中断处理、一致性协议和总线事务处理（带宽窄）。 总线复杂性由总线上连接的分接头数n与数据通路宽度w的和w+n决定.,45,多

19、级网络,单级网络：由一级开关和一种连接模式构成的互联。 多级网络则包含多级开关和多级连接模式。,每一级都用多个ab开关，通过动态设置开关状态，改变或建立输入和输出对之间的连接。 相邻级开关间有固定的级间连接（ISC)。 ab开关: a个输入和b个输出。a和b常为2的整数幂 级控制、单元控制、部分级控制 三种控制方式。,46,控制方式指对各个开关模块进行控制的方法。 (1)级控制 每一级所有开关只用一个控制信号控制，该级所有开关处于同一种状态； (2)单元控制 每个开关都有单独的控制信号，各自可处于不同的状态； (3)部分级控制 第i级的所有开关分别用i+1个信号控制，控制信号随级数增加而递加。

20、 级间连接(ISC)模式：均匀洗牌、蝶式、交换 常用开关模块：22，44，88。,多级互连网络控制方式,47,【例】Omega网络,88 Omega网络，3级。22开关。级数一般为logkn 网络左侧有8个输入，右侧有8个输出。 级间连接(ISC)是对8个对象的均匀洗牌模式。 控制开关状态可实现从输入到输出的多种连接。 交叉开关复杂性 O(n logkn) w)。w是MIN设计中链路宽度。(假设k*k开关为基本构件)。,48,Omega网络,构造Omega网络的22开关的四种连接方式：直通、交叉、上播和下播。,开关模块及状态：,上播和下播不能构成置换（允许一个输入连接两个输出）,49,【例4】

21、一个多级立方体网采用二功能开关和交换函数构成，其拓扑结构如图所示。使交换开关的设置处于某一种工作状态，可以得到的不同的多级互连网络。 (1)当所有开关都直通时，实现恒等变换； (2)当A、B、C、D四个开关交换，其余直通时实现C； (3)当E、F、G、H四个开关交换，其余直通时实现C1； (4)当I、J、K、L四个开关交换，其余直通时实现C2。,50,交叉开关网络,可看作单级开关网络。带宽和互连特性最好。交叉点能在(源，目的)之间动态连接，每个交叉点开关根据程序要求动态设置“开”或“关”。如图是多处理机中处理机-存储器间的交叉开关网络。,51,交叉开关网络,在处理机和存储模块间用交叉开关网络构成一个共享存储型多处理机，实际是一个存储器访问网络。支持并行(或交叉)存储器访问。 每个处理机可同时访问不同的存储模块。同时接通几个交叉点开关。 每个存储模块一次只能满足一台处理机的请求。每一列只能接通一个交叉点开关。 在多个请求同时到达同一存储模块时，交叉开关要分解所发生的冲突。 每台处理机可能会产生一系列地址，同时访问多个存储模块。,52,向量并行处理机(V