向量流水与向量处理机.ppt

第5章 向量流水与向量处理机,内容提要:,本章首先简要介绍向量流水的基本概念与工作原理，然后讲述向量流水处理机的组成原理、向量操作长度控制与向量访问步长、向量处理方法、向量处理机多功能部件的并行操作以及向量处理性能的评估参数与评估方法。重点是向量流水机的组成原理、向量操作长度控制与向量访问步长、向量处理方法和向量处理机多功能部件的并行操作。难点是向量操作长度控制、向量处理方法、向量处理机多功能部件的并行操作过程。,第5章 向量流水与向量处理机,5.1 向量流水的概念与工作原理 5.2 向量处理与增强向量处理性能的方法 5.3 向量处理性能的评价参数与评价方法 5.4 向量化编译技术 5.5 向量处理机举例,5.1 向量流水的概念与工作原理,5.1.1 向量流水的概念与特点 5.1.2 向量处理机的基本组成 5.1.3 向量启动时间与结果流出时间 5.1.4 向量操作长度控制与向量访问步长,5.1.1 向量流水的概念与特点,1.向量流水的概念 向量中各元素之间有固定的位置或者联系，在运算时各元素相互独立或关系很少。向量运算时各元素一般进行相同的操作。这样，只要能从存储器中不断地取出这些元素，就能进行流水处理，发挥流水线的效能。 这样，把向量数据表示与流水线技术结合起来，就构成向量流水处理机，简称为向量流水机或向量处理机（Vector Processor）。,2.向量流水处理的主要特点 一条向量指令相当于一个标量循环。这样，可降低对指令访问速度（带宽）的要求，还可消除标量机中由于循环而引起的控制（资源）相关。 每一个结果元素仅与参加运算的元素有关，与上一次运算的值无关，因此向量流水线可以有较大的深度。 若要访问的向量元素相邻，可存储到多体交叉存储器中，以提高访存速度。 在一般向量流水机中，允许访问存储器与有效地址的计算流水化，在高档向量流水机中还允许多个向量操作同时进行，即多向量并行操作。,5.1.2 向量处理机的基本组成,1.向量处理机的类型 向量元素及其处理的结果元素可存放在存储器中，也可存放在寄存器堆中，故可分为两种类型：存储器-存储器型和寄存器-寄存器型。 早期的向量处理机多属于存储器-存储器型，比如TI公司的ASC机，CDC公司的STAR100以及CYBER-205和ETA-10等。,2.向量处理机的基本组成 1976年美国CRAY公司推出寄存器-寄存器结构的向量机，易操作，速度快，指令系统简洁，因而很快成为向量处理机的主流机型。比如CRAY公司的Y-MP和C-90，日本Fujitsu公司的VP2000、VPP300/500，以及我国的YH等。 向量机的基本结构如图5.1所示，由一个标量流水部件和一个向量流水部件组成。其中标量流水部件是为实现向量中的标量运算而设置的，包括标量功能部件和若干个标量寄存器。向量流水部件主要用于向量运算，包括向量功能部件、向量存取部件、向量寄存器以及向量控制器等。,图5.1 向量处理机基本系统结构,3.向量运算 【例5.1】设有长度同为64的两个向量X和Y，其地址分别由寄存器Rx和Ry表示，通过分析Y=aX+Y，来说明向量运算过程，其中a 为标量。 解：根据题意a为标量，每一个向量元素占8个字节单元，在标量计算机中通过循环程序实现向量运算，程序如下： LD F0，a， ；标量a送入寄存器F0 ADDI R4，Rx，#512 ；向量元素的末地址送入R4 LOOP：LD F2，0(Rx) ；取向量元素X(i) MULD F2，F0，F2 ；F2aX(i) LD F4，0(Ry) ；取向量元素Y(i) ADDD F4，F2，F4 ；F4aX(i)+ Y(i) SD 0(Ry)，F4 ；存结果元素 ADDI Rx，Rx，#8 ；修改向量X元素的下标 ADDI Ry，Ry，#8 ；修改向量Y元素的下标 SUB R10，R4，Rx ；R10(R4)-(Rx) BNZ R10，LOOP ；若没有结束转移到LOOP,在向量机上使用向量机指令编程如下，其中Rx和Ry表示向量寄存器： LD F0，a ；标量a送入寄存器F0 LV V1，Rx ；取向量X MULTV V2，F0，V1 ；V2aX LV V3，Ry ；取向量Y ADDV V4，V2，V3 ；V4aX+ Y SV Ry，V4 ；存结果 通过对上述程序进行分析可以看出，在标量机上进行运算共执行964+2=578条指令，其中还包含大量的延迟等待。而在向量机上进行运算，仅需要6条向量指令。,5.1.3 向量启动时间与结果流出时间,在向量流水过程中也存在启动时间Tst，相当于标量流水线中填入时间，以设置向量操作所涉及到的参数，比如设置向量长度等。启动后结果连续输出，每输出一个结果的时间称为结果流出时间，可用Ir表示。若设向量长度为n，则一条向量指令执行时间可表示如下： Tvp=Tst+nIr （5.1） 【例5.2】在一个向量乘法流水线中，向量启动时间为10个时钟周期，启动后1个时钟周期流出一个结果，若向量长度为64，试求产生每一个结果向量元素所用的平均时间。 解：根据题意，Tst=10，Ir=1，n=64，则产生每一个结果向量元素的平均时间Tav为：,可以看出，对于运算速度较慢的向量流水操作，启动时间影响不大；对于速度较快向量流水操作，启动时间会产生较大的影响。 对于寄存器-寄存器型向量处理机来说，向量启动时间主要取决于功能部件流水线的深度，结果流出时间取决于向量功能部件以多快的频率接收数据。当向量较长时，启动稳定后的结果流出时间可视为1。,5.1.4 向量操作长度控制与向量访问步长,1.向量操作长度控制 （1）向量寄存器长度 在寄存器-寄存器型向量处理机中向量由向量寄存器存储，向量寄存器的个数称为向量寄存器长度，可用N来表示。比如，CRAY-1的向量寄存器长度为64。 （2）向量长度与向量长度寄存器 在实际运算中向量长度n不一定正好等于向量寄存器的长度，可能小于也可能大于向量寄存器的长度。因此，需用向量长度寄存器存放向量长度。 （3）向量操作长度控制 这里仍以Y=aX+Y为例来说明。设向量长度为n，FORTRAN程序如下： DO 10 I=1，n 10 Y(I)= a*X(I)+Y(I) 其中向量长度依赖于n，往往是一个过程参数，为此需设置一个向量长度寄存器VL，向量寄存器的长度用MVL表示。,当向量长度小于向量寄存器的长度时，直接存入向量寄存器，其长度存入向量长度寄存器中。如果向量长度大于向量寄存器的长度时，须分段存储和运算。向量长度寄存器的值等于向量寄存器长度MVL。采用分段技术后，上述程序可修改成如下形式： LOW=1 VL=(n MOD MVL) ；取向量的零头 DO 20 J=0，(N/MVL) ；确定外循环次数 DO 10 I=LOW，LOW+VL-1 ；按长度VL操作 Y(I)= a*X(I)+Y(I) ；运算 10 CONTINUE LOW=LOW+VL ；指向下一次开始运算的向量 VL=MVL ；修改向量长度寄存器的值 20 CONTINUE 在上述分段运算中，第一次运算的长度为（n MOD MVL），以后各次的长度为MVL，循环次数为(N/MVL)+1。,2.向量访问步长与跨步访问 目前，存储器一般采用一维地址，若存储二维或者多维数组时，须将其元素映象到一维地址空间中。常以行或列为主来存储各个元素。对于以行为主的存储方式，当按行访问时各行元素地址相邻；按列访问时，各列中相邻元素不再相邻。这个间隔称为跨步，这时的访问称为跨步访问。 例如，设有100100的数组A和B，求C=AB。设计 FORTRAN循环程序如下： DO 10 I=1，100 DO 10 J=1，100 C(I，J)=0.0 DO 10 K=1，100 10 A(I，J)= C(I，J)+ A(I，K)*B(K，J),按照K循环读取存储器中的数据时，数组A的元素按行存储，按行读取，数据地址连续；数组B的元素按行存储，按列读取，地址不连续，跨步为100。 但是向量元素读出存入向量寄存器之后，逻辑上连续。如果向量处理机能支持对向量元素的跨步访问，称为支持完全一维数据显式访问。它能以行、列甚至对角线的方向访问数组元素。上述CRAY-1巨型机就属于这种类型。而CYBER-205采用存储器-存储器结构，不支持这种完全一维数据显式访问。 通常，向量处理机要有一个专用地址流部件，来进行这种跨步向量元素的访问，甚至支持子矩阵访问、上下三角形和平行四边形访问。 3. 多体交叉存储器的使用 为提高访存速率，大多数计算机采用低位地址交叉多体存储器。当向量机支持跨步访问时，可能出现对同一存储体访问的时间间隔小于存储器的访问周期，从而出现冲突。 设某处理机有16个存储体，访问时间为12个时钟周期，共有64个向量元素。跨步为1时，共需12+64=76个时钟周期；若跨步为16的整倍数，每个元素的读写时间为12个时钟周期，访问64个元素的时间为6412=768个时钟周期。为了访存不冲突，跨步应当与存储体数互质，比如存储体数为17，跨步为16。,5.2 向量处理与增强向量处理性能的方法,5.2.1 向量处理方法 5.2.2 增强向量处理性能的方法,5.2.1 向量处理方法,在向量机中各种运算可采用不同的加工方式，主要有三种，即横向加工、纵向加工和纵横向加工。设有长度为n的三个向量A、B和C，以求D=A(B+C)为例，说明向量处理的方法。 1.横向加工 横向加工是一种最普通的加工方式，它是按照向量的顺序计算，即 D1=A1(B1+C1) D2=A2(B2+C2) Dn=An(Bn+Cn) 这种方法是逐个计算D的n个分量。先计算K1(B1+C1)，然后计算D1A1K1。这样共出现n次数据相关和2n次功能部件的切换，不适合向量流水处理。,2.纵向加工 也称为垂直加工法，它是先进行所有纵向B+C的操作，中间结果暂存到中间向量K中，然后再进行所有纵向乘法操作AK，如图5.2所示。,用向量指令的形式表示，形式如下： K=B+C D=KA 采用这种方法，数据相关仅在向量指令间发生一次，流水线功能部件的切换也仅有一次。但是需要使用一个中间向量K。,图5.2 纵向加工方法,3.纵横向加工 当参加运算的向量长度n大于向量寄存器的长度N时，需要分段进行，这样就产生了纵横向加工方式。段内纵向加工，段间横向加工，表示如下： 第一段计算： K1N=B1N+C1N D1N= K1NA1N 第二段计算： KN+12N=BN+12N+CN+12N DN+12N= KN+12NAN+12N 显然每一段两条向量指令、一次数据相关和两次流水线功能部件切换，中间向量寄存器长度为N。,5.2.2 增强向量处理性能的方法,在向量处理机中一般都采用多个独立的功能部件，以完成不同的操作。例如CRAY-1巨型机设有4组12个单功能流水部件，其中第一组是向量操作部件，包括向量加、移位和逻辑运算三个部分；第二组是浮点运算部件，包括浮点加、乘法运算和迭代求倒数三个部分；第三组是标量功能部件，包括标量加、移位、逻辑运算和数“1”/计数四个部分；第四组是地址运算部件，包括整数加和整数乘两个部分。其逻辑组成如图5.3所示。,1.多功能部件的并行操作,图5.3 CRAY-1处理机结构示意图,图5.3中，各个功能部件相互独立，只要满足一定的约束条件就能并行工作，即不存在向量寄存器使用冲突，不存在功能部件使用冲突。 （1）向量寄存器使用冲突 例如： V5V1+V2 V4V2V3 这两条向量指令都使用向量寄存器V2作为源操作向量，因此两条指令不能同时执行。类似地，还有结果向量寄存器冲突。,（2）功能部件使用冲突 例如： V1V2+V3 V4V5+V6 两条指令都要使用浮点加法器，因此谁也不能执行。 理想情况下，若有M个相互独立的功能部件，应当使系统速度提高M倍。但是由于存在可能出现的冲突，使得能完全并行工作的功能部件往往小于M。 2.向量链接技术 （1）向量链接技术的概念 在向量操作中也可象标量机中使用定向传送技术那样来提高执行部件的速度，称为向量链接技术。设有如下指令序列： ADDV V1，V2，V3 ；V1V2+V3 MULTV V4，V1，V5 ；V4V1V5,第一条加法结果存入V1，后一条使用V1作为源操作向量，即先写后读数据相关。若寄存器V1在同一时钟周期既接收加法运算结果，又把这一结果送到乘法部件，就能使两个部件链接起来工作，称为超级向量操作。充分流水状态后，一个时钟周期就可获取两个运算结果。 （2）向量链接技术的实现 需设专门机制，检测每一条向量指令能否与前一条指令链接操作。若能，则把前一条指令执行的第一结果分量作为本指令的源操作数，并启动本指令。以D=A(B+C)为例：,设向量长度n64，且向量B和C已经取至向量寄存器V0和V1。这样，可用三条指令完成： LD V3，A ；V3A ADDV V2，V0，V1 ；V2V0+V1 MULTV V4，V2，V3 ；V4V2V3 前二条指令没有向量寄存器冲突，也没有功能部件冲突，并行执行。第三条指令与前两条指令均存在先写后读的数据相关，因此可与前两条指令链接执行，如图5.4所示。,图5.4 向量并行操作与链接,三条指令全部顺序执行，节拍数为： (1+6+1)+n-1+ (1+6+1)+n-1+ (1+7+1)+n-1=3n+22 前两条指令并行执行，再与第三条指令顺序执行，节拍数为： (1+6+1)+n-1+ (1+7+1)+n-1=2n+15,如果前两条指令并行执行，且与第三条指令链接，节拍数为： (1+6+1)+(1+7+1)+n-1=n+16 注意：实现链接除了上述约束条件之外还有时间上的要求，即在前一条指令的第一个结果分量送入结果向量寄存器的那一时钟周期才能链接，否则无法再链接。另外，两条向量指令所处理的向量的长度也必须相等。 3.加快条件语句执行与稀疏矩阵的加速处理方法 （1）加快条件语句执行 对于条件语句的执行，可采用向量屏蔽技术，设有如下FORTRAN循环程序： DO 10 I=1，64 IF （A(I).NE.0） THEN A(I)=A(I)-B(I) ENDIF 10 CONTINUE,采用向量屏蔽技术，使减法仅在A(I)0时执行。在高档向量机中设有屏蔽向量寄存器VM。可通过向量测试指令对向量A(I)进行0测试，当A(I)中某元素为0时，屏蔽向量寄存器的相应位清0；而A(I)0时，则将相应位置1。这样，对应于屏蔽向量寄存器为1的位的元素可以参加运算，为0的位的元素不能参加运算。程序如下，设向量A和B的起始地址在寄存器Ra和Rb中。 LV V1，Ra ；将向量A装入V1 LV V2，Rb ；将向量B装入V2 LD F0，#0 ；F00 SENSV F0，V1 ；若V1(I)0时，VM(I)置1，否则清0 SUBV V1，V1，V2 ；在屏蔽向量的控制下进行减法运算 CVM ；将屏蔽向量寄存器置全1，即不再屏蔽 SV Ra，V1 ；存结果 其中SENSV是设置屏蔽向量的指令，SUBV是在屏蔽向量的控制下进行减法运算的指令；CVM是清除屏蔽向量寄存器的指令，将VM的所有位置1，不再屏蔽。,（2）稀疏矩阵的加速处理方法 稀疏矩阵是包含大量0元素的矩阵，典型的稀疏矩阵求和运算的程序如下： DO 10 I=1，n 10 A(K(I)=A(K(I)+B(M(I) 这里使用了指标向量K和M指示A和B中的非零元素。在这一运算中，要求A和B有相同的非零向量长度n。此外，也可以使用位向量来指明其中的非零元素。 在向量处理机中支持这种稀疏矩阵运算的基本结构是使用指标向量的散射-聚合(Scatter gather)操作，如图5.5所示。其中聚合操作如图5.5（a）所示，根据指标向量的内容选取向量元素，它的地址由基地址加上指标向量中给定的地址偏移量而形成。比如指标向量寄存器I=1单元的内容（偏移量）为4，与基地址100相加，再取稀疏向量104单元的600送入稠密向量寄存器I=1单元。聚合操作后得稠密向量。 若要恢复成稀疏向量，可使用散射操作，借助于同一指标向量来完成，其过程如图5.5（b）所示，与聚合操作正好相反。,图5.5 向量的聚合与散射,4.向量归约操作的加速方法 对于象一维数组那样的向量归约求值，结果是一个标量值。对向量归约（Reduction）操作往往难以向量化。但是，可根据运算的类型和过程进行分解，找出向量化的操作，分别处理。从而提高整体运算的速度。下面以向量点积为例说明： RED=0.0 DO 10 I=1，64 10 RED=RED+A(I)*B(I),增加了一个乘积向量，这就使第一步运算可以实现向量化；第二步进行递推归约运算。对于递推规约运算还可采用递归折叠法进行： L=32 DO 30 J=1，6 DO 10 I=1，L 10 RED(I)=RED(I)+ RED(I+L) L=L/2 30 CONTINUE,由于迭代层间数据相关，无法直接向量化。但是，可先进行乘法运算，再进行归约。使前者运算向量化，程序如下： DO 10 I=1，64 10 RED(I)= A(I)*B(I) RED1=0.0 DO 20 I=1，64 20 RED1=RED1+RED(I),5.3 向量处理性能的评价参数 与评价方法,5.3.1 机器向量长度与向量流水处理时间 5.3.2 向量流水操作中处理时间及速率与向量长度的关系 5.3.3 向量流水处理中与向量长度有关的参数,评价向量处理性能的参数主要有机器向量长度、向量流水操作时间Tvp、每一对元素的平均处理时间tvp、 向量流水线的最大性能R（渐近性能）、半性能向量长度n1/2和向量与标量的平衡点nv等。,5.3.1 机器向量长度与向量流水处理时间,1.机器向量长度与数据向量长度 机器向量长度是指机器中向量寄存器的长度，属于固有参数，可用N表示。 数据向量长度是指用户向量数据的长度，可用n表示，不由机器决定。 2.向量流水处理时间与最大性能 在向量机中，若执行一个长度为n的向量操作时间为Tvp，用Ts表示流水线建立时间，包括向量起始地址的设置、计数器加1、条件转移的判断等，T1表示第一对向量元素通过流水线的时间，Tc为流水线的时钟周期，则,Tvp=Ts+Tl+(n-1)Tc =sTc+lTc+(n-1)Tc =(s+l-1)Tc+nTc （5.2） 其中s是建立流水线的时钟周期数，l为完成每一对向量元素操作所需要的子操作次数。若令To=(s+l-1)Tc 则 Tvp=To+nTc （5.3） 每一对向量元素的平均执行时间为：,其中R表示向量长度n趋于时，向量流水处理的最大性能，也称为渐近性能，常在评价峰值性能时使用，单位为MFLOPS，是评价向量流水线的一个重要的参数。,5.3.2 向量流水操作中处理时间及速率与向量长度的关系,对于标量循环和向量流水操作方式，其处理时间与向量长度的关系如图5.6(a)所示，处理速率与向量长度的关系如图5.6(b)所示。 图中nv表示向量流水方式的工作速度优于标量循环方式时所需要的向量长度临界值。,图5.6 标量循环和向量流水操作中处理时间及处理速率与向量长度的关系,5.3.3向量流水处理中与向量长度 有关的参数,在向量流水线的性能分析中，涉及三个重要的参数。 1.向量流水线的最大性能R 如式5.6所示，R表示向量长度n趋于时，向量流水处理的最大性能，也称为渐近性能，常在评价峰值性能时使用，单位为MFLOPS。 2.半性能向量长度n1/2 n1/2表示向量流水性能达到最大值的一半时的向量长度，是评价向量流水线的建立时间对性能影响的参数，其含义如式5.8所示。 3.向量流水与标量循环平衡点nv 如图5.6(a)所示nv表示向量流水方式的工作速度优于标量循环方式时所需要的向量长度临界值。当向量长度nnv时，向量流水方式的速度优于标量循环方式。,【例5.3】若某向量处理机执行速率Rv=10MFLOPS，在标量工作方式时的执行速率Rs=1MFLOPS，设程序中可向量化的比例为，要求： 推导该向量机执行时平均速率R的公式；画出在（0，1）范围内，R与的关系曲线；为使平均执行速率R =7.5MFLOPS，应取何值？假设Rs=1MFLOPS，=0.7，为使R=2MFLOPS，Rv应为何值？ 解：（1）平均速率R的公式为,（2）在（0，1）范围内，R与的 关系图如图5.7所示。 （3）把R =7.5代入式5.10，可求出：,（4）把Rs=1、=0.7和R=2代入式5.9，可求出： Rv=3.5MFLOPS,图5.7 平均速率R与 的关系,5.4 向量化编译技术,为了在向量处理机上实现向量化运算，必须要有相应的向量化编译程序，以便在源程序中找出可向量化的部分，按照向量化的语言进行编译。 1.向量运算指令 设有如下FORTRAN语言程序： DO 10 I=1，N A(I)=B(I)+C(I) 10 CONTINUE 一条向量加法指令实现这一循环程序的功能。指令如下： ADDV A(1:N)=B(1:N)+C(1:N) 2.向量化编译技术 向量化编译技术是在源程序中寻找可用向量指令替代的程序段，并用向量指令替代之。在简单可向量化的循环程序中不存在向量化障碍，比如数据相关、条件语句等，编译比较容易。但是对于复杂程序，包含这些障碍时，需采取相应的措施予以消除。比如对条件语句可使用相应的控制向量及WHERE语句加以消除。例如：,DO 20 I=1，N 20 IF（L(I).NE.0） A(I)=A(I)+1 使用向量化指令，可写成： WHERE （L(I).NE.0） A(1:N)=A(1:N)+1 ；转换成WHERE结构,3.向量化编译优化技术 除一般向量化编译外，也可采取优化技术，比如公共子表达式消除、死代码消除、常数调入、复制语句传递等；在循环体的优化中，将固定表达式移出循环体以及归约变量消除等。 此外还有一些特殊的方法，比如向量寄存器优化分配、流水链接和功能部件并行操作优化、重排指令执行的序列以减少功能部件切换的频率等。,图5.8 向量机优化编译技术,目前，在大多数向量机中向量化编译优化技术可用图5.8表示，包括通用优化、向量寄存器使用优化、向量链接与流水线并行操作优化以及标量语句向量化等。,5.5向量处理机举例,5.5.1 多向量多处理机系统CRAY Y-MP 5.5.2 C-90,5.5.1 多向量多处理机系统CRAY Y-MP,1.系统组成 多向量多处理机CRAY Y-MP 816的系统结构如图5.9所示。整个系统可配置1台、2台、4台或8台处理机，采用共享中央存储器、I/O子系统、处理机之间的通信系统及实时钟等，CPU时钟周期为6nS。中央存储器可分成256个交叉存储体，总容量可以是16128MW，最大1GB；固态存储器的容量为32512MW，最大4GB。有四个存储器端口，允