第6章阵列处理机.ppt

《第6章阵列处理机.ppt》由会员分享，可在线阅读，更多相关《第6章阵列处理机.ppt（112页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 6 章 并行处理机和相联处理机 第第6章章 阵列处理机阵列处理机 6.1 阵列处理机的原理阵列处理机的原理 6.2 SIMD计算机的互连网络计算机的互连网络 6.3 共享主存构形阵列处理机中并行存储器的无冲突访问共享主存构形阵列处理机中并行存储器的无冲突访问 6.4 脉动阵列处理机脉动阵列处理机 第 6 章 并行处理机和相联处理机 6.1 并行处理机原理并行处理机原理 6.1.16.1.1阵列处理机的构形和特点阵列处理机的构形和特点 1.1.阵列处理机的构形阵列处理机的构形 阵列处理机有两种构形，差别主要在于存储器的组成方式和互连网络的作用不同。图6-1是采用分布式存储器的阵列处理机构形。

2、第 6 章 并行处理机和相联处理机 图6-1具有分布式存储器的阵列处理机构形第 6 章 并行处理机和相联处理机 为了高速有效地处理向量数据，这种构形要求能把数据合理地预分配到各个处理单元的局部存储器中，使各处理单元PEi主要用自己的局存PEMi中的数据运算。分布于各PEM的数据，可以经系统数据总线从外部输入，也可以用控制总线经控制部件播送。在执行向量指令时，可使用屏蔽位向量控制，让某些PE不工作(不活跃)。运算中，PE间可通过互连网络(InterconnectionNetwork,ICN)来交换数据。互连网络的连通路径选择也由控制部件统一控制。第 6 章 并行处理机和相联处理机 处理单元阵列通

3、过控制部件接到管理处理机SC上。管理处理机是一种通用机，用于管理系统资源，完成系统维护、输入/输出、用户程序的汇编及向量化编译、作业调度、存储分配、设备管理、文件管理等操作的功能。因此包括处理单元阵列、互连网络和控制部件在内的阵列处理部分，可以看成是系统的后端处理机。采用这种构形的阵列处理机是SIMD的主流。典型机器有ILLIAC、MPP、DAP、CM-2、MP-1、DAP600系列等。第 6 章 并行处理机和相联处理机 图6-2是采用集中式共享存储器的阵列处理机构形。系统存储器是由K个存储分体(MM0MMK-1)集中组成，经互连网络ICN为全部N个处理单元(PE0PEN-1)所共享。为使各处

4、理单元对长度为N的向量中各个元素都能同时并行处理，存储分体个数K应等于或多于处理单元数N。各处理单元在访主存时，为避免发生分体冲突，也要求有合适的算法能将数据合理地分配到各个存储分体中。第 6 章 并行处理机和相联处理机 图6-2具有集中式共享存储器的阵列处理机构形第 6 章 并行处理机和相联处理机 与分布式存储器构形不同的另一个地方是互连网络ICN的作用不同。其互连网络是用于在处理单元与存储器分体之间进行转接构成数据通路，希望各处理单元能高速灵活地动态与不同的存储分体相连，使尽可能多的PE能无冲突地访问共享的主存模块。因此有的阵列处理机称它为对准网络(AlignmentNetwork)。采用

5、这种构形的典型机器有BSP。第 6 章 并行处理机和相联处理机 2.并行处理机的特点并行处理机的特点并行处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。这些计算问题的共同特点是可以通过各种途径把它们转化成为对数组或向量的处理，而并行处理机正好利用多个处理单元对向量或数组所包含的各个分量同时计算，从而获得很高的处理速度。与同样擅长于向量处理的流水线处理机相比，并行处理机利用的是资源重复，而不是时间重叠；利用并行性中的同时性，而不是并发性。它的每个处理单元要同等地担负起各种运算功能，但其设备利用率却可能没有多个单功能流

6、水线部件那样高。因此，只有在硬件价格有了大幅度下降及系统结构有了较大改进的情况下，并行处理机才能具有较好的性能价格比。并行理机主要是靠增大处理单元个数来提高运算速度，比起向量流水线处理机主要依靠缩短时钟周期来说，速度提高的潜力要大得多。第 6 章 并行处理机和相联处理机 与流水线处理机不同的另一方面是阵列处理机使用简单规整的互连网络来确定处理单元间的连接。互连网络的结构形式限定了阵列处理机可用的解题算法，也会对系统多种性能指标产生显著影响，因此，互连网络的设计是重点。阵列处理机在机间互连上比固定结构的单功能流水线灵活，使相当一部分专门问题上的工作性能比流水线处理机高得多，专用性强得多。如果习惯

7、上把流水线处理机归属于通用计算机的话，阵列处理机则被看成是一种专用计算机，它是以一定数量的专门算法为背景的。另一方面，由于总希望阵列处理机解题算法的适应性更强一些，应用面更广一些，因此，与流水线处理机不同，阵列处理机的结构是和采用的并行算法紧密联系在一起的。第 6 章 并行处理机和相联处理机 如上所述，阵列处理机基本上是一台专用于向量处理的计算机，但并不是所有的运算都可以转化为向量运算，总有不少标量运算。作为整个系统的等效速度来讲，除向量运算速度外，在很大程度上还受标量运算速度和编译开销的大小所影响。如果一台机器的向量处理速度极高，甚至不受限制，而标量速度只是每秒一亿次浮点运算，那么对于标量运

8、算占10%的题目来讲，系统总的等效速度最多也不会超过每秒十亿次浮点运算。所以，提高标量的处理能力是很重要的，这就要求阵列处理机系统的控制部件必须是一台具有高性能、强功能的标量处理机，减少标量运算对系统性能的影响。第 6 章 并行处理机和相联处理机 至于编译时间的多少，则不仅与阵列机结构有关，也与机器语言的并行性程度有关，特别是想要提高阵列处理机的通用性，建立一个有向量化功能的高级语言编译程序就是非常必要的了。正因为如此，阵列处理机还必须用一台高性能单处理机作为管理计算机来配合工作，运行系统的全部管理程序。所以，阵列处理机实质上是由专门对付数组运算的处理单元阵列组成的处理机、专门从事处理单元阵列

9、的控制及标量处理的处理机和专门从事系统输入/输出及操作系统管理的处理机组成的一个异构型多处理机系统。第 6 章 并行处理机和相联处理机 6.1.2ILLIAC的处理单元阵列结构的处理单元阵列结构由于阵列处理机上的并行算法的研究是与结构紧密联系在一起的，因此，下面先介绍一下ILLIAC阵列机上处理单元的互连结构。ILLIAC是采用如图6-1所示的分布存储器构形，其处理单元阵列结构如图6-3所示。其中，PUi为处理部件，包含64位的算术处理单元PEi、所带的局部存储器PEMi和存储逻辑部件MLU。64个处理部件PU0PU63排列成88的方阵，任何一个PUi只与其上、下、左、右4个近邻PUi-8(m

10、od64)、PUi+8(mod64)、PUi-1(mod64)和PUi+1(mod64)直接相连。第 6 章 并行处理机和相联处理机 上下同一列两端的PU连成环，左右每一行右端的PU与下一行左端的PU相连，最下面一行右端的PU与最上面一行左端的PU相连，从而形成一个闭合的螺线形状，所以称其为闭合螺线阵列。在这个阵列中，步距不等于1或8的任意单元之间可以用软件寻找最短路径进行通信，其最短距离不超过7步。例如，信息由PU63送PU10,可经PU63PU7PU8PU9PU104步实现，信息由PU9送PU45可经 PU9PU1PU57PU56PU48PU47PU46PU457步 实现。普遍来讲，个处理

11、单元组成的阵列中，任意两个处理单元之间的最短距离不超过步。第 6 章 并行处理机和相联处理机 图6-3ILLIAC处理单元的互连结构第 6 章 并行处理机和相联处理机 ILLIAC的处理单元是累加器型运算器，把累加寄存器RGA中的数据和存储器中来的数据进行运算，结果保留在累加寄存器RGA中。每个处理单元内有一个数据传送寄存器RGR收发数据，实现数据在处理单元之间的传送，并有一个屏蔽触发器，用来控制让该PUi是否被屏蔽掉，使之不参与向量指令的操作。第 6 章 并行处理机和相联处理机 6.1.3ILLIAC的并行算法举例的并行算法举例1.矩阵加矩阵加阵列处理机解决矩阵加是最简单的一维情况。两个88

12、的矩阵A、B相加，所得的结果矩阵C也是一个88的矩阵。只需把A、B、C居于相应位置的分量存放在同一个PEM内，且在全部64个PEM中，让A、B和C的各分量地址均对应取相同的地址、+1和+2，如图6-4所示。这样，实现矩阵加只需用下列三条ILLIAC汇编指令：第 6 章 并行处理机和相联处理机 LDAALPHA;全部()由PEMi送PEi的累加器RGAiADRNALPHA+1;全部(+1)与(RGAi)浮点加，结果送RGAiSTAALPHA+2;全部(RGAi)由PEi送PEMi的+2单元其中，0i63。第 6 章 并行处理机和相联处理机 图6-4矩阵相加的存储器分配举例第 6 章 并行处理机和

13、相联处理机 2.矩阵乘矩阵乘矩阵乘是二维数组运算，比矩阵加要复杂。设A、B和C为3个88的二维矩阵，给定A和B，计算C=AB的64个分量可用公式其中，0i7且0j7。第 6 章 并行处理机和相联处理机 在SISD计算机上求解，可执行FORTRAN语言编写的下列程序：DO10I=0,7DO10J=0,7C(I,J)=0DO10K=0,710C(I,J)=C(I,J)+A(I,K)*B(K,J)第 6 章 并行处理机和相联处理机 需经I、J、K三重循环完成。每重循环执行8次，共需512次乘、加的时间，且每次还要包括执行循环控制判别等其它操作所需的时间。如果在SIMD阵列处理机上运算，可用8个处理单

14、元并行计算矩阵C(I,J)的某一行或一列，即将J循环或I循环转化成一维的向量处理，从而消去了一重循环。以消去J循环为例，可执行用FORTRAN语言编写的下列程序：DO10I=0,7C(I,J)=0DO10K=0,710C(I,J)=C(I,J)+A(I,K)*B(K,J)第 6 章 并行处理机和相联处理机 图6-5矩阵乘程序执行流程图第 6 章 并行处理机和相联处理机 需要说明的是其执行过程虽与SISD的类似，但实际的解决方式是不同的。每次控制部件执行的PE类指令表面上是标量指令，实际上已等效于向量指令，如向量取、向量存、向量加、向量乘等，是8个PE并行地执行同一条指令。每次播送时，利用阵列处

15、理机的播送功能将处理单元PEK中累加寄存器RGAK的内容经控制部件(CU)播送到全部8个处理单元的RGA中去。然而为了让各个处理单元PEi尽可能只访问所带局部存储器PEMi，以保证高速处理，就必须要求对矩阵A、B、C各分量在局部存储器中的分布采用如图6-6所示的方案。第 6 章 并行处理机和相联处理机 图6-6矩阵乘的存储器分配举例第 6 章 并行处理机和相联处理机 如果想把ILLIAC的64个处理单元全部利用起来并行运算，即把K循环的运算也改为并行，还可进一步提高速度，但需要在阵列存储器中重新恰当地分配数据。同时还要使8个中间积A(I,K)B(K,J)能够并行相加(其中0K7)，这就要用到下

16、面的累加和并行算法。即使如此，就K的并行来说，速度的提高也不是8倍，而只是8/log28，接近于2.7倍。第 6 章 并行处理机和相联处理机 3.3.累加和累加和这是一个将N个数的顺序相加转为并行相加的问题。为得到各项累加的部分和与最后的总和，要用到处理单元中的活跃标志位。只有处于活跃状态的处理单元才能执行相应的操作。为叙述方便取N=8，即有8个数A(I)顺序累加，其中0I7。在SISD计算机上可以写成下列FORTRAN程序：C=0DO10I=0,710 C=C+A(I)这是一个串行程序，需要8次加法时间。第 6 章 并行处理机和相联处理机 在阵列处理机上用成对递归相加算法，只需log28=3

17、次加法时间即可。首先，原始数据A(I)分别存放在8个PEM的单元中，其中，0I7。然后，按下面的步骤求累加和：(1)置全部PEi为活跃状态,0i7;(2)全部A(I)从PEMi的单元读到相应PEi的累加寄存器RGAi中，0i7；(3)令K=0;(4)将全部PEi的(RGAi)转送到传送寄存器RGRi,0i7;第 6 章 并行处理机和相联处理机(5)将全部PEi的(RGRi)经过互连网络向右传送2K步距，0i7；(6)令j=2K-1;(7)置PE0PEj为不活跃状态；(8)处于活跃状态的所有PEi执行(RGAi):=(RGAi)+(RGRi),ji7；(9)K:=K+1；(10)如K3，则转回(

18、4)，否则往下继续执行；(11)置全部PEi为活跃状态，0i7;(12)将全部PEi的累加寄存器内容(RGAi)存入相应PEMi的+1单元中，0i7。第 6 章 并行处理机和相联处理机 图6-7描绘了阵列处理机上累加和的计算过程。框中的数字表明各处理单元每次循环后相加的结果。图中用数字07分别代表A(0)A(7)。画有阴影线的处理单元表示此时不活跃。另外，图中对上述第(5)步中PE的(RGRi)在右移时超出PE7的内容没有表示出来，这是因为若右移步距为2K(mod8)，应移入PE0PEj，而这些PE在第(7)步将要置为不活跃，所以无论它的RGR接收什么内容都不会对执行结果有影响。第 6 章 并

19、行处理机和相联处理机 图6-7阵列处理机上累加和的计算过程第 6 章 并行处理机和相联处理机 6.2SIMD计算机的互连网络计算机的互连网络 6.2.16.2.1互连网络的设计目标与互连函数互连网络的设计目标与互连函数在SIMD计算机中，无论是处理单元之间，还是处理单元与存储分体之间，都要通过互连网络进行信息交换。在大规模集成电路和微处理器飞速发展的今天，建造多达214216个处理单元的阵列处理机已成为现实，但如果要求任意两个处理单元之间都有直接的通路，则互连网络的连线将多得无法实现。因此，采取让相邻的处理单元之间只有有限的几种直连方式，经过一步或少量几步传送即可实现任何两个处理单元间为完成解

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

21、对于所有的入端0、1、j、N-1，同时存在入端j连至出端f(j)的函数对应关系。在实现处理单元间的互连时，互连网络的入端和出端实际上是同一组处理单元的出端和入端，对互连网络来说，就是同一个结点。互连函数可以直接用结点间的连线图表示，但有时显得繁琐，也难以体现出连接上的内在规律。因此，常用另一种简单的函数式表示，即把所有入端x和出端f(x)都用二进制编码，从两者的二进制编码上找出其函数规律。下面将看到这种表示的例子。第 6 章 并行处理机和相联处理机 6.2.26.2.2互连网络应抉择的几个问题互连网络应抉择的几个问题在确定PE之间通信的互连网络时，需要对操作方式、控制策略、交换方法和网络的拓扑

22、结构作出抉择。操作方式有同步、异步及同步与异步组合三种。现有的阵列处理机根据其SIMD性质均采用同步操作方式，让所有PE按时钟同步操作。异步或组合操作方式一般多用于多处理机。典型的互连网络是由许多开关单元和互连线路组成的，互连通路的路径选择是通过置定开关单元的工作状态来控制的，这种置定可以有集中或分布两种控制策略。多数现有的SIMD互连网络采用由集中控制部件对全部开关单元执行集中控制的策略。第 6 章 并行处理机和相联处理机 交换方法主要有线路交换、包交换及线路与包交换组合三种。线路交换是在源和目的间建立实际的连接通路，一般适合于大批数据传输。包交换是将数据置于包内传送，不用建立实际的连接通路

23、，对短数据信息传送特别有效。SIMD互连网络多采用硬连的线路交换，包交换则多用于多处理机和计算机网络中。第 6 章 并行处理机和相联处理机 网络的拓扑结构指的是互连网络入、出端可以连接的模式，有静态和动态两种。在静态拓扑结构中，两个PE之间的链是固定的，总线不能重新配置成与其他PE相连。而动态拓扑结构中，两个PE之间的链通过置定网络的开关单元状态可以重新配置。静态拓扑有一维的线型，二维的环型、星型、树型、胖树型、网络型、脉动阵列型，三维的弦环型、立方体型、环立方体型，以及其他复杂的连接形式。由于静态网络灵活性、适应性差，很少使用，因此只讨论动态网络。第 6 章 并行处理机和相联处理机 动态网络

24、有单级和多级两类。动态单级网络只有有限的几种连接，必须经循环多次通过，才能实现任意两个处理单元之间的信息传送，故称此动态单级网络为循环网络。动态多级网络是由多个单级网络串联组成的，以实现任意两个处理单元之间的连接。将多级互连网络循环使用可实现复杂的互连，称循环多级网络或多级循环网络。循环互连网络的模型如图6-8所示。入端传送寄存器DTRi和出端传送寄存器DTRo除了各自与处理单元PE0PEN-1相连分别接收和送出数据外，在不同的循环中还可以通过多路开关MUX向单级互连网络送入DTRi数据，或送入在上一循环中DTRo从单级互连网络接收的数据，经单级互连网络转送再送回各自有关的DTRo，作为下一次

25、循环的输入。循环互连网络比多级互连网络节省设备，但通过时间长，并对网络控制要求较高。第 6 章 并行处理机和相联处理机 图6-8循环互连网络的模型第 6 章 并行处理机和相联处理机 6.2.3基本的单级互连网络基本的单级互连网络1.立方体单级网络立方体单级网络立方体单级网络(Cube)的名称来源于图6-9所示的三维立方体结构。立方体的每个顶点(网络的结点)代表一个处理单元，共有8个处理单元，用zyx三位二进制码编号。它所能实现的入、出端连接如同立方体各顶点间能实现的互连一样，即每个处理单元只能直接连到其二进制编号的某一位取反的其他3个处理单元上。如010只能连到000、011、110，不能直接

26、连到对角线上的001、100、101、111。所以，三维的立方体单级网络有3种互连函数：Cube0、Cube1和Cube2，其连接方式如图6-10中的实线所示。Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0,1,2)上0、1互反，其余各位代码都相同。第 6 章 并行处理机和相联处理机 图6-9三维立方体结构第 6 章 并行处理机和相联处理机 图6-10立方体单级网络连接示意(a)Cube0;(b)Cube1;(c)Cube2第 6 章 并行处理机和相联处理机 推广到n维时，N个结点的立方体单级网络共有n=log2N种互连函数，即式中，Pi为入端标号二进制码的第i位，且0i

27、n-1。当维数n3时称超立方体(HyperCube)网络。显而易见，单级立方体网络的最大距离为n，即反复使用单级网络，最多经n次传送就可以实现任意一对入、出端间的连接。而且任意两个结点之间至少有n条不同的路径可走，容错性强，只是距离小于n的两个结点之间各条路径的长度可能不等。第 6 章 并行处理机和相联处理机 2.PM2I单级网络单级网络PM2I单级网络是“加减2i”(PlusMinus2i)单级网络的简称。能实现与j号处理单元直接相连的是号为j2i的处理单元，即式中，0jN-1,0in-1,n=log2N。它共有2n个互连函数。由于PM2+(n-1)=PM2-(n-1),因此PM2I互连网络

28、只有2n-1种互连函数是不同的。对于N=8的三维PM2I互连网络的互连函数，有PM2+0、PM2-0、PM2+1、PM2-1、PM22等5个不同的互连函数，它们分别为第 6 章 并行处理机和相联处理机 PM2+0:(01234567)PM2-0:(76543210)PM2+1:(0246)(1357)PM2-1:(6420)(7531)PM22:(04)(15)(26)(37)其中，(01234567)表示0连到1，与此同时，1连到2,2连到3,，7连到0。图6-11只画出了其中3种互连函数的情况，PM2-0和PM2-1的连接与PM2+0和PM2+1的差别只是连接的箭头方向相反而已。可见在PM

29、2I中，0可以直接连到1、2、4、6、7上，比立方体单级网络只能直接连到1、2、4的要灵活。第 6 章 并行处理机和相联处理机 图6-11PM2I互连网络的部分连接图第 6 章 并行处理机和相联处理机 3.3.混洗交换单级网络混洗交换单级网络混洗交换单级网络(ShuffleExchange)包含两个互连函数，一个是全混(PerfectShuffle)，另一个是交换(Exchange)。图6-12表示8个处理单元间的全混连接。可以看出，其连接规律是把全部按编码顺序排列的处理单元从当中分为数目相等的两半，前一半和后一半在连接至出端时正好一一隔开。正像洗扑克牌时先把整副牌分为两半，再通过洗牌达到“全

30、混”，这也是“混洗”这个名词的由来。用互连函数表示为式中,n=log2N,Pn-1Pn-2P1P0为入端编号的二进制码。第 6 章 并行处理机和相联处理机 图6-128个处理单元间的全混连接第 6 章 并行处理机和相联处理机 Shuffle函数还有一个重要特性。如果把它再作一次Shuffle函数变换，得到的是一组新的代码，即Pn-3P0Pn-1Pn-2。这样每全混一次，新的最高位就被移至最低位。当经过n次全混后，全部N个处理单元便又恢复到最初的排列次序。在多次全混的过程中，除了编号为全“0”和全“1”的处理单元外，各个处理单元都遇到了与其他多个处理单元连接的机会。由于单纯的全混互连网络不能实现

31、二进制编号为全“0”和全“1”的处理单元与其他处理单元的连接，因此还需增加Cube0交换函数。这就是全混交换单级网络，其N=8的连接如图6-13所示。其中，实线表示交换，虚线表示全混。第 6 章 并行处理机和相联处理机 图6-13N=8时全混交换互连网络连接图第 6 章 并行处理机和相联处理机 4.4.蝶形单级网络蝶形单级网络蝶形单级网络(Butterfly)的互连函数为Butterfly(Pn-1Pn-2P1P0)=P0Pn-2P1Pn-1即将二进制地址的最高位和最低位相互交换位置。图6-14为N=8个处理单元之间用蝶形单级互连网络互连的情况。它实现的是00、14、22、36、41、55、6

32、3、77的同时连接。第 6 章 并行处理机和相联处理机 图6-148个处理单元间的蝶形单级互连第 6 章 并行处理机和相联处理机 6.2.46.2.4基本的多级互连网络基本的多级互连网络最基本的多级互连网络就是与上述前3种单级互连网络相对应组成的多级立方体互连网络、多级混洗交换网络和多级PM2I网络，此外，还介绍一下基准网络。不同的多级互连网络，在所用的交换开关、拓扑结构和控制方式上各有不同。交换开关是具有两个入端和两个出端的交换单元，用作各种多级互连网络的基本构件。不论入端或出端，如果令居于上方的都用i表示，居于下方的都用j表示，则可以定义下列4种开关状态或连接方式：第 6 章 并行处理机和

33、相联处理机(1)直连i入连i出，j入连j出；(2)交换i入连j出，j入连i出；(3)上播i入连i出和j出，j入悬空；(4)下播j入连i出和j出，i入悬空。只有前两种功能的称二功能交换单元，有全部四种功能的称四功能交换单元。两个入端同时连到一个出端会发生信息传送的冲突，是不允许的。此外，还可以有第5种开关状态，即i入连j入,i出连j出，称此为返回。它可用来实现入端与入端相连，出端与出端相连，从而将N个入端和N个出端的网络变为2N个处理单元的互连网络。第 6 章 并行处理机和相联处理机 拓扑结构是各级间出端与入端互连的模式。上述前3种单级互连网络的连接模式均可用来组合构成不同的多级互连网络。控制方

34、式是对各个交换开关进行控制的方式，以多级立方体网络为例，它可以有3种：(1)级控制同一级的所有开关只用一个控制信号控制，同时只能处于同一种状态；(2)单元控制每一个开关都有自己独立的控制信号控制，可各自处于不同的状态；(3)部分级控制第i级的所有开关分别用i+1个信号控制，0in-1，n为级数。第 6 章 并行处理机和相联处理机 1.多级立方体网络多级立方体网络多级立方体网络有STARAN网络、间接二进制n方体网络等。以8个处理单元为例，其普遍结构如图6-15所示。它们的共同特点是：第i级(0in-1)交换单元处于交换状态时，实现的是Cubei互连函数，且都采用二功能交换单元。两者的差别仅在于

35、控制方式上；STARAN网络采用级控制(称交换网络)和部分级控制(其中可实现移数功能的称移数网络)，而间接二进制n方体网络用单元控制。因此，后者具有更大的连接灵活性。第 6 章 并行处理机和相联处理机 图6-15N=8多级立方体互连网络第 6 章 并行处理机和相联处理机 STARAN网络用作交换网络时，采用级控制，实现的是交换函数。所谓交换(Flip)函数是将一组元素首尾对称地进行交换。如果一组元素包含有2s个，则它是将所有第k个元素都与第(2s-(k+1)个元素相交换。表6-1列出了三级交换网络在级控制信号采用各种不同组合情况下所实现的入、出端的连接。从表6-1可以看出，控制信号为111时，

36、实现全交换，也称镜像交换，完成对这8个处理单元(元素)的一组8元交换，其变换图像如下：入端排列01234567出端排列76543210第 6 章 并行处理机和相联处理机 控制信号为001时，完成对这8个处理单元(元素)的4组2元交换，其变换图像如下：入端排列01234567出端排列10325476第 6 章 并行处理机和相联处理机 表表6-1 6-1 三级三级STARANSTARAN交换网络实现的入、出端连接及交换网络实现的入、出端连接及所执行的交换函数功能所执行的交换函数功能(ki为第为第i级控制信号级控制信号)第 6 章 并行处理机和相联处理机 控制信号为010时，完成的功能相当于在进行4

37、组2元交换后再进行2组4元交换，其变换图像如下：1 0 3 2 5 4 7 6出端排列2 3 0 1 6 7 4 5而控制信号为101时，相当于实现上述两种交换后再进行1组8元交换，其变换图像如下：2 3 0 1 6 7 4 5出端排列 54761032 第 6 章 并行处理机和相联处理机 总之，不管控制信号是什么状态，实现的都是交换函数功能。从表6-1水平方向不难看出，任何输入端只要通过不同的级控制信号，总可以接到任何所需要的输出端上。当STARAN网络用作移数网络时，采用部分级控制，控制信号分组和控制结果列在表6-2中。可以看出它们都是执行各种不同的移数功能的。第 6 章 并行处理机和相联

38、处理机 表6-2三级移数网络能实现的入、出端连接及移数函数功能第 6 章 并行处理机和相联处理机 2.多级混洗交换网络多级混洗交换网络多级混洗交换网络又称omega网络，如图6-16所示。它由n级相同的网络组成，每一级都包含一个全混拓扑和随后一列2n-1个四功能交换单元，采用单元控制方式。比较图6-15和图6-16可以发现，omega网络中各级编号的次序与多级立方体网络正好相反。如果把omega网络的入端和出端位置对调，它就等同于间接二进制n方体网络。因此omega网络与间接二进制n方体网络只有两点差别：前者数据流向是级号n-1、n-2、1、0,用四功能交换单元，后者数据流向相反，是级号0、1

39、、n-1,用二功能交换单元。第 6 章 并行处理机和相联处理机 图6-16N=8多级混洗交换网络第 6 章 并行处理机和相联处理机 假定omega网络也采用二功能交换单元，就可看成是n方体网络的逆网络。基本互连网络可以实现任一个入端与任一个出端之间的连接，但要同时实现两对或多对的入、出端间的连接，就可能发生连接路径上的冲突。由于omega网络与n方体网络的数据入、出流向相反，因此它们产生冲突的状况不同。例如，n方体网络能同时实现5到0、7到1的连接，不能同时实现0到5、1到7的连接；而omega网络正好相反，能同时实现0到5和1到7的连接，不能同时实现5到0和7到1的连接。有一种办法可以把二者

40、统一起来，就是将入端和出端重新编号。第 6 章 并行处理机和相联处理机 仍比较图6-15与图6-16，可以发现如果把编号Pn-1Pn-2P1P0和P0P1Pn-2Pn-1互换，例如，对于n=3，就是把1、4互换，3、6互换，那么两张图上所有交换单元上的处理单元编号配对就变成一样的了。于是表6-1和表6-2中所列STARAN网络的互连函数，在按上述规则对处理单元重新编号后，便都适合于omega网络，而且所有在前者运行的SIMD程序都能向上兼容。当然，由于omega网络采用四功能交换单元，因此允许同时实现一个处理单元与多个处理单元的连接，这是多级立方体网络不可能办到的。例如，只需将图6-16中交换

41、单元E、F置为下播状态，C、I、J、K、L置为上播状态，就能一次实现入端2与全部8个出端的连接。第 6 章 并行处理机和相联处理机 3.多级多级PM2I网络网络N=8的多级PM2I网络的结构如图6-17所示。它包含n级单元间连接，每一级都是把前后两列各N=2n个单元按PM2I拓扑相互连接起来。从第i级(0in-1)来说，每一个入单元j(0jN-1)都有3根连接线分别通往出单元j、j+2imodN和j-2imodN，在图6-17中，它们分别用点线、实线和虚线表示。前面已提到，单级PM2I网络的最大距离为n/2，但组成多级PM2I网络时仍用了n级，因此在这种网络中提供了冗余路径。第 6 章 并行处

42、理机和相联处理机 例如，为实现由7将信息传到2，可以经7332，或7712，或7312等多条路径完成。这对提高可靠性和便于集成电路化都有好处。控制这三类连接线的信号分别称为平控H、下控D和上控U。为了简化对这三类信号的产生，可将各级的单元分成两组。对于第i级，让H1i、Di1、Ui1控制第i位为“0”的那些入单元，而让Hi2、Di2、Ui2控制第i位为“1”的那些入单元，此种多级PM2I网络称为数据变换网络(DataManipulator)。可以采用单元控制增强对各级单元控制的灵活性，让每一单元都有自己独立的控制信号H、D、U,此种 多 级 PM2I网 络 称 为 强 化 数 据 变 换 网

43、络ADM(AugmentedDataManipulator)，不过控制线多，成本较高。第 6 章 并行处理机和相联处理机 图6-17N=8多级PM2I网络第 6 章 并行处理机和相联处理机 ADM的拓扑结构和控制方式使它可以完全模仿omega网络的四功能交换单元。拿x、y(xy)两个入单元来说，Hx、Hy为直连，Dx、Uy为交换，Uy、Hy为下播，Dx、Hx为上播。因此，ADM可以实现omega网络的全部连接，而且其组合数还要更多。利用数据变换网络可以实现各种灵活的移数、重复、间隔、展开等函数变换。第 6 章 并行处理机和相联处理机 比较上述各种多级网络，灵活性由低到高的次序是：级控制立方体、

44、部分级控制立方体、间接二进制n方体、omega、ADM,而复杂性和成本的次序也相应增高。虽然这些网络的设计者都提出了各自的网络用途，例如STARAN网络和omega网络都是为了进行存储器与处理单元之间的数据变换，间接二进制n方体网络是为了连接成微处理器阵列，但从上面对各种网络共同性的分析可以看出，它们对多种应用场合都是适合的。第 6 章 并行处理机和相联处理机 4.4.基准网络基准网络图6-18是N=8的基准网络。它与二进制立方体网络的逆网络相似，只是在第1级的级间连接不同。它采取从输入到输出的级间互连为恒等、逆全混、子逆全混和恒等置换，所用交换单元均为二功能，采取单元控制。第 6 章 并行处

45、理机和相联处理机 图6-18N=8的基准网络第 6 章 并行处理机和相联处理机 5.多级交叉开关网络多级交叉开关网络多级交叉开关(CLOS)网络是一种非阻塞式网络，图6-19给出了一个三级交叉开关网络的结构。其网络的入、出端口数均为nr,输入级有r个nm的交叉开关，中间级有m个rr的交叉开关，输出级有r个mn的交叉开关。当m2n-1时，它就成了非阻塞网络。所谓非阻塞网络，指的是同时实现两对或多对入、出端间的连接，均不会发送传送路径上的冲突(全排列网络中介绍)，表示成N(m,n,r)。第 6 章 并行处理机和相联处理机 图6-19三级交叉开关网络的结构第 6 章 并行处理机和相联处理机 图6-2

46、0是一个N(3,2,2)的三级交叉开关网络。入、出端各有4个，如采用一级交叉开关实现共需44=16个交叉点，每个交叉点为四中选1，可能比三级交叉开关实现要便宜，尽管每个结点只需二中选1。一般来说，N(m,n,r)的多级交叉开关交叉结点总数为C=r(nm)+m(rr)+r(mn)=mr(2n+r)而一级交叉开关结点数为n2个。因此，当n值较大时，使mr(2n+r)n2，这时，采用多级交叉开关网络互连，既保证了无阻塞连接，也降低了互连网络的成本，而且便于工程实现。第 6 章 并行处理机和相联处理机 图6-20N(3,2,2)多级交叉开关互连网络第 6 章 并行处理机和相联处理机 6.多级蝶式网络多

47、级蝶式网络图6-21是由16个88交叉开关作为基本构件组成的二级蝶式网络，级间采用8路混洗，构成了6464的蝶式互连。再用其与64个88的交叉开关扩展构成512512的三级蝶式互连网络，如图6-22所示。图6-21中使用了16个88的交叉开关，图6-22则共用了388=192个88的交叉开关。如果要构造更大的蝶式网络只需增加级数即可。但蝶式网络不能实现播送，只是omega网络的一个有限制的子集。第 6 章 并行处理机和相联处理机 图6-21用88交叉开关构造的二级6464的蝶式互连网络第 6 章 并行处理机和相联处理机 图6-22用88交叉开关作为基本构件扩充成512512的三级蝶式互连网络第

48、 6 章 并行处理机和相联处理机 6.2.56.2.5全排列网络全排列网络如果互连网络是从N个入端到N个出端的一到一的映射，就可以把它看成是对此N个端的重新排列，因此互连网络的功能实际上就是用新排列来置换N个入端原有的排列。前面所介绍的各种基本多级网络都能实现任意一个入端与任意一个出端间的连接，但要同时实现两对或多对入、出端间的连接时，都有可能发生争用数据传送路径的冲突。前面在多级立方体网络和多级混洗交换网络中已举过这种例子。称 有 这 类 性 质 的 互 连 网 络 为 阻 塞 式 网 络 (BlockingNetwork)，称无这类性质的互连网络为非阻塞式网络或全排列网络。非阻塞式网络连接

49、灵活，但连线多、控制复杂、成本高。第 6 章 并行处理机和相联处理机 阻塞式网络在一次传送中不可能实现N个端的任意排列。大家知道N个端的全部排列有N!种。可是，用单元控制的n=log2N级间接二进制n方体网络(因为1到1映像，用不上播送，所以开关只需用二功能)，每级有N/2个开关，n级互连网络共用(Nlog2N)/2个二功能的交换开关，这样，全部开关处于不同状态的总数为2(Nlog2N)/2，即NN/2种。当N为大于2的整数时，总有NN/2N!，就是说它无法实现所有N!种排列。以N=8的三级网络为例，共12个二功能交换开关，只有212=4096种不同状态，最多只能控制对端子的4096种排列，不

50、可能实现全部8!=40320种排列，所以多对入、出端要求同时连接时就可能发生冲突。第 6 章 并行处理机和相联处理机 然而，只要对这个多级互连网络通行两次，每次通行时让各开关处于不同状态就可满足对N个端子的全部N!种排列。因为此时全部开关的总状态数有NN/2NN/2=NN种，足以满足N!种不同排列的开关状态要求。这种只要经过重新排列已有入、出端对的连接，就可完成所有可能的入、出端间的连接而不发生冲突的互连网络称为可重排列网络(WTBZRearrangeableNetwork)。实现时，可以在上述任何一种基本多级互连网络的出端设置锁存器，使数据在时间上顺序通行两次，这实际上就是循环多级互连网络的