第9章互连网络.

1/114▲第9章互连网络2/114▲9.1互连函数9.2互连网络的结构参数与性能指标9.3静态互连网络9.4动态互连网络9.5消息传递机制3/114▲互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。结点：处理器、存储模块或其它设备。在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。SIMD计算机和MIMD计算机的关键组成部分。3大要素：互连结构，开关元件，控制方式。4/114▲变量x：输入（设x=0，1，…，N－1）函数f(x)：输出通过数学表达式建立输入端号与输出端号的连接关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系。（有时也称为置换函数或排列函数）9.1.1互连函数9.1互连函数5/114▲9.1互连函数互连函数f(x)有时可以采用循环表示即：（x0x1x2…xj-1）表示：f(x0)=x1，f(x1)=x2，…，f(xj-1)=x0j称为该循环的长度。设n=log2N，则可以用n位二进制来表示N个输入端和输出端的二进制地址，互连函数表示为：f（xn-1xn-2…x1x0）6/114▲9.1互连函数介绍几种常用的基本互连函数及其主要特征。1.恒等函数恒等函数：实现同号输入端和输出端之间的连接。I（xn-1xn-2…x1x0）=xn-1xn-2…x1x02.交换函数交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接。9.1.2几种基本的互连函数011121011121xxxxxxxxxxxxxxEkkknnkkknn7/114▲9.1互连函数主要用于构造立方体互连网络和各种超立方体互连网络。它共有n＝log2N种互连函数。（N为结点个数）当N＝8时，n＝3，可得到常用的立方体互连函数：012012201201210120120xxxxxxCubexxxxxxCubexxxxxxCube8/114▲9.1互连函数变换图形0123456701234567(a)Cube0交换函数01234567012345670123456701234567(b)Cube1交换函数(c)Cube2交换函数N=8的立方体交换函数9/114▲9.1互连函数立方体网络00001000101110111110011010/114▲9.1互连函数3.均匀洗牌函数均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。也称为混洗函数（置换）函数关系即把输入端的二进制编号循环左移一位。101320121nnnnnxxxxxxxxxσ11/114▲9.1互连函数互连函数（设为s）的第k个子函数：把s作用于输入端的二进制编号的低k位。互连函数（设为s）的第k个超函数：把s作用于输入端的二进制编号的高k位。例如：对于均匀洗牌函数第k个子函数：σ(k)(xn-1…xk┆xk-1xk-2…x0)＝xn-1…xk┆xk-2…x0xk-1即把输入端的二进制编号中的低k位循环左移一位。第k个超函数：σ(k)(xn-1xn-2…xn-k┆xn-k-1…x1x0)＝xn-2…xn-kxn-1┆xn-k-1…x1x0即把输入端的二进制编号中的高k位循环左移一位。12/114▲9.1互连函数下列等式成立：σ(n)(X)＝σ(n)(X)＝σ(X)σ(1)(X)＝σ(1)(X)＝X对于任意一种函数f(x)，如果存在g(x)，使得f(x)×g(x)=I(x)则称g(x)是f(x)的逆函数，记为f-1(x)。f-1(x)=g(x)逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号。13/114▲9.1互连函数互连函数逆均匀洗牌是均匀洗牌的逆函数当N=8时，有：σ(x2x1x0)＝x1x0x2σ(2)(x2x1x0)＝x2x0x1σ(2)(x2x1x0)＝x1x2x0σ-1(x2x1x0)＝x0x2x1121001211xxxxxxxxnnnnσ14/114▲9.1互连函数N=8的均匀洗牌和逆均匀洗牌函数N=8的均匀洗牌函数0123456701234567(a)均匀洗牌函数σ0123456701234567(d)逆均匀洗牌函数σ-10123456701234567(b)子洗牌函数σ(2)0123456701234567(c)超洗牌函数σ(2)15/114▲9.1互连函数4.碟式函数蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。第k个子函数β(k)(xn-1…xkxk-1xk-2…x1x0)＝xn-1…xkx0xk-2…x1xk-1把输入端的二进制编号的低k位中的最高位与最低位互换。第k个超函数β(k)(xn-1xn-2…xn-k+1xn-kxn-k-1…x1x0)＝xn-kxn-2…xn-k+1xn-1xn-k-1…x1x0把输入端的二进制编号的高k位中的最高位与最低位互换。11200121nnnnxxxxxxxxβ16/114▲9.1互连函数下列等式成立β(n)(X)＝β(n)(X)＝β(X)β(1)(X)＝β(1)(X)＝X当N=8时，有：β(x2x1x0)＝x0x1x2β(2)(x2x1x0)＝x2x0x1β(2)(x2x1x0)＝x1x2x0蝶式变换与交换变换的多级组合可作为构成方体多级网络的基础。17/114▲9.1互连函数0123456701234567(a)β＝ρ0123456701234567(b)β(2)＝ρ(2)0123456701234567(c)β(2)＝ρ(2)N=8的蝶式函数和反位序函数18/114▲9.1互连函数5.反位序函数反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。互连函数第k个子函数ρ(k)(xn-1…xkxk-1xk-2…x1x0)＝xn-1…xkx0x1…xk-2xk-1即把输入端的二进制编号的低k位中各位的次序颠倒过来。12100121nnnnxxxxxxxxρ19/114▲9.1互连函数第k个超函数ρ(k)(xn-1xn-2…xn-k+1xn-kxn-k-1…x1x0)＝xn-kxn-k+1…xn-2xn-1xn-k-1…x1x0即把输入端的二进制编号的高k位中各位的次序颠倒过来。下列等式成立ρ(n)(X)＝ρ(n)(X)＝ρ(X)ρ(1)(X)＝ρ(1)(X)＝X当N=8时，有：ρ(x2x1x0)＝x0x1x2ρ(2)(x2x1x0)＝x2x0x1ρ(2)(x2x1x0)＝x1x2x06.移数函数移数函数：将各输入端都错开一定的位置（模N）后连到输出端。函数式α(x)=（x±k）modN1≤x≤N-1，1≤k≤N-1(a)左移移数函数k＝20123456701234567(b)右移移数函数k＝2012345670123456721/114▲9.1互连函数7.PM2I函数P和M分别表示加和减，2I表示2i。该函数又称为“加减2i”函数。PM2I函数：一种移数函数，将各输入端都错开一定的位置（模N）后连到输出端。互连函数PM2+i(x)＝x＋2imodNPM2-i(x)＝x－2imodN其中：0≤x≤N－1，0≤i≤n－1，n＝log2N，N为结点数。PM2I互连网络共有2n个互连函数。22/114▲9.1互连函数当N＝8时，有6个PM2I函数：PM2+0：（01234567）PM2-0：（76543210）PM2+1：（0246）（1357）PM2-1：（6420）（7531）PM2+2：（04）（15）（26）（37）PM2-2：（40）（51）（62）（73）23/114▲9.1互连函数N=8的PM2I函数0123456701234567(a)PM2+00123456701234567(b)PM2+10123456701234567(c)PM2+2阵列计算机ILLIACⅣ采用PM2±0和PM2±n/2构成其互连网络，实现各处理单元之间的上下左右互连。0123456789101112131415用移数函数构成ILLIACⅣ阵列机的互连网络25/114▲9.1互连函数例9.1现有16个处理器，编号分别为0，1，…，15，用一个N=16的互连网络互连。处理器i的输出通道连接互连网络的输入端i，处理器i的输入通道连接互连网络的输出端i。当该互连网络实现的互连函数分别为：（1）Cube3（2）PM2+3（3）PM2-0（4）σ（5）σ(σ)时，分别给出与第13号处理器所连接的处理器号。26/114▲9.1互连函数解：（1）由，得Cube3（1101）=0101，即处理器13连接到处理器5。令Cube3（x3x2x1x0）=1101，得x3x2x1x0=0101，故与处理器13相连的是处理器5。所以处理器13与处理器5双向互连。（2）由PM2+3=j+23mod16，得PM2+3（13）=13+23=5，即处理器13连接到处理器5。令PM2+3（j）=j+23mod16=13，得j=5，故与处理器13相连的是处理器5。所以处理器13与处理器5双向互连。（3）由PM2-0（j）=j-20mod16，得PM2-0（13）=13-20=12，即处理器13连接到处理器12。令PM2-0（j）=j-20mod16=13，得j=14，故与处理器13相连的是处理器14。所以处理器13连至处理器12，而处理器14连至处理器13。012301233xxxxxxxxCube）（27/114▲9.1互连函数（4）由σ(x3x2x1x0)=x2x1x0x3，得σ(1101)=1011，即处理器13连接到处理器11。令σ(x3x2x1x0)=1101，得x3x2x1x0=1110，故与处理器13相连的是处理器14。所以处理器13连至处理器11，而处理器14连至处理器13。（5）由σ(σ(x3x2x1x0))=x1x0x3x2，得σ(σ(1101))=0111，即处理器13连接到处理器7。令σ(σ(x3x2x1x0))=1101，得x3x2x1x0=0111，故与处理器13相连的是处理器7。所以处理器13与处理器7双向互连。28/114▲1.网络通常是用有向边或无向边连接有限个结点的图来表示。2.互连网络的主要特性参数有：网络规模N：网络中结点的个数。表示该网络所能连接的部件的数量。结点度d：与结点相连接的边数（通道数），包括入度和出度。9.2互连网络的结构参数与性能指标9.2.1互连网络的结构参数29/114▲9.2互连网络的结构参数与性能指标进入结点的边数叫入度。从结点出来的边数叫出度。结点距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。网络直径D：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。等分宽度b：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。30/114▲9.2互连网络的结构参数与性能指标线等分宽度：B＝b×w其中：w为通道宽度（用位表示）该参数主要反映了网络最大流量。对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。31/114▲9.2互连网络的结构参数与性能指标评估互连网络性能的两个基本指标：时延和带宽1.通信时延指从源结点到目的结点传送一条消息所需的总时间，它由以下4部分构成：软件开销：在源结点和目的结点用于收发消息的软件所需的执行时间。主要取决于两端端结点处理消息的软件内核。通道时延：通过通道传送消息所花的时间。通路时延=消息长度/通道带宽通常由瓶颈链路的通道带宽决定。9.2.2互连网络的性能指标32/114▲9.2互连网络的结构参数与性能