计算机系统结构_第章互连网络

《计算机系统结构_第章互连网络》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机系统结构_第5章互连网络互连网络的基本概念互联网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接和信息交换。硬件接口软件接口硬件接口软件接口硬件接口软件接口硬件接口软件接口…互连网络SM1SM2SMm…IPMNP1PnIPCNPIONCnLMC1LM…………磁带部件磁盘部件打印机终端网络···IPMN：处理机-存储器网络IPCN：处理机间网络PION：处理机-I/O网络P：处理机SM：共享存储器LM：本地存储器C：高速缓冲存储器一般多处理机系统的互连结构互连函数互连函数f(x)表示互连

2、网络的输出端号和输入端号之间的对应关系若x与f(x)是一对一的，则称为置换连接若一个x对应多个f(x)，则称为播送连接互连函数的表示方法：函数表示法输入输出对表示法01N-1f(0)f(1)f(N-1)……图形表示法用输入输出的连线图表示变换关系循环互连函数表示法f(x0)=x1,f(x1)=x2,…,f(xj)=x0(x0x1x2…xj)j+1称为循环长度基本互连函数恒等置换I(xn-1xn-2…x1x0)=xn-1xn-2…x1x00123456701234567n=3，N=8的恒等置换0123456701234567交换置换E(xn-1xn-2…x1x0

3、)=xn-1xn-2…x1x00123456701234567n=3，N=8的交换置换0123456710325476(01)(23)(45)(67)方体置换Ck(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-1xn-2…xk+1xkxk-1…x1x0将2n个输入端和输出端均分为2n-k组，每组2k个。每相邻两组输入与相应两组输出交叉对应。C0(x2x1x0)=x2x1x0C1(x2x1x0)=x2x1x0C2(x2x1x0)=x2x1x0012345670123456701234567012345670123456701234567n=3，N=8

4、的方体置换C0方体置换C1方体置换C2方体置换(01)(23)(45)(67)(02)(13)(46)(57)(04)(15)(26)(37)均匀洗牌置换σ(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-2xn-3…xk+1xkxk-1…x1x0xn-1将2n个输入端分为前后两半，前一半与偶数输出端依次相连，后一半与奇数输出端依次相连。将输出端序列分为前后两组，每组轮流出牌所得序列即输入端序列。把输入端二进制地址循环左移一位就是连接的输出端的二进制地址0401234567152637012345678910111213141508192103114

5、12513614715子洗牌置换σ(k)(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-1xn-2…xk+1xk-1…x1x0xk将2n个输入端分为2n-k-1组，每2k+1个输入为一组，组内进行均匀洗牌置换超洗牌置换σ(k)(xn-1xn-2…xn-kxn-k-1xn-k-2…x1x0)=xn-2…xn-kxn-k-1xn-1…x1x0xkσ(n-1)(x)=σ(n-1)(x)=σ(x)σ(0)(x)=σ(0)(x)=x将2n个输入端分为2n-k-1组，低n-k-1位完全相同的输入为一组，组内进行均匀洗牌置换0123456701234567012

6、345670123456701234567012345670123456701234567均匀洗牌置换σ子洗牌置换σ(1)超洗牌置换σ(1)逆均匀洗牌置换σ-1n=3，N=8的洗牌置换逆洗牌置换σ-1(xn-1xn-2…xk+1xkxk-1…x1x0)=x0xn-1xn-2xn-3…xk+1xkxk-1…x1将偶数输入端与前一半输出端依次相连，将奇数输入端与后一半输出端依次相连。将输入端序列分为前后两组，每组轮流出牌所得序列即输出端序列。040123456715263701234567891011121314150819210311412513614715蝶式

7、置换β(xn-1xn-2…xk+1xkxk-1…x1x0)=x0xn-2…xk+1xkxk-1…x1xn-1蝶式置换连接中共有2n-1个恒等连接，2n-2对交叉连接。对于前一半输入端的偶数部分进行恒等连接，奇数部分对应后一半输出端的偶数部分。对于后一半输入端的奇数部分进行恒等连接，偶数部分对应前一半输出端的奇数部分。012345670123456701234567012345670123456701234567蝶式置换β子蝶式置换β(1)超蝶式置换β(1)n=3，N=8的蝶式置换β(n-1)(x)=β(n-1)(x)=β(x)β(0)(x)=β(0)(x)=x

8、子蝶式置换连接中共有2n-1个恒等连接