1、第6章 向量处理机 6.1 向量的流水处理和向量流水处理机向量的流水处理和向量流水处理机6.2 阵列处理机的原理阵列处理机的原理 6.3 SIMD计算机的互连网络计算机的互连网络6.4 共享主存构形的阵列处理机中并行存储器的无冲突访问共享主存构形的阵列处理机中并行存储器的无冲突访问6.5 脉动阵列流水处理机脉动阵列流水处理机 6.6 本章小结本章小结第6章 向量处理机 6.1 向量的流水处理和向量流水处理机向量的流水处理和向量流水处理机 6.1.1 向量的处理和向量的流水处理向量的处理和向量的流水处理虽然向量运算比标量运算更易发挥出流水线的效能，但处理方式选择不当也不行。 第6章 向量处理机
2、【例【例 6-1】 计算D=A(B+C)，其中A、B、C、D都是有N个元素的向量，应该采用什么方式处理才能充分发挥流水线的效能如果采用逐个求D向量元素的方法，即访存取ai、bi、ci元素求di，再取ai+1、bi+1、ci+1求di+1， 则这种处理方式称为横向(水平)处理方式。 第6章 向量处理机 6.1.2 向量流水处理机的结构举例向量流水处理机的结构举例向量流水处理机的结构因具体机器的不同而不同。 图6 - 1只画出了CRAY-1中央处理机中有关向量流水处理部分的简图。 第6章 向量处理机 图 6-1 CRAY-1的向量流水处理部分简图第6章 向量处理机 CRAY-1有标量类和向量类指令
3、共128条，其中有4种向量指令如图6 - 2所示。 第种源向量分别取自两个向量寄存器组Vj、Vk，结果送向量寄存器组Vi。第种与第 种的差别只在于它的一个操作数取自标量寄存器Sj。 第6章 向量处理机 图 6-2 CRAY-1的四种向量指令第6章 向量处理机 6.1.3 通过并行、链接提高性能通过并行、链接提高性能一般可采取让多个流水线功能部件并行、流水线链接、加快条件语句和稀疏矩阵处理、加快向量的归约操作等办法来提高向量流水处理的性能。 第6章 向量处理机 以CRAY-1的向量流水为例，向量寄存器组Vi在同一时钟周期内可接收一个结果分量并为下次操作再提供一个源分量。每个Vi组都有单独的总线连
4、到各功能部件上，而每个功能部件也都有把运算结果送回向量寄存器组的输出总线。所谓Vi冲突，指的是并行工作的各向量指令的源向量或结果向量使用了相同的Vi。所谓功能部件冲突，指的是同一个功能部件被要求并行工作的多条向量指令所使用。 第6章 向量处理机 第一、二条指令无任何冲突，可以并行执行。第三条指令与第一、二条指令出现Vi冲突，存在先写后读数相关，本来是不能并行执行的，但若能把第一、二条指令的结果分量直接链接进第三条指令所用的功能部件，那第三条指令就能与第一、二条指令在大部分时间内并行。它们的链接过程如图6 - 3所示。 第6章 向量处理机 图 6-3 通过链接技术实现向量指令之间大部分时间并行
5、第6章 向量处理机 6.1.4 提高向量流水处理速度的其他办法提高向量流水处理速度的其他办法1. 条件语言和稀疏矩阵的加速处理条件语言和稀疏矩阵的加速处理当程序中出现条件语句或进行稀疏向量、矩阵运算时，难以发挥出向量处理的优点。2. 向量递归操作的加速处理向量递归操作的加速处理CRAY-1的向量指令还可以通过让源向量和结果向量使用同一个向量寄存器组，并控制分量计数器值的修改，来实现递归操作。 第6章 向量处理机 图6 - 4画出了其部分时间关系示意图。设源/结果向量寄存器组用V0，另一源向量寄存器组用V1。在指令开始执行前，先把V0的零分量(V00)置“0”。V1置入需要运算的全部浮点数分量。
6、向量长度寄存器VL的内容假定置为64。 第6章 向量处理机 图 6-4 递归向量和的部分时间关系第6章 向量处理机 运算结束后，V0中各个分量的内容如下： )1V(0)1V()0V()0V()1V(0)1V()0V()0V()1V(0)1V()0V()0V()1V(0)1V()0V()0V()1V(0)1V()0V()0V()1V(0)1V()0V()0V()1V(0)1V()0V()0V()1V(0)1V()0V()0V(77076606550544043303220211010000第6章 向量处理机 第二部分)1V()1V()1V()0V()0V( )1V()1V()1V()0V()0V
7、()1V()1V()1V()0V()0V()1V()1V()1V()0V()0V()1V()1V()1V()0V()0V(1571571511311311102102109191980808第6章 向量处理机 第三至第七部分)1V()1V()1V( )1V()1V()1V()1V( )1V()0V()0V( )1V()1V()1V()1V()0V()0V(5547393123157554755168016816第6章 向量处理机 (V056)=(V048)+(V156) =(V10)+(V18)+(V116)+(V124)+(V132) +(V140)+(V148)+(V156)(V057)=
8、(V049)+(V157) =(V11)+(V19)+(V117)+(V125)+(V133) +(V141)+(V149)+(V157) 第八部分(结果部分)第6章 向量处理机 (V058)=(V050)+(V158) =(V12)+(V110)+(V118)+(V126)+(V134) +(V142)+(V150)+(V158)(V059)=(V051)+(V159) =(V13)+(V111)+(V119)+(V127)+(V135) +(V143)+(V151)+(V159)第八部分(结果部分)第6章 向量处理机 (V060)=(V052)+(V160) =(V14)+(V112)+(
9、V120)+(V128)+(V136) +(V144)+(V152)+(V160)(V061)=(V053)+(V161) =(V15)+(V113)+(V121)+(V129)+(V137) +(V145)+(V153)+(V161)第八部分(结果部分)第6章 向量处理机 (V062)=(V054)+(V162) =(V16)+(V114)+(V122)+(V130)+(V138) +(V146)+(V154)+(V162)(V063)=(V055)+(V163) =(V17)+(V115)+(V123)+(V131)+(V139) +(V147)+(V155)+(V163)第八部分(结果部
10、分)第6章 向量处理机 6.2.1 阵列处理机的构形和特点阵列处理机的构形和特点1. 阵列处理机的构形阵列处理机的构形 阵列处理机有两种构形，两者的差别主要在于存储器的组成方式和互连网络的作用不同。构形构形1 图6 - 5是具有分布式存储器的阵列处理机的构形。 构形构形2 图6 - 6是具有集中式共享存储器的阵列处理机构形。 6.2 阵列处理机的原理阵列处理机的原理 第6章 向量处理机 图 6-5 具有分布式存储器的阵列处理机构形第6章 向量处理机 图 6-6 具有集中式共享存储器的阵列处理机构形第6章 向量处理机 2. 阵列处理机的特点阵列处理机的特点 阵列处理机的单指令流多数据流处理方式和
11、由它产生的特殊结构是以诸如有限差分、矩阵、信号处理、线性规划等一系列计算问题为背景发展起来的。 第6章 向量处理机 6.2.2 ILLIAC 的处理单元阵列结构的处理单元阵列结构由于阵列处理机上的并行算法的研究是与结构紧密联系在一起的，因此，下面先介绍ILLIAC 阵列机上处理单元的互连结构。ILLIAC 采用如图6 - 5所示的分布存储器构形，其处理单元阵列结构如图6 - 7所示。 第6章 向量处理机 图 6-7 ILLIAC 处理单元的互连结构第6章 向量处理机 6.2.3 ILLIAC 的并行算法举例的并行算法举例1. 矩阵加矩阵加阵列处理机解决矩阵加是最简单的一维情况。两个88的矩阵A
12、、B相加，所得的结果矩阵C也是一个88的矩阵。只需把A、B、C居于相应位置的分量存放在同一个PEM内，且在全部64个PEM中，让A、B和C的各分量地址均对应取相同的地址、+1和+2即可，如图6 - 8所示。 第6章 向量处理机 图 6-8 矩阵相加的存储器分配举例第6章 向量处理机 2. 矩阵乘矩阵乘矩阵乘是二维数组运算，比矩阵加要复杂。设A、B和C为3个88的二维矩阵，给定A和B，计算C=AB的64个分量的公式为其中，0i7且0j7。kjikkijbac71第6章 向量处理机 让J=07各部分同时在PE0PE7上运算，这样只需K、I二重循环，速度可提高为原来的8倍，即只需64次乘、加时间。其
13、程序流程图如图6 - 9所示。 第6章 向量处理机 图 6-9 矩阵乘程序执行流程图第6章 向量处理机 然而为了让各个处理单元PEi尽可能只访问所带局部存储器PEMi，以保证高速处理，就必须要求对矩阵A、B、C各分量在局部存储器中的分布采用如图6 - 10所示的方案。 第6章 向量处理机 图 6-10 矩阵乘的存储器分配举例第6章 向量处理机 3. 累加和累加和这是一个将N个数的顺序相加转为并行相加的问题。为得到各项累加的部分和与最后的总和，要用到处理单元中的活跃标志位。只有处于活跃状态的处理单元才能执行相应的操作。为叙述方便起见，取N=8，即有8个数A(I)顺序累加，其中0I7。 第6章 向
14、量处理机 图6 - 11描绘了阵列处理机上累加和的计算过程。最后一列框中的数字表明各处理单元每次循环后相加的结果。图中用数字07分别代表A(0)A(7)。画有阴影线的处理单元表示此时不活跃。第6章 向量处理机 图 6-11 阵列处理机上累加和的计算过程第6章 向量处理机 6.3.1 互连网络的设计目标与互连函数互连网络的设计目标与互连函数在SIMD计算机中，无论是处理单元之间，还是处理单元与存储分体之间，都要通过互连网络进行信息交换。 6.3 SIMD计算机的互连网络计算机的互连网络 第6章 向量处理机 6.3.2 互连网络应抉择的几个问题互连网络应抉择的几个问题在确定PE之间通信的互连网络时
15、，需要对操作方式、控制策略、交换方法和网络的拓扑结构作出抉择。循环互连网络的模型如图6 - 12所示。 第6章 向量处理机 图 6-12 循环互连网络的模型第6章 向量处理机 6.3.3 基本的单级互连网络基本的单级互连网络 1. 立方体单级网络立方体单级网络立方体单级网络(Cube)的名称来源于图6 - 13所示的三维立方体结构。 第6章 向量处理机 图 6-13 三维立方体结构第6章 向量处理机 如010只能连到000、011、110，不能直接连到对角线上的001、100、101、111。所以，三维的立方体单级网络有3种互连函数： Cube0、Cube1和Cube2，其连接方式如图6 -
16、14中的实线所示。Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0，1，2)上0、1互反，其余各位代码都相同。 第6章 向量处理机 图 6-14 立方体单级网络连接示意(a) Cube0; (b) Cube1; (c) Cube2 第6章 向量处理机 2. PM2I单级网络单级网络PM2I单级网络是“加减2i”(PlusMinus 2i)单级网络的简称。能实现与j号处理单元直接相连的是j2i号处理单元，即mod2)(2PMmod2)(2PMiiiijjNjj第6章 向量处理机 其中，(0 1 2 3 4 5 6 7)表示0连到1，与此同时，1连到2，2连到3，7连到0。图6
17、 - 15 只画出了其中3种互连函数的情况。PM2-0和PM2-1的连接与PM2+0和PM2+1的差别只是连接的箭头方向相反而已。可见在PM2I中，0可以直接连到1，2，4，6，7上，比立方体单级网络只能直接连到1，2，4的要灵活。 第6章 向量处理机 图 6-15 PM2I互连网络的部分连接图第6章 向量处理机 3. 混洗交换单级网络混洗交换单级网络混洗交换单级网络(ShuffleExchange)包含两个互连函数，一个是全混(Perfect Shuffle)，另一个是交换(Exchange)。图6 - 16表示8个处理单元间的全混连接。可以看出，其连接规律是把全部按编码顺序排列的处理单元从
18、当中分为数目相等的两半，前一半和后一半在连接至出端时正好一一隔开。全混互连函数表示为 Shuffle(Pn-1Pn-2P1P0)=Pn-2P1P0Pn-1 第6章 向量处理机 图 6-16 8个处理单元的全混连接 第6章 向量处理机 由于单纯的全混互连网络不能实现二进制编号为全“0”和全“1”的处理单元与其他处理单元的连接，因此还需增加Cube0交换函数。这就是全混交换单级网络，其N=8的连接如图6 - 17所示。其中，实线表示交换，虚线表示全混。 第6章 向量处理机 图 6-17 N=8时全混交换互连网络连接图第6章 向量处理机 4. 蝶形单级网络蝶形单级网络 蝶形单级网络(Butterfl
19、y)的互连函数为 Butterfly(Pn-1Pn-2P1P0)=P0Pn-2P1Pn-1即将二进制地址的最高位和最低位相互交换位置。 图6 - 18为N=8个处理单元之间用蝶形单级互连网络互连的情况。 第6章 向量处理机 图 6-18 8个处理单元的蝶形单级互连第6章 向量处理机 6.3.4 基本的多级互连网络基本的多级互连网络最基本的多级互连网络就是与上述前3种单级互连网络相对应组成的多级立方体互连网络、多级混洗交换网络和多级PM2I网络。 第6章 向量处理机 1. 多级立方体互连网络多级立方体互连网络 多级立方体互连网络有STARAN网络、间接二进制n方体网络等。以8个处理单元为例，其普
20、遍结构如图6 - 19所示。 表6 - 1列出了三级交换网络在级控制信号采用各种不同组合情况下所实现的入、出端的连接。 第6章 向量处理机 图 6-19 N=8的多级立方体互连网络第6章 向量处理机 表表 6 - 1 三级三级STARAN交换网络实现的入、出端连接及交换网络实现的入、出端连接及 所执行的交换函数功能所执行的交换函数功能(ki为第为第i级控制信号级控制信号) 第6章 向量处理机 从表 6 - 1 水平方向不难看出，任何输入端只要通过不同的级控制信号，总可以接到任何所需要的输出端上。当STARAN网络用作移数网络时，采用部分级控制，控制信号分组和控制结果列在表 6 - 2 中。可以
21、看出它们都是执行各种不同的移数功能的。第6章 向量处理机 表表 6 - 2 三级移数网络能实现的入、出端连接及移数函数功能三级移数网络能实现的入、出端连接及移数函数功能 第6章 向量处理机 【例【例 6-2】 Intel iPSC系统用超立方体将8128个结点进行互连，每个结点有一台80286微处理器、一台80287浮点协处理器、512 KB4.5 MB内存和7片Ethenet收发器接口芯片(因为每个结点要接7个链路，每个链路用1片)。 第6章 向量处理机 2. 多级混洗交换网络多级混洗交换网络多级混洗交换网络又称omega网络，如图6 - 20所示。3. 多级多级PM2I网络网络N=8的多级
22、PM2I网络的结构如图6 - 21所示。 第6章 向量处理机 图 6-20 N=8的多级混洗交换网络第6章 向量处理机 图 6-21 N=8的多级PM2I网络第6章 向量处理机 4. 基准网络基准网络图6 - 22所示是N=8的基准网络。5. 多级交叉开关网络多级交叉开关网络多级交叉开关(CLOS)网络是一种非阻塞式网络，图6 - 23给出了一个三级交叉开关网络的结构。 第6章 向量处理机 图 6-22 N=8的基准网络第6章 向量处理机 图 6-23 三级交叉开关网络的结构第6章 向量处理机 图6 - 24是一个N(3，2，2)的三级交叉开关网络。入、出端各有4个，如采用一级交叉开关实现，共
23、需44=16个交叉点，每个交叉点为四中选1。这种实现可能比三级交叉开关实现要便宜，尽管每个结点只需二中选1。 第6章 向量处理机 图 6-24 N(3,2,2)的多级交叉开关互连网络第6章 向量处理机 6. 多级蝶式网络多级蝶式网络图6 - 25是由16个88交叉开关作为基本构件组成的二级蝶式网络，级间采用8路混洗，构成了6464的蝶式互连再用其与64个88的交叉开关扩展构成512512的三级蝶式互连网络，如图6 - 26所示。第6章 向量处理机 图 6-25 用88交叉开关构造的二级6464的蝶式互连网络第6章 向量处理机 图 6-26 用88交叉开关作为基本构件扩充成512512的三级蝶式
24、互连网络第6章 向量处理机 6.3.5 全排列网络全排列网络如果互连网络是从N个入端到N个出端的一到一的映射，就可以把它看成是对此N个端的重新排列，因此互连网络的功能实际上就是用新排列来置换N个入端原有的排列。图6 - 27就是将三级基准网络和它的逆网络连在一起，省出中间重复的一级后构成的全排列网络，称此网络为Benes网络。 第6章 向量处理机 图 6-27 多级全排列网络举例(Benes网络)第6章 向量处理机 情况情况1 对一维数组为例，假定并行存储器分体数m为4，交叉存放一维数组a0，a1，a2，如图6 - 28所示。6.4 共享主存构形的阵列处理机中共享主存构形的阵列处理机中并行存储
25、器的无冲突访问并行存储器的无冲突访问 第6章 向量处理机 图 6-28 一维数组的存储(m=4)第6章 向量处理机 情况情况2 对于二维数组(结论也适用于多维数组)而言，假设主存有m个分体并行，从中访问有n个元素的数组子集。这n个元素的变址跳距对于二维数组的行、列、主对角线、次对角线都是不一样的，但要求都能实现无冲突访问。如果设m=n=4，一个44的二维数组直接按行存储的方案则如图6 - 29所示。 第6章 向量处理机 图 6-29 44数组的直接按行存储 (m=n=4)第6章 向量处理机 为了能使行或列的各元素都能并行访问，采取将数据在存储器中错位存放的方案，如图6 - 30所示。 第6章
26、向量处理机 图 6-30 44数组一种错位存放的方案(m=n=4，1=2=1) 第6章 向量处理机 假设nn的二维数组在并行存储器中同一列两个相邻元素地址错开的距离为1，同一行两个相邻元素地址错开的距离为2，当m取成22P+1(P为正整数)时，实现无冲突访问的充分条件是让1=2P，2=1。图6 - 31就是对44二维数组按上述规则存储的一种方案。其中，P=1，m=5，1=2，2=1。 第6章 向量处理机 图 6-31 44数组错位存放的例子(m=5，n=4，1=2，2=1) 第6章 向量处理机 【例【例 6-3】 图6 - 32表示了一个45二维数组(元素以列为主序排列)按上述规则将其存放在m
27、=7的存储器中的例子。 第6章 向量处理机 图 6-32 45二维数组在并行存储器中存放的例子(m=7，n=6)第6章 向量处理机 6.5.1 脉动阵列结构的原理脉动阵列结构的原理脉动阵列结构是由一组处理单元(PE)构成的阵列。 根据具体计算的问题不同，脉动阵列可以有一维线形、二维矩阵/六边形/二叉树形/三角形等阵列互连构形(如图6 - 33所示)，还可以有不少变形。 6.5 脉动阵列流水处理机脉动阵列流水处理机 第6章 向量处理机 图 6-33 脉动阵列结构的构形举例(a) 一维线形阵列； (b) 二维矩形阵列; (c) 二维六边形阵列； (d) 二叉树形阵列； (e) 三角形阵列 第6章
28、向量处理机 每个处理单元PE内含一个乘法器和一个加法器，可完成一个内积步运算。每经一拍，处理单元可把3个输入端送来的信息沿三个不同方向，即由左向右的水平方向、由下向上的垂直方向和由左下角到右上角的斜45方向，同时将结果传送到对应的3个输出端，使aa，bb，dab+c。现设矩阵A、B分别为 A=B=,333231232221131211aaaaaaaaa,333231232221131211bbbbbbbbb第6章 向量处理机 则 C=AB=其中，cij= aikbkj，1i3，1j3。图6 - 34给出了t1、t2、t3时刻送入阵列中的数据情况，到t6时，将从斜45向右上角同时输出c13、c1
29、2、c11、c21、c31的值，t7时输出c23、c22、c32的值，t8时输出c33的值。333231232221131211ccccccccc31k第6章 向量处理机 图 6-34 脉动式二维阵列流水举例第6章 向量处理机 6.5.2 通用脉动阵列结构通用脉动阵列结构造成脉动阵列机应用范围有限的关键因素是，受阵列结构的通用性及I/O带宽约束所限制的阵列结构的规模大小。 如把编号为偶数列的开关都置成上下连接，偶数行的开关都置成左右连接，就构成正方形或矩形的阵列结构，如图6 - 35(a)所示。 第6章 向量处理机 图 6-35 可编程脉动阵列结构(a) 控制开关按正方形阵列结构互连； (b)
30、 控制开关按二叉树形阵列结构互连第6章 向量处理机 6.6.1 知识点和能力层次要求知识点和能力层次要求(1) 识记向量有哪三种处理方式，哪些处理方式适合于流水处理。 (2) 领会阵列处理机的两种基本构形和工作原理。 (3) 以ILLIAC 阵列机为例，领会在分布式存储器构形的阵列处理机中，处理单元之间互连的结构模式、最大传送步数、典型的并行算法、数据在存储器中分布存放的规律以及处理单元产生的数据经互连网络传送的某些规律。 6.6 本本 章章 小小 结结 第6章 向量处理机 (4) 识记互连网络的设计目标和互连函数的几种表示形式。 (5) 在集中式存储器构形的阵列处理机中，能设计数据元素的存储方案，使向量数组元素在存储器中实现无冲突地被访问，要达到综合应用层次。(6) 了解脉动阵列结构的基本原理。 第6章 向量处理机 6.6.2 重点和难点重点和难点1. 重点重点 2. 难点难点
