第6章阵列处理机.ppt

1、第6章 阵列处理机,6.1 阵列处理机原理 6.2 阵列处理机的并行算法 6.3 SIMD计算机的网络互连 6.4 并行存储器的无冲突访问 6.5 并行处理机举例,本章重点： 总的要求是理解阵列处理机的结构和工作原理。了解与流水处理机的差别。理解在阵列处理机解题时对并行算法及存储单元分配规则、互连网络等的特殊要求。熟练掌握基本的单级网络及其互连函数表示。理解循环互连网络的实现。熟练掌握多级网络、全排列网络的画法。理解解决并行存储器无冲突访问的办法。 互连函数和多级互连网络。 本章难点： 并行算法和多级互连网络。,6.1 阵列处理机原理,6.1.1 阵列处理机的基本构形 阵列处理机(Array

2、Processor),也称为并行处理机(Parallel Processor)主要用于对大量向量、数组要求高速运算的场合。 阵列处理机是重复设置处理单元按一定方式连成阵列在单一控制部件控制下对各自分配的数据执行同一指令规定的操作，是操作级并行的SIMD的计算机。 由于存储器的组成方式不同，阵列处理机有两种不同的基本构形。,1、分布式存储器的阵列处理机构形 各处理单元有局部存储器PEM(Processing Element Memory)存放被分布的数据，只能被本处理单元直接访问。在控制部件CU上有一主存可传播给各个处理单元，运算中可通过互连网络ICN交换数据。 在执行主存中的用户程序时，所有指

3、令都在控制部件中进行译码，把只适合串行处理的标量或控制类指令留给控制部件CU自己执行，而把适合于并行处理的向量类指令“播送”给各个PE，控制处于“活跃”的那些PE并行执行。下图是采用分布式存储器的阵列处理机构形。,为了有效高速地处理向量数据，这种构形要求能把数据合理地预分配到各个处理单元的局部存储器中，使各处理单元PEi主要用自己的局存PEMi中的数据运算。 采用这种构形的阵列处理机是SIMD的主流。典型机器有ILLIAC 、MPP、 DAP、CM-2、MP-1、DAP600系列等。 2、集中式共享存储器的阵列处理机构形 系统存储器由K个存储体集中组成，并经ICN为全部N个处理单元所共享。 为

4、使各处理单元对长度为N的向量中各个元素都能同时并行处理，存储体体数K应等于或多于处理单元数N。,各处理单元在访主存时，为避免发生分体冲突，也要求有合适的算法能将数据合理地分配到各个存储体中。 互连网络ICN是用于在处理单元与存储器分体之间进行转接构成数据通路，使各处理单元能高速灵活地动态与不同的存储体相连，使尽可能多的PE能无冲突地访问共享的主存模块。 集中式共享存储器的阵列处理机主要特点是将资源重复和时间重复结合起来开发并行性。 采用这种构形的典型机器有BSP。,6.1.2 阵列处理机的特点 1、利用资源重复而不是时间重叠；利用并行性中的同 时性而不是并发性。 2、资源利用率不如流水线高，但

5、提高速度的潜 力比流水线处理机大。（阵列处理机主要是 靠增大处理单元数提高速度，向量流水处理 机主要靠缩短时钟周期提高速度）。 3、阵列处理机使用简单规整的互连网络来确定处 理单元间的连接，因此，互连网络设计很重要。 4、它是以某类算法为背景的专用计算机，基本上 是专用于向量处理的计算机(某类算法专用机)， 故阵列处理机专用性强。,5、阵列机的研究必须与并行算法研究密切结合，以使它的求解算法适应性更强一些，应用面更广一些(与并行算法结合研究)。 阵列处理机实质上是由专门对付数组运算的处理单元阵列组成的处理机、专门从事处理单元阵列的控制及标量处理的处理机和专门从事系统输入输出及操作系统管理的处理

6、机组成的一个异构型多处理机系统。,6.2 阵列处理机的并行算法,6.2.1 ILLIAC 的处理单元阵列结构 ILLIAC IV处理阵列由8864个PU组成。每个PU由处理部件PE和它的局部存储器PEM组成。 每一个PUi只和它的上、下、左、右四个近邻直接连接。PUi+1 mod 64、PUi-1 mod 64、PUi+8 mod 64、PUi-8 mod 64 上下方向上同一列的PU连成一个环，左右方向上构成一个闭合螺线。,采用闭合螺线最短距离不超过7步。而普通网格最短距离不超过8步。这种阵列中，任意两个单元之间的最短距离不超过 步。 例如：从PU0到PU36的距离：采用普通网格必须8步：P

7、U0 PU1 PU2 PU3 PU4 PU12 PU20 PU28 PU36或 PU0 PU8 PU16 PU24 PU32 PU33 PU34 PU35 PU36或 （等于8步的很多，大于8步的更多）如果采用闭合螺旋线，只需要7步：PU0 PU63 PU62 PU61 PU60 PU52 PU44 PU36,普通网格必须8步：PU0 PU1 PU2 PU3 PU4 PU12 PU20 PU28 PU36或 PU0 PU8 PU16 PU24 PU32 PU33 PU34 PU35 PU36或 闭合螺旋线只要7步：PU0 PU63 PU62 PU61 PU60 PU52 PU44 PU36或

8、PU0 PU63 PU55 PU47 PU39 PU38 PU37 PU36或 ,P180习题6.1,解如图：,与PU0相连的处理单元有：PU1、PU12、PU15、PU4 与PU1、PU12、PU15、PU4相连的有PU2、PU3、PU5、PU13、PU8、PU11、PU14（删去一步单元）与PU2、PU5、PU13、PU8、PU11、PU14相连的有：PU6、PU7、PU9、PU10（删去一、二步单元） PE0经一步可将信息传送至PU1、PU4、PU12、PU15。PE0至少需经二步才能将信息传送至PU2、PU3、PU5、PU8、PU11、PU13、PU14。PE0至少需经三步步才能将信息

9、传送至PU6、PU7、PU9、PU10。,6.2.2 阵列处理机的并行算法举例 1、矩阵加 把C=A+B中的属于同一位置向量元素放在同一局部存储器中。两个8 8的矩阵A、B相加，所得结果C也是8 8矩阵，矩阵相加的存储器分配如下图所示(“全并行”的工作特点，速度提高，但存储单元分配算法的设计比较麻烦)。,2、矩阵乘 把C=A*B的各向量按列存放在一个局部存储器中。 设A、B和C为3个8 8的二维矩阵，给定A和B，计算C=A*B得64个分量可用公式： 其中0 i 7且 0 j 7。 在SISD计算机上求解，用FORTRAN语言编写程序为： DO 10 I=0,7 DO 10 J=0,7 C(I,

10、J)=0 DO 10 K=0,7 10 C(I,J)=C(I,J)+A(I,K)*B(K,J),需经I、J、K三重循环完成。每重循环执行8次，共需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),让J=07各部分同时在PE0PE7上运算

11、，这样只需K、J二重循环，速度可提高至8倍，即只需64次乘、加的时间。（164页图6.5） 每次控制部件执行的PE指令表面上是标量指令，实际上已等效于向量指令，是8个PE并行地执行同一条指令。每次播送时，利用阵列处理机的播送功能将处理单元PEK中累加寄存器RAGK的内容经控制部件CU播送到全部8个处理单元的RGA中去。 为了让各个处理单元PEi尽可能只访问所带局部存储器PEMi，以保证高速处理，就必须要求对矩阵A、B、C各分量在局部存储器中的分布采用165页如图6.6所示的方案。,3、累加和 把向量存到所有处理单元的局部存储器中。 将N个数的顺序相加转为并行相加的问题。 取N=8，即有8个数A

12、(I)顺序累加，其中 0I7。 在SISD计算机上可以写成FORTRAN程序： C=0 DO 10 I=0,7 10 C=C+A(I) 这是一个串行程序，需要8次加法时间。,在阵列处理机上用成对递归相加算法，只需 次加法时间即可。首先，原始数据A(I)分别存放在8个 PEM的 单元中，其中0I7，求累加和的步骤如下： （1）置全部PEi为活跃状态， 0I7； （2）全部 A(I)从PEMi的 单元读到相应PEi的累加寄存 器RGAi中， 0I7； （3）令K=0; （4）将全部PEi的(RGAi)转送到传送寄存器RGRi, 0I7； （5）将全部PEi的(RGRi)经过互连网络向右传送2K步距

13、, 0I7； （6）令j=2K-1; （7）置PE0PEj为不活跃状态；,（8）处于活跃状态的所有PEi执行(RGAi)：= (RGAi)+ (RGRi), ji7; （9） K:=K+1; （10）如K3,则转回（4），否则往下继续执行； （11）置全部PEi为活跃状态， 0I7； （12）将全部PEi的累加寄存器内容(RGAi)存入相应 PEMi的 单元中， 0I7。 165页图6.5描绘了阵列处理机上累加和的计算过程。 上例可以实现累加和的并行运算，但由于屏蔽了部分处理单元，降低了它们的利用率，所以速度不是提高N倍，而只是N/log2N倍。,6.3 SIMD计算机的互连网络,6.3.1

14、互连网络的设计目标及互连函数 在SIMD计算机中，无论是处理单元之间，还是处理单元与存储分体之间，都要通过互连网络交换信息。 SIMD系统的互连网络的设计目标是：结构不要过分复杂，以降低成本；互连要灵活，以满足算法和应用的需要；处理单元间信息交换所需传送步数要尽可能少，以提高速度性能；能用规整单一的基本构件组合而成，或者经多次通过或者经多级连接来实现复杂的互连，使模块性好，以便于用VLSI实现并满足系统的可扩充性。,在阵列机中，各个处理单元和存储模块之 间都要经过网络交换信息。衡量互连网络性能好坏的主要因素是它的连接度、延时性、带宽、可靠性和成本。 设计互连网时应考虑的四个特征是： 1、操作方

15、式：有同步、异步及同步/异步组合 等三种。阵列机都采用同步工作方式，也就 是各种命令的广播和并行操作都由统一的时 钟加以同步控制。异步及同步/异步组合操 作方式一般多用于多处理机。,2、控制策略：集中或分布两种控制策略。多数现有的SIMD互连网络是采用由集中控制部件对全部开关单元执行集中控制策略。 3、交换方法：线路交换和包交换(又称分组交换)以及线路/包交换组合三种。SIMD互连网络多采用硬连的线路交换。包交换则多用于多处理机和计算机网络中。我们的互联网可算是一个MIMD多机系统。 4、网络的拓扑结构：指的是互连网络入、出端可以实现的连接的模式，有静态和动态两种。在阵列机中，采用的是动态拓扑

16、。,动态网络有单级和多级两类。动态单级网络只有有限的几种连接，必须经循环多次通过，才能实现任意两个处理单元之间的信息传送，故称此动态单级网络为循环网络。动态多级网络是由多个单级网络串联组成，以实现任意两个处理单元之间的连接。将多级互连网络循环使用可实现复杂的互连。循环互连网络的模型如167页图6.8（图见下页）所示。 现在的绝大多数阵列机都采用多级互连网络或多级循环互连网络。为反映互连特性，每种互连网络可用一组互连函数定义。,为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法： (1) 互连函数表示法：如：f(xn-1x1x0)=x0 xn-2x1xn-1 自变量和函数可以用二进

17、制表示，也可以用十进制等表示。(2) 图形表示法(3) 输入输出对应表示法,输入: 0 1 2 3 4 5 6 7输出: 1 0 3 2 5 4 7 6,6.3.2 基本的单级互连网络,1.立方体单级网络 立方体的每一个顶点代表一个处理单元，共有8个处理单元，用直角坐标系上zyx三位二进制码编号。每个处理单元只能连接到其二进制编号的某一位取反的其它3个处理单元上。,三维立方体结构,三维的立方体单级网络有3种互连函数：Cube0、 Cube1、 Cube2。 Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0,1,2)上0、1互反，其余各位代码都相同。其连接方式如下图中的实线所

18、示：,推广到n维时,N个节点的立方体单级网络共有n=log2N 种互连函数，即： Cubei(Pn-1PiP1P0)=Pn-1PiP1P0 式中Pi为入端标号二进制码的第i位，且 0i n-1。当n3时称超立方体网络。 单级立方体网络的最大距离为n。 2.PM2I单级网络 PM2I单级网络是加减2i单级网络的简称。能实现与j号处理单元直接相连的是号为j2i的处理单元，即：,PM2+i(j)=j+2i mod N PM2-i(j)=j-2i mod N 其中0 i n-1， 0 j N-1 n=log2N ,N是结点数。它共有2n个互连函数。 PM2I网络的最大距离为 n/2 。由于PM2+(n

19、-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+1：（0 2 4 6） （1 3 5 7） PM22 ：（0 4）（1 5）（2 6）（3 7）,3.混洗交换单级网络 混洗交换单级网络（Shuffle-Exchange） 包含两个互连函数，一个是全混（PerfectShuffle）,另一个是交换（Exchange）。 这种互连网络由全混洗和交换两种互连函数组成：

20、全混Shuffle(Pn-1Pn-2.P1P0)=(Pn-2.P0Pn-1) 式中， n=log2N。相当于将处理单元的进制地址位中的最左位移到最右位的循环移位。由于全混洗互连网络不能实现全0和全1单元与其他单元的连接，因此引入交换网络中的Cube0函数，两函数复合后为： ExchangeShuffle(Pn-1Pn-2.P1P0)= (Pn-2.P0Pn-1),在混洗交换网络中，最远的两个入、出端号是全“0”和全“1”，它们的连接需要n次交换和n-1次混洗，所以最大距离为2n-1。,6.3.3 多级互连网络 将前面三种单级互连网络重复连接，就形成了最基本的多级互连网络。即多级立方体互连网络、

21、多级混洗交换网络和多级PM2I网络。 决定多级互连网络的特性的主要因素有以下三个方面：交换开关、拓扑结构和控制方式。 交换开关是具有两个输入端和两个输出端的交换单元。交换开关有直连、交换、上播、下播四种功能；控制方式则有级控制、单元控制、部分级控三种方式。,（1）直连i入连i出，j入连j出； （2）交换i入连j出，j入连i出； （3）上播i入连i出和j出，j入悬空； （4）下播j入连i出和j出，i入悬空。 级控制同一级的所有开关只用一个控制信号 控制，同时只能处于同一种状态； 单元控制每一个开关都有自己独立的控制信 号控制，可各自处于不同的状态； 部分级控制第i级的所有开关分别用i+1个信 号

22、控制，0 i n-1，n为级数。,1.多级立方体网络 通常是采用交换互连单级网络串接起来构成的。采用三种不同的控制方式，可以构成三种不同的互连网络。采用级控制可以构成STARAN交换网。采用部分级控制，可以构成STARAN移数网。采用单元控制可以构成间接二进制n方体网。 STARAN多级互连网络就是Cube0,Cube1,Cube2三种互连函数的三个单级立方体网串接起来的。在采用不同的级控制信号时，可以实现任一输入端到任一输出端的直接连接。第i级（0 i n-1）交换单元处于交换状态时，实现的是互连函数，且都采用二功能交换单元。,N=8多级立方体互连网络,开关组合控制： 级控制、部分级控制-S

23、TARAN网络(交换、移数功能)； 单元控制-间接二进制n方体网络(更复杂的功能)。 （1）交换功能 开关组合控制方式：级控制。,分组交换功能：组间次序不变，组内元素镜像。 Cube0-4组2元交换；Cube1-2组4元交换+4组2元交换； Cube2-1组8元交换+2组4元交换。,（2）移位功能 开关组合控制方式：部分级控制(第i级有i+1种控制信号),Mod的作用：不同Mod可用于不同的分组操作。,（3）应用 交换功能很适合于双向互连等要求的实现； 移数功能很适合于累加求和等要求的实现。 （4）带宽问题 STARAN可同时多对结点连接，尚不能同时任意组合。 （5）例题 例1：16个PE采用

24、STARAN网络互连时，实现相当于4组4元交换，然后2组8元交换，再1组16元交换功能。写出互连函数一般式、各级交换开关状态。,答：因需实现交换功能，故选择STARAN的交换功能(级控制方式）。,相加 Cube0+Cube1 +Cube3,各级开关状态：k3k2k1k0=(1011),互连函数：f(b3b2b1b0)=(b3b2b1b0),例2：编号0F的PE间，要实现下列通信配对：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)。请画出互连网络结构图，写出控制方式及各开关状态。,答：因需实现双向交换功能，选择STARAN网络的交换功能(级控制方式

25、)可满足要求。,配对要求：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A) 开关控制：因7的结点与7的结点配对，故需1组16元交换；,因03的结点与8B的结点配对,故需2组8元交换； 因01的结点与AB的结点配对,故需4组4元交换； 因0结点与A结点配对，故需8组2元交换。,各级开关状态：k3k2k1k0=(1010),2.多级混洗交换网络（网络,即Omega网络）,开关组合控制： 级控制、开关二功能-STARAN交换网络的逆网络； 部分级控制、开关二功能STARAN移数网络的逆网络； 单元控制、开关二、四功能-更强大的功能。,3.多级PM2I网络

26、 N=8的多级PM2I网络的结构如174页图6.16所示。它包含n级单元间连接，每一级都是把前后两列各N=2n个单元按PM2I拓扑相互连接起来。从第i级（0in-1）来说，每一个单元j （0iN-1）都有3根连接线分别通往出单元j、j+2i mod N和j-2i mod N，在图中，它们分别用点线、实线和虚线表示。 采用单元控制增强对各级单元控制的灵活性，让每一单元都有自己独立的控制信号H、D、U（平控H、下控D、上控U）。此种多级PM2I网络称为强化数据变换网络AMD（Augmented Data Manipulator），但是控制线多，成本较高。,ADM的拓扑结构和控制方式使它可以完全模仿

27、omega网络的四功能交换单元。利用数据变换网络可以实现各种灵活的移数、重复、间隔、展开等变换函数。 多级网络比较 灵活性(低高)：STARAN、间接二进制n方体、 Omega()、ADM(混洗四功能) 成本(低高)：同上 用途： STARAN、Omega PEM 间接二进制n方体 PEPE 功能：只能实现同时部分多对多功能。,4.全排列网络 定义：所有入端、出端的连接均不发生冲突的网络，又称非阻塞型网络，即：N入N出有N！种排列。 常规多级网络(如STARAN、等)属于阻塞型网络。 证明：对n=log2N级网络，开关数=N/2n。,排列数,全排列网络实现： 思想：N!NN/2NN/2NN。

28、方法：a.原有多级网络通过锁存器运行两次即 可； b.两个log2N网络背靠背串联。 用多级网络也可以实现全排列网络。将log2N级的N个入端和N个出端的互连网络和它的逆网络连在一起，省去中间完全重复的一级，就可以得到总级数为2log2N-1级的全排列网络。175页图6.17就是以三维立方体多级网络和它的逆网络连在一起，省去中间重复的一级后构成的全排列网络，称此网络为Benes网络。,6.4 并行存储器的无冲突访问,在阵列处理机中，存储器频宽要与多个处理单元的速率匹配，如何保证在各种访问模式下，存储器都能实现无冲突访问？ 为保证对存储器的并行无冲突访问，可采用的方法有，数据交叉存储在m个存储体

29、中，并且使存储体M大于每次要访问的全部向量元素N，且为质数。将数组按行或列变换成一维数组，形成一个一维线性地址空间，地址用a表示，然后，将地址a所对应的元素存放在体号地址j=a mod m，体内地址i= a/n 的单元中，就可以满足无冲突访问的要求。,无冲突访问技术,一、访问需求 并行存取向量中各分量信息； 对矩阵可按行、列、对角线等方法访问(步长不一致)。 二、存在问题 存储器带宽限制存储器带宽达不到向量带宽； 访存方式(步长)不同，产生访存冲突。 三、解决方法 1、采用多体交叉存储器 使存储体数超过PE数，保证PE所需要的带宽。 2、对向量分组操作 解决MEM带宽小于向量长度问题，提高处理

30、效率。,3、选择适当的存储体数m 使存储体数mPE数，达到无冲突访问 一维向量： 顺序存放，防止步长与m成比例； m取质数(与PE数互质)，且与步长互质。 一维数组的并行递归算法: 并行存储体数不能再取2的整数，而应该取成质数，当变址跳距与分体数互质时，就可以进行无冲突访问。 多维向量： 错位存放，满足行、列、对角线等访问要求； 对矩阵而言(m大于PE数时)- 设m=22P+1，1=2P，同一列不同行错开距离 2=1， 同一行不同列错开距离,对Aab，体号： j=(a1+b2+C) mod m 体内序号：i=a,当向量元素不固定，或非nn时 将多维变换成一维数组S，再对S进行处理。 对S(a)

31、，体号： j=a mod m 体内序号：i= a/n,通过浪费少量存储带宽和空间来避免冲突。 浪费比例： (m-n)/m，一般n=m-1。,常用方法：存储体数为质数，将向量变换成一维数组S，再对S进行处理。,6.5 并行处理机举例,6.5.1 MPP位平面阵列处理机 MPP位平面阵列处理机是美国 Goodyear宇航公司专门设计用于遥感卫星图象处理的巨型并行处理机,1983年在美国空军投入使用.它对ILLIAC IV阵列结构的重大改进就是采用位平面结构。每一个处理单元只包含一位的硬设备，内部的算术逻辑运算按位片串行进行。这既节省了设备，又使处理单元之间的信息通路宽度大大减小。与64位的ILLI

32、AC IV阵列相比，硬件设备量可减少为原来的几十分之一，即用同样的硬件设备量至少可以扩大阵列规模几十倍，也利于采用VLSI工艺。,MPP原理图如178页图6.23所示： 1、阵列部件ARU(ARAY UNIT)由16384=128*128 个处理单元PE组成，每个PE附有1024个本地随机存储器。 2、阵列物理规模为128行*132列，其中4列允许替换硬件出故障的列，使阵列规模仍保持128*128，同时存储器有校错功能。 3、字长可有4、8、12、16、20、24、28或32等多种，基本时钟频率10MHz,循环周期为100ns。 4、在MPP阵列中，每一个 PE只与其上、下、左、右4个邻近PE

33、相连接，阵列四个边缘的连接可用程序设置，有平面、水平圆柱、垂直圆柱、开螺线和闭螺线5种不同的阵列拓扑。,5、阵列ARU的左、右两边各有一排128位的开关，各通过128根并行线与阵列相连。 6、阵列控制部件执行MPP汇编语言，除了控制数据的输入输出通路外，还要执行存储在它的程序存储器中的应用程序，功能包括循环控制、子程序调用和标量运算等。 7、整个系统的控制任务是由程序及数据管理部件PDMU来承担的。 8、系统可有独立、联机和高速数据3种运行方式。,6.5.2 CM连接机 20世纪80年代末90年代初，Thinking Machines公司推出连接机CM-2，其后端处理阵列可含（464）K个PE，采用位片结构。其中每个芯片是4*4个PE组成的网格，安置杂12维的超级立方体的顶角上，每个PE最多可自带 1Mb存储器。所有数据处理器都受定序器控制，最大速度为10GFLOPS。 CM-2已用于解决文档检索、医疗诊断、VLSI电路分析和布线、计算流体动力学等。 CM-5是CM