互连网络的基本概念课件.ppt

互连网络的基本概念,互联网络是一种由开关元件按照一定的拓扑 结构和控制方式构成的网络，用来实现计算 机系统内部多个处理机或多个功能部件之间 的相互连接和信息交换。,SM1,SM2,SMm,IPMN,P1,Pn,IPCN,PION,Cn,LM,C1,LM,磁带部件,磁盘部件,打印机,终端,网络,IPMN：处理机-存储器网络IPCN：处理机间网络PION：处理机-I/O网络P：处理机SM：共享存储器LM：本地存储器C：高速缓冲存储器,一般多处理机系统的互连结构,互连函数,互连函数f(x)表示互连网络的输出端号和 输入端号之间的对应关系若x与f(x)是一对一的，则称为置换连接若一个x对应多个f(x)，则称为播送连接,互连函数的表示方法：函数表示法输入输出对表示法,图形表示法用输入输出的连线图表示变换关系,循环互连函数表示法 f(x0)=x1,f(x1)=x2,f(xj)=x0(x0 x1 x2 xj)j+1称为循环长度,基本互连函数,恒等置换,I(xn-1 xn-2x1 x0)=xn-1 xn-2x1 x0,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,n=3，N=8的恒等置换,交换置换,E(xn-1 xn-2x1 x0)=xn-1 xn-2x1 x0,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,n=3，N=8的交换置换,方体置换,将2n个输入端和输出端均分为2n-k组，每组2k个。每相邻两组输入与相应两组输出交叉对应。,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,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,n=3，N=8的方体置换,C0方体置换,C1方体置换,C2方体置换,均匀洗牌置换,(xn-1 xn-2xk+1 xk xk-1 x1 x0)=xn-2 xn-3xk+1 xk xk-1x1 x0 xn-1,将2n个输入端分为前后两半，前一半与偶数输出端依次相连，后一半与奇数输出端依次相连。,将输出端序列分为前后两组，每组轮流出牌所得序列即输入端序列。,子洗牌置换,(k)(xn-1 xn-2xk+1 xk xk-1 x1 x0)=xn-1 xn-2xk+1 xk-1x1 x0 xk,将2n个输入端分为2n-k-1组，每2k+1个输入为一组，组内进行均匀洗牌置换,超洗牌置换,(k)(xn-1 xn-2xn-k xn-k-1 xn-k-2 x1 x0)=xn-2xn-k xn-k-1 xn-1x1 x0 xk,(n-1)(x)=(n-1)(x)=(x),(0)(x)=(0)(x)=x,将2n个输入端分为2n-k-1组，低n-k-1位完全相同的输入为一组，组内进行均匀洗牌置换,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,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,均匀洗牌置换,子洗牌置换(1),超洗牌置换(1),逆均匀洗牌置换-1,n=3，N=8的洗牌置换,逆洗牌置换,-1(xn-1 xn-2xk+1 xk xk-1 x1 x0)=x0 xn-1 xn-2 xn-3xk+1 xk xk-1x1,将偶数输入端与前一半输出端依次相连，将奇数输入端与后一半输出端依次相连。,将输入端序列分为前后两组，每组轮流出牌所得序列即输出端序列。,蝶式置换,(xn-1 xn-2xk+1 xk xk-1 x1 x0)=x0 xn-2 xk+1 xk xk-1x1 xn-1,子蝶式置换,(k)(xn-1 xn-2xk+1 xk xk-1 x1 x0)=xn-1 xn-2xk+1 x0 xk-1x1 xk,蝶式置换连接中共有2n-1个恒等连接，2n-2对交叉连接。对于前一半输入端的偶数部分进行恒等连接，奇数部分对应后一半输出端的偶数部分。对于后一半输入端的奇数部分进行恒等连接，偶数部分对应前一半输出端的奇数部分。,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,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,蝶式置换,子蝶式置换(1),超蝶式置换(1),n=3，N=8的蝶式置换,(n-1)(x)=(n-1)(x)=(x),(0)(x)=(0)(x)=x,超蝶式置换,(k)(xn-1 xn-2xn-k xn-k-1 xn-k-2 x1 x0)=xn-k-1 xn-2xn-k xn-1 xn-k-2x1 x0,子蝶式置换连接中共有2n-1个恒等连接，2n-2对交叉连接。共分为2n-k-1组，每2k+1个输入/输出端为一组，组内进行蝶式置换,超蝶式置换连接中共有2n-1个恒等连接，2n-2对交叉连接。共分为2n-k-1组，低n-k-1位相同的为一组,位序颠倒置换,(xn-1 xn-2xk+1 xk xk-1 x1 x0)=x0 x1 xk-1 xk xk+1xn-2 xn-1,对于输入x=0或2n-1，输出仍为x，即恒等连接,子位序颠倒置换,(k)(xn-1 xn-2xk+1 xk xk-1 x1 x0)=xn-1 xn-2 xk+1 x0 x1xk-1 xk,超位序颠倒置换,(k)(xn-1 xn-2xn-k xn-k-1xn-k-2 x1 x0)=xn-k-1 xn-k xn-2 xn-1 xn-k-2x1 x0,(n-1)(x)=(n-1)(x)=(x),(0)(x)=(0)(x)=x,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,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,位序颠倒置换,子位序颠倒置换(1),超位序颠倒置换(1),n=3，N=8的位序颠倒置换,移数置换,(x)=(xk)mod N 0 xN 1kN,组内移数置换,(x)(n-1):r=(x)(n-1):r,(x)(r-1):0=(x)(r-1):0 k)mod 2r,共分为2n-r组，组内进行循环移数置换,加减2I置换,PM2+i(x)=(x+2i)mod N 0 xN 0 i n,PM2-i(x)=(x-2i)mod N 0 xN 0 i n,1k2r 1r n,(n)(x)=(x),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,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,左移移数置换k=2,n=3，N=8的移数置换,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,右移移数置换k=2,组内左移移数置换k=1 r=2,组内右移移数置换k=1 r=2,左移移数置换 k=2(0 2 4 6)(1 3 5 7),右移移数置换 k=2(6 4 2 0)(7 5 3 1),组内左移移数置换 k=1 r=2(0 1 2 3)(4 5 6 7),组内右移移数置换 k=1 r=2(3 2 1 0)(7 6 5 4),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),PM2+2=(0 4)(1 5)(2 6)(3 7),PM2-2=(4 0)(5 1)(6 2)(7 3),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,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,i=0,n=3，N=8的加减2I置换,i=+1,i=+2,互连网络的结构参数与性能指标,互连网络的结构参数,网络规模 网络中的结点数。表示网络所能连接的部件个数。,结点度 一个结点射入或射出的边数。在单向网络中，入射边的数目称为入度，出射边的数 目称为出度。结点度为入度和出度之和。在无向网络中，结点度为与结点相连的边数。,结点距离 两结点间相连的最少边数。,网络直径 互连网络中任意两结点间距离的最大值。,网络对剖宽度 一个网络被切分为结点数相等的两半时，沿切口 的最少边数。,网络对称性 若从网络的任意结点来看，网络的结构都是相同的，则称该网络是对称网络。,网络可扩展性 在网络拓扑性能保持不变的情况下，可扩充结点的 能力。,互连网络的传输性能参数,A,B,机器A,机器B,机器A发送数据的步骤：,机器A应用程序,待发送数据,机器A操作系统缓冲区,机器A操作系统根据要发送的数据计算检查和，并 把它放在消息中，同时启动超时计数器,机器A操作系统缓冲区,网络接口硬件,消息,若收到机器B的回答信号则释放缓冲区中消息；若超时计数器超时还未收到回答信号则重发消息,操作系统通知硬件开始发送消息,等待来自机器B的回应,机器B接收数据的步骤：,网络接口硬件,机器B操作系统缓冲区,消息,机器B操作系统根据接收到的数据计算检查和。若计算出的检查和与发送过来的匹配，向接收方发 出回答信号；若不匹配，则删除消息,若数据通过检查：,机器B操作系统缓冲区,数据,用户地址空间,启动应用程序继续执行,频宽 互连网络传输信息的最大速率。MB/s,传输时间发送方传输时间：发送方从开始发送第一位信息 起到把消息完全发送至网络所需时间接收方传输时间：接收方从接收到第一位信息起 到完全接收到消息的时间,“飞行”时间 消息的第一位信息到达接收方所需时间。包括网 络中转发或其他硬件的时间延迟,传输时延 发送方发送第一位信息到接收方完全接收到消息 所需时间“飞行”时间+传输时间,发送方开销 发送方在缓冲区中准备好待发送消息并送至网络 接口硬件的时间,接收方开销 接收方把消息从网络接口硬件取至缓冲区并拷贝 至用户地址空间的时间,总时延,总时延=发送方开销+“飞行”时间+,+接收方开销,传输时间,总时延=发送方开销+“飞行”时间+,+接收方开销,总时延=发送方开销+传输时延+接收方开销,发送开销,传输(发送)时间,接收开销,传输(接收)时间,例：假设一个网络的频宽为10Mb/s，发送方开销为230us，接收方开销为270us，如果两台机器相距100米，现要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，总时延为多大？（光速为299792.5km/s，信号在导体中的传递速 度大约是光速的50%）,=270us+230us+0.67us+800us=1301us,T=270us+230us+,1000*106us,299792.5km/s*0.5,+,=270us+230us+6671us+800us=7971us,互连网络的性能指标,通信时延从源结点到目的结点传送一条消息所需的总时间软件开销（取决于收发端的软件内核）在源结点和目的结点用于收发消息的软件所需的执行 时间,通道时延（取决于瓶颈链路的通道带宽）通道时延=消息长度/通道带宽选路时延（取决于传送路径上的结点数）消息在传送路径上进行选路决策所需的时间开销竞争时延（取决于网络的传输状态）多个消息同时在网络中传送时解决或避免网络资 源争用冲突所需时间,网络时延 网络时延=通道时延+选路时延 与程序行为和网络传输状态无关,端口带宽 网络中从任意一个端口单位时间传送到其他端 口的最大信息量。（b/s或B/s）,聚集带宽 网络从一半结点到另一半结点，单位时间传送 的最大信息量。,对剖带宽 通过最小对剖平面的所有边的单位时间传送的 最大信息量。,静态互连网络,各结点间有专用的连接通路，且在运行中不能改变连接的网络。,线性阵列,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,线性阵列,端结点 1,N-1,N-1,1,否,N,线性阵列允许不同的结点对并发使用系统的不同部分（通道）,环,网络类型,结点度 d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,环,2,N,2,是,N,带弦环,把环中不直接相连的每两个距离相等的结点用一条边连接起来,度为3的带弦环,度为4的带弦环,循环移数网络,将环上每个结点与其距离为2整数幂的结点间增加一条附加链路而构成。设网络规模为N=2n，则结点x与以下结点有链路相连：(x2i)mod 2n(0i n),0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,+2i i=0,1,.,n-1 正度=n,-2i i=0,1,.,n-2 负度=n-1,网络类型,结点度 d,网络直径 D,链路数l,对称性,网络规格,循环移数网络,2n-1,n/2,2n-1(2n-1),是,N=2n,等分宽度 b,2n-1n,全连接网络,网络类型,结点度 d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,全连接,N-1,1,N(N-1)/2,是,N,(N/2)2,N/2,N/2,N/2,N/2,*,树形网络,拓扑结构是一棵完全二叉树。设有N个结点，共k层，则N=2k-1优点：可扩展性好 缺点：直径长,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,树形,叶结点1根结点2分支结点3,2(k-1),N-1,1,否,N=2k-1,星形网络,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,星形,根结点N-1叶结点1,2,N-1,N/2,否,N,胖树形网络,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,胖树形,第j层结点 3(k-j)+1 2j k根结点2k-2,j=1,j=2,j=3,j=4,2(k-1),k-1,否,N=2k-1,2k+1-2k-2,缓解通向根结点的通信瓶颈,l=,网格形网络,网络类型,结点度d,网络直径 D,链路数l,等分宽度b,对称性,网络规格,2D网格,k维网格,角结点 2边结点 3内结点 4,内结点 2k,2(n-1),k(n-1),N=n2,N=nk,否,否,2N-2n,knk-1(n-1),n,nk-1,三维网格形网络的内结点度为6，边结点度为4，角结点度为3，面内结点度为5。,A,B,A,B,Illiac网络,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,Illiac网络,4,n-1,2N,2n,否,N=n2,环网形网络,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,2D环网,4,2,n/2,2N,2n,是,N=n2,搏动式阵列,网络类型,结点度d,网络直径D,链路数l,等分宽度 b,对称性,网络规格,搏动式 阵列,左右两角结点2上下两角结点3边结点4内结点6,2(n-1),3n2-4n+1,2n-1,否,N=n2,超立方体,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,超立方体,n,n,nN/2,N/2,是,N=2n,环中有K个结点,带环立方体,k/2,下一维指针,环中下一结点,环中上一结点,k/2,K维转发,d=(2k-1)+k/2,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,带环k-立方体,3,2k-1+,k/2,3N/2,N/(2k),是,N=k2k(k3),A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,O3,O2,A1,O2,k元n-立方体,网络类型,结点度d,网络直径 D,链路数l,等分宽度 b,对称性,网络规格,k元n-立方体,2n,nN,n,k/2,2kn-1,是,N=kn,动态互连网络,动态互连网络可通过设置有源开关，从而根据需要借助控制信号对连接通路加以重新组合，实现所要求的通信模式。,多处理机总线互连,用一组导线和插座将处理机、存储模块和各种外围设备互连起来，总线上的各模块需要通信时，发出申请，由总线仲裁逻辑对多个请求进行仲裁，进行总线服务分配。总线上各模块通过争用或时分方式获得总线服务。价格较低，带宽较窄,磁盘和磁带部件,打印机或绘图仪,网络（以太网等）,总线互连的缺点 带宽有限 没有冗余链路 可扩展性有限 层次总线的可扩展层次数有限,交叉开关互连,大大展宽了互连传输频带，提高了系统的效率；但交叉开关设备量过大，成本过高（一般n16）,采用按空间分配的机制,多级互连网络,ISC,ISC,ISC,a+1,a,2a-1,an-a,an-a+1,an-1,b+1,b,2b-1,bn-b+1,bn-b,bn-1,an-1个,ban-2个,bn-1个,级1,级2,级n,多级互连网络把重复设置的多套动态单级网络串联起来，单级网络级间采用固定的级间连接模式，通过动态控制各单级网络的开关状态实现多级互连网络的输入端和输出端之间所需要的连接,开关模块,通常取a=b=2k（k1）,2功能开关,4功能开关,级间连接模式 多级互连网络中上一级开关模块的输出端和 下一级开关模块的输入端相互连接的模式 可用互连函数表示,控制方式互连网络拓扑结构可动态重构：可通过控制信号动态控制开关模块的状态来实现所要求的互连,级控方式 对同一级的所有开关用一个控制信号控制 组控方式 对第i级的开关分为i+1组，每组用一个控制 信号控制（0i n-1）单元控制方式 每一个开关有自己单独的控制信号,多级互连网络的分类 阻塞网：在一对以上输入端和输出端可同 时实现互连的网络中，可能发生2个或2个 以上的输入端对输出端的连接要求产生路 径争用冲突。所用开关数量少，延时不长，路径控制较 简单。,可重排非阻塞网络：如果重新安排现有的 连接，就可实现无阻塞的任意端点对的连 接，从而满足一个新的端点对的连接请求。多级非阻塞网络：不必改变原来的开关状 态就可满足任意输入端和输出端的连接请 求。交叉开关网络为单级非阻塞网,Omega网络,N*N；共n=log2N级开关，从输入端至输 出端依次为Kn-1,K1,K0 采用2*2的4功能开关 每级N/2个开关，共m=(N/2)log2N个开关，可实现4m种置换连接,采用单元控制方式,级间连接从输入端至输出端依次为Cn,C1,C0;其中，CnC1为均匀洗牌置换，C0为恒等置换=EEEI=(E)n（E为开关级在开关控制方式下实现的交换置换）,K2,K1,K0,C3,C2,C1,C0,Omega网络(N=8),采用终端标记寻径（D标记寻径）xn-1xn-2x1x0yn-1yn-2y1y0(D),xn-1xn-2x1x0,xn-2xn-3x1x0 xn-1,Kn-1,xn-2xn-3x1x0 xn-1,Cn-1,xn-3x1x0 xn-1xn-2,xn-3x1x0 xn-1xn-2,x0 xn-1xn-2x1,xn-1xn-2x1x0,xn-1xn-2x1x0,xn-1xn-2x1x0=yn-1yn-2y1y0,yi=0，第i级即Ki开关级上对应开关的输入端与开关的上输出端相连；,yi=1，第i级即Ki开关级上对应开关的输入端与开关的下输出端相连；,可能产生争用开关状态的冲突,若两对连接的源端xi-1,x0,xn-1,xi+1均相同，xi不同，终端xi(yi)相同，则该两对连接在Ki开关级的xi-1,x0,xn-1,xi+1开关上产生冲突例如:000101与100110在K2级开关0上产生争用下输出端的冲突；101100与011101在K1级开关3上产生争用上输出端的冲突；在实现源与终端结点各不相同的置换连接时，如果不产生冲突，所有开关均不会出现上播或下播的状态；,例：在N=8的Omega网络中采用终端标记寻径法，至少要连接几次才能实现蝶式置换所要求的连接？,第一次实现00,14,22,36第二次实现41,55,63,77,00,41 争用K2级0开关的上输出端，从而争用K1级0开关的上输出端；14,55 争用K2级1开关的下输出端，从而争用K1级3开关的上输出端；22,63 争用K2级2开关的上输出端，从而争用K1级0开关的下输出端；36,77 争用K2级3开关的下输出端，从而争用K1级3开关的下输出端,K2,K1,K0,C3,C2,C1,C0,例：试给出一个简单的寻径算法实现Omega网络的任一源端对所有终端的广播连接。,仅在播送连接中才可能出现开关的上播和下播状态,K2,K1,K0,C3,C2,C1,C0,例：用一个N=8的三级Omega网络连接8个处理 机(P0P7)，8个处理机的输出端分别依序连 接Omega网络的8个输入端07，8个处理机 的输入端分别依序连接Omega网络的8个输 出端07。如果处理机P6要把数据播送给处 理机P0P4，处理机P3要把数据播送给处理 机P5P7。那么，Omega网络能否同时为它 们的播送要求实现连接？请画出实现播送 的Omega网络的开关状态图。,STARAN网络,N*N；共n=log2N级开关，从输入端至输 出端依次为K0,K1,Kn-1 采用2*2的2功能开关，直送和交叉 每级N/2个开关，共m=(N/2)log2N个开关，共可实现2m种置换连接,采用级控方式或组控方式,级间连接从输入端至输出端依次为C0,C1,Cn;其中，C1Cn为逆洗牌置换，C0为 恒等置换 S=IE-1E-1E-1=(E-1)n（E为开关级在开关控制方式下实现的交换置换）,K0,K1,K2,C0,C1,C2,C3,STARAN网络(N=8),级控方式及交换置换,xi-1x0 xn-1xi,Ki,xi-1x0 xn-1xi,可实现N种置换,x2x1x0,4组2元,4组2元+2组4元,2组4元,2组4元+1组8元,4组2元+2组4元+1组8元,4组2元+1组8元,1组8元,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,x2x1x0,例如：实现2组4元交换,F=(000),F=(001),F=(010),F=(011),F=(100),F=(101),F=(110),F=(111),组控方式及移数置换,组控信号F中有m=n(n+1)/2个位信号，可 实现2m种置换 若n=3，F=(f23 f22 f21 f12 f11 f0),f23f22f21f12f11f0,001011,011110,111000,000011,000110,000001,000000,01234567,12345670,23456701,45670123,12305674,23016745,10325476,01234567,组控信号,输入端号,移数功能,移 1mod 8,移 2mod 8,移 4mod 8,移 1mod 4,移 2mod 4,移 1mod 2,不移 恒等,K0,K1,K2,C0,C1,C2,C3,例如：实现移2模8置换,移1模2,移1模4,移2模4,恒等,移1模8,移2模8,移4模8,例：设有一四级立方体网络，对于下述连接分别 写出网络的级控信号和互连函数。4组4元交换 4组4元交换+1组16元交换,F=f3f2f1f0=0011,F=f3f2f1f0=1100,间接二进制n方体网络,N*N；共n=log2N级开关，从输入端至输出端 依次为K0,K1,Kn-1 采用2*2的2功能开关，直送和交叉 每级N/2个开关，共m=(N/2)log2N个开关，可 实现2m种置换连接 级间连接从输入端至输出端依次为C0,C1,Cn;其中，C1Cn-1为子蝶式置换，C0为恒等置换，Cn为逆洗牌置换 C=IE(1)E(2)E(n-1)E-1（E为开关级在开关控制方式下实现的交换置换）,采用单元控制方式,K0,K1,K2,C0,C1,C2,C3,间接二进制n方体网络(n=3),xn-1xn-2x1x0,K0,C1,K1,xn-1xn-3xn-2x0 xn-2,xn-2xn-3x0 xn-1,Kn-1,xn-2xn-3x0 xn-1,xn-1xn-2x1x0=yn-1yn-2y1y0,(S)xn-1xn-2x1x0yn-1yn-2y1y0(D),xn-1xn-2x1x0,xn-1xn-2x2x1x0,xn-1xn-2x2x0 x1,xn-1xn-2x2x0 x1,xn-1xi+1xi-1x0 xi,Ki,xn-1xi+1xi-1x0 xi,Cn-2,终端标记寻径（D标记寻径）,用yi控制Ki级上所到达开关的状态：若yi=0，从该开关的上输出端输出；若yi=1，从该开关的下输出端输出。,若两个源结点序号的xi+1xn-1，x0 xi-1均相同，xi不同，即到达Ki级同一开关(开关号为xn-1xi+1xi-1x0)的不同输入端。若yi相同，则产生对该开关的上(yi=0)或下(yi=1)通道的争用冲突,上控法,用到达开关级Ki相应开关的上输入端(xi=0)的终端标记yi来控制该开关的状态：yi=0，该开关为直送状态；yi=1，该开关为交叉状态。,若到达Ki级某开关的下输入端，则遵守由到达该开关上输入端的某对连接所确定的状态。若遵守状态后导致本连接xi=yi（即两个终结点序号yi相同），则产生冲突，不能同时实现此两对连接。,例1：实现连接05，12，26，33，44，57，61，70。采用上控法和T标记寻径法是否会发生阻塞？,12与26争用K1级0开关的下输出端，并导致K2级2开关为上播状态；,44与70争用K1级2开关的上输出端，并导致K2级0开关为下播状态；,K0,K1,K2,C0,C1,C2,C3,采用上控法,K0,K1,K2,C0,C1,C2,C3,采用T标记寻径法,例2：实现连接03，16，24，31，42，57，65，70。采用上控法和T标记寻径法是否会发生阻塞？,不发生阻塞。,K0,K1,K2,C0,C1,C2,C3,采用上控法,Delta网络,an*bn；开关从输入端至输出端依次为K1,K2,Kn 采用a*b的开关 Ki级开关的开关数为an-ibi-1(1i n)，Ki 的输入端数为an-i+1bi-1，输出端数为an-ibi,级间连接从输入端至输出端依次为C0,C1,Cn;Ci的输入和输出端数均为an-ibi。C0和Cn为恒等连接，其余级间连接均采 用q洗牌置换 q洗牌置换：将qr张牌分成q组，每组r 张，洗牌时先将所有组的第一张牌顺序 放在前q个位置，再将所有组的第二牌顺 序放在接下来的q个位置，直到各组牌全 部取完为止。,在Ci级中，对an-ibi个输入端分为an-ibi-1组，每组b个进行q洗牌置换,采用单元控制方式,采用终端标记寻径方法来实现源端对终端 的连接,0,1,2,3,0,1,2,4,5,6,7,3,4,5,8,9,10,11,6,7,8,12,13,14,15,9,10,11,00,01,02,10,11,12,20,21,22,K1,K2,C0,C1,C2,例：17,42*32的Delta网络,x经开关Ki+1后变为：x/a*b+wi+1(0in,0wi+1b)x经级间连接Ci后变为：(x mod b)*an-ibi-1+x/b(0 in),S=s0*a0+s1*a1+sn-1*an-1,D=d0*b0+d1*b1+dn-1*bn-1,S,(s1*a0+sn-1*an-2)*b+w1,(s1*a0+sn-1*an-2)+w1*an-1,(s2*a0+sn-1*an-3+w1*an-2)*b+w2,(s2*a0+sn-1*an-3+w1*an-2)+w2*an-2b,(sn-1*a0+w1*a1+w2*ab+wn-2*abn-3)*b+wn-1,(sn-1*a0+w1*a1+w2*ab+wn-2*abn-3)+wn-1*abn-2,(w1+w2*b1+wn-2*bn-3+wn-1*bn-2)*b+wn,=d0*b0+d1*b1+dn-2*bn-2+dn-1*bn-1,=wn*b0+w1*b1+wn-2*bn-2+wn-1*bn-1,(w1+w2*b1+wn-2*bn-3+wn-1*bn-2)*b+wn,用di控制开关级Ki(1in)，d0控制开关级Kn,例：比较4*9的单级交叉开关和用二级2*3的交叉开关组成的4*9的Delta网络，比较这两种互连网络的开关设备量。,4*9单级交叉开关的开关数为36，每套开关内部有4选1的多路转换逻辑和可对4个请求信号进行仲裁的仲裁模块。二级22*32的Delta网络的开关数为30，每个开关只需2选1的多路选择器和可对2个请求信号进行仲裁的仲裁模块。,Benes二进制置换网络,N*N；共2log2N=2n级开关，从输入端至输 出端依次为K0,K1,Kn-1,Kn,K2n-1 采用2*2的2功能开关，直送和交叉 每级N/2个开关，共N(log2N)个开关,级间连接从输入端至输出端依次为C0,C1,Cn,Cn+1,C2n;其中，C0,Cn,C2n是 恒等置换;C1Cn-1为逆子洗牌置换(Ci=(n-i)-1 1i n-1);Cn+1C2n-1为子洗牌置换(Ci=(i-n)n+1i 2n-1)=IE(n-1)-1 E(n-2)-1E(1)-1EIE(1)E(n-1)EI（E为开关级在开关控制方式下实现的交换置换）,采用单元控制方式,可将Kn-1和Kn级合并为一个开关级,K0,K1,K2,K3,K4,K5,C0,C1,C2,C3,C4,C5,C6,d0,d1,d2,d2,d1,d0,(2)-1,(1)-1,(1),(2),I,I,I,采用改进的终端标记控制算法：上控法或 下控法,上控法：用到达开关级Ki相应开关的上输入端的终端标记yi来控制该开关的状态：yi=0，该开关为直送状态；yi=1，该开关为交叉状态,下控法：用到达开关级Ki相应开关的下输入端的终端标记yi来控制该开关的状态：yi=0，该开关为交叉状态；yi=1，该开关为直送状态,为可重排非阻塞网络，可实现N!种源终端 间的置换连接。但并不是所有置换连接都 能一次实现，每一对源和终结点的连接至 少存在两条路径，当一条走不通时可选择 另一条,又称为全排列网络,N个输入端和N个输出端的置换连接共有N！种。,采用上控法若通过Ki(0in-2)级某开关后使得xi=yi，称为产生了变异，若该变异能在K2n-1-i级恢复，则称为变异被修正。若通过Ki(ni)级某开关后使得xi=yi，也称产生了变异，且该变异是不能修正的。若通过Kn-1级某开关后使得xn-1=yn-1，也称产生了变异，且该变异是不能修正的。,所谓冲突情况是:当某条路径P经过在某级I的某开关E时,它自己的出路被别的路径所占用。这样，只好走另外的那条出路。（图中：虚线为应走路径，实线为实走路径）,冲突,上图,下图,修正,某条路径P在某级I的开关E上的冲突意味着：它本应该作“交换”却没有“交换”（上图情况）；或它本不应该作“交换”而却作了“交换”（下图情况）。这种情况我们称为“变异”，这样，有冲突必有变异。那么，怎样去“修正”这种变异？Benes二进制置换网络是左右对称的，之所以这样设计，是为了在左边发生的变异而在右边去修正这种变异。只是这种修正应该在与左边相对称的开关级上进行。,例1：实现位序颠倒置换,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,K0,K1,K2,K3,K4,K5,C0,C1,C2,C3,C4,C5,C6,d0,d1,d2,d2,d1,d0,例2：实现置换00,11,27,33,44,56,65,72,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,K0,K1,K2,K3,K4,K5,C0,C1,C2,C3,C4,C5,C6,d0,d1,d2,d2,d1,d0,互连网络的消息传递机制,数据传递的方式：共享变量方式 共享存储器多处理器系统消息传递方式 分布式存储器多处理器系统,所有的处理器共享一个统一编址的物理存储器，它可以是集中式的，也可以分布在各个处理器结点中,每个处理器只能对本地存储器直接进行读/写操作,消息格式,消息：由任意数目的长度固定的包组成，是结 点间通信的基本单位,包：包含寻径目的地址的结点间通信的基本单 位；可异步传输，每个包有一个包序号，以便在接收方进行包重组,片：将包分成等长的片，寻径信息（源地址和 目的地址）和序号形成头片，其余是数据片,消息寻径方式,消息寻径方式：消息从发送地传送到目的 地对路径的选取方式,存储转发寻径,在网络中，包是基本传输单位 网络中每个结点有一个包缓冲区 包从源结点经过一系列中间结点到达目的结点 当一个包到达一个中间结点后，首先被存入该结 点的包缓冲区，当所要求的输出通道和接收结点 的包缓冲区可使用时，才将包传送给下一结点,设包长为m，包传送经过l条链路，ts为启动时间（打包，执行寻径算法，建立通信条件的时间），th为结点延迟时间（包头穿越网络中两直接相连的处理器所需时间），tw为传输每个字的时间（链路带宽的倒数）。,把包进一步分成更小的片，中间结点只需很小的片缓冲区，在与结点相连的硬件寻径器中有片缓冲区，一旦接收到头片，就由头片中的寻径信息进行寻径，把头片传送至下一个结点，同时包中的所有片以流水方式在寻径器中顺序传送,切通寻径（虫蚀寻径）,包由头片和数据片组成，头片中含有目的地 址，所有数据片必须跟着头片。不同的包 可交替传送，但同一个包的片必须顺序传送，否则可能送至错误的目的地 用包的头片开辟出一条路径，包中的片按头 片开辟的路径以流水方式在网络中向前“蠕动”当消息的头片到达结点A的寻径器后，寻径器 根据头片的寻径信息立即作出路由选择：如果 所选择的通道空闲且所选择的结点B的片缓冲 区可用，则该头片不必等待，直接通过结点A 传向结点B,如果所选择的通道忙或结点的片缓冲区不可用，则包的所有片必须在所占用各结点的片缓冲区中等待，直到两者成为可用为止。被阻塞消息不从网络中移去，片也不放弃它所占有的结点和通道,由于 tw thtcomm(SF)=ts+mtw*ltcomm(CT)=ts+mtw,存储转发网络的消息传送延时与源和目的之间的距离成正比；切通网络的消息传送延时与源和目的之间的距离无关。,寻径方法,算术寻径法（维序寻径法）,属于确定寻径，即寻找的传输路径是预先唯一确定的，与网络的状态无关，路径完全由源和目的地址确定。维序寻径法适用于网格网，按结点坐标维的顺序选择通信链路,X-Y寻径法,适用于二维网格，任何包在网络中任何一个结点先沿X维方向传送，在沿Y维方向传送,Begin 沿X维将包向左或向右传送至与目的结点列号相同的结点；沿Y维将包向上或向下传送至目的结点。End,S2,D4,D3,S1,D2,S3,S4,D1,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,8*8二维网格网中的X-Y寻径,例：在一个8*8的二维网格中，有4对包传输要求：S1(2,2)D1(6,6)，S2(0,4)D2(3,6)，S3(4,1)D3(1,5)，S4(5,2)D4(1,3)。是否会发生包争用传送链路或结点包缓冲区的冲 突？,解决包冲突的方法：阻塞流控制法在虫蚀寻径中出现包冲突时，包1继续传输，包2被阻塞不再前进，但没有被扬弃，等资源可用时再继续传输,扬弃并重发法出现包冲突时，包1继续传输，包2被扬弃，并由源结点重发包2,包1,包2,绕道传送法出现包冲突时，包1继续传输，包2选择另一路径绕道传输,迂回通道,输出通道,包1,包2,多维维序寻径法,适用于多维网格，任何包在网络中任何一个结点依次沿各维方向传送,E-立方寻径法,S(sn-1s1s0)D(dn-1d1d0),Begin for i=0 to n-1 do ri=si di end for i=0,V=S while in do if ri=1 then 从当前结点V沿维i传送一步到结点V 2i end if i=i+1 end whileEnd,00000,00100,11011,00101,00111,00011,01011,例：在5维超立方体中，包从S=00100传送到