并行计算机体系结构第六章课件

第六章互联网络第六章互联网络1互连网络的作用用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着决定性的影响。一个例子：具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构互连网络的作用用来实现计算机系统内部多个处理机或多个功能部件2磁盘SM1SM2SMmPMN……CnPnLMC1P1LMPCN……………………PION磁带打印机终端网络…(共享存储器)(共享I/O与外设)磁盘SM1SM2SMmPMN……CnPnLMC1P1LMPC3互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络的主要特性有：(1)网络规模：网络中结点的个数(2)结点度：与结点相连接的边数称为结点度进入结点的边数叫入度从结点出来的边数则叫出度(3)距离：两个结点之间相连的最少边数(4)网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示互连网络的特性互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络4互连网络的性能参数发送方的步骤如下：(1)用户程序把要发送的数据拷贝到系统缓冲区。(2)缓冲区中的数据打包并发送到网络接口部件。(3)网络接口硬件开始发送消息。数据包的接收步骤如下：(1)把数据包从网络接口部件拷贝到系统缓冲区。(2)检查收到的数据包，如果正确，发回答信号。(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区互连网络的性能参数发送方的步骤如下：5互连网络的主要性能参数：(1)频带宽度(Bandwidth)：传输信息的最大速率(2)传输时间(Transmissiontime)：等于消息长度除以频宽。(3)飞行时间(Timeofflight)：第一位信息到达接收方所花费的时间。(4)传输时延(Transportlatency)：等于飞行时间与传输时间之和。(5)发送方开销(Senderoverhead)：处理器把消息放到互连网络的时间。(6)接收方开销(Receiveroverhead)：处理器把消息从网络取出来的时间。互连网络的主要性能参数：6一个消息的总时延可以用下面公式表示：总时延＝发送方开销＋飞行时间＋消息长度/频宽＋接收方开销例7.1：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销分别为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？一个消息的总时延可以用下面公式表示：7解：光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50％。相距100米时总时延为：相距1000公里时的总时延为：解：光的速度为299792.5KM/S，信号在导体中传递速度8为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法：(1)互连函数表示法：

如：f(xn-1…x1x0)=x0xn-2…x1xn-1(2)图形表示法(3)输入输出对应表示法互连

网络…0011…n-1n-1输入:01234567

输出:10325476互连网络的表示方法为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示9互连函数互连函数也称为互连置换或互连排列等。1.交换函数（Exchange）当n＝3时，有3种函数，每种能表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数， 用Cube表示，如：Cube0、Cube1、Cube2等。互连函数互连函数也称为互连置换或互连排列等。10并行计算机体系结构第六章课件112.全混洗函数（Perfectshuffle）函数关系：把二进制结点号循环左移一位子混洗(subshuffle)S(k),最低k位循环左移一位超混洗(supershuffle)S(k),最高k位循环左移一位

2.全混洗函数（Perfectshuffle）12并行计算机体系结构第六章课件133.蝶式函数（Butterfly）蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。函数关系： 将输入端二进制结点号的最高位和最低位互换位置。子蝶式(subbutterfly)B(k)

最低k位的高低位互换超蝶式(superbutterfly)B(k)

最高k位的高低互换

显然成立：3.蝶式函数（Butterfly）14并行计算机体系结构第六章课件154.反位序函数（BitReversal）函数关系：将二进制自变量的位序反过来。子反位序函数，最低k位的位序反过来超反位序函数，最高k位的位序反过来4.反位序函数（BitReversal）165.移数函数函数关系：将输入端向量循环移动一定的位置经常取r＝2i，因此移数函数又称为加减2i函数、PM2I函数等。子移数函数： 其中：0xN-1，0i,kn-1，n=log2N。Illiac函数包含PM20和PM2n/2等4个互连函数每个接点与它的上下左右4个相邻接点连接5.移数函数17并行计算机体系结构第六章课件18例6.2：假设16个处理机的编号分别为0、1、…、15，采用单级互连网络。互连函数分别为：

(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal

第12号处理机分别与哪一个处理机相连？例6.2：假设16个处理机的编号分别为0、1、…、15，采用19解：(12)10=(1100)2(1)Cube3，(2)PM2+3，(3)PM2-0，

(4)Shuffle，(5)Butterfly，(6)Reversal1100最高位取反得0100，4号处理机

(12+8)MOD16=4，4号处理机

12–1=11，11号处理机

1100循环左移1位得到1001,9号处理机

1100的最高最低位交换0101,5号处理机

1100的位序反过来为0011,3号处理机解：(12)10=(1100)220

补充:基本的单级互连网络1.立方体单级网络立方体的每个顶点代表一个结点，结点的编号用二进制码（C2C1C0）表示。N＝8的三维立方体结构补充:基本的单级互连网络N＝8的三维立方体结构21

立方体单级网络的互连函数实现二进制编号中第k位值不同的结点之间的连接。故三维的立方体单级网络有三种互连函数：Cube0、Cube1和Cube2，分别建立结点编号中C0不同或C1不同或C2不同的结点之间的连结。N＝8的三维立方体三种互连方式 立方体单级网络的互连函数实现二进制编号中第k位值不同的22

一般情况下，一个n维立方体有N＝2n个结点，共有n种互连函数，分别由n位编号中的每一位的位值求反来确定。当维数n＞3时，称为超立方体(HyperCube)网络。对于n维立方体单级网络，要实现任意两个结点之间的连接，最多需使用n次不同的互连函数因此n维立方体单级网络的最大距离为n。 一般情况下，一个n维立方体有N＝2n个结点，共有n种互连函232．PM2I（是加减2i的简称，plus－minus2i）

PM2I单级网络能实现j号结点与j±2i

modN号结点的直接相连，N为处理器的个数，n＝log2N。因此，它共有2n个互连函数，即PM2＋i（j）＝j＋2i

modNPM2－i（j）＝j－2imodN

式中，0≤j≤N－1，0≤i≤n－1。 设N＝8，则各互连循环为

PM2＋0：（01234567）

PM2－0：（76543210）

PM2＋1：（0246）（1357）

PM2－1：（6420）（7531）

PM2±2：（04）（15）（26）（37）2．PM2I（是加减2i的简称，plus－minus2i）24N＝8的PM2I互连网络的部分连接图

网络的最大距离为

n/2=log2N/2

，这里表示向上取整。由三维PM2I互连网络可以看出，最多只要两次使用，即可实现任意一对入出端号间的连接。

PM2I互连特性N＝8的PM2I互连网络的部分连接图网络的最253.混洗交换(shuffleexchange)混洗交换互连网络包含全混洗和交换两种互连函数。（1）全混洗 全混洗的互连函数为Shuffle（Pn－1Pn－2…P1P0）＝Pn－2…P1P0Pn－1

全混洗互连示意图3.混洗交换(shuffleexchange)26（2）交换 由于单一的全混洗互连网络不能实现二进制编号为全“0”和全“1”的结点与其他任何结点的连接，所以又增加了Cube0交换互连函数。同时采用了全混洗和交换的单级互连网络称为混洗交换单级互连网络。N＝8的全混交换互连网络连接图

在混洗交换网络中，最远的两个入出端号是全“0”和全“1”，它们的连接需要n次交换和n-1次混洗，所以其最大距离为2n-1。（2）交换N＝8的全混交换互连网络连接图在混洗交27互连网络的种类静态互连网络循环互连网络多级互连网络 互连网络的种类静态互连网络28静态互连网络：在各结点之间有固定的连接通路，在运行过程中不能改变。一般不能实现任意结点到结点之间的互连。循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连。多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连，是动态互连网络的一种，适用于SIMD和MIMD。静态互连网络：在各结点之间有固定的连接通路，在运行过程中不能29静态互连网络

在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。一般静态互连网络不能实现任意结点到结点之间的互连。一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方体等。静态互连网络在各结点之间有固定的连接通路，在运行过程中不30循环互连网络一般静态互连网不能实现任意两结点之间的互连。有两种解决办法：循环互连网：多次重复使用同一个单级互连网络多级互连网：将多套相同的单级互连网络连接起来前一种方法是牺牲时间换取设备，后一种方法是以设备换取时间。循环互连网络一般静态互连网不能实现任意两结点之间的互连。有两31多级互连网络

多级网络互连是将多套单级互连网络通过关模块串连扩展成多级互连网络（简称MIN）的方式。与单级网络相比，多级网络可以通过改变开关的控制方式灵活地实现各种连接，满足系统应用的需要。多级互连网络采用多个相同的或不同的单级互连网络直接连接起来。一个时钟周期就能够实现任意结点到结点之间的互连。常见的有多级立方体互连网络、多级混洗交换网络（Omega网络）、多级PM2I网络、多级BENES可重排网络及多级CLOS网络等。

多级互连网络 多级网络互连是将多套单级互连网络通过关模32多级互连网络采用的关键技术：

(1)交换开关，

(2)交换开关之间的拓扑连接，

(3)对交换开关的不同控制方式。多级互连网络采用的关键技术：331.交换开关一个a×b交换开关有a个输入和b个输出。最常用的二元开关：a=b=2。每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为交叉开关。具有直通和交换两种功能的开关称为二功能开关，或交换开关。用一位控制信号控制。具有所有4种功能的交换开关称为四功能开关，用两位控制信号控制。1.交换开关34

交换开关的四种功能交换开关的四种功能352.拓扑结构又称为级间连接模式ISC(interstageconnection)，是前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。级间连接是固定的，可以用互连函数表示级间连接模式。常用的级间连接模式包括混洗、交叉、立方体连接等，从而构成具有不同连接特性的多级互连网络。2.拓扑结构363.控制方式控制方式是指通过对开关模块的状态控制来实现多级网络间互连要求的方式，称之为互连网络拓扑结构可动态重构。有多级交换开关，每一级又有多个交换开关。 通常有三种控制方式级控制：同一级交换开关使用同一个控制信号控制。单元级控制：每个交换开关分别控制。部分级控制：第i级使用i+1个控制信号控制（0in-1）。同一个多级互连网络分别常用三种不同的控制方式，可以构成三种不同的互连网络。3.控制方式374.多级立方体网络是将Cube0、Cube1和Cube2三种函数构成的单级网络串接起来，是一种STARAN网络。使用二功能交换开关，即直通和交换，分级控制，可实现交换网络功能。采用不同方式控制，可实现不同连通功能。即当第i级控制信号为0时，开关直通；若控制信号为1，则开关交换，实现Cubei的功能。若采用部分级控，则实现移数网络功能，若采用单元控制，则是间接二进制n方体网络。

N＝8立方体多级互连网络4.多级立方体网络N＝8立方体多级互连网络38级控制信号（K2K1K0）000001010011100101110111入端号012345670123456710325476230167453210765445670123547610326745230176543210执行的交换函数功能恒等四组二元四组二元＋二组四元二组四元二组四元＋一组八元四组二元＋二组四元＋一组八元四组二元＋一组八元一组八元iCube0Cube1Cube0＋Cube1Cube2Cube0＋Cube2Cube1＋Cube2Cube0＋Cube1＋Cube2三级STARAN交换网络（N＝8）级控制信号的组合及所实现的功能级控制信号（K2K1K0）00000101001110010395.多级混洗交换网络又称为OMEGA网络，由n级相同的网络组成，各级包含一个全混洗拓扑和一列四功能的交换开关，采用单元控制方式。对于一个N=2n个输入输出端的OMEGA网络，共需要n级2×2开关，每一级包含N/2个采用单元控制的四功能交换开关。5.多级混洗交换网络40

N＝8多级混洗交换网络N＝8多级混洗交换网络416.多级PM2I网络包含n级单元连接，每一级都是把前后两列各N＝2

n个单元按PM2I拓扑相互连接起来的。对于第i级(0≤i≤n-1),每一个输入端j都有三条输出线与之连接，即j、(j+2i)modN和(j-2i)modN，也就是通过交换开关选择直通、上播和下播。三级PM2I网络中第0级完成的是PM2I±0的函数功能，第1级完成的是PM2I±1的函数功能，第2级完成的是PM2I±2的函数功能。6.多级PM2I网络42系统互连结构系统互连结构：计算机子系统互连在一起或构造多处理机或多计算机的静态和动态网络。我们先介绍组成网络的拓扑结构，再讨论互连网络的通信特性（时延、等分带宽、数据寻径功能）。网路的通信效率对并行计算机的性能十分重要。网络数据传送率高、时延低、通信频带宽。系统互连结构系统互连结构：计算机子系统互连在一起或构造多处理43网络特性和寻径功能互连网络的拓扑可以采用静态或动态结构。静态网路由点-点直接相连而成，这种连接方式在程序执行过程中不会改变。动态网路是用开关通道实现的，它可以动态改变结构，使之与用户程序中的通信要求匹配网络特性和寻径功能互连网络的拓扑可以采用静态或动态结构。静态44网络特性和寻径功能静态网络常用来实现集中式系统的子系统之间或分布式系统的多个计算结点之间的固定连接。动态网络包括总线、交叉开关和多级网络，常用于共享存储型多处理机中。网络特性和寻径功能静态网络常用来实现集中式系统的子系统之间或45网络特性和寻径功能网路是用有向边或无向边连接有限个结点的图表示的。图中结点的数量成为网络规模结点度：与结点相连接的边的数量。入度、出度。网路直径：网络中任意两个结点之间最短路径的最大值。网络直径的度量：链路数。网络直径应该尽可能小网络特性和寻径功能网路是用有向边或无向边连接有限个结点的图表46网络特性和寻径功能等分带宽：网络被切成相等的两部分，沿切口的最小边数成为通道等分宽度。通信网络中，每条边相当于一条线宽为w位的通道。线等分宽度B=b*w。B反映了网络的布线密度。等分带宽反映沿等分网络最大通信带宽。结点之间的线长：影响信号的时延网络特性和寻径功能等分带宽：网络被切成相等的两部分，沿切口的47网络特性和寻径功能数据寻径功能：数据寻径网络用来进行PE间数据交换。寻径网路可以是动态的，也可以是静态的。寻径网络的功能强大，有利于减少数据交换所需要的时间，能够显著改善系统性能。常见的寻径功能：移数、循环、置换、广播、选播、洗牌、交换等网络特性和寻径功能数据寻径功能：数据寻径网络用来进行PE间数48网络特性和寻径功能置换：对n个对象来说，有n！种置换，n个对象可以按照置换排序。∏=(a,b,c)(d,e)。循环(a,b,c)的周期为3，(d,e)的周期为2。则∏的周期为6网络特性和寻径功能置换：对n个对象来说，有n！种置换，n个对49网络特性和寻径功能均匀洗牌和交换:均匀洗牌是为平行处理应用提出的一种特殊置换功能。均匀洗牌逆均匀洗牌网络特性和寻径功能均匀洗牌和交换:均匀洗牌是为平行处理应用提50网络特性和寻径功能超立方体寻径功能网络特性和寻径功能超立方体寻径功能51网络特性和寻径功能广播是一种一对全体的映射选播是一种一个子集到另一个子集的映射。个人广播：只将个人信息传送给选定的接收者。网络特性和寻径功能广播是一种一对全体的映射52网络特性和寻径功能网络性能：功能特性—网络如何支持数据寻径、中断处理等网络时延—单位消息通过网络传送时最坏情况下的时间延迟带宽—通过网络的最大数据传输率硬件复杂性—硬件造价（导线、开关网络特性和寻径功能网络性能：53静态连接网络线性阵列：内部结点度2，外部1。直径为N-1，等分宽度b=1静态连接网络线性阵列：内部结点度2，外部1。直径为N-1，等54静态连接网络线性阵列：内部结点度2，外部1。直径为N-1，等分宽度b=1。当n很大时，通信效率很低。N=2，线性阵列经济线性阵列可以由多个结点并发使用线路不同部分。总线不行静态连接网络线性阵列：内部结点度2，外部1。直径为N-1，等55静态连接网络环和带弦环：结点度2。单向环直径为N，双向环直径为N/2。静态连接网络环和带弦环：结点度2。单向环直径为N，双向环直径56静态连接网络带弦环：增加的链路越多，节点度越高，网络直径越小。静态连接网络带弦环：增加的链路越多，节点度越高，网络直径越小57静态连接网络循环移数网络：将环上每个结点到与其距离为2整数幂的结点之间增加一条附加链构成的设网络规模N=2n结点度d=2n-1直径D=n/2静态连接网络循环移数网络：将环上每个结点到与其距离为2整数幂58静态连接网络树形和星形结点度=3直径2（k-1）其中规模N=2k-1胖树是对二叉树的改进，通向根节点的瓶颈问题静态连接网络树形和星形结点度=3胖树是对二叉树的改进，59静态连接网络网格型和环形

静态连接网络网格型和环形60静态连接网络超立方体：n-立方体结点度等于n，网络直径等于n。静态连接网络超立方体：n-立方体结点度等于n，网络直径等于n61静态连接网络超立方体：n-立方体结点度等于n，网络直径等于n。静态连接网络超立方体：n-立方体结点度等于n，网络直径等于n62静态连接网络带环立方体：k-带环立方体直径为2k。结点度数为3，与维数无关静态连接网络带环立方体：k-带环立方体直径为2k。63静态连接网络网络吞吐量：单位时间内网络能处理的总信息量。可以用网络通量来衡量，也就是网络中能同时容纳的信息总量。网络的最大吞吐量是容量的一部分静态连接网络网络吞吐量：64动态连接网络为了得到多用或通用的目的，需要采用动态链接网络、它能够根据程序要求实现通信模式，不用固定连接，而是沿着连接通路使用开关或国际网络以进行节点之间的动态连接。动态连接网络为了得到多用或通用的目的，需要采用动态链接网络、65动态连接网络

1.动态互连网络的三个主要操作特征

定时开关控制2.根据级间连结方式，动态互连网络分为

(1)单级网络也称循环网络

(2)多级网络由一级以上的开关元件构成。这类网络可以把任一输入与任一输出相连。动态连接网络定时2.根据级间连结方式，动态互连网络分为66

阻塞网络

如果同时连接多个输入输出对时,可能会引起开关和通信链路使用上的冲突。大多数多级网络都是阻塞网络。非阻塞网络

如果多级网络通过重新安排连接方式可以建立所有可能的输入输出之间的连接。阻塞网络67动态连接网络数字总线：一组导线和插座用于处理与总线相连的处理机、存储模块和外围设备间的数据业务。总线主设备、从设备、争用动态连接网络数字总线：一组导线和插座用于处理与总线相连的处理68动态连接网络开关模块：开关状态直送、交叉，上翻、下翻动态连接网络开关模块：开关状态直送、交叉，上翻、下翻69动态连接网络开关模块和合法状态ModuleSizeLegitimateStatesPermutationConnection动态连接网络开关模块和合法状态ModuleSizeLegi70动态连接网络多级网络：Ω网络。注意构成方法。级数：log2n每级n/2个开关动态连接网络多级网络：Ω网络。注意构成方法。级数：log2n71动态连接网络多级网络：基准网络。注意构成方法。动态连接网络多级网络：基准网络。注意构成方法。72动态连接网络多级网络：交叉开关网络动态连接网络多级网络：交叉开关网络73三种动态网络比较总线造价最低，但是每台处理机可用的带宽较窄。总线容易产生故障。交叉开关的硬件复杂性成n2上升，造价昂贵。但是交叉开关的带宽和寻径性能最好。对于小规模网络，是理想选择多级网络是两个极端的折中。采用模块结构，可扩展性好。但是时延随网络级数logn上升三种动态网络比较总线造价最低，但是每台处理机可用的带宽较窄。74互连网络切换技术互连网络切换技术75第六章互联网络第六章互联网络76互连网络的作用用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着决定性的影响。一个例子：具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构互连网络的作用用来实现计算机系统内部多个处理机或多个功能部件77磁盘SM1SM2SMmPMN……CnPnLMC1P1LMPCN……………………PION磁带打印机终端网络…(共享存储器)(共享I/O与外设)磁盘SM1SM2SMmPMN……CnPnLMC1P1LMPC78互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络的主要特性有：(1)网络规模：网络中结点的个数(2)结点度：与结点相连接的边数称为结点度进入结点的边数叫入度从结点出来的边数则叫出度(3)距离：两个结点之间相连的最少边数(4)网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示互连网络的特性互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络79互连网络的性能参数发送方的步骤如下：(1)用户程序把要发送的数据拷贝到系统缓冲区。(2)缓冲区中的数据打包并发送到网络接口部件。(3)网络接口硬件开始发送消息。数据包的接收步骤如下：(1)把数据包从网络接口部件拷贝到系统缓冲区。(2)检查收到的数据包，如果正确，发回答信号。(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区互连网络的性能参数发送方的步骤如下：80互连网络的主要性能参数：(1)频带宽度(Bandwidth)：传输信息的最大速率(2)传输时间(Transmissiontime)：等于消息长度除以频宽。(3)飞行时间(Timeofflight)：第一位信息到达接收方所花费的时间。(4)传输时延(Transportlatency)：等于飞行时间与传输时间之和。(5)发送方开销(Senderoverhead)：处理器把消息放到互连网络的时间。(6)接收方开销(Receiveroverhead)：处理器把消息从网络取出来的时间。互连网络的主要性能参数：81一个消息的总时延可以用下面公式表示：总时延＝发送方开销＋飞行时间＋消息长度/频宽＋接收方开销例7.1：假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销分别为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？一个消息的总时延可以用下面公式表示：82解：光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50％。相距100米时总时延为：相距1000公里时的总时延为：解：光的速度为299792.5KM/S，信号在导体中传递速度83为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法：(1)互连函数表示法：

如：f(xn-1…x1x0)=x0xn-2…x1xn-1(2)图形表示法(3)输入输出对应表示法互连

网络…0011…n-1n-1输入:01234567

输出:10325476互连网络的表示方法为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示84互连函数互连函数也称为互连置换或互连排列等。1.交换函数（Exchange）当n＝3时，有3种函数，每种能表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数， 用Cube表示，如：Cube0、Cube1、Cube2等。互连函数互连函数也称为互连置换或互连排列等。85并行计算机体系结构第六章课件862.全混洗函数（Perfectshuffle）函数关系：把二进制结点号循环左移一位子混洗(subshuffle)S(k),最低k位循环左移一位超混洗(supershuffle)S(k),最高k位循环左移一位

2.全混洗函数（Perfectshuffle）87并行计算机体系结构第六章课件883.蝶式函数（Butterfly）蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。函数关系： 将输入端二进制结点号的最高位和最低位互换位置。子蝶式(subbutterfly)B(k)

最低k位的高低位互换超蝶式(superbutterfly)B(k)

最高k位的高低互换

显然成立：3.蝶式函数（Butterfly）89并行计算机体系结构第六章课件904.反位序函数（BitReversal）函数关系：将二进制自变量的位序反过来。子反位序函数，最低k位的位序反过来超反位序函数，最高k位的位序反过来4.反位序函数（BitReversal）915.移数函数函数关系：将输入端向量循环移动一定的位置经常取r＝2i，因此移数函数又称为加减2i函数、PM2I函数等。子移数函数： 其中：0xN-1，0i,kn-1，n=log2N。Illiac函数包含PM20和PM2n/2等4个互连函数每个接点与它的上下左右4个相邻接点连接5.移数函数92并行计算机体系结构第六章课件93例6.2：假设16个处理机的编号分别为0、1、…、15，采用单级互连网络。互连函数分别为：

(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal

第12号处理机分别与哪一个处理机相连？例6.2：假设16个处理机的编号分别为0、1、…、15，采用94解：(12)10=(1100)2(1)Cube3，(2)PM2+3，(3)PM2-0，

(4)Shuffle，(5)Butterfly，(6)Reversal1100最高位取反得0100，4号处理机

(12+8)MOD16=4，4号处理机

12–1=11，11号处理机

1100循环左移1位得到1001,9号处理机

1100的最高最低位交换0101,5号处理机

1100的位序反过来为0011,3号处理机解：(12)10=(1100)295

补充:基本的单级互连网络1.立方体单级网络立方体的每个顶点代表一个结点，结点的编号用二进制码（C2C1C0）表示。N＝8的三维立方体结构补充:基本的单级互连网络N＝8的三维立方体结构96

立方体单级网络的互连函数实现二进制编号中第k位值不同的结点之间的连接。故三维的立方体单级网络有三种互连函数：Cube0、Cube1和Cube2，分别建立结点编号中C0不同或C1不同或C2不同的结点之间的连结。N＝8的三维立方体三种互连方式 立方体单级网络的互连函数实现二进制编号中第k位值不同的97

一般情况下，一个n维立方体有N＝2n个结点，共有n种互连函数，分别由n位编号中的每一位的位值求反来确定。当维数n＞3时，称为超立方体(HyperCube)网络。对于n维立方体单级网络，要实现任意两个结点之间的连接，最多需使用n次不同的互连函数因此n维立方体单级网络的最大距离为n。 一般情况下，一个n维立方体有N＝2n个结点，共有n种互连函982．PM2I（是加减2i的简称，plus－minus2i）

PM2I单级网络能实现j号结点与j±2i

modN号结点的直接相连，N为处理器的个数，n＝log2N。因此，它共有2n个互连函数，即PM2＋i（j）＝j＋2i

modNPM2－i（j）＝j－2imodN

式中，0≤j≤N－1，0≤i≤n－1。 设N＝8，则各互连循环为

PM2＋0：（01234567）

PM2－0：（76543210）

PM2＋1：（0246）（1357）

PM2－1：（6420）（7531）

PM2±2：（04）（15）（26）（37）2．PM2I（是加减2i的简称，plus－minus2i）99N＝8的PM2I互连网络的部分连接图

网络的最大距离为

n/2=log2N/2

，这里表示向上取整。由三维PM2I互连网络可以看出，最多只要两次使用，即可实现任意一对入出端号间的连接。

PM2I互连特性N＝8的PM2I互连网络的部分连接图网络的最1003.混洗交换(shuffleexchange)混洗交换互连网络包含全混洗和交换两种互连函数。（1）全混洗 全混洗的互连函数为Shuffle（Pn－1Pn－2…P1P0）＝Pn－2…P1P0Pn－1

全混洗互连示意图3.混洗交换(shuffleexchange)101（2）交换 由于单一的全混洗互连网络不能实现二进制编号为全“0”和全“1”的结点与其他任何结点的连接，所以又增加了Cube0交换互连函数。同时采用了全混洗和交换的单级互连网络称为混洗交换单级互连网络。N＝8的全混交换互连网络连接图

在混洗交换网络中，最远的两个入出端号是全“0”和全“1”，它们的连接需要n次交换和n-1次混洗，所以其最大距离为2n-1。（2）交换N＝8的全混交换互连网络连接图在混洗交102互连网络的种类静态互连网络循环互连网络多级互连网络 互连网络的种类静态互连网络103静态互连网络：在各结点之间有固定的连接通路，在运行过程中不能改变。一般不能实现任意结点到结点之间的互连。循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连。多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连，是动态互连网络的一种，适用于SIMD和MIMD。静态互连网络：在各结点之间有固定的连接通路，在运行过程中不能104静态互连网络

在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。一般静态互连网络不能实现任意结点到结点之间的互连。一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方体等。静态互连网络在各结点之间有固定的连接通路，在运行过程中不105循环互连网络一般静态互连网不能实现任意两结点之间的互连。有两种解决办法：循环互连网：多次重复使用同一个单级互连网络多级互连网：将多套相同的单级互连网络连接起来前一种方法是牺牲时间换取设备，后一种方法是以设备换取时间。循环互连网络一般静态互连网不能实现任意两结点之间的互连。有两106多级互连网络

多级网络互连是将多套单级互连网络通过关模块串连扩展成多级互连网络（简称MIN）的方式。与单级网络相比，多级网络可以通过改变开关的控制方式灵活地实现各种连接，满足系统应用的需要。多级互连网络采用多个相同的或不同的单级互连网络直接连接起来。一个时钟周期就能够实现任意结点到结点之间的互连。常见的有多级立方体互连网络、多级混洗交换网络（Omega网络）、多级PM2I网络、多级BENES可重排网络及多级CLOS网络等。

多级互连网络 多级网络互连是将多套单级互连网络通过关模107多级互连网络采用的关键技术：

(1)交换开关，

(2)交换开关之间的拓扑连接，

(3)对交换开关的不同控制方式。多级互连网络采用的关键技术：1081.交换开关一个a×b交换开关有a个输入和b个输出。最常用的二元开关：a=b=2。每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为交叉开关。具有直通和交换两种功能的开关称为二功能开关，或交换开关。用一位控制信号控制。具有所有4种功能的交换开关称为四功能开关，用两位控制信号控制。1.交换开关109

交换开关的四种功能交换开关的四种功能1102.拓扑结构又称为级间连接模式ISC(interstageconnection)，是前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。级间连接是固定的，可以用互连函数表示级间连接模式。常用的级间连接模式包括混洗、交叉、立方体连接等，从而构成具有不同连接特性的多级互连网络。2.拓扑结构1113.控制方式控制方式是指通过对开关模块的状态控制来实现多级网络间互连要求的方式，称之为互连网络拓扑结构可动态重构。有多级交换开关，每一级又有多个交换开关。 通常有三种控制方式级控制：同一级交换开关使用同一个控制信号控制。单元级控制：每个交换开关分别控制。部分级控制：第i级使用i+1个控制信号控制（0in-1）。同一个多级互连网络分别常用三种不同的控制方式，可以构成三种不同的互连网络。3.控制方式1124.多级立方体网络是将Cube0、Cube1和Cube2三种函数构成的单级网络串接起来，是一种STARAN网络。使用二功能交换开关，即直通和交换，分级控制，可实现交换网络功能。采用不同方式控制，可实现不同连通功能。即当第i级控制信号为0时，开关直通；若控制信号为1，则开关交换，实现Cubei的功能。若采用部分级控，则实现移数网络功能，若采用单元控制，则是间接二进制n方体网络。

N＝8立方体多级互连网络4.多级立方体网络N＝8立方体多级互连网络113级控制信号（K2K1K0）000001010011100101110111入端号012345670123456710325476230167453210765445670123547610326745230176543210执行的交换函数功能恒等四组二元四组二元＋二组四元二组四元二组四元＋一组八元四组二元＋二组四元＋一组八元四组二元＋一组八元一组八元iCube0Cube1Cube0＋Cube1Cube2Cube0＋Cube2Cube1＋Cube2Cube0＋Cube1＋Cube2三级STARAN交换网络（N＝8）级控制信号的组合及所实现的功能级控制信号（K2K1K0）000001010011100101145.多级混洗交换网络又称为OMEGA网络，由n级相同的网络组成，各级包含一个全混洗拓扑和一列四功能的交换开关，采用单元控制方式。对于一个N=2n个输入输出端的OMEGA网络，共需要n级2×2开关，每一级包含N/2个采用单元控制的四功能交换开关。5.多级混洗交换网络115

N＝8多级混洗交换网络N＝8多级混洗交换网络1166.多级PM2I网络包含n级单元连接，每一级都是把前后两列各N＝2

n个单元按PM2I拓扑相互连接起来的。对于第i级(0≤i≤n-1),每一个输入端j都有三条输出线与之连接，即j、(j+2i)modN和(j-2i)modN，也就是通过交换开关选择直通、上播和下播。三级PM2I网络中第0级完成的是PM2I±0的函数功能，第1级完成的是PM2I±1的函数功能，第2级完成的是PM2I±2的函数功能。6.多级PM2I网络117系统互连结构系统互连结构：计算机子系统互连在一起或构造多处理机或多计算机的静态和动态网络。我们先介绍组成网络的拓扑结构，再讨论互连网络的通信特性（时延、等分带宽、数据寻径功能）。网路的通信效率对并行计算机的性能十分重要。网络数据传送率高、时延低、通信频带宽。系统互连结构系统互连结构：计算机子系统互连在一起或构造多处理118网络特性和寻径功能互连网络的拓扑可以采用静态或动态结构。静态网路由点-点直接相连而成，这种连接方式在程序执行过程中不会改变。动态网路是用开关通道实现的，它可以动态改变结构，使之与用户程序中的通信要求匹配网络特性和寻径功能互连网络的拓扑可以采用静态或动态结构。静态119网络特性和寻径功能静态网络常用来实现集中式系统的子系统之间或分布式系统的多个计算结点之间的固定连接。动态网络包括总线、交叉开关和多级网络，常用于共享存储型多处理机中。网络特性和寻径功能静态网络常用来实现集中式系统的子系统之间或120网络特性和寻径功能网路是用有向边或无向边连接有限个结点的图表示的。图中结点的数量成为网络规模结点度：与结点相连接的边的数量。入度、出度。网路直径：网络中任意两个结点之间最短路径的最大值。网络直径的度量：链路数。网络直径应该尽可能小网络特性和寻径功能网路是用有向边或无向边连接有限个结点的图表121网络特性和寻径功能等分带宽：网络被切成相等的两部分，沿切口的最小边数成为通道等分宽度。通信网络中，每条边相当于一条线宽为w位的通道。线等分宽度B=b*w。B反映了网络的布线密度。等分带宽反映沿等分网络最大通信带宽。结点之间的线长：影响信号的时延网络特性和寻径功能等分带宽：网络被切成相等的两部分，沿切口的122网络特性和寻径功能数据寻径功能：数据寻径网络用来进行PE间数据交换。寻径网路可以是动态的，也可以是静态的。寻径网络的功能强大，有利于减少数据交换所需要的时间，能够显著改善系统性能。常见的寻径功能：移数、循环、置换、广播、选播、洗牌、交换等网络特性和寻径功能数据寻径功能：数据寻径网络用来进行PE间数123网络特性和寻径功能置换：对n个对象来说，有n！种置换，n个对象可以按照置换排序。∏=(a,b,c)(d,e)。循环(a,b,c)的周期为3，(d,e)的周期为2。则∏的周期为6网络特性和寻径功能置换：对n个对象来说，有n！种置换，n个对124网络特性和寻径功能均匀洗牌和交换:均匀洗牌是为平行处理应用提出的一种特殊置换功能。均匀洗牌逆均匀洗牌网络特性和寻径功能均匀洗牌和交换:均匀洗牌是为平行处理应用提125网络特性和寻径功能超立方体寻径功能网络特性和寻径功能超立方体寻径功能126网络特性和寻径功能广播是一种一对全体的映射选播是一种一个子集到另一个子集的映射。个人广播：只将个人信息传送给选定的接收者。