第7章互联网络.ppt

《第7章互联网络.ppt》由会员分享，可在线阅读，更多相关《第7章互联网络.ppt（55页珍藏版）》请在第壹文秘上搜索。

1、第7章 互连网络7.1 互连网络的基本概念7.2 互连网络的结构1.互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。结点：处理器、存储模块或其他设备。互连网络在系统中的位置，如图所示。在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。7.1 互连网络的基本概念7.1.1 互连网络的功能和特性7.1 互连网络的基本概念 互连网络互连网络 结结 点点 链路链路 结结 点点 链路链路 结结 点点 链路链路 互连网络在系统中的位置互连网络在系统中的位置7.1 互连网络的基本概念1.可以从4个不同的方面来描述互连网络定时方式：有同步和异步

2、两种。q同步系统：同步系统：使用一个统一的时钟。使用一个统一的时钟。SIMDSIMD阵列处理机就属于这一种类型。阵列处理机就属于这一种类型。q异步系统：异步系统：没有统一的时钟，系统中的各个处理机都没有统一的时钟，系统中的各个处理机都是独立地工作。是独立地工作。交换方法：有线路交换和分组交换两种。q线路交换：线路交换：源结点和目的结点之间的物理通路在整个源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。数据传送期间一直保持连接。q分组交换：分组交换：把信息分割成许多组（又称为包），将它把信息分割成许多组（又称为包），将它们分别送入互连网络。们分别送入互连网络。7.1 互连网络的基本

3、概念n这些数据包可以通过不同的路径传送，到达目这些数据包可以通过不同的路径传送，到达目的结点后再拼合成原来的数据。的结点后再拼合成原来的数据。n结点之间不存在固定连接的物理通路。结点之间不存在固定连接的物理通路。控制策略：有集中式和分散式两种q集中控制方式：集中控制方式：有一个全局的控制器接收所有的通有一个全局的控制器接收所有的通信请求，并由它设置互连网络的开关连接。信请求，并由它设置互连网络的开关连接。q分散控制方式：分散控制方式：不存在全局的控制器，通信请求的不存在全局的控制器，通信请求的处理和开关的设置由互连网络分散地进行。处理和开关的设置由互连网络分散地进行。7.1 互连网络的基本概念

4、拓扑结构：有静态和动态两种。q静态拓扑结构：静态拓扑结构：在各结点之间有专用的连接通路，且在各结点之间有专用的连接通路，且在运行过程中不能改变。在运行过程中不能改变。q动态拓扑结构：动态拓扑结构：可根据需要设置互连网络中的开关，可根据需要设置互连网络中的开关，从而对结点之间的连接通路进行重新组合，实现所要从而对结点之间的连接通路进行重新组合，实现所要求的通信模式。求的通信模式。7.1 互连网络的基本概念 变量x：输入（设x=0，1，N1）函数f(x)：输出 通过数学表达式建立输入端与输出端的一一对应关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。互连函数反映了网络输入数组和输出数组

5、之间对应的置换关系或排列关系。（有时也称为（有时也称为置换函数置换函数或或排列函数排列函数）7.1.2 互连函数7.1 互连网络的基本概念互连函数f(x)有时可以采用循环表示 即：（x0 x1 x2 xj-1）表示：f(x0)=x1，f(x1)=x2，f(xj-1)=x0 j称为该循环的长度。几种常用的基本互连函数及其主要特征：1.交换函数 交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接。011121011121xxxxxxxxxxxxxxEkkknnkkknn7.1 互连网络的基本概念主要用于构造立方体互连网络和各种超立方体互连网络。它共有nlog2N种互连函数。（N N

6、为结点个数）为结点个数）当N8时，n3，可得到常用的立方体互连函数：012012201201210120120 xxxxxxCxxxxxxCxxxxxxC7.1 互连网络的基本概念q变换图形变换图形 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7(a)C0交换函数交换函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7(b)C1交换函数交换函数(c)C2交换函数交换函数 N=8 N=8 的立方体交换函数的立方体交换函数 7.1 互连网络的基本概念立方体网络立方体网络7.1 互连网络的基本概念1.均匀

7、洗牌函数均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。q函数关系函数关系 即把输入端的二进制编号循环左移一位。即把输入端的二进制编号循环左移一位。101320121nnnnnxxxxxxxxxS7.1 互连网络的基本概念qN=8N=8 的的均匀洗牌均匀洗牌和和逆均匀洗牌逆均匀洗牌函数函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7(a)均均匀匀洗洗牌牌函函数数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7(b)逆逆均均匀匀洗洗牌牌函函数数 N=8 N=8 的均匀洗牌和逆均匀洗

8、牌函数的均匀洗牌和逆均匀洗牌函数7.1 互连网络的基本概念逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号。q互连函数互连函数 逆均匀洗牌是均匀洗牌的逆函数逆均匀洗牌是均匀洗牌的逆函数 1.碟式函数 蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。121001211xxxxxxxxSnnnn11200121nnnnxxxxxxxxB7.1 互连网络的基本概念1.反位序函数 反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。q互连函数互连函数 q对于对于N N8 8的情况，的情况，B(x)B(x)函数等于函数等于R(x)R

9、(x)函数。函数。12100121nnnnxxxxxxxxR7.1 互连网络的基本概念qN N8 8的蝶式函数的变换图形的蝶式函数的变换图形 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7(a)碟式函数碟式函数(b)反位序函数反位序函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 N=8 N=8 的碟式函数和反位序函数的碟式函数和反位序函数7.1 互连网络的基本概念1.PM2I函数 PM2I函数：一种移数函数，它是将各输入端都循环移动一定的位置连到输出端。互连函数 PM2+i(x)x2i mod N PM2-i(x)x2i mod N 其中：其中：0 xN0

10、 xN1 1，0in0in1 1，n nloglog2 2N N，N N为结点数。为结点数。PM2I互连网络共有2n个互连函数。7.1 互连网络的基本概念当N8时，有6个PM2I函数：qPM2PM2+0+0 ：（0 1 2 3 4 5 6 70 1 2 3 4 5 6 7）qPM2PM2-0-0 ：（7 6 5 4 3 2 1 07 6 5 4 3 2 1 0）qPM2PM2+1+1 ：（0 2 4 6 0 2 4 6）（）（1 3 5 71 3 5 7）qPM2PM2-1-1 ：（6 4 2 06 4 2 0）（）（7 5 3 17 5 3 1）qPM2PM22 2：（0 40 4）（）（1

11、 51 5）（）（2 62 6）（）（3 73 7）7.1 互连网络的基本概念N=8 N=8 的的PM2IPM2I函数函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7(a)PM2+0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7(b)PM2+1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7(c)PM2+2 阵列计算机ILLIAC 采用采用PM2PM20 0和和PM2PM2n/2n/2构成其互连网络，实现各构成其互连网络，实现各处理单元之间的上下左右互连处理单元之间的上下左右互连 。0 1 2 3 4 5 6 7 8 9 10 11 12

12、13 14 15 用移数函数构成用移数函数构成ILLIAC ILLIAC 阵列机的互连网络阵列机的互连网络7.1 互连网络的基本概念1.网络通常是用有向边或无向边连接有限个结点的图来表示。2.互连网络的主要特性参数有：网络规模：网络中结点的个数。表示该网络所能连接的部件的数量。表示该网络所能连接的部件的数量。结点度：与结点相连接的边数（通道数），包括入度和出度。q进入结点的边数称为进入结点的边数称为入度入度。q从结点出来的边数称为从结点出来的边数称为出度出度。7.1.3 互连网络的特性参数7.1 互连网络的基本概念距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的

13、最小值。网络直径：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。网络直径应当尽可能地小。结点之间的线长：两个结点之间连线的长度，用米、千米等表示。等分宽度：当某一网络被切成相等的两半时，沿切口的边数（通道数）的最小值称为通道等分宽度，用b表示。7.1 互连网络的基本概念q线等分宽度：线等分宽度：B Bb bw wq其中：其中：w w为通道宽度（用位表示）。为通道宽度（用位表示）。q该参数主要反映了网络最大流量。该参数主要反映了网络最大流量。对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。对称网络比较容易实现，编程也比较容易。互连网

14、络通常可以分为两大类：静态互连网络 各结点之间有固定的连接通路且在运行中不能改各结点之间有固定的连接通路且在运行中不能改变的网络。变的网络。动态互连网络 由交换开关构成、可按运行程序的要求动态地改由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。变连接状态的网络。下面介绍几种静态互连网络。（其中：（其中：N N表示结点的个数）表示结点的个数）7.2 互连网络的结构7.2.1 静态互连网络7.2 互连网络的结构1.线性阵列 一种一维的线性网络，其中N个结点用N-1个链路连成一行。q端结点的度：端结点的度：1 1q其余结点的度：其余结点的度：2 2q直径：直径：N N1 1q等分宽度等分

15、宽度b=1b=1 7.2 互连网络的结构7.2 互连网络的结构q对称对称q结点的度：结点的度：2 2q双向环的直径：双向环的直径：N/2N/2q单向环的直径：单向环的直径：N N 1.环和带弦环 环 用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。7.2 互连网络的结构带弦环 增加的链路愈多，结点度愈高，网络直径就愈小。7.2 互连网络的结构全连接网络 q结点度：结点度：1515q直径最短，为直径最短，为1 1。1.循环移数网络通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。N=16N=16q结点度：结点度：7 7q直径：直径：2

16、2 7.2 互连网络的结构一般地，如果j-i=2r（r=0,1,2,n-1，n=log2N），则结点i与结点j连接。q结点度：结点度：2n2n1 1q直径：直径：n/2n/27.2 互连网络的结构1.树形和星形 一棵5层31个结点的二叉树 一般说来，一棵k层完全平衡的二叉树有N=2k-1个结点。q最大结点度：最大结点度：3 3q直径：直径：2(k-1)2(k-1)星形 q结点度较高，为结点度较高，为N N1 1。q直径较小，是一常数直径较小，是一常数2 2。q可靠性比较差，只要中心结点出故障，整个系统就会可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。瘫痪。7.2 互连网络的结构7.2 互连网络的结构1.胖树形 7.2 互连网络的结构1.网格形和环网形 网格形q一个一个3 33 3的的网格形网络网格形网络q一般来说，一般来说，N=nN=nk k 个结点的个结点的k k维网络的内部结点度是维网络的内部结点度是2k2k，网络直径为网络直径为k(n-1)k(n-1)。环形网q可看作是直径更短的另一种网格。可看作是直径更短的另一种网格。q将环形和网格形组合在一起，并能向高维扩展。将环形和网