均匀洗牌互连函数σ000001010011100101110111000001010.PPT

6.2 静态互连网络 网格形和环形网格 ( c ) 环形网格 ( a ) 网格形 ( b ) Illiac网 6.2 静态互连网络 超立方体和带环立方体 ( c ) 带环立方体 ( a ) 3维立方体 ( b ) 4维立方体 6.2 静态互连网络 二 . 静态网络特性表 6.3 动态互连网络 动态互连网络使用开关或者裁决器提供动态连接特性，在运行过程中由程序来确定具体的连接方式。 一. 总线互连方式 总线互连方式是多处理机实现互连的一种最简单的方式。 在总线互连方式中，多个处理机、存储模块及I/O部件等通过各自的接口部件连接在一条公共总线上，或多个计算机模块通过各自的接口部件与一条总线连接。 6.3 动态互连网络 每一次总线只能用于一个源部件到一个或多个目的部件之间的数据传送。 具有价格低、带宽较窄的特点。 6.3 动态互连网络 二. 交叉开关互连方式 交叉开关互连方式通过开关把多个处理机、存储器模块或其他I/O设备连接在一起，形成一种网络结构。 P1 P2 P16 M1 M2 M16 网络中行线和列线交叉点有开关控制其接通与否。 每个开关只需两种状态：通与断。 6.3 动态互连网络 三. 多级网络互连方式 是把多个单级互连网络通过交换开关或交叉开关串联起来而构成的网络。 a×b 开关 a×b 开关 a×b 开关 a×b 开关 a×b 开关 a×b 开关 a×b 开关 a×b 开关 a×b 开关 ISC1 ISC2 ISCn 第1级 第n-1级 0 1 b - 1 b 2b - 1 b + 1 bm - b bm - 1 第0级 0 1 a - 1 a a + 1 2a - 1 am - a am - 1 构成多级互连网络的三要素： 1）交换开关 2）拓扑结构 3）控制方式 6.3 动态互连网络 （１）交换开关 简单开关逻辑 C 0 0 1 1 6.3 动态互连网络 2×2开关的四种连接方式 0 0 1 1 ( a ) 直送 0 0 1 1 ( b ) 交叉 0 0 1 1 ( c ) 上播 0 0 1 1 ( d ) 下播 　图中表示了直通、交叉、上播和下播四种允许的状态，称为合法状态。如果出现两个输入端连接到同一个输出端的状态，就会造成信号的冲突，此状态为非法。 6.3 动态互连网络 开关模块的合法状态 输入与输出之间只有一对一的关系,即排除了上播和下播的可能性时的连接. 6.3 动态互连网络 （2）控制方式 对开关的控制方式有三种不同的控制方式： 1） 级控制 即每一级中所有的开关模块使用同一个控制信号，所以该级中的每一个开关都处于同一种状态。 2）单元控制 系统中的每一个开关模块都有自己专用的控制信号，实施个别控制，各开关均可处于自己特定的状态。 3） 部分级控制 在一个n级的网络中，取0 ≤ i ≤ n – 1，第i级的所有开关用i + 1个信号进行控制。 四. 几种主要多级网络 1．Ω（Omega）网络（多级混洗交换网络） 一个用若干级全混洗网络将开关连接起来组成的多级网络称为Ω网络。 由于采用全混洗网络是这个多级网络组织的基本特色，所以Ω网络又称为多级混洗交换网络。 1 2 0 3 4 5 6 7 1 2 0 3 4 5 6 7 输入端 输出端 C3 C1 C0 C2 K2 K1 K0 Ω网络中，开关采用的是单元控制方式。 1 2 0 3 4 5 6 7 1 2 0 3 4 5 6 7 K2 K1 K0 终端（D） 输入端 输出端 ① ① （000） ② （110） ② ③ ③ （010） 源端（S） 6.3 动态互连网络 终端标记法可以描述为：以待连接终端（输出端）号的二进制编码作为对开关控制的基准，其中的每一位用作对应开关级中开关单元的控制信号，从而实现从指定的源端到终端间的连接。 发生阻塞 6.3 动态互连网络 阻塞网络: 网络总是可以实现一对或多对输入输出的连接，但可能出现几对互连的端口之间发生冲突。 非阻塞网络: 可以实现任意端口之间的连接，不会产生如阻塞网络中出现的那种冲突。 6.3 动态互连网络 2．STARAN网络 1 2 0 3 4 5 6 7 1 2 0 3 4 5 6 7 输入端 输出端 C0 C2 C3 C1 K0 K1 K2 I A B C D E G F H J K L