计算机系统结构第5章互连网络.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,n=3，N=8的恒等置换,交换置换,E(xn-1 xn-2x1 x0)=xn-1 xn-2x1 x0,n=3，N=8的交换置换,( 0 1 ) ( 2 3 ) ( 4 5 ) ( 6 7 ),方体置换,将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方体置换,( 0 1 ) ( 2 3 ) ( 4 5 ) ( 6 7 ),( 0 2 ) ( 1 3 ) ( 4 6 ) ( 5 7 ),( 0 4 ) ( 1 5 ) ( 2 6 ) ( 3 7 ),均匀洗牌置换,(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,蝶式置换连接中共有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,子蝶式置换连接中共有2n-1个恒等连接，2n-2对交 叉连接。 共分为2n-k-1组，每2k+1个输入/输出端为一组， 组内进行蝶式置换,子蝶式置换,(k)(xn-1 xn-2xk+1 xk xk-1 x1 x0) =xn-1 xn-2xk+1 x0 xk-1x1 xk,超蝶式置换,(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组，低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 0xN 1kN,组内移数置换,(x)(n-1):r = (x) (n-1):r,(x)(r-1):0 = (x) (r-1):0 k) mod 2r,共分为2n-r组，组内进行循环移数置换,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,加减2I置换,PM2+i(x)=(x+2i) mod N 0xN 0 i n,PM2-i(x)=(x-2i) mod N 0xN 0 i n,左移移数置换 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的带弦环,结点度 3 链路数 3N/2 网络直径 4 等分宽度 4 对称性 否 网络规模 N,度为4的带弦环,结点度 4 链路数 4N/2 网络直径 3 等分宽度 N/2+2 对称性 是 网络规模 N,循环移数网络,将环上每个结点与其距离为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个结点，共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,A,B,环网形网络,网络类型,结点度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-3x1x0xn-1,Kn-1,xn-2xn-3x1x0xn-1,Cn-1,xn-3x1x0xn-1xn-2,xn-3x1x0xn-1xn-2,x0xn-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-1x0xn-1xi,Ki,xi-1x0xn-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),f23 f22 f21 f12 f11 f0,0 0 1 0 1 1,0 1 1 1 1 0,1 1 1 0 0 0,0 0 0 0 1 1,0 0 0 1 1 0,0 0 0 0 0 1,0 0 0 0 0 0,0 1 2 3 4 5 6 7,1 2 3 4 5 6 7 0,2 3 4 5 6 7 0 1,4 5 6 7 0 1 2 3,1 2 3 0 5 6 7 4,2 3 0 1 6 7 4 5,1 0 3 2 5 4 7 6,0 1 2 3 4 5 6 7,组 控 信 号,输 入 端 号,移数 功能,移 1 mod 8,移 2 mod 8,移 4 mod 8,移 1 mod 4,移 2 mod 4,移 1 mod 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-2x0xn-2,xn-2xn-3x0xn-1,Kn-1,xn-2xn-3x0xn-1,xn-1xn-2x1x0 =yn-1yn-2y1y0, ,(S) xn-1xn-2x1x0yn-1yn-2y1y0 (D),xn-1xn-2x1x0,xn-1xn-2x2x1x0,xn-1xn-2x2x0x1,xn-1xn-2x2x0x1,xn-1xi+1xi-1x0xi,Ki,xn-1xi+1xi-1x0xi,Cn-2,终端标记寻径（D标记寻径）,用yi控制Ki级上所到达开关的状态：若yi=0，从该 开关的上输出端输出；若yi=1，从该开关的下输出 端输出。,若两个源结点序号的xi+1xn-1，x0xi-1均相同，xi 不同，即到达Ki级同一开关(开关号为xn-1xi+1 xi-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,多级PM2I网络,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,入端,出端,PM2+2,PM2-2,PM2+1,PM2-1,PM2+0,PM2-0,2级,1级,0级,N=8的多级PM2I网络,就i级而言（0=i=n-1,0=i=2），每个输入端j（ 0=j=2 ）都是三根线分别输出端（j-2i）mod N，j和（j+2i）mod N，图中分别用蓝线、黑线和红线表示。 第0级完成的是PM2+0,第1级完成的是PM2+1,第2级完成的是PM2+2。 从一个单元到另一个单元的路由有多条路径可供选择，如从6号处理单元到4号处理单元，可以经过6-6-4-4，也可6-2-4-4，显然，在多级网络中提供了冗余通路，有利于提高系统的可靠性。 当各级处理单元均采用单元控制时，这种多级PM+I网络成为了强化数据交换网络(augmented data manipulator，简称ADM网络),基准网络,N=8的基准网络 特点： 1）采用直送和交叉的22的功能开关，开关级数n=log2N，每级有N/2个开关，网络开关数(N/2)log2N。 2）开关级编号从输入到输出依次为K0, K1, , Kn-1 。 3）级间连接模式编号从输入到输出依次为C0,C1, , Cn 。其中，C0,Cn恒等置换， C1逆均匀洗牌置换，C2Cn-1都是子逆均匀洗牌置换。 4）单元控制，寻径算法：终端标记法,采取从输入到输出的级间互连为恒等、逆全混、子逆 全混和恒等置换,多级CLOS网络（非阻塞网络）,特点： 输入级r个开关，中间级m个开关， 输出级r个开关。 三级网络可用三个参数表示N(m,n,r)，可以证明，当m=2n-1时，多级CLOS网络N(m,n,r)是一个非阻塞网络。,（3）多级CLOS网络N(m,n,r)所需总的交叉点个数 C=r(mn)+m(rr)+r(mn)=mr(2n+r) 当n值较大时，使mr(2n+r)n2，这时既保证了 无阻塞连接，也降低了互连网络的成本，便于 工程实现,N(3,2,2)CLOS交叉开关网络连接图如下：,输入级,输出级,中间级,N（3，2，2）CLOS交叉开关网络,23,22,32,多级蝶式网络,图中由16个8*8交叉开关作为基本构件组成的二级蝶式网络，级 间采用8路混洗，构成了64*64的蝶式互连,互连网络的消息传递机制,数据传递的方式： 共享变量方式 共享存储器多处理器系统 消息传递方式 分布式存储器多处理器系统,所有的处理器共享一个统一编址的物理存储器，它 可以是集中式的，也可以分布在各个处理器结点中,每个处理器只能对本地存储器直接进行读/写操作,消息格式,消息：由任意数目的长度固定的包组成，是结 点间通信的基本单位,包：包含寻径目的地址的结点间通信的基本单 位；可异步传输，每个包有一个包序号， 以便在接收方进行包重组,片：将包分成等长的片，寻径信息（源地址和 目的地址）和序号形成头片，其余是数据片,消息寻径方式,消息寻径方式：消息从发送地传送到目的 地对路径的选取方式,存储转发寻径,在网络中，包是基本传输单位 网络中每个结点有一个包缓冲区 包从源结点经过一系列中间结点到达目的结点 当一个包到达一个中间结点后，首先被存入该结 点的包缓冲区，当所要求的输出通道和接收结点 的包缓冲区可使用时，才将包传送给下一结点,设包长为m，包传送经过l条链路，ts为启动时间 （打包，执行寻径算法，建立通信条件的时间）， th为结点延迟时间（包头穿越网络中两直接相连 的处理器所需时间），tw为传输每个字的时间 （链路带宽的倒数）。,把包进一步分成更小的片，中间结点只需很小的 片缓冲区，在与结点相连的硬件寻径器中有片缓冲 区，一旦接收到头片，就由头片中的寻径信息进行 寻径，把头片传送至下一个结点，同时包中的所有 片以流水方式在寻径器中顺序传送,切通寻径（虫蚀寻径）,包由头片和数据片组成，头片中含有目的地 址，所有数据片必须跟着头片。不同的包 可交替传送，但同一个包的片必须顺序传送， 否则可能送至错误的目的地 用包的头片开辟出一条路径，包中的片按头 片开辟的路径以流水方式在网络中向前“蠕动” 当消息的头片到达结点A的寻径器后，寻径器 根据头片的寻径信息立即作出路由选择：如果 所选择的通道空闲且所选择的结点B的片缓冲 区可用，则该头片不必等待，直接通过结点A 传向结点B,如果所选择的通道忙或结点的片缓冲区不可用， 则包的所有片必须在所占用各结点的片缓冲区中等 待，直到两者成为可用为止。被阻塞消息不从网络 中移去，片也不放弃它所占有的结点和通道,由于 tw th tcomm(SF)=ts+mtw*l tcomm(CT)=ts+mtw,存储转发网络的消息传送延时与源和目的之间的 距离成正比；切通网络的消息传送延时与源和目 的之间的距离无关。,寻径方法,算术寻径法（维序寻径法）,属于确定寻径，即寻找的传输路径是预先唯一确定 的，与网络的状态无关，路径完全由源和目的地址 确定。维序寻径法适用于网格网，按结点坐标维的 顺序选择通信链路,X-Y寻径法,适用于二维网格，任何包在网络中任何一个结点先 沿X维方向传送，在沿Y维方向传送,Begin 沿X维将包向左或向右传送至与目的结点列号 相同的结点； 沿Y维将包向上或向下传送至