计算机系统结构第6章互连网络课件教学.pptVIP

第6章 互连网络 第6章 互连网络 6.1 互连网络的基本概念 6.2 静态互连网络 6.3 动态互连网络 6.4 消息传送与控制 6.1 互连网络的基本概念 6.1.1 互连网络的功能与特征 6.1.2 互连函数 6.1.1 互连网络的功能与特征 6.1.2 互连函数 6.2 静态互连网络 6.2 静态互连网络 6.2.1 静态互连网络结构 6.2.2 静态互连网络特性 6.2.1 静态互连网络结构 6.2.2 静态互连网络特性 6.3 动态互连网络 6.3.1 总线互连方式 6.3.2 交叉开关互连方式 6.3.3 多级网络互连方式 6.3.1 总线互连方式 6.3.2 交叉开关互连方式 6.3.3 多级网络互连方式 6.4 消息传送与控制 6.4.1 消息寻径方式 6.4.2 虚拟通道与死锁 6.4.3 流控制策略 6.4.1 消息寻径方式 6.4.2 虚拟通道与死锁 6.4.3 流控制策略 【例6.4】在一个8输入三级混洗交换网络中，欲使输入端6与输出端0～4连接，输入端3与其余3个输出端连接，试画出网络图。 解：在图6.25所示网络中，只要使用控制信号把开关C、E、H、L设置成下播，把I、J设置成上播，D、F设置成交换，K设置成直通，就可以了，如图6.26所示。 图6.26 三级混洗交换网络举例 2级 1级 0级 0 4 1 5 2 6 3 7 0 1 2 3 4 5 6 7 0 4 1 5 2 6 3 7 0 2 4 6 1 3 5 7 0 2 4 6 1 3 5 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 3.多级PM2I互连网络 也称为数据交换网络，可包含n级单元连接，每一级都是把前后两列各N=2n个单元按照PM2I拓扑结构连接起来，如图6.27所示，其中n=log28=3，即三级PM2I互连网络。 对于第i级 (0≤i≤n-1),每一个输入端j都有三条输出线与之连接，即j、(j+2i) mod N和(j-2i) mod N，也就是通过交换开关选择直通、上播和下播。三级PM2I网络中第0级完成的是PM2I±0的函数功能，第1级完成的是PM2I±1的函数功能，第2级完成的是PM2I±2的函数功能。 可以看出，从每一个输入到输出都有三条线路，为信息传送提供了冗余通路。例如，从输入端7到输出端2的路径有： 7—3—3—2 7—3—1—2 7—7—1—2 图6.27 三级PM2I互连网络 4.基准网络 图6.28 N=8的基准网络 如图6.28所示是一种N=8的互连网络，与三级多立方体网络的逆网络相似，只是在第1级的级间互连不同。基准网络的级间互连从输入到输出依次是直通、逆混洗、子逆均匀混洗和直通置换。开关采用二功能交换开关，单元控制。 明显特征是可扩展性，图6.29是N=16的基准网络。这种网络常用于多级互连网络的研究，把基准网络作为中间介质，模拟一种网络的拓扑结构和功能。 图6.29 N=16的基准网络 5.多级CLOS网络 （1）三级CLOS网络 是一种非阻塞网络，输入输出端口数相同，都是n×r，其组成如图6.30所示。输入级有r个交叉开关，每个交叉开关均为n×m；中间级有m个交叉开关，每个交叉开关均为 r×r；输出级有r个交叉开关，每个开关均为m×n。 图6.30 三级CLOS网络 这种多级CLOS网络可用三个参数(m，n，r)来表示。当m≥2n-1时，多级CLOS网络N(m，n，r)是一个非阻塞网络。例如N(3，2，2)的网络结构如图6.31所示，每一级有12个交叉点，共计36个交叉点。 图6.31 N (3, 2, 2)CLOS交叉开关网络 由于输入端和输出端仅有4个，因此若用单级4×4的交叉开关来实现，共需4×4=16个交叉点，似乎要简单一些。 但是，对于图6.30来说，若设C表示多级CLOS网络中总的交叉点数，则： C=r(n×m)+m(r×r)+r(m×n)=mr(2n+r) 如果输入输出端数很大时，选用多级CLOS网络既可实现无阻塞连接，而且工程设计容易，成本低。 （2）可重排三级CLOS网络 当m=n=r时，可构成三级可重排CLOS网络，通过重排，可以消除信息传送中所遇到的阻塞。为简单起见，以m=n=r=2为例来说明可重排网络的原理。如图6.32所示，实现 的置换。 0 1 2 3 3 1 0 2 图6.32 可重排三级CLOS网络 若按图6.32(a)所示路径，可实现0→3和2→0的连接，但