阵列处理机和相联处理机.ppt

1、第 6 章 阵列处理机和相联处理机,6.1 阵列处理机的原理 6.2 SIMD计算机的互连网络 6.3 并行存储器的无冲突访问 6.4 脉动阵列处理机,本章要点,阵列处理机的构型及特点 基本的单级互联网络结构图及互联函数 两功能交换开关及四功能交换开关 多级立方体网络拓扑结构图的画法 多级混洗交换网络拓扑结构图的画法 并行存储器的无冲突访问,1.阵列处理机的构形 阵列机通常由一个控制部件CU、N个处理器单元PE、M个存储模块以及一个互连网络部件(IN)组成。,根据存储器模块是以分布式方式存取还是集中方式存取，阵列机可分为两种基本结构：分布式存储器的阵列机和共享存储器的阵列机。,6.1 阵列处理

2、机的原理,6.1.1 阵列处理机的构形与特点,分布存储器的阵列机结构,（1）分布式存储器的阵列机 各个处理单元设有局部存储器存放分布式数据，只能被本 处理单元直接访问。在控制部件CU内设有一个用来存放程序和 数据的主存储器CUM。各个PE同步执行来自CU的操作命令， 各处理单元通过IN来交换数据。,具有共享存储器的阵列机结构,（2）集中式共享存储器的阵列机 每个PE没有局部存储器，存储模块以集中形式为所有PE共 享。互连网IN受CU控制，用来构成PE和MM的数据交换通路 ， 具有双向性。,2阵列机的特点,并行处理机有如下特点： （1） 利用资源重复（空间因素）而非时间重叠。 （2）利用同时性而

3、非并发性。它的每个处理单元在同一时刻要 同等地担负起各种运算功能。 （3）提高运算速度主要是靠增大处理单元个数，比起向量流水 线处理机主要依靠缩短时钟周期来说，速度提高的潜力要大得多 （4）使用简单而又规整的互连网络来确定多个处理单元之间的 连接模式。 （5） 并行处理机（阵列机）研究必须与并行算法研究密切结合 ，使之适应性更强，应用面更广。,6.1.2 ILLIAC-IV处理单元阵列结构,处理单元阵列由64个PUi构成,每个PUi包括(PEi、PEMi和MLU) 由64个结构完全相同的处理单元PEi 构成，每个处理单元 PEi字长64位，PEMi为隶属于PEi的局部存储器，全部PEi由CU

4、统一管理，PEi都有一根方式位线，用来向CU传送每个PEi的方 式寄存器D中的方式位，使CU能了解各PEi的状态是否活动，作 为控制它们工作的依据。,阵列控制器CU 相当一台小型控制计算机 对处理单元阵列实现控制,(发控制信号,广播公共地址,(广播公 共数据)）对指令流进行译码控制,利用CU内部资源可以进行标 量操作,接受和处理各类中断，其他输入输出操作。,I/O系统 由磁盘文件系统DFS，输入输出子系统和宿主计算机S/C构成,ILLIAC 的组成,ILLIAC-IV的处理单元互连结构,特点: (1)闭合螺线阵列 (2)任意单元的最短距离不超过7步 将PU63传送到PU10，最快可经 PU63

5、PU7PU8PU9PU10。 (3)一般来讲： 个处理单元组成的阵列中，任 意两个处理单元之间的最短距离不会超过 步 （4）处理单元为通常的累加型运算器，把累加寄存器RGA 中的数据和存储器来的数据进行运算操作，数据传送寄存器RGR收发数据，实现数据在处理单元之间的传送。,一 矩阵加 矩阵加(配比加)是最简单的情况。假定两个8*8的矩阵 A、B相加，所得结果矩阵C也是一个8*8的矩阵 。设A、B 的分量元素分别存在PEM i的Z,Z+1单元中,所得结果矩阵C 各分量存在PEM i 的Z+2单元中 用下面三条指令可一次完成(64个处理单元并行) LDA Z；全部（Z）由PEMi送到PE的累加器R

6、GAi ADRN Z+1；全部（Z+1）与（RGAi）进行浮点加，结果 送RGAi STA Z+2；全部（RGAi）由PE送到PEMi的（Z+2）单元,这里0 i 63,6.1.3 ILLIAC 的并行算法举例,矩阵加存储器分举例,A(0,0),B(0,0),C(0,0),PEM0,a a+1 a+2,A(0,1),B(0,1),C(0,1),PEM1,A(7,7),B(7,7),C(7,7),PEM63,处理速度为顺序处理的64倍,二 矩阵乘,a0,0 a0,1 a0,7 a1,0 a1,1 a1,7 a7,0 a7,1 a7,7,b0,0 b0,1 b0,7 b1,0 b1,1 b1,7

7、b7,0 b7,1 b7,7,a0,0b0,0+a0,1b1,0+a0,7b7,0 a0,0b0,7+a0,1b1,7+a0,7b7,7 a1,0b0,0+a1,1b1,0+a1,7b7,0 a1,0b0,7+a1,1b1,7+a1,7b7,7 a7,0b0,0+a7,1b1,0+a7,7b7,0 a7,0b0,7+a7,1b1,7+a7,7b7,7,=,如果顺序执行C=AB，那么，计算每个元素cij需要做8次乘法，7次加法，共需做15次乘/加运算。 在ILLIAC IV的处理机上，操作数B的64个元素存储在64个PEM中。当每次计算元素cij时，就把操作数A的8个元素aik(0=k=7)播送

8、到相应的8个PE中，然后并行地一次完成8个中间积的运算。最后对8个中间积做7次加法，累加得到cij 。,矩阵乘存储器分配举例 （设用八个处理单元即PU并行）,.,八个局部存储器PEM i,每个连续存放A,B和结果向量C的一列元素,三、累加和 （成对递归）,这是一个将N个数的顺序相加过程转变为并行相加过程的问题。 设N为8，即有8个数A（I）顺序累加，其中0I 7。 在SISD计算机上可写成下列程序： C=0 DO 10 I=0，7 10 C=C+A（I）,用成对递归算法，只需 Log2 8=3 在SIMD计算机上可写成下列程序 C=A DO 10 K=0, Log2 8 - 1 10 C=C+

9、SHFTR(C,2*K),其中SHFTR(C,2*K)是向量传送语句,C向量各分量向右传送步距为2的K次幂,用成对递归算法求累加和的步骤： 1.置全部PEi为活跃状态， 0i 7。 2.全部A（i）从PEMi的a单元读到相应PEi的累加寄存器RGAi中， 0i 7； 3.令k=0； 4.将全部PEi的（RGAi）传送到寄存器RGRi，0i 7； 5.将全部PEi的（RGRi）经过互连网络向右传送2k步距， 0i 7； 6.令j= 2k-1； 7.置PE0至 PEj为不活跃状态； 8.处于活跃状态的所有PEj执行（RGAi）:= (RGAi)+（RGRi） ， ji 7； 9.k:=k+1; 1

10、0.如k3,则转回4,否则往下继续执行; 11.置全部PEi为活跃状态， 0i 7,存结果至a + 1单元。,设原始数据A（I）分别存在8个PEM的某a单元中,设原始数据A（I）分别存在PEM的某个单元中,步距1 步距2 步距4,K=0 K=1 K=2 PE0 A0 A0 A0 A0 PE1 A1 A0+A1 A0+A1 A0+A1 PE2 A2 A1+A2 A0+A1+A2 A0+A1+A2 PE3 A3 A2+A3 A0+A1+A2+A3 A0+A1+A2+A3 PE4 A4 A3+A4 A1+A2+A3+A4 A0+A1+A2+A3+A4 PE5 A5 A4+A5 A2+A3+A4+A5

11、 A0+A1+A2+A3+A4+A5 PE6 A6 A5+A6 A3+A4+A5+A6 A0+A1+A2+A3+A4+A5+A6 PE7 A7 A6+A7 A4+A5+A6+A7 A0+A1+A2+A3+A4+A5+A6+A7,二、递归折叠求和,用递归折叠方法来求累加和过程如下图所示。,上述求累加和算法虽然使计算次数减少，但是速度的提高的倍 数只是N/ Log2 N，速度并没有提高多少。,长度为N的递归计算 时间正比于Log2 N,例：A和B都是元素为浮点表示的6464的二维数组，一次浮点加法的计算过程由取数、求阶差、对阶、尾数加、规格化和存数共6个段组成。若每个段的执行时间均为t，请分别求出

12、在下列结构不同的处理机上完成C=A+B所需时间及相对于顺序处理的加速比。 (1)顺序处理方式的处理机 (2)具有浮点加法流水线的流水处理机，且浮点加法流水线分为6个段，各段执行时间均为t。 (3)88的阵列处理机，且处理阵列上的每个处理器只能顺序处理浮点加运算。 (4)88的阵列处理机，且处理阵列上的每个处理器均能流水处理浮点加运算。 (4)6464的阵列处理机。,a0,0 a0,1 a0,63 a1,0 a1,1 a1,63 a63,0 a63,1 a63,63,b0,0 b0,1 b0,63 b1,0 b1,1 b1,63 b63,0 b63,1 b63,63,+,a0,0 + b0,0

13、a0,1 + b0,1 a0,63 + b0,63 a1,0 + b1,0 a1,1 + b1,1 a1,63 + b1,63 a63,0+b63,0 a63,1+b63,1 a63,63+b63,63,=,解： (1)顺序处理方式下，需要顺序执行的浮点加法次数为6464=4096，每次浮点加运算所需时间为6t ，则全部运算所需时间为： T1=40966t=24576t (2)需要流水执行的浮点加法次数为6464=4096，则一个K=6段浮点加法流水线处理全部运算所需时间为： T2=(k+n-1)t=(6+4096-1)t=4101t 加速比： S2=T1/T2=5.9,(3)对于88的处理阵

14、列，每个处理器需要处理6464二维数组中的一个88子数组，因此，每个处理器需要执行的浮点加法次数为88。每次浮点加法运算需要时间6t 。每个处理器顺序执行64次浮点加法所需时间为646t=384t。64个处理器并行处理，同时完成各自的64次浮点加运算，所以，全部运算所需时间为： T3=384t 加速比： S2=T1/T3=64 (4)对于88的处理阵列，每个处理器需要处理6464二维数组中的一个88子数组，因此，每个处理器需要执行的浮点加法次数为88。K=6段的浮点加法流水线处理64次浮点加运算需要时间(k+n-1)t=(6+64-1)t=67t 。64个处理器并行处理，同时完成各自的64次浮

15、点加运算，所以，全部运算所需时间为： T4=67t 加速比： S2=T1/T4=366.8,(5) 对于6464的处理阵列，每个处理器只需执行一次浮点加运算，所需时间为6t ，所以，全部运算所需时间为： T5=6t 加速比： S2=T1/T5=4096,6.2 SIMD计算机的互连网络,6.2.1 互连网络的设计目标及互连函数,1.互联网络的设计目标,a.采取让相邻的处理单元之间只用有限的几种直连方式实现任何两个处理单元之间所需要的信息传送。,b.设计目标：结构不要太复杂；灵活性高；信息交换所需传送步数尽可能少；能用规整单一的基本构件组合而成，模块性好；,2.互连函数,互连网络的连接特征一般用

16、一组互连函数表示。 互连函数：出端编码是入端编码的排列、组合、移位、取反等操作的结果。表示所有入端与出端的连接关系。,互连函数有2种表示方法：(1)输入输出对应表示法 互连 0 1 N-1函数 f(0) f(1) f(N-1) (2)函数式表示法： 入端编码表示： x = bn-1b0 n=log2N 出端编码表示：f(x) = 基于bn-1b0的操作的结果。 自变量和函数可以用二进制表示，也可以用十进制等表示,输入: 0 1 2 3 4 5 6 7输出: 1 0 3 2 5 4 7 6,6.2.2 互联网络的应选择的几个问题 （1）操作方式：有同步、异步、同异组合三种； （2）控制策略：集中

17、和分布两种； （3）交换方法：有线路交换、包交换及线路与包交换组合三种。 （4）网络拓扑：互联网络入、出端可以实现连接的模式。有静 态和动态两种；动态网络又有单级循环网络和多级互连网络两 类；,6.2.3 基本的单级互连网络,立方体、PM2I和混洗交换和蝶形单级网络。,三维立方体结构,处理单元,Z Y X三位二进制码编号,每个处理单元只能直接连到其二进制编号的某一位取反的其 他 3 个处理单元上。,1. 立方体单级网络(交换互连网络),互连函数：,Cube0 (b2b1b0)=(b2b1b0)；Cube1(b2b1b0)=(b2b1b0) Cube2(b2b1b0)=(b2b1b0)。,互连特

18、性：,交换功能-互连函数可逆；,互连函数个数=log28=3；,最大连接度=log28=3；,结点最大间距=log28=3。,互连函数：,Cubei函数表示相连的入端和出端的二进制编号只在 右起第i位(i=0, 1, 2)上有差别，即仅在该位上的代码 “0”、“1”互反，其余各位代码都相同。,立方体单级网络连接图,Cube0=(b2b1b0) （0，1）（2，3）（4，5）（6，7）,Cube1=(b2b1b0) （0，2）（1，3）（4，6）（5，7）,Cube2=(b2b1b0) （0，4）（1，5）（2，6）（3，7）,其连接方式如下图中的实线所示。,注意：立方体坐标编号不能标错。,推广

19、到n维的情形，N个节点的立方体单级网络共有n=log2N种互连函数， 即,式中，0in-1，bi为入端号二进制码的第i位。当维数n3时，称为超立方体(Hyper Cube)网络。它的最大距离为n，任意两个结点间有至少n条路径，容错性较强。, PM2I单级网络是“加减2i” 单级网络的简称。能实现与j号处理单元直接相连的是号为j2i的处理单元， 即,2. PM2I单级网络,对于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

20、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),式中，0jN-1, 0in-1, n=log2N。因此，它共有2n个互连函数。由于总存在PM2+(n-1)=PM2-(n-1)，所以实际上，PM2I互连网络只有2n-1种不同的互连函数。,PM2I互连网络的部分连接图,PM2I单级网络的最大距离为n/2(向上取整)。以上面的三维PM2I互连网络的例子就可以看出，最多只要二次使用，即可实现任意一对入、 出端号之间的连接。,应用：几种PM2I变换的组合，可实现某结点到任意结点

21、的连接，组合不同效率不同。,例：闭合螺旋结构为PM2I0(横向)及PM2In/2(纵向)互连函数。,3. 混洗交换互连网络,8 个处理单元的全混连接,这种互连网络由全混洗和交换两种互连函数组成： 全混Shuffle(bn-1bn-2.b1b0)=(bn-2.b1b0bn-1) 相当于将处理单元的二进制地址位中的最左位移到最右位的循环移位。下图示出了有8个PE的全混洗连接。,由于全混洗互连网络不能实现全0和全1单元与其他单元 的连接，因此引入交换网络中的Cube0交换互连函数，表达形 式如下： Exchange(bn-1bn-2.b1b0)=bn-1bn-2.b1b0 两函数复合后为： Exch

22、angeShuffle(bn-1bn-2.b1b0)=(bn-2.b1b0 bn-1) 下图示出了这种混洗交换互连网络的连接图。（实线表示交换 ，虚线表示全混）,N=8 时全混交换互连网络连接图,在混洗交换网络中，最大距离为2n-1。最远的两个PE（全0和全1 ）连接需要n次交换和n-1次混洗。,4、蝶式置换 -编码最高位和最低位位交换位置 互连函数：(bn-1bn-2b1b0)=(b0bn-2b1bn-1)；,000 001 010 011 100 101 110 111,N=8蝶式置换,000 001 010 011 100 101 110 111,N=8 (1)子蝶式置换,子蝶式置换：

23、(k)(bn-1bk+1bkbk-1b0)=(bn-1bk+1b0bk-1b1bk) (k)(bn-1bn-kbn-k-1bn-k-2b0)=(bn-k-1bn-2bn-kbn-1bn-k-2b0),5、移数置换 -编码值移位 互连函数：(X)=(X+k) mod N，0kN-1；,互连特性：互连函数不可逆(k=0除外)； n位编码有2n个移数变换功能。,例：编号为0、1、15的16个处理器用单级互连网络互连 ，当互连函数分别为: （1）Cube3 （2）PM2+3 （3） PM2+2（ Cube1 ） （4）Shuffle(Cube2 (PM2-3) 时，第13号处理器各连至哪一 个处理器？

24、,解：编号为0、1、.15的16个处理器，所以可用4位二进制码 b3 b2b1 b0 表示。第13号处理器的二进制编号为1101。所以 （1） Cube3（1101）=0101，即连接到5号处理器上。 （2）PM2+3 （13+23）mod 16=5，即连接到5号处理器上。 （3） PM2+2( Cube1 (1101) =3 ，即连接到3号处理器上。 （4）Shuffle (Cube2 (PM2-3(13) = Shuffle(Cube2 (0101) = Shuffle（0001）=0010，即连接到2号处理器上。,6.2.4 基本的多级互连网络,交换开关 交换开关是组成互连网络的基本构件

25、。通常，它是二功能 或四功能的。二功能是直连或交换。四功能就是在二功能基础 上在加上上播和下播，开关状态连接方式如下图所示；,决定多级互连网络的特性的主要因素有以下三个方面：交 换开关、拓扑结构和控制方式。,a. 直连i入连i出， j入连j出；,b. 交换i入连j出， j入连i出；,c.上播i入连i出和j出， j入悬空；,d.下播j入连i出和j出， i入悬空。,拓扑结构是指各级之间出端和入端相互连接的模式。 可将单级互连网络的那些连接模式进行不同的组合，构成多 种不同的多级互连网络。,控制方式是对各个交换开关进行控制的方式，以多级立方体网络为例，它可以有 3 种： (1) 级控制同一级的所有开

26、关只用一个控制信号控制， 同时只能处于同一种状态； (2) 单元控制每一个开关都有自己独立的控制信号控制， 可各自处于不同的状态； (3) 部分级控制对不同的级采用不同数量的控制信号。第i级的所有开关分别用i+1个信号控制， 0in-1, n为级数。是前面两种方式的折衷。,控制方式,1. 多级立方体网络（ STARAN和间接二进制n方体网络 ） 以8个处理单元为例，其结构如下图所示。 共同特点：第i级交换单元处于交换状态时，实现的是Cubei互连函数，且都采用二功能交换单元。 区别：控制方式不同， STARAN网络采用级控制和部分级控制，间接二进制n方体网络采用单元控制。,常用的多级互连网络有

27、：多级立方体网络、多级混洗交换网络又称omega网络和多级PM2I网络。,N=8 多级立方体互连网络,Cube0,Cube1,Cube2,具有N个入端和N个出端的多级立方体网络拓扑结构图 的画法为： 先求出该多级立方体网络的级数n，每级画N/2个二功能 交换开关；级编号从输入到输出依次是：0,1,in-1;让所有 第i级各交换开关的两个出入端均按Cubei的关系配对编上号； 再将各级开关同一编号的端用线连上。 STARAN网络用作交换网络时，采用级控制，实现的是交换 函数。所谓交换(Flip)函数，是将一组元素首尾对称地进行 交换。如果一组元素包含有2s个，则它是将所有第k个元素都 与第(2s

28、-(k+1)个元素相交换。如下表1列出级控信号采用各 种不同组合情况下3级交换网络所实现的入、出端的连接。,K0控制Cube0,K1控制Cube1,K2控制Cube2,Ki=0,直连 Ki=1,交换,表 1 三级 STAR AN交换网络实现的入出端连接及所执行的交换函数功能(Ki为第I级控制 信号),(1)交换功能的控制与实现 开关组合控制方式：级控制。,(2)移位功能的控制与实现 开关组合控制方式：部分级控制(第i级有i+1种控制信号),Mod的作用：不同Mod可用于不同的分组操作。,(3)网络功能的应用 交换功能很适合于双向互连(对称)要求的实现； 移数功能很适合于累加求和等要求的实现。,

29、例1：阵列有07共8个处理单元，要求按（0，5）、（1，4）、（2，7）、（3，6）配对通信。 (1)写出实现此功能的互连函数一般式。 （2）画出用三级立方体网络实现互联函数的网络拓扑结构图，标出各级交换开关状态。,交换,直连,交换,例2：16个PE采用STARAN网络互连时，实现相当于4组4元交 换，然后2组8元交换，再1组16元交换功能。写出互连函数一般 式,画出相应多级网络拓扑结构图，标出各级交换开关状态。,答：因需实现交换功能，故选择STARAN的交换功能(级控制方式）。,相加 Cube0+Cube1 +Cube3,各级开关状态：k3k2k1k0=(1011) 由此得出第0、1、3级开

30、关状态为交换，第2级为直连,交换,交换,交换,直连,共有16个结点，编码需要4位，开关共4级。,例3：现有16个PE(编号0F)与网络连接，程序在某个时刻需实现下列通信配对：7D、6C、5F、4E、39、28、1B、0A。请画出互连网络结构图，并写出控制方式及各开关状态。,答：因需实现双向交换功能，选择STARAN网络的交换功能(级控制方式)可满足要求。,网络拓扑结构： 共有16个结点，编码需要4位，开关共4级。,配对要求：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A) 开关控制： 7的结点7的结点，需1组16元交换； 注意：组内交换后结点次序已

31、经镜像,03的结点8B的结点，需2组8元交换；,01的结点AB的结点，需4组4元交换；,0结点A结点配对，已经过3次镜像 需8组2元交换。,各级开关状态：k3k2k1k0=(1010),由此得出第1、3级开关状态为交换，第0、2级为直通,交换开关：四功能； 拓扑结构：多级Shuffle； Omega网络中各级编号的次序与多级立方体网络正好相反，把 Omega网络的入、出端对调，就等于多级立方体网络。,2.多级混洗交换网络( omega网络),开关组合控制： 级控制、开关二功能-STARAN交换网络的逆网络； 部分级控制、开关二功能STARAN移数网络的逆网络; 单元控制、开关二、四功能-更强大

32、的功能。,网络关系：按全混方法 Shuffle（pn-1 pn-2 p0）= pn-2 p0 pn-1 则有： 入 0 0 出 入 41 出 1 2 53 2 4 65 3 6 77,混洗拓扑就是将编号为0，1.N-1的入端分成前后个数相等的两半，前一半和后一半在连至输出时顺次一一相隔。各级画好后，再将连线沿途所经过的端号均标成同一端号即可。,例：画出07号共8个处理器的三级混洗交换网络，在该图 上标出实现将6号处理器数据播送给04号，同时将3号处理 器数据播送给其余3个处理器时的各有关交换开关的控制状态；,3. 多级PM2I网络（数据交换网络）,N=8三级PM2I网络,2,j,j+2i mo

33、d N,j-2i mod N,结构：n级，每一级把前后各N=2n个单元按PM2I拓扑互连接。 对第i级，每一个单元j（0 j N-1）都有3根连线分别连到出端单元j、 j+2i mod N和j-2i mod N，图中分别用不同的线段表示。 控制这三类连接线的信号分别为平控H、上控D、下控U。若采用单元控制方式，每一级都有自己独立的控制信号H、D、U，称此PM2I网络为强化数据交换网络（ADM）。,6.2.5 全排列网络,(1)多级网络比较,灵活性(低高)：STARAN、间接二进制n方体、 Omega()、ADM(混洗四功能) 成本(低高)：同上,用途： STARAN、Omega PEPM 间接

34、二进制n方体 PE-PE,功能：同时只能实现部分互连函数功能。,(2)全排列网络 定义：所有入端、出端的连接均不发生冲突的网络，又称非阻塞型网络，即：N入N出有N！种排列。,常规多级网络(如STARAN、等)属于阻塞型网络。,证明：对n=log2N级网络，开关数=N/2n。,排列数,回下页,(3)全排列网络实现,方法：a.原有多级网络通过锁存器运行两次即可；,思想：N!NN/2NN/2NN。,b.两个log2N网络背靠背串联。,Benes网络,6.3 并行存储器无冲突访问,一、访问需求 并行存取向量中各分量信息； 对矩阵可按行、列、对角线等方法访问(步长不一致)。,二、存在问题,存储器带宽限制存储器带宽达不到向量带宽；,访存方式(步长)不同，产生访存冲突。,三、解决方法,1、采用多体交叉存储器