系统结构第六章互联网络.

第六章互连网络6.1互连网络的基本概念6.2静态互连网络6.3动态互连网络6.1互连网络的基本概念一.互连网络的功能1．什么是互连网络?从广义上讲，凡是用以实现部件、设备或系统之间连接用的部件都可以称为互连网络。狭义上讲，互连网络是一种由开关元件按一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多处理机或多功能部件之间的相互连接。它通过硬件线路，实现设备之间的连接；通过开关选择，构成一对一或一对多的信息通路。6.1互连网络的基本概念系统存储器部件控制处理机数据传送部件主存储器标量部件数据传送部件主存储器部件量部件向量标处理部件122221224×224交叉开关处理部件VP2000二级存储器数据传送部件主存储器标量部件数据传送部件主存储器部件量部件向量标互连网络富士通VPP500并行向量处理机:更为一般的系统：存储器存储器存储器处理机—存储器网络m12共享存储器处理机间网络处理机存储器处理机存储器处理机—外设网络磁带设备磁盘设备打印设备网络共享外设系统以多处理机为核心，各处理机有自己专用的存储器，称为本地存储器，处理机内包含有独用的Cache。此外还有各处理机公用的存储器，称为共享存储器，各处理机对共享存储器的访问通过处理机—存储器网络进行交换。6.1互连网络的基本概念2．互连网络的主要功能1）连接各个结点，构成信息通路，传送数据或控制命令。2）通过路径选择，实现有目的的信息交换，其中包括一到一和一到多的选择与交换。6.1互连网络的基本概念二.互连网络的主要特性1）网络规模：即一个网络中所连接的结点数。2）结点度：每个结点与外部连接的边数称为一个结点的度，用d表示。结点A结点B线路(b)双向结点A结点B线路(a)单向6.1互连网络的基本概念3）距离：任意两结点之间相连的最少边数。4）网络直径（D）：网络中任意结点之间距离中的最大值。BACDAB的距离:1AC的距离:1AD的距离:1BC的距离:2BD的距离:1CD的距离:1网络直径:D=25）结点间线长：两个结点之间实际连接用的线长。6.1互连网络的基本概念6）等分宽度：通道等分宽度：一个网络被切割成对等的两半时，沿切口所具有的边数（通道数），称为通道等分宽度，用k表示。线等分宽度：若用w表示通道宽度（用位表示），则线等分宽度为：B=k×w。7）对称性：如果从任一个结点观察网络，所看到的网络拓扑结构都是相同的，该网络是一个对称网络。8）数据寻经功能：表示互连网络把数据从一端传送到另一端的方式和能力。寻径方式分为静态和动态两种。寻径功能有一到一、一到多、散射、汇合/聚集等。6.1互连网络的基本概念三.互连函数1．互连网络的功能表示无论何种互连网络，在系统中所起的作用都是一样的，即进行有关部件（或设备）间的有效连接，完成信息的传输。如果将互连网络看作一个黑盒子，盒子的输出端口与输入端口间就存在一定的位置变换关系，这就是互连函数。6.1互连网络的基本概念特别应该强调指出，这里所谓的变换关系并不是信号形式的变换，而只是端口位置的变换关系，所以用以表征黑盒子特性的不是传输函数，而是互连函数。互连网络f(i)12N12N6.1互连网络的基本概念2.互连函数表示法1）函数表示法：在函数表示法中，通常用x表示输入端变量（即端口编号），f(x)就用以表示互连函数。其中x常用端口编号的二进制值表示，x=xn-1xn-2…x1x0。而相应的互连函数就可以写成：f(xn-1xn-2…x1x0)。如果变换函数发生了变化，其表示也就可以相应的写成：σ(xn-1xn-2…x1x0)。一个完整的函数就应在其等式的右边写出该函数的值，即变换的结果。例如：σ(xn-1xn-2…x1x0)=xn-2xn-3…x1x0xn-16.1互连网络的基本概念2）输入输出对应表示法：即列出对应端口间的对应关系表，输入输出对应关系列出在符号框内，其表示形式为：7351624076543210在符号框内，上一个元素与下一个元素分别对应输入与输出的连接关系。6.1互连网络的基本概念0000010100111001011101110000010100111001011101113）图形表示法图形表示法是直接用连线将输入与输出的关系连接在一起，非常直观。其缺点是不容易从中看出规律性的东西，即函数关系不能一目了然。6.1互连网络的基本概念3.基本互连函数1）恒等互连函数如果相同输入/输出编号的端口对应互连，所实现的变换称为恒等变换。其表示式为：I(xn-1xn-2…x1x0)=xn-1xn-2…x1x0000001010011100101110111000001010011100101110111等式左边和右边端口编号的二进制编码完全相等。图形表示的恒等变换如右图所示：6.1互连网络的基本概念2）交换互连函数将输入端口编号的二进制码中的第0位取反，得到的互连函数称为交换互连函数。其表示式为：0000010100111001011101110000010100111001011101112---()1210101nnnnxxxxxxxxE-=……6.1互连网络的基本概念3）方体互连函数将输入端口编号的二进制码内的某一位（第k位）作取反操作，所得的值就是与之相连的输出端口编码。其表示式为：如果输入端口有N个，每个端口编号的二进制编码就有n=log2N位，k可以是其中的任意一位，所以方体变换也就可以有n种。按照被变换位的位置，分别可以表示成：C0，C1，…，Cn-1等。()011121011121xxxxxxxxxxxxxxCkkknnkkknnk-+---+--=…………6.1互连网络的基本概念比如，网络结点N=8时，允许有三种方体互连函数，他们分别是：()0120120xxxxxxC=()0120121xxxxxxC=()0120122xxxxxxC=(c)C2方体(a)C0方体000001010011100101110111(b)C1方体0000010100111001011101110000010100111001011101110000010100111001011101110000010100111001011101110000010100111001011101116.1互连网络的基本概念4）均匀洗牌（全混洗）互连函数均匀洗牌互连函数是将输入端分为数目相同的两个部分，分别与输出端进行均匀洗牌，即一个隔一个地与输出端相连。函数表示式为：()101320121-----=nnnnnxxxxxxxxxS……均匀洗牌互连函数σ0000010100111001011101110000010100111001011101116.1互连网络的基本概念循环移位也可以由左移改为右移，这时就成了逆均匀洗牌，这种方式可以看作是均匀洗牌的逆函数。函数表达式为：()121001211xxxxxxxxnnnn-----=S……逆均匀洗牌0000010100111001011101110000010100111001011101115）PM2I互连函数“加减2i”互连函数也称为循环移数互连函数，其移数的值为2的某一个幂次。其表示式为：式中，0≤X≤N-1，0≤i≤n–1，n=log2N，N为网络结点数。即：结点数为N的网络，其PM2I互连函数的个数为2n，（n=log2N）。()()NXXiimod2PM2I+=+()()NXXiimod2PM2I-=-6.1互连网络的基本概念按互连函数画出的图形如下图所示。012345670123456701234567012345670123456701234567(a)i=0(b)i=+1(c)i=+26.1互连网络的基本概念6.1互连网络的基本概念6）蝶式互连函数将输入端编号的二进制码的最高位和最低位对调，所得的二进制编码就是与之相连的输出端口编号，这种连接称为蝶式置换。其函数表示式为：()11200121----=nnnnxxxxxxxxB……0000010100111001011101110000010100111001011101116.1互连网络的基本概念7）反位序互连函数就是将输入端二进制编号的位序颠倒过来求得相应输出端的编号，其函数表示式为：()1n-20121---=n0nnxxxxxxxR……x16.1互连网络的基本概念8）混洗交换互连函数就是由全混洗互连函数与交换互连函数构成的复合函数，其函数表示式为：()102[0121----=nnnnxxxExxxxS……[E]]102--=nnxxx…6.1互连网络的基本概念例：设有64个处理器，其编号依次是0，1，2，…，63。当按照互连函数Exchange()4连接时,第21号处理器应与哪个处理器连接?解:设待求处理器的序号为i，表示为Pi，则Pi=Exchange(010101)4=010101=000101所以，第21号处理器应与第5号处理器连接。6.2静态互连网络静态互连网络是指在点到点之间使用直接链路，一旦设计成功，固定不变。即使在工作过程中，也不能用程序改变。系统中的每一个结点往往不止只连接一个相邻结点，即结点的度往往大于1。于是在信息传递时，就必须解决正确选择通信对象的问题。为此，每个结点中都必须设置“寻径器”，所以，这种网络又被称作基于寻径器的网络。6.2静态互连网络一.网络拓扑结构线性阵列012N-1N-2N-3网络直径：N-1环和带弦环0123456789101112131415（a）环形网单向连接时，网络直径：双向连接时，网络直径：N-1[N/2]网络直径越大，传输延时越大6.2静态互连网络环和带弦环0123456789101112131415(b)3度带弦环形网络0123456789101112131415(c)4度带弦环形网络0123456789101112131415（a）环形网网络直径为5网络直径为36.2静态互连网络循环移数网络这也是通过在环形网络结构上增加“弦”的方法使直径减小的改进网络。只是，加弦的规律是：从任一结点出发与距该结点距离为2的整数幂结点相连0123456789101112131415网络直径为26.2静态互连网络树形与胖树形二叉树结构网络二叉胖树结构网络6.2静态互连网络网格形和环形网格(c)环形网格(a)网格形(b)Illiac网6.2静态互连网络超立方体和带环立方体(c)带环立方体(a)3维立方体(b)4维立方体6.2静态互连网络二.静态网络特性表网络类型结点度d网络直径D链路数l等分带宽B对称性网络规格评注线性阵列2N-1N-11非N个结点环形2[N/2]N2是N个结点全连接N-11N(N-1)/2(N/2)2是N个结点二叉树32(h-1)N-11非树高h=[log2N]星形N-12N-1(N/2)非N个结点2D网络42(r-1)2N-2rr非r×r网络，N=r2Illiac网4r-12N2r非与N=r2的带弦环等效2D环网42(r/2)2N2r是r×r环网，N=r2超立方体nNnN/2N/2是N个结点，n=log2N带环立方体32k-1+(k/2)3N/2N/(2k)是N=k•2k个结点，环长k≥3k元n-立方体2nn(k/2)nN2kn-1是N=kn个结点6.3动态互连网络动态互连网络使用开关或者裁决器提供动态连接特性，在运行过程中由程序来确定具体的连接方式。一.总线互连方式总线互连方式是多处理机实现互连的一种最简单的方式。在总线互连方式中，多个处理机、存储模块及I/O部件等通过各自的接口部件连接在一条公共总线上，或多个计算机模块通过各自的接口部件与一条总线连接。6.3动态互连网络每一次总线只能用于一个源部件到一个或多个目的部件之间的数据传送。具有价格低、带宽较窄的特点。6.3动态互连网络二.交叉开关互连方式交叉开关互连方式通过开关把多个处理机、存储器模块或其他I/O设备连接在一起，形成一种网络结构。P1P2P16M1M2M16•网络中行线和列线交叉点有开关控制其接通与否。•每个开关只需两种状态：通与断。6.3动态互连网络三.多级网