互连网络的基本概念课件

互连网络的基本概念互联网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接和信息交换。硬件接口软件接口硬件接口软件接口硬件接口软件接口硬件接口软件接口…互连网络互连网络的基本概念互联网络是一种由开关元件按照一定的拓扑硬1SM1SM2SMm…IPMNP1PnIPCNPIONCnLMC1LM…………磁带部件磁盘部件打印机终端网络···IPMN：处理机-存储器网络IPCN：处理机间网络PION：处理机-I/O网络P：处理机SM：共享存储器LM：本地存储器C：高速缓冲存储器一般多处理机系统的互连结构SM1SM2SMm…IPMNP1PnIPCNPIONCnLM2互连函数互连函数f(x)表示互连网络的输出端号和输入端号之间的对应关系若x与f(x)是一对一的，则称为置换连接若一个x对应多个f(x)，则称为播送连接互连函数互连函数f(x)表示互连网络的输出端号和3互连函数的表示方法：函数表示法输入输出对表示法01N-1f(0)f(1)f(N-1)……互连函数的表示方法：01N-1f(0)f(1)f(N-1)…4图形表示法用输入输出的连线图表示变换关系循环互连函数表示法

f(x0)=x1

,f(x1)=x2,…,f(xj)=x0

(x0x1x2…xj)j+1称为循环长度图形表示法循环互连函数表示法5基本互连函数恒等置换I(xn-1xn-2…x1x0)=xn-1xn-2…x1x00123456701234567n=3，N=8的恒等置换基本互连函数恒等置换I(xn-1xn-2…x1x0)6交换置换E(xn-1xn-2…x1x0)=xn-1xn-2…x1x00123456701234567n=3，N=8的交换置换交换置换E(xn-1xn-2…x1x0)=xn-1x7方体置换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)=x2x1x0方体置换Ck(xn-1xn-2…xk+1xkxk-18012345670123456701234567012345670123456701234567n=3，N=8的方体置换C0方体置换C1方体置换C2方体置换0123456701234567012345670123459均匀洗牌置换σ(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-2xn-3…xk+1xkxk-1…x1x0xn-1将2n个输入端分为前后两半，前一半与偶数输出端依次相连，后一半与奇数输出端依次相连。将输出端序列分为前后两组，每组轮流出牌所得序列即输入端序列。040123456715263701234567891011121314150819210311412513614715均匀洗牌置换σ(xn-1xn-2…xk+1xkxk-10子洗牌置换σ(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…xk+1xkx11超洗牌置换σ(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位完全相同的输入为一组，组内进行均匀洗牌置换超洗牌置换σ(k)(xn-1xn-2…xn-kxn-k120123456701234567012345670123456701234567012345670123456701234567均匀洗牌置换σ子洗牌置换σ(1)超洗牌置换σ(1)逆均匀洗牌置换σ-1n=3，N=8的洗牌置换01234567012345670123456701234513逆洗牌置换σ-1(xn-1xn-2…xk+1xkxk-1…x1x0)=x0xn-1xn-2xn-3…xk+1xkxk-1…x1

将偶数输入端与前一半输出端依次相连，将奇数输入端与后一半输出端依次相连。将输入端序列分为前后两组，每组轮流出牌所得序列即输出端序列。040123456715263701234567891011121314150819210311412513614715逆洗牌置换σ-1(xn-1xn-2…xk+1xkxk14蝶式置换β(xn-1xn-2…xk+1xkxk-1…x1

x0)=x0xn-2…xk+1xkxk-1…x1

xn-1子蝶式置换β(k)(xn-1xn-2…xk+1

xkxk-1…x1

x0)=xn-1xn-2…xk+1

x0xk-1…x1

xk蝶式置换连接中共有2n-1个恒等连接，2n-2对交叉连接。对于前一半输入端的偶数部分进行恒等连接，奇数部分对应后一半输出端的偶数部分。对于后一半输入端的奇数部分进行恒等连接，偶数部分对应前一半输出端的奇数部分。蝶式置换β(xn-1xn-2…xk+1xkxk-115012345670123456701234567012345670123456701234567蝶式置换β子蝶式置换β(1)超蝶式置换β

(1)n=3，N=8的蝶式置换β(n-1)(x)=β(n-1)(x)=β(x)β(0)(x)=β(0)(x)=x01234567012345670123456701234516超蝶式置换β(k)(xn-1xn-2…xn-k

xn-k-1xn-k-2…x1x0)=xn-k-1xn-2…xn-k

xn-1xn-k-2…x1x0子蝶式置换连接中共有2n-1个恒等连接，2n-2对交叉连接。共分为2n-k-1组，每2k+1个输入/输出端为一组，组内进行蝶式置换超蝶式置换连接中共有2n-1个恒等连接，2n-2对交叉连接。共分为2n-k-1组，低n-k-1位相同的为一组超蝶式置换β(k)(xn-1xn-2…xn-kxn-k17位序颠倒置换ρ(xn-1xn-2…xk+1xkxk-1…x1x0)=x0x1…xk-1xkxk+1…xn-2xn-1对于输入x=0或2n-1，输出仍为x，即恒等连接子位序颠倒置换ρ(k)(xn-1xn-2…xk+1xkxk-1…x1x0)=xn-1xn-2…xk+1x0x1…xk-1xk超位序颠倒置换ρ(k)(xn-1xn-2…xn-kxn-k-1xn-k-2…x1x0)=xn-k-1xn-k…xn-2xn-1xn-k-2…x1x0ρ(n-1)(x)=ρ

(n-1)(x)=ρ

(x)ρ(0)(x)=ρ

(0)(x)=x位序颠倒置换ρ(xn-1xn-2…xk+1xkxk-18012345670123456701234567012345670123456701234567位序颠倒置换ρ子位序颠倒置换ρ(1)超位序颠倒置换ρ

(1)n=3，N=8的位序颠倒置换01234567012345670123456701234519移数置换α(x)=(x±k)modN0≤x<N1≤k<N

组内移数置换α(x)(n-1):r=(x)(n-1):r

α(x)(r-1):0=((x)(r-1):0

±k)mod2r

共分为2n-r组，组内进行循环移数置换加减2I置换PM2+i(x)=(x+2i)modN0≤x<N0≤

i<n

PM2-i(x)=(x-2i)modN0≤x<N0≤

i<n

1≤k<2r1≤r≤

nα(n)(x)=α(x)

移数置换α(x)=(x±k)modN0≤x<N20012345670123456701234567012345670123456701234567左移移数置换k=2n=3，N=8的移数置换0123456701234567右移移数置换k=2组内左移移数置换k=1r=2组内右移移数置换k=1r=201234567012345670123456701234521左移移数置换k=2(0246)(1357)右移移数置换k=2(6420)(7531)组内左移移数置换k=1r=2(0123)(4567)组内右移移数置换k=1r=2(3210)(7654)PM2+0=(01234567)PM2-0=(76543210)PM2+1=(0246)(1357)PM2-1=(6420)(7531)PM2+2=(04)(15)(26)(37)PM2-2=(40)(51)(62)(73)左移移数置换k=2(0246)(13522012345670123456701234567012345670123456701234567i=0n=3，N=8的加减2I置换i=+1i=+201234567012345670123456701234523互连网络的结构参数与性能指标互连网络的结构参数

网络规模网络中的结点数。表示网络所能连接的部件个数。

结点度

一个结点射入或射出的边数。在单向网络中，入射边的数目称为入度，出射边的数目称为出度。结点度为入度和出度之和。在无向网络中，结点度为与结点相连的边数。互连网络的结构参数与性能指标互连网络的结构参数网络规模24

结点距离两结点间相连的最少边数。

网络直径互连网络中任意两结点间距离的最大值。

网络对剖宽度一个网络被切分为结点数相等的两半时，沿切口的最少边数。结点距离网络直径网络对剖宽度25

网络对称性若从网络的任意结点来看，网络的结构都是相同的，则称该网络是对称网络。

网络可扩展性在网络拓扑性能保持不变的情况下，可扩充结点的能力。网络对称性网络可扩展性26互连网络的传输性能参数AB机器A机器B机器A发送数据的步骤：机器A应用程序待发送数据机器A操作系统缓冲区机器A操作系统根据要发送的数据计算检查和，并把它放在消息中，同时启动超时计数器机器A操作系统缓冲区网络接口硬件消息互连网络的传输性能参数AB机器A机器B机器A发送数据的步骤27若收到机器B的回答信号则释放缓冲区中消息；若超时计数器超时还未收到回答信号则重发消息操作系统通知硬件开始发送消息等待来自机器B的回应若收到机器B的回答信号则释放缓冲区中消息；操作系统通知硬件开28机器B接收数据的步骤：网络接口硬件机器B操作系统缓冲区消息机器B操作系统根据接收到的数据计算检查和。若计算出的检查和与发送过来的匹配，向接收方发出回答信号；若不匹配，则删除消息若数据通过检查：机器B操作系统缓冲区数据用户地址空间启动应用程序继续执行机器B接收数据的步骤：网络接口硬件机器B操作系统缓冲区消息机29

频宽

互连网络传输信息的最大速率。MB/s

传输时间发送方传输时间：发送方从开始发送第一位信息起到把消息完全发送至网络所需时间接收方传输时间：接收方从接收到第一位信息起到完全接收到消息的时间频宽传输时间30

“飞行”时间消息的第一位信息到达接收方所需时间。包括网络中转发或其他硬件的时间延迟

传输时延发送方发送第一位信息到接收方完全接收到消息所需时间“飞行”时间+传输时间“飞行”时间传输时延31

发送方开销发送方在缓冲区中准备好待发送消息并送至网络接口硬件的时间

接收方开销接收方把消息从网络接口硬件取至缓冲区并拷贝至用户地址空间的时间发送方开销接收方开销32

总时延总时延=发送方开销+“飞行”时间+消息长度频宽+接收方开销传输时间总时延=发送方开销+“飞行”时间++接收方开销总时延=发送方开销+传输时延+接收方开销总时延总时延=发送方开销+“飞行”时间+消息长度频宽+接收33发送开销传输(发送)时间飞行时间接收开销传输(接收)时间发送开销传输(发送)时间飞行时间接收开销传输(接收)时间34发送方开销传输(发送)时间飞行时间传输(接收)时间接收方开销传输时延互连网络的传输性能参数关系图总时延发送第一个发送最后一个第一个到达接收方最后一个到达接收方发送方开销传输(发送)时间飞行时间传输(接收)时间接收方开销35例：假设一个网络的频宽为10Mb/s，发送方开销为230us，接收方开销为270us，如果两台机器相距100米，现要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，总时延为多大？（光速为299792.5km/s，信号在导体中的传递速度大约是光速的50%）例：假设一个网络的频宽为10Mb/s，发送方开销36T=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=7971usT=270us+230us+0.1km299792.5km/37互连网络的性能指标

通信时延从源结点到目的结点传送一条消息所需的总时间软件开销（取决于收发端的软件内核）在源结点和目的结点用于收发消息的软件所需的执行时间互连网络的性能指标通信时延38通道时延（取决于瓶颈链路的通道带宽）

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

网络时延

网络时延=通道时延+选路时延与程序行为和网络传输状态无关

端口带宽网络中从任意一个端口单位时间传送到其他端口的最大信息量。（b/s或B/s）网络时延端口带宽40

聚集带宽网络从一半结点到另一半结点，单位时间传送的最大信息量。

对剖带宽通过最小对剖平面的所有边的单位时间传送的最大信息量。聚集带宽对剖带宽41静态互连网络各结点间有专用的连接通路，且在运行中不能改变连接的网络。静态互连网络各结点间有专用的连接通路，且在运行中不42线性阵列中间结点2网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格线性阵列端结点1N-1N-11否N线性阵列允许不同的结点对并发使用系统的不同部分（通道）线性阵列网络类型结点度d网络直径链路数l等分宽度对称性网络43环网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格环2单向环N-1双向环N/2N2是N环网络类型结点度网络直径链路数l等分宽度对称性网络规格环44带弦环把环中不直接相连的每两个距离相等的结点用一条边连接起来0123456781011121314159度为3的带弦环带弦环把环中不直接相连的每两个距离相等的结点用一条0123450123456781011121314159度为4的带弦环0123456781011121314159度为4的带弦环46循环移数网络将环上每个结点与其距离为2整数幂的结点间增加一条附加链路而构成。设网络规模为N=2n，则结点x与以下结点有链路相连：(x±2i)mod2n(0≤i＜n)0123456789101112131415+2i

i=0,1,..,n-1正度=n-2i

i=0,1,..,n-2负度=n-1循环移数网络将环上每个结点与其距离为2整数幂的结点间增加047网络类型结点度d网络直径D链路数l对称性网络规格循环移数网络2n-1n/22n-1(2n-1)是N=2n等分宽度b2n-1n网络类型结点度网络直径链路数l对称性网络规格循环移2n-148全连接网络网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格全连接N-11N(N-1)/2是N(N/2)2全连接网络网络类型结点度网络直径链路数l等分宽度对称性网络49N/2N/2N/2N/2*N/2N/2N/2N/2*50树形网络拓扑结构是一棵完全二叉树。设有N个结点，共k层，则N=2k-1优点：可扩展性好缺点：直径长网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格树形叶结点1根结点2分支结点32(k-1)N-11否N=2k-1树形网络拓扑结构是一棵完全二叉树。设有N个结点，共k网络类51星形网络网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格星形根结点N-1叶结点12N-1N/2否N星形网络网络类型结点度d网络直径链路数l等分宽度对称性网络52胖树形网络网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格胖树形第j层结点3(k-j)+12≤j≤k根结点2k-2j=1j=2j=3j=42(k-1)k-1否N=2k-12k+1-2k-2缓解通向根结点的通信瓶颈胖树形网络网络类型结点度d网络直径链路数l等分宽度对称性网53l=j=1k-1(k-j)*2jl=j=1k-1(k-j)*2j54网格形网络网络类型结点度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网格形网络网络类型结点度d网络直径链路数l等分对称性网络规55三维网格形网络的内结点度为6，边结点度为4，角结点度为3，面内结点度为5。三维网格形网络的内结点度为6，边结点度为4，56ABAB57ABAB58Illiac网络网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格Illiac网络4n-12N2n否N=n2Illiac网络网络类型结点度d网络直径链路数l等分宽度对59ABAB60环网形网络网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格2D环网42n/22N2n是N=n2环网形网络网络类型结点度d网络直径链路数l等分宽度对称性网61搏动式阵列网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格搏动式阵列左右两角结点2上下两角结点3边结点4内结点62(n-1)3n2-4n+12n-1否N=n2搏动式阵列网络类型结点度d网络链路数l等分宽度对称性网络规62超立方体网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格超立方体nnnN/2N/2是N=2n超立方体网络类型结点度d网络直径链路数l等分宽度对称性网络63互连网络的基本概念课件64环中有K个结点带环立方体环中有带环立方体65k/2

下一维指针环中下一结点环中上一结点k/2

K维转发,d=(2k-1)+k/2

网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格带环k-立方体32k-1+k/23N/2N/(2k)是N=k×2k(k≥3)k/2下一维指针环中下一结点环中上一结点k/266ABCDEFGHIJKLMNOPA1B1B2C2C3G3G4O4O3O2A1O2ABCDEFGHIJKLMNOPA1B1B2C2C3G3G467k元n-立方体网络类型结点度d网络直径D链路数l等分宽度b对称性网络规格k元n-立方体2nnNnk/22kn-1是N=knk元n-立方体网络类型结点度d网络直径链路数l等分宽度对68动态互连网络动态互连网络可通过设置有源开关，从而根据需要借助控制信号对连接通路加以重新组合，实现所要求的通信模式。动态互连网络动态互连网络可通过设置有源开关，从而根69多处理机总线互连

用一组导线和插座将处理机、存储模块和各种外围设备互连起来，总线上的各模块需要通信时，发出申请，由总线仲裁逻辑对多个请求进行仲裁，进行总线服务分配。总线上各模块通过争用或时分方式获得总线服务。价格较低，带宽较窄多处理机总线互连

用一组导线和插座将处理机、存储模块和各种外70本地总线LMCPUIOC高速缓存IFCPU板本地外围设备存储器总线IF存储器板MC存储器单元数据总线IOP缓冲IFI/O板IF数据总线缓冲IF通信板IFCC系统总线（底板上）磁盘和磁带部件打印机或绘图仪网络（以太网等）本地总线LMCPUIOC高速缓存IFCPU板本地外围设备71机群间总线CCCPCP…CCCPCP…CCCPCP……存储器存储器……存储器机群间总线CCCPCP…CCCPCP…CCCPCP……存储器72总线互连的缺点

带宽有限没有冗余链路可扩展性有限层次总线的可扩展层次数有限总线互连的缺点73交叉开关互连大大展宽了互连传输频带，提高了系统的效率；但交叉开关设备量过大，成本过高（一般n≤16）采用按空间分配的机制交叉开关互连大大展宽了互连传输频带，提高了系统的效率；74M1M2Mn…P1PmI/O1I/Or……n≥r+mM1M2Mn…P1PmI/O1I/Or……n≥r+m75存储器模块多路转换器模块仲裁模块数据读/写地址自处理机P0~Pn-1数据读/写地址请求0请求1请求n-1存储器使能控制结点开关的结构存储器多路转换仲裁模块数据读/写地址自处理机数据读/写地址请76多级互连网络a×b……a×b………a×b……a×b……a×b………a×b……………………a×b……a×b………a×b………………ISCISCISC10a-1a+1a2a-1an-aan-a+1an-110b-1b+1b2b-1bn-b+1bn-bbn-1an-1个ban-2个bn-1个级1级2级n多级互连网络……………77多级互连网络把重复设置的多套动态单级网络串联起来，单级网络级间采用固定的级间连接模式，通过动态控制各单级网络的开关状态实现多级互连网络的输入端和输出端之间所需要的连接多级互连网络把重复设置的多套动态单级网78开关模块a×b……10a-110b-1通常取a=b=2k（k≥1）2功能开关4功能开关0101010101010101直送交叉上播下播开关模块……10a-110b-1通常取a=b=2k（k≥179级间连接模式多级互连网络中上一级开关模块的输出端和下一级开关模块的输入端相互连接的模式可用互连函数表示级间连接模式80控制方式互连网络拓扑结构可动态重构：可通过控制信号动态控制开关模块的状态来实现所要求的互连级控方式对同一级的所有开关用一个控制信号控制组控方式对第i级的开关分为i+1组，每组用一个控制信号控制（0≤i≤n-1）单元控制方式每一个开关有自己单独的控制信号控制方式级控方式81多级互连网络的分类

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

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

Ω=σEσE…σEI=(σE)n（E为开关级在开关控制方式下实现的交换置换）级间连接从输入端至输出端依次为Cn,…,850123456701234567K2K1K0C3C2C1C0Omega网络(N=8)0123456701234567K2K1K0C3C2C1C086采用终端标记寻径（D标记寻径）

xn-1xn-2…x1x0

yn-1yn-2…y1y0(D)xn-1xn-2…x1x0Cnxn-2xn-3…x1x0xn-1Kn-1xn-2xn-3…x1x0xn-1’Cn-1xn-3…x1x0xn-1’xn-2Kn-2xn-3…x1x0xn-1’xn-2’C1x0xn-1’xn-2’…x1’xn-1’xn-2’…x1’x0K0xn-1’xn-2’…x1’x0’C0xn-1’xn-2’…x1’x0’=yn-1yn-2…y1y0…………K1yi=0，第i级即Ki开关级上对应开关的输入端与开关的上输出端相连；yi=1，第i级即Ki开关级上对应开关的输入端与开关的下输出端相连；采用终端标记寻径（D标记寻径）xn-1xn-2…x1x0C87可能产生争用开关状态的冲突xi-1…x0xn-1’…xi+1’xiKixi-1…x0xn-1’…xi+1’xi’若两对连接的源端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上产生争用上输出端的冲突；在实现源与终端结点各不相同的置换连接时，如果不产生冲突，所有开关均不会出现上播或下播的状态；可能产生争用开关状态的冲突xi-1…x0xn-1’…xi+88例：在N=8的Omega网络中采用终端标记寻径法，至少要连接几次才能实现蝶式置换所要求的连接？第一次实现00,14,22,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开关的下输出端例：在N=8的Omega网络中采用终端标记寻径法，第一次实现890123456701234567K2K1K0C3C2C1C00123456701234567K2K1K0C3C2C1C090例：试给出一个简单的寻径算法实现Omega网络的任一源端对所有终端的广播连接。Si=01使Ki级相应开关上播使Ki级相应开关下播仅在播送连接中才可能出现开关的上播和下播状态例：试给出一个简单的寻径算法实现Omega网络Si=01使K910123456701234567K2K1K0C3C2C1C00123456701234567K2K1K0C3C2C1C092例：用一个N=8的三级Omega网络连接8个处理机(P0~P7)，8个处理机的输出端分别依序连接Omega网络的8个输入端0~7，8个处理机的输入端分别依序连接Omega网络的8个输出端0~7。如果处理机P6要把数据播送给处理机P0~P4，处理机P3要把数据播送给处理机P5~P7。那么，Omega网络能否同时为它们的播送要求实现连接？请画出实现播送的Omega网络的开关状态图。例：用一个N=8的三级Omega网络连接8个处理930123456701234567K2K1K0C3C2C1C00123456701234567K2K1K0C3C2C1C094STARAN网络N*N；共n=log2N级开关，从输入端至输出端依次为K0,K1…,Kn-1采用2*2的2功能开关，直送和交叉

每级N/2个开关，共m=(N/2)log2N个开关，共可实现2m种置换连接STARAN网络N*N；共n=log2N级开关，从输入端95采用级控方式或组控方式级间连接从输入端至输出端依次为C0,C1,…,Cn;其中，C1~Cn为逆洗牌置换，C0为恒等置换

S=IEσ-1Eσ-1…Eσ-1=(Eσ-1)n（E为开关级在开关控制方式下实现的交换置换）采用级控方式或组控方式级间连接从输入端至输出端依次为C0960123456701234567K0K1K2C0C1C2C3STARAN网络(N=8)0123456701234567K0K1K2C0C1C2C397xn-1xn-2…x1x0C0K0C1K1Cn-1xn-3’xn-2’…x0’xn-1xn-2’xn-2’xn-3’…x0’xn-1Kn-1xn-2’xn-3’…x0’xn-1’Cnxn-1’xn-2’…x1’x0’=yn-1yn-2…y1y0…………Kn-2(S)xn-1xn-2…x1x0

yn-1yn-2…y1y0(D)xn-1xn-2…x1x0xn-1xn-2…x1x0’x0’xn-1xn-2…x1x0’xn-1xn-2…x1’C2xn-1xn-2…x1x0C0K0C1K1Cn-1xn-3’98级控方式及交换置换xi’=E(xi)=xi+fixi-1’…x0’xn-1…xiKixi-1’…x0’xn-1…xi’E(xn-1xn-2…x1x0)=(+fn-1,xn-1+fn-2,xn-2…+f1,x1+f0)x0可实现N种置换级控方式及交换置换xi’=E(xi)=xi+fixi-1’99若级控信号F中仅fi为1，其余各位为0：

E(xn-1…xi…x1x0)=xn-1…xi…x1x0=Cubei(x)分组交换置换：若分为2n-k组，每组2k个元素，则同组元素低k位必不同，高n-k位必相同。让同组元素反序，得到输出序列。

xn-1…xkxk-1…x1x0xn-1…xkxk-1…x1x0若级控信号F中仅fi为1，其余各位为0：分组交换置换：若100x2x1x04组2元4组2元+2组4元2组4元2组4元+1组8元4组2元+2组4元+1组8元4组2元+1组8元1组8元x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0x2x1x0例如：实现2组4元交换x2x1x04组2元4组2元+2组4元2组4元2组4元+1组101000001010011100101110111012345670123456710233210456754677654321076453201546776540123102376453201恒等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+C2C1+C2C0+C1+C200000101001110010111011100123410201234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567012345670123456701234567F=(000)F=(001)F=(010)F=(011)F=(100)F=(101)F=(110)F=(111)0000000000000000F=(000)F=(001)103组控方式及移数置换组控信号F中有m=n(n+1)/2个位信号，可实现2m种置换

若n=3，F=(f23f22f21f12f11f0)可实现的移数置换：

α(x)=(x+2m)mod2P+x/2p*2p

(0≤m<p≤n)

共可实现(n2+n+2)/2种移数置换连接

组控方式及移数置换组控信号F中有m=n(n+1)/2个位104f23f22f21f12f11f00010110111101110000000110001100000010000000123456712345670234567014567012312305674230167451032547601234567组控信号输入端号移数功能移1mod8移2mod8移4mod8移1mod4移2mod4移1mod2不移恒等f23001000001241210组输移数移1移2移1050123456701234567K0K1K2C0C1C2C3例如：实现移2模8置换0123456701234567K0K1K2C0C1C2C310601234567012345670123456701234567012345670123456701234567012345670123456701234567移1模2移1模4移2模4恒等移1模80123456701234567移2模8移4模801234567012345670000000000移1模2移1模4移2模4恒等移1模800107例：设有一四级立方体网络，对于下述连接分别写出网络的级控信号和互连函数。4组4元交换4组4元交换+1组16元交换E(x3x2x1x0)=x3x2x1x0=Cube1(Cube0(x3x2x1x0))F=f3f2f1f0=0011E(x3x2x1x0)=x3x2x1x0=Cube3(Cube2(x3x2x1x0))F=f3f2f1f0=1100例：设有一四级立方体网络，对于下述连接分别E(x3x2x1x108间接二进制n方体网络N*N；共n=log2N级开关，从输入端至输出端依次为K0,K1…,Kn-1采用2*2的2功能开关，直送和交叉每级N/2个开关，共m=(N/2)log2N个开关，可实现2m种置换连接级间连接从输入端至输出端依次为C0,C1,…,Cn;其中，C1~Cn-1为子蝶式置换，C0为恒等置换

，Cn为逆洗牌置换

C=IE

(1)

E

(2)

…E

(n-1)

Eσ-1（E为开关级在开关控制方式下实现的交换置换）采用单元控制方式间接二进制n方体网络N*N；共n=log2N级开关，从输1090123456701234567K0K1K2C0C1C2C3间接二进制n方体网络(n=3)0123456701234567K0K1K2C0C1C2C3110xn-1xn-2…x1x0C0K0C1K1Cn-1xn-1xn-3’xn-2’…x0’xn-2’xn-2’xn-3’…x0’xn-1Kn-1xn-2’xn-3’…x0’xn-1’Cnxn-1’xn-2’…x1’x0’=yn-1yn-2…y1y0…………Kn-2(S)xn-1xn-2…x1x0

yn-1yn-2…y1y0(D)xn-1xn-2…x1x0xn-1xn-2…x2x1x0’xn-1xn-2…x2x0’x1xn-1xn-2…x2x0’x1’xn-1…xi+1xi-1’…x0’xiKixn-1…xi+1xi-1’…x0’xi’Cn-2xn-1xn-2…x1x0C0K0C1K1Cn-1xn-1x111终端标记寻径（D标记寻径）用yi控制Ki级上所到达开关的状态：若yi=0，从该开关的上输出端输出；若yi=1，从该开关的下输出端输出。若两个源结点序号的xi+1~xn-1，x0’~xi-1’均相同，xi不同，即到达Ki级同一开关(开关号为xn-1…xi+1xi-1’…x0’)的不同输入端。若yi相同，则产生对该开关的上(yi=0)或下(yi=1)通道的争用冲突终端标记寻径（D标记寻径）用yi控制Ki级上所到达开关的状112上控法用到达开关级Ki相应开关的上输入端(xi=0)的终端标记yi来控制该开关的状态：yi=0，该开关为直送状态；yi=1，该开关为交叉状态。若到达Ki级某开关的下输入端，则遵守由到达该开关上输入端的某对连接所确定的状态。若遵守状态后导致本连接xi’=yi（即两个终结点序号yi相同），则产生冲突，不能同时实现此两对连接。上控法用到达开关级Ki相应开关的上输入端(xi=0)的终端113T标记寻径法用ti=xiyi作为单元控制标记。若ti=0，则开关状态为直送；否则开关状态为交叉。若两个源结点到达Ki级同一开关的不同输入端，即它们的xi+1~xn-1，x0’~xi-1’均相同，xi不同，开关号为xn-1…xi+1xi-1’…x0’。若xiyi不同，则产生开关状态争用冲突++T标记寻径法用ti=xiyi作为单元控制标记。若t114例1：实现连接05，12，26，33，44，57，61，70。采用上控法和T标记寻径法是否会发生阻塞？12与26争用K1级0开关的下输出端，并导致K2级2开关为上播状态；44与70争用K1级2开关的上输出端，并导致K2级0开关为下播状态；例1：实现连接05，12，26，33，12与261150123456701234567K0K1K2C0C1C2C3采用上控法0123456701234567K0K1K2C0C1C2C31160123456701234567K0K1K2C0C1C2C3采用T标记寻径法0123456701234567K0K1K2C0C1C2C3117例2：实现连接03，16，24，31，42，57，65，70。采用上控法和T标记寻径法是否会发生阻塞？不发生阻塞。例2：实现连接03，16，24，31，不发生阻塞。1180123456701234567K0K1K2C0C1C2C3采用上控法0123456701234567K0K1K2C0C1C2C3119Delta网络an*bn；开关从输入端至输出端依次为K1,K2…,Kn采用a*b的开关Ki级开关的开关数为an-ibi-1(1≤i≤

n)，Ki的输入端数为an-i+1bi-1，输出端数为an-ibiDelta网络an*bn；开关从输入端至输出端依次为K1120级间连接从输入端至输出端依次为C0,C1,…,Cn;Ci的输入和输出端数均为an-ibi。C0和Cn为恒等连接，其余级间连接均采用q洗牌置换

q洗牌置换：将qr张牌分成q组，每组r张，洗牌时先将所有组的第一张牌顺序放在前q个位置，再将所有组的第二牌顺序放在接下来的q个位置，直到各组牌全部取完为止。f(x)=(xmodr)*q+x/r在Ci级中，对an-ibi个输入端分为an-ibi-1组，每组b个进行q洗牌置换级间连接从输入端至输出端依次为C0,C1,f(x)=(x121采用单元控制方式采用终端标记寻径方法来实现源端对终端的连接采用单元控制方式采用终端标记寻径方法来实现源端对终端122an×bn的Delta网络a×b……a×b………a×b……a×b……a×b………a×b……………………a×b……a×b………a×b………………10a-1a+1a2a-1an-aan-a+1an-110b-1b+1b2b-1bn-b+1bn-bbn-1an-1个ban-2个bn-1个K1K2KnC0C1C2Cn-1Cn…q洗牌置换q洗牌置换q洗牌置换an×bn的Delta网络……………12301230124567345891011678121314159101101230124567345891011678000102101112202122K1K2C0C1C2例：1742*32的Delta网络012301245673458910116781213141124x经开关Ki+1后变为：x/a*b+wi+1(0≤i<n,0≤wi+1<b)x经级间连接Ci后变为：(xmodb)*an-ibi-1+x/b(0<i<n)S=s0*a0+s1*a1+…sn-1*an-1D=d0*b0+d1*b1+…dn-1*bn-1SK1(s1*a0+…sn-1*an-2)*b+w1C1(s1*a0+…sn-1*an-2)+w1*an-1K2(s2*a0+…sn-1*an-3+w1*an-2)*b+w2C2(s2*a0+…sn-1*an-3+w1*an-2)+w2*an-2bKn-1(sn-1*a0+w1*a1+w2*ab…+wn-2*abn-3)*b+wn-1Cn-1(sn-1*a0+w1*a1+w2*ab…+wn-2*abn-3)+wn-1*abn-2x经开关Ki+1后变为：S=s0*a0+s1125Kn(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-1Cn(w1+w2*b1+…+wn-2*bn-3+wn-1*bn-2)*b+wn用di控制开关级Ki(1≤i<n)，d0控制开关级KnKn(w1+w2*b1+…+wn-2*bn-3+wn-1*b126例：比较4*9的单级交叉开关和用二级2*3的交叉开关组成的4*9的Delta网络，比较这两种互连网络的开关设备量。4*9单级交叉开关的开关数为36，每套开关内部有4选1的多路转换逻辑和可对4个请求信号进行仲裁的仲裁模块。二级22*32的Delta网络的开关数为30，每个开关只需2选1的多路选择器和可对2个请求信号进行仲裁的仲裁模块。例：比较4*9的单级交叉开关和用二级2*3的交叉4*9单级交127Benes二进制置换网络N*N；共2log2N=2n级开关，从输入端至输出端依次为K0,K1…,Kn-1,Kn,…,K2n-1采用2*2的2功能开关，直送和交叉每级N/2个开关，共N(log2N)个开关Benes二进制置换网络N*N；共2log2N=2n级开128级间连接从输入端至输出端依次为C0,C1,…,Cn,Cn+1,…,C2n;其中，C0,Cn,C2n是恒等置换;C1~Cn-1为逆子洗牌置换(Ci=

(n-i)

-11≤i≤n-1);Cn+1~C2n-1为子洗牌置换(Ci=

(i-n)

n+1≤i≤2n-1)

=IE

(n-1)

-1

E

(n-2)-1…E(1)

-1EIE(1)…E(n-1)EI（E为开关级在开关控制方式下实现的交换置换）采用单元控制方式可将Kn-1和Kn级合并为一个开关级级间连接从输入端至输出端依次为C0,C1,采用单元控制方1290123456701234567K0K1K2K3K4K5C0

C1C2C3C4C5C6d0d1d2d2d1d0

(2)

-1

(1)

-1

(1)

(2)

III0123456701234567K0K1K2K3K4K5C0130(S)xn-1xn-2…x1x0

yn-1yn-2…y1y0(D)xn-1xn-2…x1x0K0xn-1xn-2…x1x0’C1x0’xn-1xn-2…x1K1x0’xn-1xn-2…x1’C2x0’x1’xn-1xn-2…x2K2x0’x1’xn-1xn-2…x2’C3x0’x1’x2’xn-1xn-2…x3Kn-1x0’x1’x2’…xn-1’Cnx0’x1’x2’…xn-1’Knx0’x1’x2’…xn-1’’Cn+1x0’x1’x2’…xn-1’’xn-2’…Kn+1x0’x1’…xn-1’’xn-2’’Cn+2x0’x1’…xn-1’’xn-2’’xn-3’…K2n-1xn-1’’xn-2’’…x1’’x0’’=yn-1yn-2…y1y0(S)xn-1xn-2…x1x0yn-1yn-2…y1131采用改进的终端标记控制算法：上控法或下控法上控法：用到达开关级Ki相应开关的上输入端的终端标记yi来控制该开关的状态：yi=0，该开关为直送状态；yi=1，该开关为交叉状态下控法：用到达开关级Ki相应开关的下输入端的终端标记yi来控制该开关的状态：yi=0，该开关为交叉状态；yi=1，该开关为直送状态采用改进的终端标记控制算法：上控法或上控法：用到达开关级132为可重排非阻塞网络，可实现N!种源终端间的置换连接。但并不是所有置换连接都能一次实现，每一对源和终结点的连接至少存在两条路径，当一条走不通时可选择另一条又称为全排列网络N个输入端和N个输出端的置换连接共有N！种。为可重排非阻塞网络，可实现N!种源终端又称为全排列网络N133网络置换连接比例N=8比例值Omega(NN/2)/N!4096/40320STARAN级控N/N!8/40320STARAN组控2n(n+1)/2/N!64/40320间接二进制n方体(NN/2)/N!4096/40320Benes二进制置换N!/N!1网络置换连接比例N=8比例值Omega(NN/2)/N!40134采用上控法若通过Ki(0≤i≤n-2)级某开关后使得xi’=yi，称为产生了变异，若该变异能在K2n-1-i级恢复，则称为变异被修正。若通过Ki(n≤i)级某开关后使得xi’’=yi，也称产生了变异，且该变异是不能修正的。若通过Kn-1级某开关后使得xn-1’=yn-1，也称产生了变异，且该变异是不能修正的。采用上控法若通过Ki(0≤i≤n-2)级某开关后使得135

所谓冲突情况是:当某条路径P经过在某级I的某开关E时,它自己的出路被别的路径所占用。这样，只好走另外的那条出路。（图中：虚线为应走路径，实线为实走路径）冲突上图下图修正所谓冲突情况是:当某条路径P经过在某级I的某开关E时136

某条路径P在某级I的开关E上的冲突意味着：它本应该作“交换”却没有“交换”（上图情况）；或它本不应该作“交换”而却作了“交换”（下图情况）。这种情况我们称为“变异”，这样，有冲突必有变异。那么，怎样去“修正”这种变异？

Benes二进制置换网络是左右对称的，之所以这样设计，是为了在左边发生的变异而在右边去修正这种变异。只是这种修正应该在与左边相对称的开关级上进行。某条路径P在某级I的开关E上的冲突意味着：它本应该作137例1：实现位序颠倒置换例1：实现位序颠倒置换1380123456701234567K0K1K2K3K4K5C0C1C2C3C4C5C6d0d1d2d2d1d0变异修正变异修正变异修正变异修正0123456701234567K0K1K2K3K4K5C0139例2：实现置换00,11,27,33,44,56,65,72例2：实现置换00,11,27,33,441400123456701234567K0K1K2K3K4K5C0C1C2C3C4C5C6d0d1d2d2d1d0变异修正变异变异修正变异修正变异变异变异变异修正变异修正未修正0123456701234567K0K1K2K3K4K5C0141互连网络的消息传递机制数据传递的方式：共享变量方式共享存储器多处理器系统消息传递方式分布式存储器多处理器系统所有的处理器共享一个统一编址的物理存储器，它可以是集中式的，也可以分布在各个处理器结点中每个处理器只能对本地存储器直接进行读/写操作互连网络的消息传递机制数据传递的方式：所有的处理器共享一142消息格式消息：由任意数目的长度固定的包组成，是结点间通信的基本单位包：包含寻径目的地址的结点间通信的基本单位；可异步传输，每个包有一个包序号，以便在接收方进行包重组片：将包分成等长的片，寻径信息（源地址和目的地址）和序号形成头片，其余是数据片消息格式消息：由任意数目的长度固定的包组成，是结包：包143DDDDDDSR消息包片R：寻径信息S：顺序号D：数据片DDDDDDSR消息包片R：寻径信息S：顺序号144消息寻径方式

消息寻径方式：消息从发送地传送到目的地对路径的选取方式消息寻径方式消息寻径方式：消息从发送地传送到目的145