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

1、 互连网络的基本概念互连网络的基本概念互联网络是一种由开关元件按照一定的互联网络是一种由开关元件按照一定的拓扑拓扑 结构结构和和控制方式控制方式构成的网络，用来实现计算构成的网络，用来实现计算 机系统内部多个处理机或多个功能部件之间机系统内部多个处理机或多个功能部件之间 的的相互连接相互连接和和信息交换信息交换。硬件接口硬件接口软件接口软件接口硬件接口硬件接口软件接口软件接口硬件接口硬件接口软件接口软件接口硬件接口硬件接口软件接口软件接口互连网络互连网络SM1SM2SMmIPMNP1PnIPCNPIONCnLMC1LM磁带部件磁带部件磁盘部件磁盘部件打印机打印机终端终端网络网络IPMN：处理机

2、：处理机-存储器网络存储器网络IPCN：处理机间网络：处理机间网络PION：处理机：处理机-I/O网络网络P：处理机：处理机SM：共享存储器：共享存储器LM：本地存储器：本地存储器C：高速缓冲存储器：高速缓冲存储器一般多处理机系统的互连结构一般多处理机系统的互连结构 互连函数互连函数互连函数互连函数f(x)表示互连网络的输出端号和表示互连网络的输出端号和 输入端号之间的对应关系输入端号之间的对应关系l若若x与与f(x)是是一对一一对一的，则称为的，则称为置换连接置换连接l若若一个一个x对应对应多个多个f(x)，则称为，则称为播送连接播送连接互连函数的表示方法：互连函数的表示方法：l函数表示法函

3、数表示法l输入输出对表示法输入输出对表示法01N-1f(0)f(1)f(N-1)l图形表示法图形表示法用输入输出的用输入输出的连线图连线图表示变换关系表示变换关系l循环互连函数表示法循环互连函数表示法 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 x00123456701234567n=3，N=8的恒等置换的恒等置换 交换置换交换置换E(xn-1 xn-2x1 x0)=xn-1 xn-2x1 x0012345670

4、1234567n=3，N=8的交换置换的交换置换 方体置换方体置换Ck(xn-1 xn-2xk+1 xk xk-1 x1 x0)=xn-1 xn-2xk+1 xk xk-1x1 x0将将2n个输入端和输出端均分为个输入端和输出端均分为2n-k组，每组组，每组2k个。每相邻两组输入与相应两组输出交叉对应。个。每相邻两组输入与相应两组输出交叉对应。C0(x2 x1 x0)=x2 x1 x0C1(x2 x1 x0)=x2 x1 x0C2(x2 x1 x0)=x2 x1 x0012345670123456701234567012345670123456701234567n=3，N=8的方体置换的方体置

5、换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个输入端分为前后两半，前一半与个输入端分为前后两半，前一半与偶数输出端偶数输出端依次依次相连，后一半与相连，后一半与奇数输出端奇数输出端依次相连。依次相连。将将输出端序列输出端序列分为前后两组，每组轮流出牌所得序列即分为前后两组，每组轮流出牌所得序列即输入端序列输入端序列。040123456715263701234567891011121314150819210311412513

6、614715 子洗牌置换子洗牌置换(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个输入为一组，组内个输入为一组，组内进行均匀洗牌置换进行均匀洗牌置换 超洗牌置换超洗牌置换(xn-1 xn-2xn-k xn-k-1 xn-k-2 x1 x0)= xn-2xn-k xn-k-1 xn-1x1 x0 xk将将2n个输入端分为个输入端分为2n-k-1组，低组，低n-k-1位完全相同的输入为位完全相同的输入为一组，组内进行均匀洗牌置换一组，组内进行均匀洗牌置换01234567

7、01234567012345670123456701234567012345670123456701234567均匀洗牌均匀洗牌置换置换子洗牌置子洗牌置换换超洗牌置超洗牌置换换逆均匀洗牌逆均匀洗牌置换置换n=3，N=8的洗牌置换的洗牌置换 逆洗牌置换逆洗牌置换(xn-1 xn-2xk+1 xk xk-1 x1 x0)=x0 xn-1 xn-2 xn-3xk+1 xk xk-1x1 将将偶数偶数输入端与输入端与前一半输出端前一半输出端依次相连，将依次相连，将奇数奇数输入端与输入端与后一半输出端后一半输出端依次相连。依次相连。将将输入端序列输入端序列分为前后两组，每组轮流出牌所得分为前后两组，每组

8、轮流出牌所得序列即序列即输出端序列输出端序列。040123456715263701234567891011 1213 14 1508192 103 114 125136147 15 蝶式置换蝶式置换(xn-1 xn-2xk+1 xk xk-1 x1 x0)=x0 xn-2 xk+1 xk xk-1x1 xn-1 子蝶式置换子蝶式置换(xn-1 xn-2xk+1 xk xk-1 x1 x0)=xn-1 xn-2xk+1 x0 xk-1x1 xkl蝶式置换连接中共有蝶式置换连接中共有2n-1个恒等连接，个恒等连接，2n-2对交叉对交叉连接。连接。l对于前一半输入端的偶数部分进行恒等连接，奇对于前一

9、半输入端的偶数部分进行恒等连接，奇数部分对应后一半输出端的偶数部分。数部分对应后一半输出端的偶数部分。l对于后一半输入端的奇数部分进行恒等连接，偶对于后一半输入端的奇数部分进行恒等连接，偶数部分对应前一半输出端的奇数部分。数部分对应前一半输出端的奇数部分。012345670123456701234567012345670123456701234567蝶式置换蝶式置换子蝶式子蝶式置换置换超蝶式超蝶式置换置换 n=3，N=8的蝶式置换的蝶式置换 超蝶式置换超蝶式置换(xn-1 xn-2xn-k xn-k-1 xn-k-2 x1 x0)= xn-k-1 xn-2xn-k xn-1 xn-k-2x1

10、x0 l子蝶式置换连接中共有子蝶式置换连接中共有2n-1个恒等连接，个恒等连接，2n-2对交对交叉连接。叉连接。l共分为共分为2n-k-1组，每组，每2k+1个输入个输入/输出端为一组，输出端为一组，组内进行蝶式置换组内进行蝶式置换l超蝶式置换连接中共有超蝶式置换连接中共有2n-1个恒等连接，个恒等连接，2n-2对交对交叉连接。叉连接。l共分为共分为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-1l对于输入对于输入x=0或或2n-1，输出仍为

11、，输出仍为x，即恒等连接，即恒等连接 子位序颠倒置换子位序颠倒置换(xn-1 xn-2xk+1 xk xk-1 x1 x0)=xn-1 xn-2 xk+1 x0 x1xk-1 xk 超位序颠倒置换超位序颠倒置换(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 012345670123456701234567012345670123456701234567位序颠倒位序颠倒置换置换子位序颠子位序颠倒置换倒置换超位序颠超位序颠倒置换倒置换 n=3，N=8的位序颠倒置换的位序颠倒置换 移数置换移数置换 组内移数置换

12、组内移数置换 k) mod 2r l共分为共分为2n-r组，组内进行循环移数置换组，组内进行循环移数置换 加减加减2I置换置换 (x) 012345670123456701234567012345670123456701234567左移移数左移移数置换置换n=3，N=8的移数置换的移数置换0123456701234567右移移数右移移数置换置换组内左移移数组内左移移数置换置换组内右移组内右移移数置换移数置换左移移数置换左移移数置换 k=2 (0 2 4 6) (1 3 5 7)右移移数置换右移移数置换 k=2 (6 4 2 0) (7 5 3 1)组内左移移数置换组内左移移数置换 k=1 r=

13、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)012345670123456701234567012345670123456701234567n=3，N=8的加减的加减2I置换置换 互连网络的结

14、构参数与性能指标互连网络的结构参数与性能指标 互连网络的结构参数互连网络的结构参数 网络规模网络规模 网络中的结点数。表示网络所能连接的部件个数。网络中的结点数。表示网络所能连接的部件个数。 结点度结点度 一个结点射入或射出的边数。一个结点射入或射出的边数。 在单向网络中，入射边的数目称为在单向网络中，入射边的数目称为入度，入度，出射边的数出射边的数 目称为目称为出度。出度。 结点度结点度为为入度入度和和出度出度之和。之和。 在无向网络中，在无向网络中，结点度结点度为与结点相连的边数。为与结点相连的边数。 结点距离结点距离 两结点间相连的最少边数。两结点间相连的最少边数。 网络直径网络直径 互

15、连网络中任意两结点间距离的最大值。互连网络中任意两结点间距离的最大值。 网络对剖宽度网络对剖宽度 一个网络被切分为结点数相等的两半时，沿切口一个网络被切分为结点数相等的两半时，沿切口 的的最少边数最少边数。 网络对称性网络对称性 若从网络的任意结点来看，网络的结构都是若从网络的任意结点来看，网络的结构都是相同相同的，的， 则称该网络是则称该网络是对称网络对称网络。 网络可扩展性网络可扩展性 在网络拓扑性能保持不变的情况下，在网络拓扑性能保持不变的情况下，可扩充结点的可扩充结点的 能力能力。 互连网络的传输性能参数互连网络的传输性能参数AB机器机器A机器机器B机器机器A发送数据的步骤：发送数据的

16、步骤：l机器机器A应用程序应用程序待发送数据待发送数据机器机器A操作系统缓冲区操作系统缓冲区 l机器机器A操作系统根据要发送的数据操作系统根据要发送的数据计算检查和计算检查和，并，并 把它放在把它放在消息消息中，同时启动中，同时启动超时计数器超时计数器l机器机器A操作系统缓冲区操作系统缓冲区网络接口硬件网络接口硬件 消息消息l若收到机器若收到机器B的回答信号则的回答信号则释放释放缓冲区中消息；缓冲区中消息； 若超时计数器超时还未收到回答信号则若超时计数器超时还未收到回答信号则重发重发消息消息l操作系统通知硬件开始发送消息操作系统通知硬件开始发送消息l等待来自机器等待来自机器B的回应的回应机器机

17、器B接收数据的步骤：接收数据的步骤：l网络接口硬件网络接口硬件机器机器B操作系统缓冲区操作系统缓冲区消息消息l机器机器B操作系统根据接收到的数据操作系统根据接收到的数据计算检查和计算检查和。 若计算出的检查和与发送过来的若计算出的检查和与发送过来的匹配匹配，向接收方发，向接收方发 出出回答信号回答信号；若；若不匹配不匹配，则，则删除删除消息消息l若数据通过检查：若数据通过检查：机器机器B操作系统缓冲区操作系统缓冲区数据数据用户地址空间用户地址空间l启动应用程序继续执行启动应用程序继续执行 频宽频宽 互连网络传输信息的互连网络传输信息的最大速率最大速率。MB/s 传输时间传输时间l发送方传输时间

18、：发送方传输时间：发送方从开始发送第一位信息发送方从开始发送第一位信息 起到把消息完全发送至网络所需时间起到把消息完全发送至网络所需时间l接收方传输时间：接收方传输时间：接收方从接收到第一位信息起接收方从接收到第一位信息起 到完全接收到消息的时间到完全接收到消息的时间 “飞行飞行”时间时间 消息的消息的第一位信息第一位信息到达接收方所需时间。包括网到达接收方所需时间。包括网 络中转发或其他硬件的时间延迟络中转发或其他硬件的时间延迟 传输时延传输时延 发送方发送第一位信息到接收方完全接收到消息发送方发送第一位信息到接收方完全接收到消息 所需时间所需时间 “飞行飞行”时间时间+传输时间传输时间 发

19、送方开销发送方开销 发送方在缓冲区中准备好待发送消息并送至网络发送方在缓冲区中准备好待发送消息并送至网络 接口硬件的时间接口硬件的时间 接收方开销接收方开销 接收方把消息从网络接口硬件取至缓冲区并拷贝接收方把消息从网络接口硬件取至缓冲区并拷贝 至用户地址空间的时间至用户地址空间的时间 总时延总时延总时延总时延=发送方开销发送方开销+“飞行飞行”时间时间+消息长度消息长度频宽频宽+接收方开销接收方开销传输时间传输时间总时延总时延=发送方开销发送方开销+“飞行飞行”时间时间+接收方开销接收方开销总时延总时延=发送方开销发送方开销+传输时延传输时延+接收方开销接收方开销发送开销传输(发送)时间飞行时

20、间接收开销传输(接收)时间发送第一个发送第一个发送最后一个发送最后一个第一个到达接收方第一个到达接收方最后一个到达接收方最后一个到达接收方例：假设一个网络的频宽为例：假设一个网络的频宽为10Mb/s，发送方开销，发送方开销为为230us，接收方开销为，接收方开销为270us，如果两台机器相，如果两台机器相距距100米，现要发送一个米，现要发送一个1000字节的消息给另一字节的消息给另一台机器，试计算总时延。如果两台机器相距台机器，试计算总时延。如果两台机器相距1000公里，总时延为多大？公里，总时延为多大？（光速为（光速为299792.5km/s，信号在导体中的传递速，信号在导体中的传递速 度

21、大约是光速的度大约是光速的50%）T=270us+230us+0.1km299792.5km/s*0.51000*8b10Mb/s+= 270us+230us+0.67us+800us=1301usT=270us+230us+1000*106us299792.5km/s*0.51000*8b10Mb/s+= 270us+230us+6671us+800us=7971us 互连网络的性能指标互连网络的性能指标 通信时延通信时延从源结点到目的结点传送一条消息所需的总时间从源结点到目的结点传送一条消息所需的总时间l软件开销（取决于收发端的软件内核）软件开销（取决于收发端的软件内核） 在源结点和目的结

22、点用于收发消息的软件所需的执行在源结点和目的结点用于收发消息的软件所需的执行 时间时间l通道时延（取决于瓶颈链路的通道带宽）通道时延（取决于瓶颈链路的通道带宽） 通道时延通道时延=消息长度消息长度/通道带宽通道带宽l选路时延（取决于传送路径上的结点数）选路时延（取决于传送路径上的结点数） 消息在传送路径上进行选路决策所需的时间开销消息在传送路径上进行选路决策所需的时间开销l竞争时延（取决于网络的传输状态）竞争时延（取决于网络的传输状态） 多个消息同时在网络中传送时解决或避免网络资多个消息同时在网络中传送时解决或避免网络资 源争用冲突所需时间源争用冲突所需时间 网络时延网络时延 网络时延网络时延

23、=通道时延通道时延+选路时延选路时延 与程序行为和网络传输状态无关与程序行为和网络传输状态无关 端口带宽端口带宽 网络中从任意一个端口单位时间传送到其他端网络中从任意一个端口单位时间传送到其他端 口的最大信息量。（口的最大信息量。（b/s或或B/s） 聚集带宽聚集带宽 网络从一半结点到另一半结点，单位时间传送网络从一半结点到另一半结点，单位时间传送 的最大信息量。的最大信息量。 对剖带宽对剖带宽 通过最小对剖平面的所有边的单位时间传送的通过最小对剖平面的所有边的单位时间传送的 最大信息量。最大信息量。 静态互连网络静态互连网络各结点间有专用的连接通路，且在运行中各结点间有专用的连接通路，且在运

24、行中不不能改变连接能改变连接的网络。的网络。 线性阵列线性阵列中间结中间结点点2网络类型网络类型结点度结点度d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性网络规格网络规格 线性阵列线性阵列端结点端结点 1N-1N-11否否N线性阵列允许不同的结点对线性阵列允许不同的结点对并发并发使用系统的不同部分使用系统的不同部分（通道）（通道） 环环网络类型网络类型结点度结点度 d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性网络规格网络规格 环环2单向环单向环N-1双向环双向环 N/2N2是是N 带带环环把环中把环中不直接相连不直接相连的每两个的每两个距离相等距离

25、相等的结点用一条的结点用一条边连接起来边连接起来0123456781011121314159度为度为3的带弦环的带弦环0123456781011121314159度为度为4的带弦环的带弦环 循环移数网络循环移数网络将环上每个结点与其距离为将环上每个结点与其距离为2整数幂整数幂的结点间增加的结点间增加一条附加链路而构成。一条附加链路而构成。设网络规模为设网络规模为N=2n，则结点，则结点x与以下结点有链路相与以下结点有链路相连：连：(x2i) mod 2n (0i n) 0123456789101112131415网络类型网络类型结点度结点度 d网络直径网络直径 D链路数链路数l对称性对称性网络

26、规格网络规格 循环移循环移数网络数网络2n-1n/22n-1(2n-1)是是N=2n等分宽度等分宽度 b2n-1n 全连接网络全连接网络网络类型网络类型结点度结点度 d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性网络规格网络规格 全连接全连接N-11N(N-1)/2是是N(N/2)2N/2N/2N/2N/2* 树形网络树形网络拓扑结构是一棵完全二叉树。设有拓扑结构是一棵完全二叉树。设有N个结点，共个结点，共k层，则层，则N=2k-1优点：可扩展性好优点：可扩展性好 缺点：直径长缺点：直径长网络类型网络类型结点度结点度d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b

27、对称性对称性网络规格网络规格 树形树形叶结点叶结点1根结点根结点2分支结点分支结点32(k-1)N-11否否N=2k-1 星形网络星形网络网络类型网络类型 结点度结点度d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性网络规格网络规格 星形星形根结点根结点N-1叶结点叶结点12N-1N/2否否N 胖树形网络胖树形网络网络类型网络类型结点度结点度d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性网络规格网络规格 胖树形胖树形第第j层结点层结点 3(k-j)+1 2j k根结点根结点2k-2j=1j=2j=3j=42(k-1)k-1否否N=2k-12k+1-2k

28、-2缓解通向根结点的通信瓶颈缓解通向根结点的通信瓶颈l=j=1k-1(k-j)*2j 网格形网络网格形网络网络类型网络类型结点度结点度d网络直径网络直径 D链路数链路数l等分等分宽度宽度b对称性对称性网络规格网络规格 2D网格网格k维网格维网格角结点角结点 2边结点边结点 3内结点内结点 4内结点内结点 2k2(n-1)k(n-1)N=n2N=nk否否否否2N-2nknk-1(n-1)nnk-1三维网格形网络的内结点度为三维网格形网络的内结点度为6，边结点度为，边结点度为4，角结点度为角结点度为3，面内结点度为，面内结点度为5。ABAB Illiac网络网络网络类型网络类型 结点度结点度d网络

29、直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性 网络规格网络规格 Illiac网络网络4n-12N2n否否N=n2AB 环网形网络环网形网络网络类型网络类型 结点度结点度d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性 网络规格网络规格 2D环网环网42 n/22N2n是是N=n2 搏动式阵列搏动式阵列网络类型网络类型 结点度结点度d网络网络直径直径D链路数链路数l等分宽度等分宽度 b对称性对称性 网络规格网络规格 搏动式搏动式 阵列阵列左右两角结点左右两角结点2上下两角结点上下两角结点3边结点边结点4内结点内结点62(n-1)3n2-4n+12n-1否否N

30、=n2 超立方体超立方体网络类型网络类型 结点度结点度d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性 网络规格网络规格 超立方体超立方体nnnN/2N/2是是N=2n环中有环中有K个结点个结点 带环立方体带环立方体下一维指针下一维指针环中下一结点环中下一结点环中上一结点环中上一结点K维转发维转发,d=(2k-1)+网络类型网络类型 结点度结点度d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性 网络规格网络规格 带环带环k-立方体立方体32k-1+ k/23N/2N/(2k)是是N=k2k (k3)ABCDEFGHIJKLMNOPA1B1B2C2C3G3

31、G4O4O3O2A1O2 k元元n-立方体立方体网络类型网络类型 结点度结点度d网络直径网络直径 D链路数链路数l等分宽度等分宽度 b对称性对称性 网络规格网络规格 k元元n-立方体立方体2nnNn k/22kn-1是是N=kn 动态互连网络动态互连网络动态互连网络可通过设置有源开关，从而根动态互连网络可通过设置有源开关，从而根据需要借助控制信号对连接通路加以据需要借助控制信号对连接通路加以重新组重新组合合，实现所要求的通信模式。，实现所要求的通信模式。多处理机总线互连多处理机总线互连l用一组导线和插座将处理机、存储模块和用一组导线和插座将处理机、存储模块和各种外围设备互连起来，总线上的各模块

32、各种外围设备互连起来，总线上的各模块需要通信时，发出申请，由需要通信时，发出申请，由总线仲裁逻辑总线仲裁逻辑对多个请求进行仲裁，进行总线服务分配。对多个请求进行仲裁，进行总线服务分配。l总线上各模块通过总线上各模块通过争用争用或或时分时分方式获得总方式获得总线服务。线服务。l价格较低，带宽较窄价格较低，带宽较窄本地总线本地总线LMCPUIOC高速缓存高速缓存 IFCPU板板本地外围设备本地外围设备存储器总线存储器总线 IF存储器板存储器板MC存储器单元存储器单元数据总线数据总线IOP缓冲缓冲 IFI/O板板 IF数据总线数据总线缓冲缓冲 IF通信板通信板 IF CC系统总线（底板上）系统总线（

33、底板上）磁盘和磁带部件磁盘和磁带部件打印机或绘图仪打印机或绘图仪网络（以太网等）网络（以太网等）机群间总线机群间总线CCCPCPCCCPCPCCCPCP存储器存储器存储器存储器存储器存储器 总线互连的缺点总线互连的缺点l 带宽有限带宽有限l 没有冗余链路没有冗余链路l 可扩展性有限可扩展性有限l 层次总线的可扩展层次数有限层次总线的可扩展层次数有限 交叉开关互连交叉开关互连 大大展宽了互连传输频带，提高了系统的效率；大大展宽了互连传输频带，提高了系统的效率； 但交叉开关设备量过大，成本过高（一般但交叉开关设备量过大，成本过高（一般n16） 采用采用按空间分配按空间分配的机制的机制M1M2MnP

34、1PmI/O1I/Ornr+m存储器存储器模块模块多路转换多路转换器模块器模块仲裁模块仲裁模块数据数据读读/写写地址地址自处理机自处理机 P0Pn-1数据数据读读/写写地址地址请求请求0请求请求1请求请求n-1存储器存储器 使能使能控制控制结点开关的结构结点开关的结构 多级互连网络多级互连网络abababababababababISCISCISC10a-1a+1a2a-1an-aan-a+1an-110b-1b+1b2b-1bn-b+1bn-bbn-1an-1个个ban-2个个bn-1个个级级1级级2级级n多级互连网络把重复设置的多级互连网络把重复设置的多套动态单级网多套动态单级网络络串联起来

35、，单级网络级间采用串联起来，单级网络级间采用固定的级间固定的级间连接模式连接模式，通过，通过动态控制动态控制各单级网络的各单级网络的开关开关状态状态实现多级互连网络的输入端和输出端之实现多级互连网络的输入端和输出端之间所需要的连接间所需要的连接 开关模块开关模块ab10a-110b-1通常取通常取a=b=2k（k1）l 2功能开关功能开关l 4功能开关功能开关0101010101010101直送直送交叉交叉上播上播下播下播 级间连接模式级间连接模式 多级互连网络中上一级开关模块的输出端和多级互连网络中上一级开关模块的输出端和 下一级开关模块的输入端相互连接的模式下一级开关模块的输入端相互连接的

36、模式 可用可用互连函数互连函数表示表示 控制方式控制方式互连网络拓扑结构可动态重构互连网络拓扑结构可动态重构：可通过：可通过控制控制信号信号动态控制开关模块的状态来实现所要求动态控制开关模块的状态来实现所要求的互连的互连l 级控方式级控方式 对同一级的所有开关用一个控制信号控制对同一级的所有开关用一个控制信号控制l 组控方式组控方式 对第对第i级的开关分为级的开关分为i+1组，每组用一个控制组，每组用一个控制 信号控制（信号控制（0i n-1）l 单元控制方式单元控制方式 每一个开关有自己单独的控制信号每一个开关有自己单独的控制信号 多级互连网络的分类多级互连网络的分类l 阻塞网阻塞网：在一对

37、以上输入端和输出端可同：在一对以上输入端和输出端可同 时实现互连的网络中，可能发生时实现互连的网络中，可能发生2个或个或2个个 以上的输入端对输出端的连接要求产生以上的输入端对输出端的连接要求产生路路 径争用冲突径争用冲突。l 所用开关数量少，延时不长，路径控制较所用开关数量少，延时不长，路径控制较 简单。简单。l可重排非阻塞网络可重排非阻塞网络：如果重新安排现有的：如果重新安排现有的 连接，就可实现无阻塞的任意端点对的连连接，就可实现无阻塞的任意端点对的连 接，从而满足一个新的端点对的连接请求。接，从而满足一个新的端点对的连接请求。l 多级非阻塞网络多级非阻塞网络：不必改变原来的开关状：不必

38、改变原来的开关状 态就可满足任意输入端和输出端的连接请态就可满足任意输入端和输出端的连接请 求。求。 交叉开关网络交叉开关网络为为单级非阻塞网单级非阻塞网 Omega网络网络 N*N；共；共n=log2N级开关，从输入端至输级开关，从输入端至输 出端依次为出端依次为Kn-1,K1,K0 采用采用2*2的的4功能开关功能开关 每级每级N/2个开关，共个开关，共m=(N/2)log2N个开关，个开关， 可实现可实现4m种置换连接种置换连接 采用采用单元控制方式单元控制方式级间连接从输入端至输出端依次为级间连接从输入端至输出端依次为Cn,C1,C0; 其中，其中，CnC1为为均匀洗牌置换均匀洗牌置换

39、，C0为为恒等置换恒等置换 0123456701234567K2K1K0C3C2C1C0Omega网络网络(N=8) 采用终端标记寻径（采用终端标记寻径（D标记寻径）标记寻径）(S) xn-1xn-2x1x0yn-1yn-2y1y0 (D)xn-1xn-2x1x0Cnxn-2xn-3x1x0 xn-1Kn-1xn-2xn-3x1x0 xn-1Cn-1xn-3x1x0 xn-1xn-2Kn-2xn-3x1x0 xn-1xn-2C1x0 xn-1xn-2x1xn-1xn-2x1x0K0 xn-1xn-2x1x0C0 xn-1xn-2x1x0=yn-1yn-2y1y0 K1yi=0，第，第i级即级即

40、Ki开关级上对应开关的输入端与开关开关级上对应开关的输入端与开关的的上输出端上输出端相连；相连；yi=1，第，第i级即级即Ki开关级上对应开关的输入端与开关开关级上对应开关的输入端与开关的的下输出端下输出端相连；相连； 可能产生争用开关状态的冲突可能产生争用开关状态的冲突xi-1x0 xn-1xi+1xiKixi-1x0 xn-1xi+1xi若两对连接的源端若两对连接的源端xi-1,x0,xn-1,xi+1均相同，均相同，xi不同，终端不同，终端xi(yi)相同，则该两对连接在相同，则该两对连接在Ki开关级的开关级的xi-1,x0,xn-1,xi+1开关上产生冲突开关上产生冲突例如例如: 00

41、0101与与100110在在K2级开关级开关0上产上产生争用下输出端的冲突；生争用下输出端的冲突；101100与与011101在在K1级开关级开关3上产生争用上产生争用上输出端的冲突；上输出端的冲突；在实现源与终端结点各不相同的置换连接时，如在实现源与终端结点各不相同的置换连接时，如果不产生冲突，所有开关均不会出现上播或下播果不产生冲突，所有开关均不会出现上播或下播的状态；的状态；例：在例：在N=8的的Omega网络中采用终端标记寻径法，网络中采用终端标记寻径法，至少要连接几次才能实现蝶式置换所要求的连接？至少要连接几次才能实现蝶式置换所要求的连接？第一次实现第一次实现00, 14, 22,

42、36第二次实现第二次实现41, 55, 63, 7700, 41 争用争用K2级级0开关的上输出端，从而争用开关的上输出端，从而争用K1级级0开关的上输出端；开关的上输出端；14, 55 争用争用K2级级1开关的下输出端，从而争用开关的下输出端，从而争用K1级级3开关的上输出端；开关的上输出端；22, 63 争用争用K2级级2开关的上输出端，从而争用开关的上输出端，从而争用K1级级0开关的下输出端；开关的下输出端；36, 77 争用争用K2级级3开关的下输出端开关的下输出端，从而争用，从而争用K1级级3开关的下输出端开关的下输出端0123456701234567K2K1K0C3C2C1C0例：

43、试给出一个简单的寻径算法实现例：试给出一个简单的寻径算法实现Omega网络网络的任一源端对所有终端的广播连接。的任一源端对所有终端的广播连接。Si=01使使Ki级相应开关上播级相应开关上播使使Ki级相应开关下播级相应开关下播仅在播送连接中才可能出现开关的上播和下播状态仅在播送连接中才可能出现开关的上播和下播状态0123456701234567K2K1K0C3C2C1C0例：用一个例：用一个N=8的三级的三级Omega网络连接网络连接8个处理个处理 机机 (P0P7)，8个处理机的输出端分别依序连个处理机的输出端分别依序连 接接Omega网络的网络的8个输入端个输入端07，8个处理机个处理机 的

44、输入端分别依序连接的输入端分别依序连接Omega网络的网络的8个输个输 出端出端07。如果处理机。如果处理机P6要把数据播送给处要把数据播送给处 理机理机P0P4，处理机，处理机P3要把数据播送给处理要把数据播送给处理 机机P5P7。那么，。那么，Omega网络能否同时为它网络能否同时为它 们的播送要求实现连接？请画出实现播送们的播送要求实现连接？请画出实现播送 的的Omega网络的开关状态图。网络的开关状态图。0123456701234567K2K1K0C3C2C1C0 STARAN网络网络 N*N；共；共n=log2N级开关，从输入端至输级开关，从输入端至输 出端依次为出端依次为K0,K1

45、,Kn-1 采用采用2*2的的2功能开关，直送和交叉功能开关，直送和交叉n 每级每级N/2个开关，共个开关，共m=(N/2)log2N个开关，个开关， 共可实现共可实现2m种置换连接种置换连接 采用采用级控方式或组控方式级控方式或组控方式n 级间连接从输入端至输出端依次为级间连接从输入端至输出端依次为C0, C1, ,Cn; 其中，其中，C1Cn为为逆洗牌置换逆洗牌置换，C0为为 恒等置换恒等置换 0123456701234567K0K1K2C0C1C2C3STARAN网络网络(N=8)xn-1xn-2x1x0C0K0C1K1Cn-1xn-3xn-2x0 xn-1xn-2xn-2xn-3x0

46、xn-1Kn-1xn-2xn-3x0 xn-1Cnxn-1xn-2x1x0=yn-1yn-2y1y0 Kn-2(S) xn-1xn-2x1x0yn-1yn-2y1y0 (D)xn-1xn-2x1x0 xn-1xn-2x1x0 x0 xn-1xn-2x1x0 xn-1xn-2x1C2 级控方式及交换置换级控方式及交换置换xi=E(xi)=xi+ fixi-1x0 xn-1xiKixi-1x0 xn-1xiE(xn-1xn-2x1x0)=(+ fn-1,xn-1+ fn-2,xn-2+ f1,x1+ f0)x0 可实现可实现N种置换种置换 若级控信号若级控信号F中仅中仅fi为为1，其余各位为，其余

47、各位为0： E(xn-1xix1x0)=xn-1xix1x0=Cubei(x) 分组交换置换：若分为分组交换置换：若分为2n-k组，每组组，每组2k个个 元素，则同组元素低元素，则同组元素低k位必不同，高位必不同，高n-k位位 必相同。让同组元素反序，得到输出序列。必相同。让同组元素反序，得到输出序列。 xn-1xkxk-1x1x0 xn-1xkxk-1x1x0 x2x1x04组组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

48、 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0 x2x1x0例如：实现例如：实现2组组4元交换元交换000001010011100101110111012345670123456710233210456754677654321076453201546776540123102376453201恒等恒等4组组2元元4组组2元元2组组4元元2组组4元元2组组4元元1组组8元元4组组2元元2组组4元元1组组8元元4组组2元元1组组8元元1组组8元元iC0C1C0+C1C2C0+C2

49、C1+C2C0+C1+C201234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567F=(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) 可

50、实现的移数置换：可实现的移数置换： 共可实现共可实现(n2+n+2)/2种移数置换连接种移数置换连接 f23f22f21f12f11f00010110111101110000000110001100000010000000123456712345670234567014567012312305674230167451032547601234567组组控控信信号号输输入入端端号号移数移数功能功能移移 1mod 8移移 2mod 8移移 4mod 8移移 1mod 4移移 2mod 4移移 1mod 2不移不移 恒等恒等0123456701234567K0K1K2C0C1C2C3例如：实现移例如：