《第7章互联网络.ppt》由会员分享，可在线阅读，更多相关《第7章互联网络.ppt（55页珍藏版）》请在课桌文档上搜索。
1、第7章 互连网络,7.1 互连网络的基本概念7.2 互连网络的结构,互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。结点：处理器、存储模块或其他设备。互连网络在系统中的位置，如图所示。在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。,7.1 互连网络的基本概念,7.1.1 互连网络的功能和特性,7.1 互连网络的基本概念,互连网络在系统中的位置,7.1 互连网络的基本概念,可以从4个不同的方面来描述互连网络定时方式：有同步和异步两种。同步系统：使用一个统一的时钟。SIMD阵列处理机就属于这一种类型。异步系统：没有统一的时钟，系
2、统中的各个处理机都是独立地工作。交换方法：有线路交换和分组交换两种。线路交换：源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。分组交换：把信息分割成许多组（又称为包），将它们分别送入互连网络。,7.1 互连网络的基本概念,这些数据包可以通过不同的路径传送，到达目的结点后再拼合成原来的数据。结点之间不存在固定连接的物理通路。控制策略：有集中式和分散式两种集中控制方式：有一个全局的控制器接收所有的通信请求，并由它设置互连网络的开关连接。分散控制方式：不存在全局的控制器，通信请求的处理和开关的设置由互连网络分散地进行。,7.1 互连网络的基本概念,拓扑结构：有静态和动态两种。静态拓扑结
3、构：在各结点之间有专用的连接通路，且在运行过程中不能改变。动态拓扑结构：可根据需要设置互连网络中的开关，从而对结点之间的连接通路进行重新组合，实现所要求的通信模式。,7.1 互连网络的基本概念,变量x：输入（设x=0，1，N1）函数f(x)：输出 通过数学表达式建立输入端与输出端的一一对应关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系。（有时也称为置换函数或排列函数）,7.1.2 互连函数,7.1 互连网络的基本概念,互连函数f(x)有时可以采用循环表示 即：（x0 x1 x2 xj-1）表示：f(x0)=x1，f(
4、x1)=x2，f(xj-1)=x0 j称为该循环的长度。几种常用的基本互连函数及其主要特征：交换函数 交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接。,7.1 互连网络的基本概念,主要用于构造立方体互连网络和各种超立方体互连网络。它共有nlog2N种互连函数。（N为结点个数）当N8时，n3，可得到常用的立方体互连函数：,7.1 互连网络的基本概念,变换图形,N=8 的立方体交换函数,7.1 互连网络的基本概念,立方体网络,7.1 互连网络的基本概念,均匀洗牌函数均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于
5、混洗的结果）。函数关系 即把输入端的二进制编号循环左移一位。,7.1 互连网络的基本概念,N=8 的均匀洗牌和逆均匀洗牌函数,N=8 的均匀洗牌和逆均匀洗牌函数,7.1 互连网络的基本概念,逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号。互连函数 逆均匀洗牌是均匀洗牌的逆函数 碟式函数 蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。,7.1 互连网络的基本概念,反位序函数 反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。互连函数 对于N8的情况，B(x)函数等于R(x)函数。,7.1 互连网络的基本概念,N8的蝶式
6、函数的变换图形,N=8 的碟式函数和反位序函数,7.1 互连网络的基本概念,PM2I函数 PM2I函数：一种移数函数，它是将各输入端都循环移动一定的位置连到输出端。互连函数 PM2+i(x)x2i mod N PM2-i(x)x2i mod N 其中：0 xN1，0in1，nlog2N，N为结点数。PM2I互连网络共有2n个互连函数。,7.1 互连网络的基本概念,当N8时，有6个PM2I函数：PM2+0：（0 1 2 3 4 5 6 7）PM2-0：（7 6 5 4 3 2 1 0）PM2+1：（0 2 4 6）（1 3 5 7）PM2-1：（6 4 2 0）（7 5 3 1）PM22：（0
7、4）（1 5）（2 6）（3 7）,7.1 互连网络的基本概念,N=8 的PM2I函数,阵列计算机ILLIAC 采用PM20和PM2n/2构成其互连网络，实现各处理单元之间的上下左右互连。,用移数函数构成ILLIAC 阵列机的互连网络,7.1 互连网络的基本概念,网络通常是用有向边或无向边连接有限个结点的图来表示。互连网络的主要特性参数有：网络规模：网络中结点的个数。表示该网络所能连接的部件的数量。结点度：与结点相连接的边数（通道数），包括入度和出度。进入结点的边数称为入度。从结点出来的边数称为出度。,7.1.3 互连网络的特性参数,7.1 互连网络的基本概念,距离：对于网络中的任意两个结点，
8、从一个结点出发到另一个结点终止所需要跨越的边数的最小值。网络直径：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。结点之间的线长：两个结点之间连线的长度，用米、千米等表示。等分宽度：当某一网络被切成相等的两半时，沿切口的边数（通道数）的最小值称为通道等分宽度，用b表示。,7.1 互连网络的基本概念,线等分宽度：Bbw其中：w为通道宽度（用位表示）。该参数主要反映了网络最大流量。对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。,互连网络通常可以分为两大类：静态互连网络 各结点之间有固定的连接通路且在运行中不能改变的网络。动态互连网络
9、由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。下面介绍几种静态互连网络。（其中：N表示结点的个数）,7.2 互连网络的结构,7.2.1 静态互连网络,7.2 互连网络的结构,线性阵列 一种一维的线性网络，其中N个结点用N-1个链路连成一行。,端结点的度：1其余结点的度：2直径：N1等分宽度b=1,7.2 互连网络的结构,7.2 互连网络的结构,对称结点的度：2双向环的直径：N/2单向环的直径：N,环和带弦环 环 用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。,7.2 互连网络的结构,带弦环 增加的链路愈多，结点度愈高，网络直径就愈小。,7.2 互
10、连网络的结构,全连接网络 结点度：15直径最短，为1。,循环移数网络通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。,N=16结点度：7直径：2,7.2 互连网络的结构,一般地，如果j-i=2r（r=0,1,2,n-1，n=log2N），则结点i与结点j连接。结点度：2n1直径：n/2,7.2 互连网络的结构,树形和星形 一棵5层31个结点的二叉树 一般说来，一棵k层完全平衡的二叉树有N=2k-1个结点。最大结点度：3直径：2(k-1)星形 结点度较高，为N1。直径较小，是一常数2。可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。,7.2 互连网络的结构,7.
11、2 互连网络的结构,胖树形,7.2 互连网络的结构,网格形和环网形 网格形一个33的网格形网络一般来说，N=nk 个结点的k维网络的内部结点度是2k，网络直径为k(n-1)。环形网可看作是直径更短的另一种网格。将环形和网格形组合在一起，并能向高维扩展。沿阵列的每行和每列都有环形连接。一个nn二元环网结点度：4直径：2n/2,7.2 互连网络的结构,7.2 互连网络的结构,超立方体 一种二元n维立方体结构一般来说，一个二元n维立方体由N=2n 个结点组成，它们分布在n维上，每维有两个结点。例 8个结点的3维立方体 4维立方体为实现一个n维立方体，只要把两个（n1）维立方体中相对应的结点用链路连接
12、起来即可。共需要2n-1条链路。n维立方体中结点的度都是n，直径也是n。,7.2 互连网络的结构,静态互连网络一览表,7.2 互连网络的结构,总线一组导线和插座，用于进行与总线相连的处理机、存储模块和外围设备等之间的数据传送。每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。多个功能模块之间的争用总线或时分总线。特点价格低带宽较窄,7.2.2 动态互连网络,7.2 互连网络的结构,一种由总线连接的多处理机系统,7.2 互连网络的结构,多级互连网络MIMD和SIMD计算机都使用多级互连网络MIN（Multistage Interconnection Network）一种
13、通用的多级互连网络 由ab开关模块和级间连接构成的通用多级互连网络结构每一级都用了多个ab开关a个输入和b个输出在理论上，a和b不一定相等，然而实际上a和b经常选为2的整数幂，即ab2k，k1。相邻各级开关之间都有固定的级间连接,7.2 互连网络的结构,7.2 互连网络的结构,几种常用的开关模块,7.2 互连网络的结构,最简单的开关模块：22开关 22开关的4种连接方式,7.2 互连网络的结构,各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。控制方式：对各个开关模块进行控制的方式。级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态；单元控制：每一个开关都
14、有一个独立的控制信号，可各自处于不同的状态；部分级控制：第i级的所有开关分别用i1个信号控制，0in1，n为级数。常用的级间互连模式：均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等,7.2 互连网络的结构,两种多级互连网络 Omega网络,88的Omega网络,7.2 互连网络的结构,一个N输入的Omega网络有log2N级，每级用N/2个22开关模块，共需要Nlog2N/2个开关。每个开关模块均采用单元控制方式。不同的开关状态组合可实现各种置换、广播或从输入到输出的其他连接。,7.2 互连网络的结构,多级立方体网络 采用二功能（直送和交换）的22开关和交换函数构成级间互连按从左到右的次序分
15、别是C0、C1、C2互连函数例如：当所有开关都直送时，实现恒等变换；当A、B、C、D四个开关交换、其余直送时，实现C0互连函数；当E、F、G、H四个开关交换、其余直送时，实现C1互连函数；当I、J、K、L四个开关交换、其余直送时，实现C2互连函数。,7.2 互连网络的结构,多级立方体网络,7.2 互连网络的结构,通过选择不同的控制方式，可以构成不同的互连网络。例如：采用以下3种不同的控制方式可以构成3种不同的互连网络：级控制：构成交换网；部分级控制：构成移数网；单元控制：构成间接二进制n方体网。,7.2 互连网络的结构,交叉开关网络 单级开关网络 交叉点开关能在对偶（源、目的）之间形成动态连接，同时实现多个对偶之间的无阻塞连接。带宽和互连特性最好。一个nn的交叉开关网络，可以无阻塞地实现n!种置换。C.mmp多处理机的互连结构（一种交叉网络）,7.2 互连网络的结构,7.2 互连网络的结构,动态网络的比较,
