高级时间体系结构课件——第7章

1、1 1/55/55第7章 互连网络张晨曦张晨曦 刘依刘依www.GotoS2 2/55/557.1 互连网络的基本概念7.2 互连网络的结构3 3/55/551. 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。结点：处理器、存储模块或其他设备。互连网络在系统中的位置，如图所示。在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。 7.1 互连网络的基本概念7.1.1 互连网络的功能和特性4 4/55/557.1 互连网络的基本概念 互连网络互连网络 结结 点点 链路链路 结结 点点 链路链路 结结 点点 链路链路 互连网络在系统

2、中的位置互连网络在系统中的位置5 5/55/557.1 互连网络的基本概念1. 可以从4个不同的方面来描述互连网络定时方式：有同步和异步两种。q同步系统：同步系统：使用一个统一的时钟。使用一个统一的时钟。 SIMDSIMD阵列处理机就属于这一种类型。阵列处理机就属于这一种类型。q异步系统：异步系统：没有统一的时钟，系统中的各个处理机都没有统一的时钟，系统中的各个处理机都是独立地工作。是独立地工作。交换方法：有线路交换和分组交换两种。q线路交换：线路交换：源结点和目的结点之间的物理通路在整个源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。数据传送期间一直保持连接。q分组交换：分组交

3、换：把信息分割成许多组（又称为包），将它把信息分割成许多组（又称为包），将它们分别送入互连网络。们分别送入互连网络。6 6/55/557.1 互连网络的基本概念n这些数据包可以通过不同的路径传送，到达目这些数据包可以通过不同的路径传送，到达目的结点后再拼合成原来的数据。的结点后再拼合成原来的数据。n结点之间不存在固定连接的物理通路。结点之间不存在固定连接的物理通路。控制策略：有集中式和分散式两种q集中控制方式：集中控制方式：有一个全局的控制器接收所有的通有一个全局的控制器接收所有的通信请求，并由它设置互连网络的开关连接。信请求，并由它设置互连网络的开关连接。q分散控制方式：分散控制方式：不存在

4、全局的控制器，通信请求的不存在全局的控制器，通信请求的处理和开关的设置由互连网络分散地进行。处理和开关的设置由互连网络分散地进行。7 7/55/557.1 互连网络的基本概念拓扑结构：有静态和动态两种。q静态拓扑结构：静态拓扑结构：在各结点之间有专用的连接通路，且在各结点之间有专用的连接通路，且在运行过程中不能改变。在运行过程中不能改变。q动态拓扑结构：动态拓扑结构：可根据需要设置互连网络中的开关，可根据需要设置互连网络中的开关，从而对结点之间的连接通路进行重新组合，实现所要从而对结点之间的连接通路进行重新组合，实现所要求的通信模式。求的通信模式。8 8/55/557.1 互连网络的基本概念

5、变量x：输入（设x=0，1，N1） 函数f(x)：输出 通过数学表达式建立输入端与输出端的一一对应关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系。（有时也称为（有时也称为置换函数置换函数或或排列函数排列函数） 7.1.2 互连函数9 9/55/557.1 互连网络的基本概念互连函数f(x)有时可以采用循环表示 即：（x0 x1 x2 xj-1） 表示： f(x0)=x1，f(x1)=x2，f(xj-1)=x0 j称为该循环的长度。几种常用的基本互连函数及其主要特征：1. 交换函数 交换函数：实现二进制地址编码中第k位

6、互反的输入端与输出端之间的连接。011121011121xxxxxxxxxxxxxxEkkknnkkknn1010/55/557.1 互连网络的基本概念主要用于构造立方体互连网络和各种超立方体互连网络。它共有nlog2N种互连函数。 （N N为结点个数）为结点个数）当N8时，n3，可得到常用的立方体互连函数： 012012201201210120120 xxxxxxCxxxxxxCxxxxxxC1111/55/557.1 互连网络的基本概念q变换图形变换图形 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) C0交换函数交换函数 0 1 2 3 4 5 6 7 0 1 2

7、 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (b) C1交换函数交换函数 (c) C2交换函数交换函数 N=8 N=8 的立方体交换函数的立方体交换函数 1212/55/557.1 互连网络的基本概念立方体网络立方体网络1313/55/557.1 互连网络的基本概念1. 均匀洗牌函数均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。 q函数关系函数关系 即把输入端的二进制编号循环左移一位。即把输入端的二进制编号循环左移一位。101320121nnnnnxxxxxxxxxS14

8、14/55/557.1 互连网络的基本概念qN=8N=8 的的均匀洗牌均匀洗牌和和逆均匀洗牌逆均匀洗牌函数函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) 均均匀匀洗洗牌牌函函数数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (b) 逆逆均均匀匀洗洗牌牌函函数数 N=8 N=8 的均匀洗牌和逆均匀洗牌函数的均匀洗牌和逆均匀洗牌函数1515/55/557.1 互连网络的基本概念逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号。q互连函数互连函数 逆均匀洗牌是均匀洗牌的逆函数逆均匀洗牌是均匀洗牌的逆函数 1. 碟式函数 蝶式互

9、连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。 121001211xxxxxxxxSnnnn11200121nnnnxxxxxxxxB1616/55/557.1 互连网络的基本概念1. 反位序函数 反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。q互连函数互连函数 q对于对于N N8 8的情况，的情况，B(x)B(x)函数等于函数等于R(x)R(x)函数。函数。12100121nnnnxxxxxxxxR1717/55/557.1 互连网络的基本概念qN N8 8的蝶式函数的变换图形的蝶式函数的变换图形 0 1 2 3 4 5 6 7 0 1 2

10、3 4 5 6 7 (a) 碟式函数碟式函数 (b) 反位序函数反位序函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 N=8 N=8 的碟式函数和反位序函数的碟式函数和反位序函数1818/55/557.1 互连网络的基本概念1. PM2I函数 PM2I函数：一种移数函数，它是将各输入端都循环移动一定的位置连到输出端。互连函数 PM2+i(x) x2i mod N PM2-i(x) x2i mod N 其中：其中： 0 xN0 xN1 1，0in0in1 1，n nloglog2 2N N，N N为结点数。为结点数。PM2I互连网络共有2n个互连函数。1919/55/557

11、.1 互连网络的基本概念当N8时，有6个PM2I函数：qPM2PM2+0+0 ：（0 1 2 3 4 5 6 70 1 2 3 4 5 6 7）qPM2PM2-0-0 ：（7 6 5 4 3 2 1 07 6 5 4 3 2 1 0）qPM2PM2+1+1 ：（0 2 4 6 0 2 4 6 ）（）（1 3 5 71 3 5 7）qPM2PM2-1-1 ：（6 4 2 06 4 2 0）（）（7 5 3 17 5 3 1）qPM2PM22 2：（0 40 4）（）（1 51 5）（）（2 62 6）（）（3 73 7） 2020/55/557.1 互连网络的基本概念N=8 N=8 的的PM2I

12、PM2I函数函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) PM2+0 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (b) PM2+1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (c) PM2+2 阵列计算机ILLIAC 采用采用PM2PM20 0和和PM2PM2n/2n/2构成其互连网络，实现各构成其互连网络，实现各处理单元之间的上下左右互连处理单元之间的上下左右互连 。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 用移数函数构成用移数函数构成ILLIAC ILLIAC 阵列机的互连网络阵

13、列机的互连网络2222/55/557.1 互连网络的基本概念1. 网络通常是用有向边或无向边连接有限个结点的图来表示。2. 互连网络的主要特性参数有：网络规模：网络中结点的个数。 表示该网络所能连接的部件的数量。表示该网络所能连接的部件的数量。结点度：与结点相连接的边数（通道数），包括入度和出度。q进入结点的边数称为进入结点的边数称为入度入度。q从结点出来的边数称为从结点出来的边数称为出度出度。7.1.3 互连网络的特性参数2323/55/557.1 互连网络的基本概念距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。网络直径：网络中任意两个结点之间距离的

14、最大值。网络直径应当尽可能地小。网络直径应当尽可能地小。结点之间的线长：两个结点之间连线的长度，用米、千米等表示。等分宽度：当某一网络被切成相等的两半时，沿切口的边数（通道数）的最小值称为通道等分宽度，用b表示。2424/55/557.1 互连网络的基本概念q线等分宽度：线等分宽度：B Bb bw wq其中：其中：w w为通道宽度（用位表示）。为通道宽度（用位表示）。q该参数主要反映了网络最大流量。该参数主要反映了网络最大流量。对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。 对称网络比较容易实现，编程也比较容易。对称网络比较容易实现，编程也比较容易。2525/55/55互连网络通

15、常可以分为两大类：静态互连网络 各结点之间有固定的连接通路且在运行中不能改各结点之间有固定的连接通路且在运行中不能改变的网络。变的网络。动态互连网络 由交换开关构成、可按运行程序的要求动态地改由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。变连接状态的网络。下面介绍几种静态互连网络。 （其中：（其中：N N表示结点的个数）表示结点的个数） 7.2 互连网络的结构7.2.1 静态互连网络2626/55/557.2 互连网络的结构1. 线性阵列 一种一维的线性网络，其中N个结点用N-1个链路连成一行。q端结点的度：端结点的度：1 1q其余结点的度：其余结点的度：2 2q直径：直径：N

16、N1 1q等分宽度等分宽度b=1b=1 2727/55/557.2 互连网络的结构2828/55/557.2 互连网络的结构q对称对称q结点的度：结点的度：2 2q双向环的直径：双向环的直径：N/2N/2q单向环的直径：单向环的直径：N N 1. 环和带弦环 环 用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。2929/55/557.2 互连网络的结构带弦环 增加的链路愈多，结点度愈高，网络直径就愈小。3030/55/557.2 互连网络的结构全连接网络 q结点度：结点度：1515q直径最短，为直径最短，为1 1。 1. 循环移数网络通过在环上每个结点到所有与其

17、距离为2的整数幂的结点之间都增加一条附加链而构成。N=16N=16q结点度：结点度：7 7q直径：直径：2 2 3232/55/557.2 互连网络的结构一般地，如果j-i=2r（r=0,1,2,n-1，n=log2N），则结点i与结点j连接。q结点度：结点度：2n2n1 1q直径：直径：n/2n/23333/55/557.2 互连网络的结构1. 树形和星形 一棵5层31个结点的二叉树 一般说来，一棵k层完全平衡的二叉树有N=2k-1个结点。q最大结点度：最大结点度：3 3q直径：直径：2(k-1) 2(k-1) 星形 q结点度较高，为结点度较高，为N N1 1。q直径较小，是一常数直径较小，

18、是一常数2 2。q可靠性比较差，只要中心结点出故障，整个系统就会可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。瘫痪。 3434/55/557.2 互连网络的结构3535/55/557.2 互连网络的结构1. 胖树形 3636/55/557.2 互连网络的结构1. 网格形和环网形 网格形q一个一个3 33 3的的网格形网络网格形网络q一般来说，一般来说，N=nN=nk k 个结点的个结点的k k维网络的内部结点度是维网络的内部结点度是2k2k，网络直径为网络直径为k(n-1)k(n-1)。 环形网q可看作是直径更短的另一种网格。可看作是直径更短的另一种网格。 q将环形和网格形组合在一起，并

19、能向高维扩展。将环形和网格形组合在一起，并能向高维扩展。q沿阵列的每行和每列都有环形连接。沿阵列的每行和每列都有环形连接。q一个一个n nn n二元环网二元环网n结点度：结点度：4 4n直径：直径：2 2 n/2n/2 3737/55/557.2 互连网络的结构3838/55/557.2 互连网络的结构1. 超立方体 一种二元n维立方体结构一般来说，一个二元n维立方体由N=2n 个结点组成，它们分布在n维上，每维有两个结点。 例例 8 8个结点的个结点的3 3维立方体维立方体 4 4维立方体维立方体为实现一个n维立方体，只要把两个（n1）维立方体中相对应的结点用链路连接起来即可。共需要2n-1

20、条链路。n维立方体中结点的度都是n，直径也是n。 3939/55/557.2 互连网络的结构静态互连网络一览表静态互连网络一览表 网络类型网络类型 结点度结点度d d 网络直径网络直径D D 链路数链路数l l 等分宽度等分宽度B B 对称性对称性 网络规格说明网络规格说明 线线阵列线线阵列 2 2 N-1 N-1 N-1 N-1 1 1非非 N N个结点个结点 环形环形 2 2 N/2 N/2 N N2 2是是 N N个结点个结点 全连接全连接 N-1 N-1 1 1N(N-1)/2 N(N-1)/2 (N/2)(N/2)2 2 是是 N N个结点个结点 二叉树二叉树 3 3 2(h-1)

21、2(h-1) N-1 N-1 1 1非非 树高树高h=logh=log2 2N N 星形星形 N-1 N-1 2 2N-1 N-1 N/2N/2非非 N N个结点个结点 2D2D网格网格 4 4 2(r-1) 2(r-1) 2N-2r 2N-2r r r非非 r rr r网格，网格， IlliacIlliac网网 4 4 r-1r-12N2N2r2r非非 与与 的带弦的带弦环等效环等效 2D2D环网环网 4 4 2r/2 2r/2 2N2N2r2r是是 r rr r网格，网格，超立方体超立方体 n n n n nN/2 nN/2 N/2N/2是是 N N个结点个结点n=logn=log2 2N

22、NCCC CCC 3 3 2k-1+k/2 2k-1+k/2 3N/2 3N/2 N/(2k) N/(2k) 是是 N=kN=k2 2k k结点结点环长环长k3 k3 NrNr Nr 4141/55/557.2 互连网络的结构1. 总线一组导线和插座，用于进行与总线相连的处理机、存储模块和外围设备等之间的数据传送。每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。多个功能模块之间的争用总线或时分总线。 特点q价格低价格低q带宽较窄带宽较窄7.2.2 动态互连网络4242/55/557.2 互连网络的结构一种由总线连接的多处理机系统 4343/55/557.2 互连网络

23、的结构1. 多级互连网络MIMD和SIMD计算机都使用多级互连网络MIN（Multistage Interconnection Network）一种通用的多级互连网络 q由由a ab b开关模块和级间连接构成的通用多级互连网络结构开关模块和级间连接构成的通用多级互连网络结构q每一级都用了多个每一级都用了多个a ab b开关开关na a个输入和个输入和b b个输出个输出n在理论上，在理论上，a a和和b b不一定相等，然而实际上不一定相等，然而实际上a a和和b b经常经常选为选为2 2的整数幂，即的整数幂，即a ab b2 2k k，k1k1。 q相邻各级开关之间都有固定的级间连接相邻各级开关

24、之间都有固定的级间连接4444/55/557.2 互连网络的结构4545/55/557.2 互连网络的结构几种常用的开关模块 模块大小模块大小 合法状态合法状态 置换连接置换连接 2 22 2 4 4 2 24 44 4 25625624248 88 8 16 777 21616 777 21640 32040 320n nn n n nn n n! n! 4646/55/557.2 互连网络的结构最简单的开关模块：22开关 22开关的4种连接方式 4747/55/557.2 互连网络的结构各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。q控制方式控制方式：对各个开关模块

25、进行控制的方式。：对各个开关模块进行控制的方式。n级控制：级控制：每一级的所有开关只用一个控制信号每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态；控制，只能同时处于同一种状态；n单元控制：单元控制：每一个开关都有一个独立的控制信每一个开关都有一个独立的控制信号，可各自处于不同的状态；号，可各自处于不同的状态；n部分级控制：部分级控制：第第i i级的所有开关分别用级的所有开关分别用i i1 1个信个信号控制，号控制，0in0in1 1，n n为级数。为级数。 q常用的级间互连模式：常用的级间互连模式：均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等均匀洗牌、蝶式、多路洗牌、纵横交叉

26、、立方体连接等 4848/55/557.2 互连网络的结构两种多级互连网络 qOmegaOmega网络网络 0 0 0 0 0 4 2 1 1 1 2 2 1 4 2 5 6 3 3 3 4 4 2 1 4 6 3 5 5 5 6 6 3 5 6 7 7 7 7 7 8 88 8的的OmegaOmega网络网络4949/55/557.2 互连网络的结构n一个一个N N输入的输入的OmegaOmega网络有网络有loglog2 2N N级，每级用级，每级用N/2N/2个个2 22 2开关模块，共需要开关模块，共需要NlogNlog2 2N/2N/2个开关。个开关。n每个开关模块均采用单元控制方式

27、。每个开关模块均采用单元控制方式。n不同的开关状态组合可实现各种置换、广播或不同的开关状态组合可实现各种置换、广播或从输入到输出的其他连接。从输入到输出的其他连接。5050/55/557.2 互连网络的结构q多级立方体网络多级立方体网络 n采用二功能（直送和交换）的采用二功能（直送和交换）的2 22 2开关和交换函数构成开关和交换函数构成n级间互连按从左到右的次序分别是级间互连按从左到右的次序分别是C C0 0、C C1 1、C C2 2互连函数互连函数例如：例如： 当所有开关都直送时，实现恒等变换；当所有开关都直送时，实现恒等变换； 当当A A、B B、C C、D D四个开关交换、其余直送时，实现四个开关交换、其余直送时，实现C C0 0互连互连函数；函数； 当当E E、F F、G G、H H四个开关交换、其余直送时，实现四个开关交换、其余直送时，实现C C1 1互连互连函数；函数； 当当I I、J J、K K、L L四个开关交换、其余直送时，实现四个开关交换、其余直送时，实现C C2 2互连互连函数。函数。5151/55/557.2 互连