第 6 章 并行处理机和相联处理机 第 6 章 并行处理机和相联处理机 6.1 并行处理机原理 6.2 并行处理机举例 6.3 相联处理机 第 6 章 并行处理机和相联处理机 6.1 并行处理机原理 6.1.1 并行处理机的构形与特点 1. 并行处理机的基本构形 图 6.1 具有分布式存贮器的并行处理机构形 第 6 章 并行处理机和相联处理机 图 6.2 具有集中式共享存贮器的并行处理机构形 第 6 章 并行处理机和相联处理机 2. 并行处理机的特点并行处理机的单指令流多数据流处理方式和由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。这些计算问题的共同特点是可以通过各种途径把它们转化成为对数组或向量的处理，而并行处理机正好利用多个处理单元对向量或数组所包含的各个分量同时计算， 从而获得很高的处理速度。与同样擅长于向量处理的流水线处理机相比，并行处理机利用的是资源重复，而不是时间重叠；利用并行性中的同时性，而不是并发性。它的每个处理单元要同等地担负起各种运算功能，但其设备利用率却可能没有多个单功能流水线部件那样高。因此，只有在硬件价格有了大幅度下降及系统结构有了较大改进的情况下，并行处理机才能具有较好的性能价格比。并行理机主要是靠增大处理单元个数来提高运算速度，比起向量流水线处理机主要依靠缩短时钟周期来说， 速度提高的潜力要大得多。 第 6 章 并行处理机和相联处理机 6.1.2 并行处理机的算法 1. ILLIAC 的处理单元阵列结构 图 6.3 ILLIAC 处理单元的互连结构 第 6 章 并行处理机和相联处理机 PUi为处理部件，包含 64 位的算术处理单元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 步。 第 6 章 并行处理机和相联处理机 例如，要将PU63的信息传送到PU10，最快可经PU63PU7PU8PU9PU104 步即可实现，而要将PU9的信息传送到PU45，最快可经PU9PU1PU57PU56PU48PU47PU46PU45 7 步实现。 普遍来讲， 个处理单元组成的阵列中，任意两个处理单元之间的最短距离不会超过 步。 第 6 章 并行处理机和相联处理机 2. 阵列处理机的算法举例1) 有限差分问题求解场方程时，常使用有限差分法。它是把一个有规则的网格覆盖在整个场域上，用网格点上的变量值写出差分方程组来代替场方程进行计算。在解决物理问题时，如果将描述平面场的拉普拉斯方程 中的二阶偏导数表示为差分形式： 第 6 章 并行处理机和相联处理机 并代入原方程， 即可得有限差分计算公式 式中， (x, y)为网格点坐标， h为网格点的间距。 第 6 章 并行处理机和相联处理机 2) 矩阵加在阵列处理机上，解决矩阵加法是最简单的一维情形。若有两个 88 的矩阵A、B相加，所得结果矩阵C也是一个 88 的矩阵。只需把A、B居于相应位置的分量存放在同一个PEM内，且在全部 64 个PEM中，令A的分量均为同一地址，B的分量单元均为同一地址+1，而结果矩阵C的各个结果分量也相应存放于各PEM同一地址+2的单元内，如图 6.4 所示。这样，只需用下列3条ILLIAC 的汇编指令就可以一次实现矩阵相加： 第 6 章 并行处理机和相联处理机 LDA ALPHA ; 全部()由PEMi送PEi的累加器RGAiADRN ALPHA+1 ; 全部(+1)与(RGAi)进行浮点规舍加， 结果送RGAiSTA ALPHA+2 ; 全部(RGAi)由PEi送PEMi的+2单元这里， 0i63。 第 6 章 并行处理机和相联处理机 图 6.4 矩阵相加的存贮器分配举例 第 6 章 并行处理机和相联处理机 3) 矩阵乘由于矩阵乘是二维数组运算，故它比循环加要复杂一些。设A、B和C为3个 88 的二维矩阵。若给定A和B，则为计算C=A*B的 64 个分量，可用下列公式 其中， 0i7 且 0j7。 第 6 章 并行处理机和相联处理机 在SISD计算机上求解这个问题， 可执行用FORTRAN语言编写的下列程序 DO 10 I=0,7DO 10 J=0, 7C(I,J)=0DO 10 K=0, 710 C(I,J)=C(I,J)+A(I,K)*B(K,J) 第 6 章 并行处理机和相联处理机 需要经过I、J、K三重循环完成。每重循环执行 8 次，总共需要512次乘、加的时间，此外每次还应包括执行循环控制、 判别等其他操作需花费的时间。而如果在SIMD阵列处理机上运算，则可用 8 个处理单元并行计算矩阵C(I，J)的某一行或某一列，即将J循环或I循环转化成一维的向量处理，从而消去了一重循环。以消去J循环为例，可执行用FORTRAN语言编写的下列程序DO 10 I=0, 7C(I,J)=0DO 10 K=0, 710 C(I,J)=C(I,J)+A(I,K)*B(K,J) 第 6 章 并行处理机和相联处理机 图 6.5 矩阵乘程序执行流程图第 6 章 并行处理机和相联处理机 图 6.6 矩阵乘的存贮器分配举例 第 6 章 并行处理机和相联处理机 4) 累加和这是一个将N个数的顺序相加过程转变为并行相加过程的问题。为了得到各项累加的部分和和最后的总和，要用到处理单元中的活跃标志位。 只有处于活跃状态的处理单元，才能执行相应的操作。为叙述方便，取N为8，即有8 个数A(I)顺序累加，其中 0I7。在SISD计算机上可写成下列FORTRAN程序：C=0DO 10 I=0, 710 C=C+A(I)这是一个串行程序， 需要 8 次加法时间。 第 6 章 并行处理机和相联处理机 如果在并行处理机上，采用成对递归相加的算法，则只 需log28=3 次加法时间就够了。首先，原始数据A(I)分别存放 在 8 个PEM的单元中，其中 0I7。 然后，按照下面的步骤 求累加和：第一步 置全部PEi为活跃状态， 0i7；第二步 全部A(I)从PEMi的单元读到相应PEi的累加寄存 器RGAi中， 0i7;第三步 令k=0;第四步 将全部PEi的(RGAi)转送到传送寄存器RGRi， 0i7；第五步 将全部PEi的(RGRi)经过互连网络向右传送2k步距 ，0i7; 第 6 章 并行处理机和相联处理机 第六步 令j=2k-1 ;第七步 置PE0至PEj为不活跃状态；第八步 处于活跃状态的所有PEi执行(RGAi):=(RGAi)+(RGRi)， ji7；第九步 k:=k+1 ;第十步 如k3，则转回第四步，否则往下继续执行；第十一步 置全部PEi为活跃状态， 0i7;第十二步 将全部PEi的累加寄存器内容(RGAi)存入相应PEMi的+1单元中， 0i7。 第 6 章 并行处理机和相联处理机 图 6.7 并行处理机上累加和计算过程的示意图 第 6 章 并行处理机和相联处理机 图 6.8 循环互连网络组成框图 6.1.3 SIMD计算机的互连网络 1. 互连网络的设计目标及互连函数 第 6 章 并行处理机和相联处理机 2. 基本的单级互连网络 1) 立方体单级网络 图 6.9 三维立方体结构 第 6 章 并行处理机和相联处理机 这是一个三维的情形。立方体的每一个顶点(网络的节点)代表一个处理单元，共有 8 个处理单元，用zyx三位二进制码编号。它所能实现的入、出端连接如同立方体各顶点间能实现的互连一样，即每个处理单元只能直接连到其二进制编号的某一位取反的其他 3 个处理单元上。如 010 只能连到 000、 011、110，不能直接连到对角线上的 001、100、101、111。 所以，三维的立方体单级网络有 3 种互连函数：Cube0、 Cube1和Cube2。其连接方式如图 6.10 中的实线所示。Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0, 1, 2)上有差别，即仅在该位上的代码“0”、“1”互反，其余各位代码都相同。 第 6 章 并行处理机和相联处理机 图 6.10 立方体单级网络连接图 第 6 章 并行处理机和相联处理机 推广到n维的情形，N个节点的立方体单级网络共有n=log2N种互连函数， 即 式中，0in-1，Pi为入端号二进制码的第i位。当维数n3时，称为超立方体(Hyper Cube)网络。 第 6 章 并行处理机和相联处理机 2) PM2I单级网络PM2I单级网络是“加减2i”(Plus-Minus 2i)单级网络的简称。能实现与j号处理单元直接相连的是号为j2i的处理单元， 即 式中，0jN-1, 0in-1, n=log2N。因此，它共有2n个互连函数。由于总存在PM2+(n-1)=PM2-(n-1)，所以实际上，PM2I互连网络只有2n-1种不同的互连函数。 第 6 章 并行处理机和相联处理机 对于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 章 并行处理机和相联处理机 图 6.11 PM2I互连网络的部分连接图 第 6 章 并行处理机和相联处理机 有的阵列处理机采用单向环网或双向环网实现处理器的互连，可以看成是PM2I网络的特例，它仅使用了其中的PM2+0、 PM2-0或PM20互连函数。不难看出，ILLIAC 处理单元的互连也是PM2I互连网络的特例，只采用了其中的PM20和 (即PM23)4 个互连函数。PM2I单级网络的最大距离为n/2。以上面的三维PM2I互连网络的例子就可以看出，最多只要二次使用，即可实现任意一对入、 出端号之间的连接。 第 6 章 并行处理机和相联处理机 3) 混洗交换单级网络 图 6.12 8 个处理单元的全混连接 第 6 章 并行处理机和相联处理机 用互连函数表示为 式中，n=log2N，Pn-1Pn-2P1P0为入端编号的二进制码。 第 6 章 并行处理机和相联处理机 Shuffle函数还有一个重要特性。如果把它再作一次Shuffle函数变换，得到的是一组新的代码，即Pn-3P0Pn-1Pn-2。这样， 每全混一次，新的最高位就被移至最低位。当经过 n次全混后， 全部N个处理单元便又恢复到最初的排列次序。在多次全混的过程中，除了编号为全“0”和全“1”的处理单元外，各个处理单元都遇到了与其他多个处理单元连接的机会。 图 6.13 N=8 时全混交换互连网络连接图 第 6 章 并行处理机和相联处理机 3. 多级互连网络 交换开关是具有两个入端和两个出端的交换单元，用作各种多级