互连网络_714008295.

互连与通信郑纬民[e-mail]清华大学计算机系2020/1/7互连与通信1互连网络的作用2静态网络3动态网络4通信问题1互连网络的作用定义：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。操作方式：同步通信（SynchronousCommunication)异步通信(AsynchronousCommunication)控制策略：集中控制(Centralizedcontrol)分布控制(Distributedcontrol)交换方式：电路交换(Circuitswitching)分组交换(Packetswitching)Wormhole交换(Wormholeswitching)网络拓扑结构：静态网络(Staticnetwork)动态网络(Dynamicnetwork)互连与通信1互连网络的作用2静态网络2.1静态网络的特点与指标2.2典型的静态网络3动态网络4通信问题2静态网络2.1静态网络的特点与指标1.静态网络的特点静态网络由点—点直接相连而成，这种连结方式在程序执行过程中不会改变。如果用图来表示，结点代表开关，边代表通信链路，则(1)结点间的链路无源，不能重构(2)开关元件与处理机相连(3)不直接相连结点间的通信需通过中间结点中转。2.静态网络的指标结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：结点度=入度+出度其中入度是进入结点的通道数，出度是从结点出来的通道数。距离：与两个结点之间相连的最少边数。网络直径：网络中任意两个结点间距离的最大值。网络规模：网络中结点数，表示该网络功能连结部件的多少。等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。结点间的线长：两个结点间的线的长度。对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。结点是否同构。通道是否有缓冲。2.2典型的静态网络1.线性阵列对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。N很大时，通信效率很低。线性阵列与总线的区别：线性阵列：允许不同的源结点和目的结点对并发使用系统的不同部分。总线：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据。2.环对N个结点的环，考虑相邻结点数据传送方向：双向环：链路数为N，直径N/2，度为2，对称，等宽度为2。比如KSR-1（1990）。单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。3.带弦环对上图中12个结点的带弦双向环，结点度为3：链路数为18，直径4（比如红色结点），度为3，不对称，等分宽度为2。结点度为4：链路数为24，直径3（比如红色结点），度为4，对称，等分宽度为8。度为3的带弦环度为4的带弦环4.全链接全链接是带弦环的一种特殊情形。全链接中的每个结点和其他结点之间都有单一的直接链路。如下图中8个结点的全链接：有28条链路，直径为1，度为7，对称，等分宽度为16。5.树形4层的二叉树一棵K层完全二叉树应有N=2K-1个结点，大多数结点的结点度为3，直径为2（K-1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1。由于结点度为常数，所以树是一种可扩展的系统结构。树形的扩展：带环树二叉胖树这两种结构都可以缓解根结点的瓶颈问题。6.星形星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N-1条链路，直径为2，最大结点度为N-1，非对称，等分宽度为1。Nr7.网格有N个结点的rr网格（其中)，有2N-2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。Nr网格的变形：a.Illiac网有N个结点的rr网格（其中)，有2N条链路，直径为r-1，结点度为4。Nrb.环形网（2D—Torus）有N个结点的rr网（其中)，有2N条链路，直径为2r/2，结点度为4，对称。c.搏动式阵列（SystolicArray）8.超立方体0-立方体1-立方体2-立方体3-立方体4-立方体一个n-立方体由N=2n个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构。例子：Intel的iPSC/1、iPSC/2、nCUBE9.带环立方体一个带环n-立方体由N=2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n2n个。直径通常为2n，结点度为3，对称。带环3-立方体10.k元n-立方体网络4元3-立方体（隐藏的结点与连接没有画出)在一个k元n-立方体网络中，结点的数目N=kn，即：NnNkknlog,其中，k称为基数（radix），n称为维数（dimension）。k元n-立方体的结点可以用基数为k的n位地址A=a0a1a2...an来表示，其中ai代表第i维结点的位置。传统的环网等价于4元2-立方体。互连与通信1互连网络的作用2静态网络3动态网络3.1互连函数3.2多级互联网络4通信问题3动态网络特点：网络的开关元件有源，链路可通过设置这些开关的状态来重构。只有在网络边界上的开关元件才能与处理机相连。3.1互连函数排列：N个数的每一种有确定次序的放置方法叫做一个N排列。置换：把一个N排列变成另一个N排列的变换叫做N阶置换。在有N个输入端和N个输出端的网络中，输入端和输出端的连接关系可以用置换来表示（输入端与输出端一一对应）。一些常见的置换方式可以用下面的函数表示：1.恒等函数)()(021021XXXXXXXXfknnknne其中，Xn-1Xn-2XkX0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：0000010100111001011101110000010100111001011101112.方体函数（cube0，cube1，…，cuben-1))()(021021XXXXXXXXcubeknnknnk方体函数是由n个互连函数组成，其中0kn。比如，n为3时，3-立方体各结点地址如下：YZX010011110000111001100101000001010011100101110111000001010011100101110111Cube0:)()(0120120XXXXXXcube01234567000001010011100101110111000001010011100101110111Cube1:)()(0120121XXXXXXcube01234567000001010011100101110111000001010011100101110111Cube2:)()(0120122XXXXXXcube012345670000010100111001011101110000010100111001011101113.洗牌函数01234567)()(102021nknknnXXXXXXXXSh洗牌函数的变形：a.均匀洗牌（Shuffle-Exchange)是洗牌函数与Cube0函数的组合。01234567：Cube0：洗牌b.第k个子洗牌)()(01110111kkknkkknkXXXXXXXXXXSh即最低k位循环左移一位。c.第k个超洗牌)()(01120121XXXXXXXXXXShknnknnknknnnk即最高k-1位循环左移一位。0000010100111001011101110000010100111001011101114.逆洗牌函数01234567)()(1100111XXXXXXShnn0000010100111001011101110000010100111001011101115.蝶式01234567)()(11200121nnnnXXXXXXXX6.PM2I函数（加减2i）共有2n个互连函数，对N个结点的网络为NnniNjNjjPMNjjPMiiii2log1010mod2)(2mod2)(2，，其中，例1：N=8（8个结点），则n=log28=3，所以：i=0，1，2；j=0，1，…，7。6个PM2I函数如下：PM2+0:(01234567）01234567PM2-0:(76543210）01234567PM2+1:(0246）（1357）01234567PM2-1:(6420）（7531）01234567PM22:(04）（15）（26）（37）0123456701234567例2：89101112131415上面的网络可以用四个PM2I函数表示。PM2+0:(012…15)PM2-0:(151413…0)PM22:(04）（15）（26）（37）(48）（59）（610）（711）(812）（913）（1014）（1115）(120）（131）（142）（153）3.2多级互连网络1.多级网络的三要素（1）开关单元：a个输入a个输出的开关单元记做aa的开关单元，其中，a是2的整数倍。常见的有22、44、88等。根据开关单元功能的多少，22又可以分为两功能和四功能开关。如下图所示：0101直送0101交叉0101上播0101下播（2）级间互连模式（InterStageConnection）：均匀洗牌、蝶式、多路洗牌（比如四路洗牌即是把牌平均分成4份，然后4堆分别进行均匀洗牌）、纵横开关（CrossSwitch)及立方体连结等。（3）控制方式级控制：每级只有一个控制信号单元控制：每个开关一个控制信号部分级控制：几个开关合用一个控制信号2.Ω网0123456701234567第0级第1级第2级Ω网的特点：开关单元：22四功能开关ISC：洗牌变换+恒等变换控制方式：采用单元控制方式。当目的地址编码从高位开始的第i位（从0开始）为0时，第i级的22开关的输入端与上输出端连接，否则输入端与下输出端连接。例子：UIUC的CedarIBM的RP3NYU的Ultracomputer0123456701234567第0级第1级第2级无阻塞的实现置换π1=（07642）（13）（5）0123456701234567第0级第1级第2级置换π2=（06473）（15）（2）在开关F、G、H、I和J上发生阻塞FGHJIΩ网的特点(2)：并不是所有的置换在Ω网中一次通过便可以实现。Ω网是阻塞网络：出现冲突时，可以采用几次通过的方法来解决冲突。0123456701234567第0级第1级第2级Ω网的广播功能：0018个输出端01第1级44开关构成的Ω网：多路洗牌如16输入4路洗牌：网路级数为log416=2234567891011121314150123456789101112131415第0级当采用kk开关元件时，则可以定义k路洗牌函数来构造更大的级数为logkn的Ω网络。3.蝶式网络（Butterflyswitchnetwork）蝶式网络的开关不允许广播功能，它实际上是Omega网的一个子集。两级6464的蝶式网络如下图所示：它采用16个88交叉开关构成，两级间采用8路洗牌连接。8888880...7888888第1级第0级8...1556...63.........078155663........................两级6464的蝶式网络4.其他连接方式总线交叉开关互连与通信1互连网络的作用2静态网络3动态网络4通信问题4.1基本术语与性能指标4.2寻径算法4.3虚拟通道与死锁4.4包冲突的解决4.5维序寻径4.6通信模式4通信问题4.1基本术语与性能指标1.消息、包和片消息（Message）：是在多计算机系统的处理结点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的