《并行处理技术》PPT课件.ppt

《《并行处理技术》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《并行处理技术》PPT课件.ppt（87页珍藏版）》请在三一办公上搜索。

1、计算机系统结构,第6章 并行处理技术,本章学习要求,理解并行处理机的结构和工作原理；了解并行处理机与流水处理机的差别；熟练掌握基本的单级互连网络及其互连函数表示；理解循环互连网络的实现；熟练掌握多级网络、全排列网络的画法；,本章学习要求,了解多处理机的特点及主要技术；掌握并行算法研究思路，程序并行性分析结论，任务的派生和汇合；理解多处理机任务粒度、通信开销对性能的影响；了解多处理机操作系统,并行处理技术,是获取高性能计算的重要手段通过资源的重复设置以实现性能的改善，其发展是没有极限的有双重含义：同时性（Simultaneity）和并发性（Concurrency）,6.1 并行处理技术的基本概念

2、,并行处理的目的提高速度对于一个固定规模的问题，采用并行计算技术可以使求解时间更少现在的微型机也开始借助于流水线技术、多核技术等并行计算技术来提高系统的速度扩大问题求解规模由于器件本身的限制，任何单处理器的速度不能超过某个上限要突破这个上限，必须采用并行计算技术,6.1 并行处理技术的基本概念,数据处理过程中可能存在若干个可以同时进行处理的部分。用一个处理部件按时间顺序先后处理它们，称串行处理用若干个处理部件同时处理这些部分，称并行处理 并行性概念同时性并发性,6.1 并行处理技术的基本概念,并行处理相对于串行处理而言，着重开发计算过程中的并发事件，用并行性粒度 G 来描述；,所有处理器处理时

3、间的总和,所有处理器通信时间的总和,6.1 并行处理技术的基本概念,粒度细,表明处理器间通信时间长;粒度粗,表明处理器之间通信量小,性能较好。程序执行过程分个 5 级别：作业级,任务级,程序级,指令级,指令内操作级,粗粒度级别,细粒度级别,主要由多处理机或多计算机系统实现。开发手段:软件,在单处理机实现,开发手段:硬件.如流水技术,6.1 并行处理技术的基本概念,并发性开发的途径有：时间重叠：多个处理过程在时间上错开，重叠使用同一部件，以赢得速度，如指令流水执行方式。资源重复：通过设置多套功能部件，利用空间上的并行性提高指令执行速度资源共享：利用软件的方法，让多个任务在时间上轮流使用一套资源，

4、以提高资源的利用率。,6.2 SIMD并行计算机（阵列处理机）,并行处理机（Parallel Processor）的一个重要特点是处理机有并列的多个处理单元，每个单元的组成都相同或相似。并行处理机内部有数十、数百甚至更多个处理单元，每个单元可以有自己的运算器、存储器、寄存器组或别的硬件设备。阵列机（Array Processor）作为并行处理机，在差分、乘法、矩阵和向量运算等领域用之甚多。,6.2 SIMD并行计算机（阵列处理机）,阵列机的处理单元被画成“阵列”的样子，处理单元作为这个这个阵列的节点，通过一个环形的网络把节点连接起来了,网络同时也把控制器CU 和各节点连接起来。CU 通过网络向

5、各个处理单元“广播”，共享资源。阵列机属于SIMD,6.2 SIMD并行计算机（阵列处理机）,阵列处理机由一个控制器(CU)、N个处理单元(PE)、M个存储器模块(M)和一个互连网络(IN)组成。由CU控制将指令广播给系统中的各个PE，所有活跃的PE将以同步方式执行相同的指令（单指令流），它们从相应的存储模块中取得自己所需的数据对象（多数据流）,I LLIAC-IV 阵列机处理单元内部方块图,RGA,RGB,RGR,RGS,RGX,RGM,AU,LU,SU,ADA,PEM,累加寄存器64b存放第1操作数,操作数寄存器 64b 存放第2操作数,被乘数寄存器 64b兼互连寄存器,通用寄存器 64b

6、中间寄存器,PE单元存储器:容量204864 b访问时间 350ns,变址寄存器 64bADA的地址修改,MAR,MLU,存储器逻辑控制器,模式寄存器 8b指示标志位,PEM地址寄存器 11b,算术运算器,逻辑运算器,移位运算器,地址加法器,PE,DFS,ILLIAC说明,ILLIAC-IV 阵列机,RGA,RGB,RGR,RGS,RGX,RGM,AU,LU,SU,ADA,CDC,B6700,PEM,IOS,标量ALU,CUB,CDB(64),MBL(64),CU(64),ICL(200),1024总线,2048 X 64 b,13,管理系统资源完成编译汇编进行作业调度,BIOM,阵列控制计算

7、机CU,输入输出系统,阵列 PE 共 64个,PE,变址(16b),模式(8b),acc,gr,dr,nr,buffer,6.2 SIMD并行计算机（阵列处理机）,图 6.1 阵列处理机两种结构,a.分布存储器的阵列机,b.共享存储器的阵列机,6.2 SIMD并行计算机（阵列处理机）,阵列机的主要特点它采用资源重复方法它是以某一类算法为背景的专用机器阵列机的研究必须以并行算法的研究密切结合从处理单元来看，由于都是相同的，故阵列机是同构的并行处理机,6.4 SIMD计算机的互联网络,互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。节点：处理

8、器、存储模块或其他设备。互连网络在系统中的位置，如图所示。在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。,6.4 SIMD计算机的互联网络,互连网络在系统中的位置,6.4 SIMD计算机的互联网络,可以从4个不同的方面来描述互连网络通信工作方式：有同步和异步两种。同步系统：使用一个统一的时钟。SIMD阵列处理机就属于这一种类型。异步系统：没有统一的时钟，系统中的各个处理机都是独立地工作。控制策略：有集中式和分散式两种集中控制方式：有一个全局的控制器接收所有的通信请求，并由它设置互连网络的开关连接。分散控制方式：不存在全局的控制器，通信请求的处理和开关的设置由互连网络分散地进行。,

9、6.4 SIMD计算机的互联网络,交换方法：有线路交换和分组交换两种。线路交换：源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。分组交换：把信息分割成许多组（又称为包），将它们分别送入互连网络。这些数据包可以通过不同的路径传送，到达目的结点后再拼合成原来的数据。结点之间不存在固定连接的物理通路。,7.1 互连网络的基本概念,拓扑结构：有静态和动态两种。静态拓扑结构：在各结点之间有专用的连接通路，且在运行过程中不能改变。动态拓扑结构：可根据需要设置互连网络中的开关，从而对结点之间的连接通路进行重新组合，实现所要求的通信模式。,6.4 SIMD计算机的互联网络,SIMD系统互连网络的

10、设计目标(1)结构不要过分复杂，以降低成本；(2)互连要灵活，以满足算法和应用的需要；(3)处理单元间信息交换所需传送步数要尽可能少，以提高速度性能；(4)能用规整单一的基本构件组合而成，或经多次通过或多级连接来实现复杂的互连，使模块性好，以便于VLSI实现并满足系统的可扩展性。,6.4 SIMD计算机的互联网络,三、互连网络的分类,互联函数,互连函数互连函数是反映互连网络连接特性的一组定义。如果把互连网络的N个入端和N个出端（N=2n）各自用0,1,N-1的整数编号表示，则互连函数就是表示互连网络的出端号和入端号的一一对应关系。如入端号的二进制表示为xn-1xn-2x2x1,则与此入端相连接

11、的出端可用互连函数f(xn-1xn-2x2x1)表示。恒等置换函数,6.4.2 互联函数,2.方体(Cube)N个节点的立方体单级网络共有n=log2N种互连函数,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(

12、000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,K=0,K=1,K=2,6.4.2 互联函数,3.全混洗单级网络,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,6.4.2 互联函数,4.交换单级网络,(001)1,(010)2,(01

13、1)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,6.4.2 互联函数,5.蝶式单级网络,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,6.4.2 互联函数,6.子蝶式单级网络,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(00

14、0)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,K=0,K=1,K=2,6.4.

15、2 互联函数,*7.移位单级网络,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,6.4.2 互联函数,8.PM2I单级网络,PM2+0,(001)1,(010)2,(011)3,(100)4,(10

16、1)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,6.4.2 互联函数,8.PM2I单级网络,PM2+0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,0,1,2,3,4,5,6,7,6.4.2 互联函数,8.PM2I单级网络,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6

17、,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,PM2-0,0,1,2,3,4,5,6,7,6.4.2 互联函数,8.PM2I单级网络,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,PM2+1,0,1,2,3,4,5,6,7,6.4.2 互联函数,8.PM2I单级网络,(001)1,(010)2,(011)3,(100)4,(

18、101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,0,1,2,3,4,5,6,7,PM2-1,6.4.2 互联函数,8.PM2I单级网络,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,(001)1,(010)2,(011)3,(100)4,(101)5,(110)6,(111)7,(000)0,PM22,0,1,2,3,4,5,6,7,阵列计算机ILLIAC,采用PM20和PM2n/2构成ILLIAC 阵列机的互连

19、网络,互联网络分类与结构参数,Fig.6.17 互连网络的分类,互连网络通常可以分为两大类：静态互连网络 各结点之间有固定的连接通路且在运行中不能改变的网络。动态互连网络 由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。下面介绍几种静态互连网络。（其中：N表示结点的个数）,静态互连网络,6.4.4 静态互连网络,静态互联网络的参数,（1）结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数。一个网络的度是这个网络中各结点的度的最大值。结点度反映了网络中结点之间的连接能力。结点度=入度+出度其中入度是进入结点的通道数，出度是从结点出来的通道数。（2）距离：网络中两个

20、结点之间的拓扑距离用这两个结点之间相连的最少边数表示。,（3）网络直径：网络中任意两个结点间距离的最大值，即最远两个结点之间的距离。（4）网络规模：指网络中的结点数，表示该网络功能连结部件的多少。（5）带宽总和：指网络中各链路的传输带宽的总和，它代表了网络在理想状况下的传输能力，即每个结点的处理器同时与其它直接连接的结点进行通信时的网络传输能力。（6）等分(bisection)带宽：当某一网络被切成相等的两半时，沿切口的边数（通道数）的最小值称为通道等分宽度，用b表示。,静态互联网络的参数,6.4.4 静态互连网络,1、线性阵列 一种一维的线性网络，其中N个结点用N-1个链路连成一行。,端结点

21、的度：1其余结点的度：2直径：N1等分宽度b=1,6.4.4 静态互连网络,对称结点的度：2双向环的直径：N/2单向环的直径：N,2、环和带弦环 环用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。,6.4.4 静态互连网络,带弦环增加的链路愈多，结点度愈高，网络直径就愈小。,3、循环移数网络通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。,N=16结点度：7直径：2,6.4.4 静态互连网络,全连接网络 结点度：15直径最短，为1,6.4.4 静态互连网络,树形和星形 一棵5层31个结点的二叉树 一般说来，一棵k层完全平衡的二叉树有

22、N=2k-1个结点。最大结点度：3直径：2(k-1)星形 结点度较高，为N1。直径较小，是一常数2。可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。,6.4.4 静态互连网络,6.4.4 静态互连网络,胖树形,6.4.4 静态互连网络,网格形和环网形 网格形一个33的网格形网络一般来说，N=nk 个结点的k维网络的内部结点度是2k，网络直径为k(n-1)。闭合螺旋（环形网）可看作是直径更短的另一种网格。将环形和网格形组合在一起，并能向高维扩展。沿阵列的每行和每列都有环形连接。一个nn二元环网结点度：4直径：2n/2,6.4.4 静态互连网络,6.4.4 静态互连网络,立方体 一种二元n维立

23、方体结构一般来说，一个二元n维立方体由N=2n 个结点组成，它们分布在n维上，每维有两个结点。例 8个结点的3维立方体 4维立方体为实现一个n维立方体，只要把两个（n1）维立方体中相对应的结点用链路连接起来即可。共需要2n-1条链路。n维立方体中结点的度都是n，直径也是n。,6.4.4 静态互连网络,动态互联网络,1.动态互连网络的三个参量 由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。动态互连网络用三个参量来描述。（1）交叉开关（2）连接模式（或拓扑结构）（3）控制方式,6.4.5 动态互联网络,（1）交叉开关交叉开关是一种有源的开关元件,它可根据控制信号，工作在各种不同的状态

24、，实现输入端和输出端的不同连接。常用的交叉开关有22，44，88.22交叉开关的4种工作状态直连交换上播下播,(a)直连,(b)交叉,(c)上播,(c)下播,6.4.5 动态互联网络,（2）连接模式也称网络拓扑结构，它是多级互连网络的各级开关之间链路的连接模式。连接模式实现的互连函数不同，就构成各种不同的互连网络。（3）控制方式：指网络中各级开关的控制方式。级控方式：同一级开关用一个信号来控制，所有开关都处于一种工作状态单元控制：每一个开关都有单独的控制信号部分级控方式：用i+1个控制信号来控制第i级的所有开关，其中，0=in。,(1)单级混洗交换网络 n=3的混洗网络拓扑形状如下图绿线所示，

25、可以看出它不是一个连通图，所以还需要增加一个交换函数（Cube0，图中红线所示），才能构成完整的单级混洗交换网络。,8个处理单元的混洗交换互连网络连接图,6.4.5 动态互联网络,该网络由PM2I函数定义，PM2I函数共有n对成员，分别是PM2 0，PM2 1，PM2(n-1)。PM2I函数定义：PM2i的功能是对入端结点编号加或减2i，然后再作模N运算PM2+i（j）=j+2i mod NPM2-i（j）=j-2i mod N 其中j=0 N-1，i=0 n-1。例如：当N=8时，PM2+0（0）=0+20=1，PM2+0（1）=1+20=2，PM2+0（7）=7+20=0，PM2+1（0）

26、=0+21=2。N=8的PM2+1（j）函数开关状态如右图所示，其连接规律是把各入端结点编号加上相同的增量21（mod N），获得出端结点编号。,(2)单级加减2i网（PM2I网，移数网),N=8的PM2+i网络拓扑形状如下图所示，可以看出它包含多个强连通子图（即除去若干边以后仍能保证任何一对结点互相可达），所以这2n个函数并不是实现互连网的最小集合。实际应用中为了降低造价，人们往往取它们的一个子集来构造互连网。性质1：对相同的i值，PM2+i与PM2-i函数的传送路径相同，方向相反（右图中所有箭头反向即为PM2-1的拓扑形状）；性质2：PM2+(n-1)=PM2-(n-1)。根据性质2，我们

27、知道单级PM2I网络实际上只能实现2n-1种不同的置换。,(2)单级加减2i网（PM2I网，移数网),0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,PM2+0互连循环函数(0 1 2 3 4 5 6 7)及连接图,PM2+1互连循环函数(0 2 4 6)(1 3 5 7)及连接图,PM2+2互连循环函数(0 4)(1 5)(2 6)(3 7)及连接图,6.4.5 动态互联网络 3.多级互联网络,交叉开关是一种单级互联网络，输入端的数据经过一个开关元件就被输出。这种网络的设备量较大，解决的办法是采用多级网络，即用多个开关元件构成多级的开关阵列，降

28、低互联网络的成本。在MIMD和SIMD计算机都使用多级互连网络，相邻各级开关之间都有固定的级间连接，如图：,6.4.5 动态互联网络,3、基本的多级互连网络,1.多级立方体网络,STARAN网络,间接二进制n方体网络,交换网络,*移数网络,2.多级混洗交换网络（omega网络或网络）,*3.基准网络,*4.全排列网络,6.4.5 动态互联网络,（1）STARRAN网络（2）间接二进制n方体网络共同点：第i级交换开关处于交换状态时,实现的是Ci互连函数,且都采用二功能交换开关（即直连和交换）差别：STARAN网络采用级控制（称交换网络）和部分级控制（其中可实现移数功能的称移数网络）;而间接二进制

29、n方体网络采用单元控制。,6.4.5 动态互联网络,（1）STARAN网络STARAN网络的特点：网络规模:N个节点的网络由n=log2N级构成,每级开关的编号从输入端到输出端依次为K0,K1,Kn-1;每级的交换开关数为N/2个,每个开关都是2功能的（即直连和交换）拓扑结构:N个节点的网络共有n+1级拓扑结构，其编号从输入端到输出端依次为C0,C1,Cn;C0为恒等置换,C1-Cn为逆混洗置换STARAN网络的控制方式：级控制和部分级控制STARAN网络的典型应用：交换网络和移数网络,6.4.5 动态互联网络,（1）STARAN网络（交换网络）STARAN网络用作交换网络时，采用级控制方式工

30、作，实现的是交换函数的功能。交换函数是将一组元素首尾对称地进行交换。,A,B,C,D,E,F,G,H,I,J,K,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,C0,C1,C2,C3,K0,K1,K2,表6-1 三级STARAN交换网络实现的入出端连接及所 执行的交换函数功能（ki为第i级控制信号）,除F=(000)实现恒等置换外，其他7种实现分组交换置换，如F=(101)实现的置换可表示为：,0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 1 0 3 2 5 4 7 6 1 0 3 2 5 4 7 6 2 3 0 1 6 7 4 5 2 3 0 1 6 7

31、 4 5 5 4 7 6 1 0 3 2,入端排列：分成4组：每组二元交换：分成二组：每组四元交换：分成一组：每组八元交换：,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,01234567,F=(000),F=(001),F=(010),F=(011),F=(100),F=(101),F=(110),F=(111),可以发现：F=(f2f1f0)=001的交换置换就是Cub

32、e0置换，F=(f2f1f0)=010的交换置换就是Cube1置换，F=(f2f1f0)=100的交换置换就是Cube2置换，也就是说，fi实现Cubei置换。例如，当F=(f2f1f0)=011，3级STARAN网络实现的交换置换为：E(X2X1X0)=Cube1(Cube0(X2X1X0)=X2X1X0记为Cube0+Cube1。,6.4.5 动态互联网络,*（1）STARAN网络（移数网络）当STARAN网络采用部分级控制时，实现的是移数函数的功能，故称为移数网络。,*表6-2 三级移数网络能实现的入出端连接及移数函数功能,6.4.5 动态互联网络,（2）间接二进制n方体网络网络规模:N

33、个节点的网络由n=log2N级构成,每级开关的编号从输入端到输出端依次为K0,K1,Kn-1;每级的交换开关数为N/2个,每个开关都是2功能的（直连和交换）拓扑结构:N个节点的网络共有n+1级拓扑结构，其编号从输入端到输出端依次为C0,C1,Cn;C0为恒等置换,C1-Cn-1为子蝶式置换，Cn为逆混洗置换控制方式:单元控制典型应用:交换置换、移数置换等,6.4.5 动态互联网络,（2）间接二进制n方体网络的拓扑结构,A,B,C,D,E,F,G,H,I,J,K,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,C0,C1,C2,C3,K0,K1,K2,6.4.5 动态互联网络

34、,2.多级混洗交换网络（omega网络或网络）网络规模:N个节点的网络由n=log2N级构成,每级开关的编号从输入端到输出端依次为Kn-1,Kn-2,K0;每级的交换开关数为N/2个,每个交换开关都是4功能的（即直连、交换、上播和下播）.拓扑结构:N个节点的网络共有n+1级拓扑结构,其编号从输入端到输出端依次为Cn,Cn-1,C0;C0为恒等置换,C1-Cn为全混洗置换。控制方式：单元控制典型应用：恒等置换,移数置换等各种函数的变形置换;可完成数组按行,列,对角线,子块等无冲突访问。,6.4.5 动态互联网络,2.多级混洗交换网络（omega网络或网络）,A,B,C,D,E,F,G,H,I,J

35、,K,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,C3,C2,C1,C0,K2,K1,K0,N=8个节点的网络的拓扑结构,6.4.5 动态互联网络,2.多级混洗交换网络（omega网络或网络）网络的寻径算法:设网络输入端地址编号为S=sn-1sn-2s1s0,输出端地址编号为D=dn-1dn-2d1d0.从输入端开始，每一级开关状态由终端地址所对应位控制。若终端地址某位为0，则对应级上开关的输入端与上输出端相连；若某位为1，则对应级上开关的输入与下输出端相连。,6.4.5 动态互联网络,A,B,C,D,E,F,G,H,I,J,K,L,0,1,2,3,4,5,6,7,0,

36、1,2,3,4,5,6,7,C3,C2,C1,C0,K2,K1,K0,2.多级混洗交换网络（omega网络或网络）,6.4.5 动态互联网络,*3.基准网络网络规模:N个节点的网络由n=log2N级构成,每级开关的编号从输入端到输出端依次为K0,K1,Kn-1;每级的交换开关数为N/2个,每个开关都是2功能的（直连和交换）拓扑结构:N个节点的网络共有n+1级拓扑结构，其编号从输入端到输出端依次为C0,C1,Cn;C0和Cn为恒等置换,C1为逆混洗置换，C2-Cn-1为子逆混洗置换。控制方式:单元控制，可采用终端地址标记的寻径算法典型应用:,6.4.5 动态互联网络,*3.基准网络,A,B,C,

37、D,E,F,G,H,I,J,K,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,N=8的基准网络的拓扑结构,6.4.5 动态互联网络,*4.全排列网络,课堂练习题1：编号为0、1、15的16个处理器用单级互连网络互连。当互连函数分别为：Cube3PM2+3PM2-0ShuffleShuffle(Shuffle)时，第13号处理器各连至哪一个处理器？分析 编号为0、1、15的16个处理器，其号可用4位二进制码P3P2P1P0表示。第13号处理器二进制编号为1101Cube3实现将处理器号为P3P2P1P0与处理器号为P3P2P1P0的数据进行交换。PM2+3实现将j号处理器数

38、据送至第（j+23 mod 16）处理器上。PM2-0实现将j号处理器数据送至第（j-20 mod 16）处理器上。Shuffle实现将处理器号为P3P2P1P0的信息送至处理器号为P2P1P0P3的处理器上。Shuffle（Shuffle）实现将处理器号为P3P2P1P0的信息送至处理器号为P1P0P3P2的处理器上。,解答1）第1101处理器连至0101处理器号上，即第5号处理器上。2）第13号处理器数据送至第（13+23 mod 16）处理器上，即第5号处理器上。3）第13号处理器数据送至第（13-20 mod 16）处理器上，即第12号处理器上。4）第1101处理器连至1011处理器号

39、上，即第11号处理器上。5）第1101处理器连至0111处理器号上，即第7号处理器上。,题2：画出16台处理器仿ILLIAC 的连接模式进行互连的互连结构图，列出PE0分别只经过一步、二步和三步传送能将信息传送到的各处理器号。,分析：ILLIAC 处理器数N为64个，构成88方阵，各PE之间的连接规律可以有PM2+0(mod N)和PM2+n/2(mod N)。其中PM2+n/2 因为n=log2N=log264=6，所以实际是PM2+3。按照ILLIAC 的连接模式，不难看出，当N为16个处理单元时，构成的是88方阵，各PE之间的连接规律就是PM2+0(mod 16)和PM2+2(mod 1

40、6)，根据所画出的互连结构图，PE0只经一步、二步和三步传送将信息传送到的各处理器号就可很容易求得了。解：16台处理器仿ILLIAC 的连接模式互连的结构图如下所示。,PE0经一步可将信息传送到的处理器号有PE1、PE4、PE12、PE15。PE0经二步可将信息传送到的处理器号除了一步可送到的有PE1、PE4、PE12、PE15外，还有PE2、PE3、PE5、PE8、PE11、PE13、PE14。PE0经三步可将信息传送到的处理器号除了上述处理器号外，还有PE6、PE7、PE9、PE10。由此可见，最多经3步可以将PE0的信息传送到任何其它的处理器上，所以其最大的距离为3步。,题3：编号分别为

41、0,1,2,F的16个处理器之间要求按下列配对通讯：(B,1),(8,2),(7,D),(6,C),(E,4),(A,0),(9,3),(5,F)。试选择互连网络类型、控制方式，并画出该互连网络的拓扑结构和各级交换开关状态图。,分析：要求配对通讯的处理器号用二进制表示如下：(B,1)是(1011,0001)(8,2)是(1000,0010)(7,D)是(0111,1101)(6,C)是(0110,1100)(E,4)是(1110,0100)(A,0)是(1010,0000)(9,3)是(1001,0011)(5,F)是(0101,1111)可以发现，处理器P3P2P1P0与处理器P3P2P1P

42、0配对交换数据，由于都是交换函数功能，因此，采用低成本的级控多级立方体互连网络即可。对于16个端的多级立方体互连网络来说，N=16，有n=log2N=log216=4级，每级使用N/2=16/2=8个二功能交换开关，其中第1级和第3级处于交换状态，第0级和第2级处于直通状态。,01,23,45,67,89,AB,CD,EF,01,23,45,67,89,AB,CD,EF,Cube0,Cube1,Cube2,Cube3,直连,直连,交换,交换,入端,出端,题4：并行处理机有16个处理器，要实现相当于先4组4元交换，然后是两组8元交换，再次是一组16元交换的交换函数功能，请写出此时各处理器之间所实现之互连憾事的一般式；画出相应多级网络拓扑结构图，标出各级交换开关的状态。,