并行处理机和相联处理机.ppt

《并行处理机和相联处理机.ppt》由会员分享，可在线阅读，更多相关《并行处理机和相联处理机.ppt（72页珍藏版）》请在三一办公上搜索。

1、第 6 章 并行处理机和相联处理机,6.1 并行处理机原理 6.2 并行处理机举例 6.3 相联处理机,6.1 并行处理机原理,6.1.1 并行处理机的构形与特点,1.并行处理机的基本构形,图 6.1 具有分布式存贮器的并行处理机构形,图 6.2 具有集中式共享存贮器的并行处理机构形,2.并行处理机的特点 并行处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。这些计算问题的共同特点是可以通过各种途径把它们转化成为对数组或向量的处理，而并行处理机正好利用多个处理单元对向量或数组所包含的各个分量同时计算，从而获得很高的处

2、理速度。与同样擅长于向量处理的流水线处理机相比，并行处理机利用的是资源重复，而不是时间重叠；利用并行性中的同时性，而不是并发性。它的每个处理单元要同等地担负起各种运算功能，但其设备利用率却可能没有多个单功能流水线部件那样高。因此，只有在硬件价格有了大幅度下降及系统结构有了较大改进的情况下，并行处理机才能具有较好的性能价格比。并行理机主要是靠增大处理单元个数来提高运算速度，比起向量流水线处理机主要依靠缩短时钟周期来说，速度提高的潜力要大得多。,6.1.2 并行处理机的算法,1.ILLIAC 的处理单元阵列结构,图 6.3 ILLIAC 处理单元的互连结构,PUi为处理部件，包含 64 位的算术处

3、理单元PEi、所带的局部存贮器PEMi和存贮器逻辑部件MLU。64个处理部件PU0PU63 排列成 88 的方阵。任何一个PUi只与其上、下、左、右 4个近邻PUi-8(mod 64)、PUi+8(mod 64)、PUi-1(mod 64)和PUi+1(mod 64)直接相连。循此规则，上、下方向上同一列两端的PU相连构成一个环，左、右方向上每一行的右端PU与下一行的左端PU相连，最下面一行右端的PU与最上面一行左端PU相连，从而形成一种闭合的螺线形状，所以又称闭合螺线阵列。在这个阵列中，步距不等于1 或8 的任意处理单元之间的通信，可以用软件方法寻找最短路径进行，其最短距离都不会超过 7 步

4、。,例如，要将PU63的信息传送到PU10，最快可经PU63PU7PU8PU9PU104 步即可实现，而要将PU9的信息传送到PU45，最快可经PU9PU1PU57PU56PU48PU47PU46PU45 7 步实现。普遍来讲，个处理单元组成的阵列中，任意两个处理单元之间的最短距离不会超过 步。,2.阵列处理机的算法举例 1)有限差分问题 求解场方程时，常使用有限差分法。它是把一个有规则的网格覆盖在整个场域上，用网格点上的变量值写出差分方程组来代替场方程进行计算。在解决物理问题时，如果将描述平面场的拉普拉斯方程,中的二阶偏导数表示为差分形式：,并代入原方程，即可得有限差分计算公式,式中，(x,

5、y)为网格点坐标，h为网格点的间距。,2)矩阵加 在阵列处理机上，解决矩阵加法是最简单的一维情形。若有两个 88 的矩阵A、B相加，所得结果矩阵C也是一个 88 的矩阵。只需把A、B居于相应位置的分量存放在同一个PEM内，且在全部 64 个PEM中，令A的分量均为同一地址，B的分量单元均为同一地址+1，而结果矩阵C的各个结果分量也相应存放于各PEM同一地址+2的单元内，如图 6.4 所示。这样，只需用下列3条ILLIAC 的汇编指令就可以一次实现矩阵相加：,LDA ALPHA;全部()由PEMi送PEi的累加器RGAiADRN ALPHA+1;全部(+1)与(RGAi)进行浮点规舍加，结果送R

6、GAiSTA ALPHA+2;全部(RGAi)由PEi送PEMi的+2单元这里，0i63。,图 6.4 矩阵相加的存贮器分配举例,3)矩阵乘 由于矩阵乘是二维数组运算，故它比循环加要复杂一些。设A、B和C为3个 88 的二维矩阵。若给定A和B，则为计算C=A*B的 64 个分量，可用下列公式,其中，0i7 且 0j7。,在SISD计算机上求解这个问题，可执行用FORTRAN语言编写的下列程序,DO 10 I=0,7 DO 10 J=0,7 C(I,J)=0 DO 10 K=0,710 C(I,J)=C(I,J)+A(I,K)*B(K,J),需要经过I、J、K三重循环完成。每重循环执行 8 次，

7、总共需要512次乘、加的时间，此外每次还应包括执行循环控制、判别等其他操作需花费的时间。而如果在SIMD阵列处理机上运算，则可用 8 个处理单元并行计算矩阵C(I，J)的某一行或某一列，即将J循环或I循环转化成一维的向量处理，从而消去了一重循环。以消去J循环为例，可执行用FORTRAN语言编写的下列程序 DO 10 I=0,7 C(I,J)=0 DO 10 K=0,7 10 C(I,J)=C(I,J)+A(I,K)*B(K,J),图 6.5 矩阵乘程序执行流程图,图 6.6 矩阵乘的存贮器分配举例,4)累加和 这是一个将N个数的顺序相加过程转变为并行相加过程的问题。为了得到各项累加的部分和和最

8、后的总和，要用到处理单元中的活跃标志位。只有处于活跃状态的处理单元，才能执行相应的操作。为叙述方便，取N为8，即有8 个数A(I)顺序累加，其中 0I7。在SISD计算机上可写成下列FORTRAN程序：C=0 DO 10 I=0,7 10 C=C+A(I)这是一个串行程序，需要 8 次加法时间。,如果在并行处理机上，采用成对递归相加的算法，则只需log28=3 次加法时间就够了。首先，原始数据A(I)分别存放在 8 个PEM的单元中，其中 0I7。然后，按照下面的步骤求累加和：第一步 置全部PEi为活跃状态，0i7；第二步 全部A(I)从PEMi的单元读到相应PEi的累加寄存器RGAi中，0i

9、7;第三步 令k=0;第四步 将全部PEi的(RGAi)转送到传送寄存器RGRi，0i7；第五步 将全部PEi的(RGRi)经过互连网络向右传送2k步距，0i7;,第六步 令j=2k-1;第七步 置PE0至PEj为不活跃状态；第八步 处于活跃状态的所有PEi执行(RGAi):=(RGAi)+(RGRi)，ji7；第九步 k:=k+1;第十步 如k3，则转回第四步，否则往下继续执行；第十一步 置全部PEi为活跃状态，0i7;第十二步 将全部PEi的累加寄存器内容(RGAi)存入相应PEMi的+1单元中，0i7。,图 6.7 并行处理机上累加和计算过程的示意图,图 6.8 循环互连网络组成框图,6

10、.1.3 SIMD计算机的互连网络,1.互连网络的设计目标及互连函数,2.基本的单级互连网络,1)立方体单级网络,图 6.9 三维立方体结构,这是一个三维的情形。立方体的每一个顶点(网络的节点)代表一个处理单元，共有 8 个处理单元，用zyx三位二进制码编号。它所能实现的入、出端连接如同立方体各顶点间能实现的互连一样，即每个处理单元只能直接连到其二进制编号的某一位取反的其他 3 个处理单元上。如 010 只能连到 000、011、110，不能直接连到对角线上的 001、100、101、111。所以，三维的立方体单级网络有 3 种互连函数：Cube0、Cube1和Cube2。其连接方式如图 6.

11、10 中的实线所示。Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0,1,2)上有差别，即仅在该位上的代码“0”、“1”互反，其余各位代码都相同。,图 6.10 立方体单级网络连接图,推广到n维的情形，N个节点的立方体单级网络共有n=log2N种互连函数，即,式中，0in-1，Pi为入端号二进制码的第i位。当维数n3时，称为超立方体(Hyper Cube)网络。,2)PM2I单级网络 PM2I单级网络是“加减2i”(Plus-Minus 2i)单级网络的简称。能实现与j号处理单元直接相连的是号为j2i的处理单元，即,式中，0jN-1,0in-1,n=log2N。因此，它共有

12、2n个互连函数。由于总存在PM2+(n-1)=PM2-(n-1)，所以实际上，PM2I互连网络只有2n-1种不同的互连函数。,对于N=8的三维PM2I互连网络的互连函数有PM2+0、PM2-0、PM2+1、PM2-1、PM22等 5 个不同的互连函数，它们分别为：PM2+0:(0 1 2 3 4 5 6 7)PM2-0:(7 6 5 4 3 2 1 0)PM2+1:(0 2 4 6)(1 3 5 7)PM2-1:(6 4 2 0)(7 5 3 1)PM22:(0 4)(1 5)(2 6)(3 7),图 6.11 PM2I互连网络的部分连接图,有的阵列处理机采用单向环网或双向环网实现处理器的互连

13、，可以看成是PM2I网络的特例，它仅使用了其中的PM2+0、PM2-0或PM20互连函数。不难看出，ILLIAC 处理单元的互连也是PM2I互连网络的特例，只采用了其中的PM20和(即PM23)4 个互连函数。PM2I单级网络的最大距离为n/2。以上面的三维PM2I互连网络的例子就可以看出，最多只要二次使用，即可实现任意一对入、出端号之间的连接。,3)混洗交换单级网络,图 6.12 8 个处理单元的全混连接,用互连函数表示为,式中，n=log2N，Pn-1Pn-2P1P0为入端编号的二进制码。,Shuffle函数还有一个重要特性。如果把它再作一次Shuffle函数变换，得到的是一组新的代码，即

14、Pn-3P0Pn-1Pn-2。这样，每全混一次，新的最高位就被移至最低位。当经过n次全混后，全部N个处理单元便又恢复到最初的排列次序。在多次全混的过程中，除了编号为全“0”和全“1”的处理单元外，各个处理单元都遇到了与其他多个处理单元连接的机会。,图 6.13 N=8 时全混交换互连网络连接图,3.多级互连网络,交换开关是具有两个入端和两个出端的交换单元，用作各种多级互连网络的基本构件。不论入端或出端，如果令居于上方的都用i表示，居于下方的都用j表示，则可以定义下列 4 种开关状态或连接方式：(1)直连i入连i出，j入连j出；(2)交换i入连j出，j入连i出；(3)上播i入连i出和j出，j入悬

15、空；(4)下播j入连i出和j出，i入悬空。,只具有前两种功能的称二功能交换单元，具有全部 4 种功能的称四功能交换单元。两个入端同时连到一个出端的情形是不允许的，因为会发生信息传送的冲突现象。此外，还可以有第 5 种开关状态，即i入连j入，i出连j出，称此为返回。它可用来实现入端与入端相连，出端与出端相连，从而将N个入端和N个出端的网络变为 2N个处理单元的互连网络。拓扑结构是指各级之间出端和入端相互连接的模式。,控制方式是对各个交换开关进行控制的方式，以多级立方体网络为例，它可以有 3 种：(1)级控制同一级的所有开关只用一个控制信号控制，同时只能处于同一种状态；(2)单元控制每一个开关都有

16、自己独立的控制信号控制，可各自处于不同的状态；(3)部分级控制第i级的所有开关分别用i+1个信号控制，0in-1,n为级数。,1)多级立方体网络多级立方体网络有STARAN网络、间接二进制n方体网络等。,图 6.14 N=8 多级立方体互连网络,STARAN网络用作交换网络时，采用级控制，实现的是交换函数。所谓交换(Flip)函数，是将一组元素首尾对称地进行交换。如果一组元素包含有2s个，则它是将所有第k个元素都与第(2s-(k+1)个元素相交换。,表 6.1 三级STARAN交换网络实现的入出端连接及所执行的交换函数功能(Ki为第i级控制信号),从表 6.1 可以看出，控制信号为111 时，

17、实现的是全交换，又称镜像交换，完成对这 8 个处理单元(元素)的一组 8 元交换，其变换图像如下：入端排列|0 1 2 3 4 5 6 7|出端排列|7 6 5 4 3 2 1 0|控制信号为 001 时，完成对这 8 个处理单元(元素)的 4 组 2 元交换，其变换图像为：入端排列|0 1|2 3|4 5|6 7|出端排列|1 0|3 2|5 4|7 6|,控制信号为 010 时，完成的功能相当于在 4 组 2 元交换后，再 2 组 4 元交换，其变换图像是：|1 0 3 2|5 4 7 6|2 3 0 1|6 7 4 5|而控制信号为 101 时，相当于在实现上述两种交换后，再1 组 8

18、元交换，其变换图像是：|2 3 0 1 6 7 4 5|5 4 7 6 1 0 3 2|,出端排列,出端排列,表 6.2 三级移数网络能实现的入出端连接及移数函数功能,2)多级混洗交换网络多级混洗交换网络又称omega网络，如图 6.15 所示。,图 6.15 N=8多级混洗交换网络,3)多级PM2I网络,图 6.16 N=8多级PM2I网络,4.全排列网络 如果互连网络是从N个入端到N个出端的一到一的映射，就可以把它看成是对此N个端的重新排列。因此，互连网络的功能实际上就是用新排列来置换N个入端原有的排列。前面所介绍的各种基本多级网络都能实现任意一个入端与任意一个出端间的连接，但是要同时实现

19、两对或多对入端与出端之间的连接时，都有可能因争用数据传送路径而发生冲突。我们称具有这类性质的互连网络为阻塞式网络(Blocking Network)。反之，不具有这类性质的互连网络为非阻塞式网络，或称为全排列网络。非阻塞式网络连接的灵活性好，但连线多，控制复杂，成本高。,阻塞式网络在一次传送中不可能实现N个端的任意排列。大家知道，N个端的全部排列共有N!种。可是，对使用单元控制的n=log2N级组成的间接二进制n方体网络来说，每级有N/2个开关，n级互连网络所用交换开关的总数为(Nlog2N)/2。为实现入出端的一对一映射，每个开关只能使用直连和交换两种功能。这样，所有开关处于不同状态的总数最

20、多只有2(Nlog2N)/2，即NN/2种。当N为大于 2 的任何整数时，总有NN/2N!,这就是说，它无法实现相应的所有N!种排列。以N=8的三级网络为例，共12个两功能交换开关，只有 212=4 096 种不同状态，最多只能控制对端子的 4 096 种排列，不可能实现全部 8!=40 320 种排列。所以，多对入出端要求同时连接时，就有可能发生冲突。,然而，只要对这个多级互连网络通行两次，每次通行时，让各开关处于不同状态，就可以满足对N个端子的全部N!种排列。因为此时，全部开关的总状态数可有NN/2NN/2=NN种，足以满足N!种不同排列的开关状态要求。这种只要经过重新排列已有入出端对的连

21、接，就可以完成所有可能的入出端间的连接而不发生冲突的互连网络，称为可重排列网络(Rearrangeable Network)。实现时，可以在上述任何一种基本多级互连网络的出端设置锁存器，使数据在时间上顺序通过两次，这实际上就是循环互连网络的实现思路。,图 6.17 多级全排列网络举例(Benes网络),6.1.4 并行存贮器的无冲突访问,图 6.18 一维数组的存贮(m=4),如果设m=n=4,一个44 的二维数组直接按行存贮，方案如图 6.19 所示。虽然，同时访问某一行、主对角线或次对角线上的所有元素时，都可以做到无冲突地访问，但要同时访问某一列的各元素时，由于它们集中存放在同一存贮分体内

22、，会产生访存冲突，所以每次只能顺序访问其中的一个元素，致使实际频宽降低成 1/4。,图 6.19 44 数组的直接按行存贮(m=n=4),图 6.20 44 数组一种错位存放的方案(m=n=4,1=2=1),假设在nn的二维数组中，同一列两个相邻元素在并行存贮器中错开的地址距离为1，而同一行两个相邻元素在并行存贮器中错开的距离为2，当m取成22p+1(p为任意正整数)时，实现无冲突访问的充分条件就是让1=2p,2=1。图 6.21 就是对 44 的二维数组按上述规则存贮的一种方案。其中 p=1,m=5,1=2,2=1。,图 6.21 44 数组错位存放的例子(m=5,n=4,1=2,2=1),

23、图 6.22 45 二维数组在并行存贮器中存放的例子(m=7,n=6),6.2 并行处理机举例,6.2.1 ILLIAC 阵列处理机,图 6.23 ILLIAC 的组成,PE的字长为 64 位，内部主要包括 4 个 64 位的寄存器，它们是累加器A、操作数寄存器B、数据路由寄存器R、通用存贮寄存器S。其运算部分有一个加法/乘法器、逻辑部件以及分别用于算术、布尔和移位操作的桶形开关。另有一个 16 位的变址寄存器X，一个 8 位的用于存放测试结果和PE屏蔽标志的方式寄存器，一个形成访存地址的地址加法器。在PE中能进行 64 或 32 位浮点运算、48 或 24 位定点运算、8 位字符处理、64

24、位逻辑运算等。所有PE都按CU播送来的指令工作，但可通过屏蔽标志来确定本PE是否活跃，即是否执行该指令。PEMi是依附于PEi的局部存贮器，容量为2 K字。,并行读写磁盘用作后援存贮器，容量为109 位。传送控制器将数据从磁盘取到PEM时，按CU来的要求向B6500 发中断请求。缓冲I/O存贮器用作B6500的缓冲。I/O接口用作处理单元阵列与I/O子系统及磁盘间的数据通路转接和缓冲。PEM中的指令或数据经CU总线送往CU，每次可送 8 个字，即 512 位。CU经 64 位的公共数据总线向所有PE播送公用信息，经指令控制线向所有PE发送控制命令。方式位线共 64 根，每个PEi有一根，用来向

25、CU传送该PEi的方式寄存器中的方式位。,6.2.2 BSP科学处理机,图 6.24 BSP的5 级数据流水线结构示意图,图 6.25 BSP科学处理机系统组成,6.2.3 MPP位平面阵列处理机,图 6.26 MPP并行处理机原理框图,6.2.4 CM连接机,图 6.27 CM-5 的组成,图 6.28 二叉胖树,6.3 相 联 处 理 机,6.3.1 相联处理机和相联存贮器的组成 1.相联处理机的特点和组成,图 6.29 相联处理机的构成,2.相联存贮器的组成及相联处理机的结构类型,图 6.30 相联存贮器的组成,图 6.31 相联存贮器位单元的逻辑电路方案,6.3.2 相联检索算法,1)

26、全等查找算法 所谓全等查找，是指找出与比较数寄存器CR未屏蔽的那部分内容完全相同的全部字单元。因此，只要将比较查找的内容装入比较数寄存器CR中，然后对屏蔽寄存器MR中为“1”的那些位片段，逐位地进行相联查找即可。凡出现与比较数寄存器内容不相等，即当CRj=1而Bij=0 或 CRj=0 而Bij=1 时，查找产生的信号将字选择寄存器的WSRi置成“0”。这样，只要等各位片逐一查找比较完毕之后，字选择寄存器WSR中标志位仍为 1 的那些存贮单元就是全等查找的响应单元，其内容必定与比较数完全相等。由于全等查找比较简单，如采用全并行方式工作的相联存贮器，硬件保证位片间同时操作，将使查找速度有显著提高

27、。,2)最大值查找算法 所谓最大值查找，是要找出存贮器中所存的最大数及存放此最大数的所有单元，相同的最大值完全可能有多个。与全等查找算法类似，同样可以事先设置好屏蔽寄存器和字选择寄存器的初始状态来控制位向和字向的哪些部分参与查找。首先，将字选择寄存器置成全“1”，比较数寄存器CR置初始值为全“1”，屏蔽寄存器的最高位置为“1”、其余位置为“0”。然后，进行比较，看是否有单元响应。这时只是检查各待查单元的最高位是否为 1。,若有响应，表明最大值的最高位为 1，让所有未响应单元产生信号，将字选择寄存器的对应位WSRi都置成“0”，使其不再继续参与下一个位片的查找；如果没有一个响应，表明最大值的最高

28、位为 0，因此只要将比较数寄存器的该位改置为“0”，并维持字选择寄存器中的内容不变即可。下一步，将屏蔽寄存器的次高位置为“1”，其余位置为“0”，再进行类似的比较及处理。这样，自左到右逐位比较处理完毕，其比较数寄存器中保留的内容就是要找的最大值，而字选择寄存器中的状态就是存放此最大值所在存贮单元的位置。,3)幅值比较查找算法 幅值比较查找是指在给定某比较数后，要分别找出存贮器中内容大于、等于、小于该比较数的单元位置，也就是将存贮器的单元按给定幅值进行比较，将其分成 3 类。为此，可对每个单元设置一个三位的标志位XYZ。查找开始前，设各单元的标志位XYZ为 100，表示“未定”状态。然后自左至右

29、逐位查找，结果可能会出现下面 3 种状况：(1)CRj=0,Bij=1。这表示i单元第j位的值大于比较数第j位的值，可以置标志位XYZ为 010，此后，该i单元不再参与比较；,(2)CRj=1,Bij=0。这表示i单元第j位的值小于比较数第j位的值，可以置标志位XYZ为 001，此后，该i单元也不再参与比较；(3)CRj=Bij。这表示i单元的第j位的值等于比较数第j位的值，让标志位维持 100 不变，之后，该i单元仍继续参与下一个位片的比较。如果将所有单元从最高位到最低位全部查找一遍，根据各个单元标志位XYZ的状态就能知道哪些单元的内容等于比较数，哪些大于比较数，哪些小于比较数。这样，按幅值分类的工作也就完成了。4)其他算法,6.3.3 相联处理机结构举例,1.PEPE系统,图 6.32 PEPE系统的逻辑结构,2.STARAN系统,图 6.33 STARAN机系统结构框图,图 6.34 相联阵列模块的结构,