向量流水与向量处理机

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第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,=,a,X,+,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 ；F2,a,X,(i),LD F4，0(Ry)；取向量元素,Y,(i),ADDD F4，F2，F4 ；F4,a,X,(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 ；V2a,X,LV V3，Ry ；取向量,Y,ADDV V4，V2，V3 ；V4a,X,+,Y,SV Ry，V4 ；存结果,通过对上述程序进行分析可以看出，在标量机上进行运算共执行964+2=578条指令，其中还包含大量的延迟等待。而在向量机上进行运算，仅需要6条向量指令。,5.1.3 向量启动时间与结果流出时间,在向量流水过程中也存在启动时间,T,st,，相当于标量流水线中填入时间，以设置向量操作所涉及到的参数，比如设置向量长度等。启动后结果连续输出，每输出一个结果的时间称为结果流出时间，可用,I,r,表示。若设向量长度为,n,，则一条向量指令执行时间可表示如下：,T,vp,=,T,st,+,n,I,r,（,5.1,）,【例,5.2,】在一个向量乘法流水线中，向量启动时间为,10,个时钟周期，启动后,1,个时钟周期流出一个结果，若向量长度为,64,，试求产生每一个结果向量元素所用的平均时间。,解：,根据题意，,T,st,=10，,I,r,=1，,n,=64，则产生每一个结果向量元素的平均时间,T,av,为：,T,av,=1.16,T,vp,n,T,st,+,n,I,r,n,10+64,1,64,可以看出，对于运算速度较慢的向量流水操作，启动时间影响不大；对于速度较快向量流水操作，启动时间会产生较大的影响。,对于寄存器-寄存器型向量处理机来说，向量启动时间主要取决于功能部件流水线的深度，结果流出时间取决于向量功能部件以多快的频率接收数据。当向量较长时，启动稳定后的结果流出时间可视为1。,5.1.4 向量操作长度控制与向量访问步长,1.向量操作长度控制,（1）向量寄存器长度,在寄存器-寄存器型向量处理机中向量由向量寄存器存储，向量寄存器的个数称为向量寄存器长度，可用,N,来表示。比如，CRAY-1的向量寄存器长度为64。,（2）向量长度与向量长度寄存器,在实际运算中向量长度,n,不一定正好等于向量寄存器的长度，可能小于也可能大于向量寄存器的长度。因此，需用向量长度寄存器存放向量长度。,（3）向量操作长度控制,这里仍以,Y,=,a,X,+,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,=,A,B,。设计 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.横向加工,横向加工是一种最普通的加工方式，它是按照向量的顺序计算，即,D,1,=,A,1,(,B,1,+,C,1,),D,2,=,A,2,(,B,2,+,C,2,),D,n,=,A,n,(,B,n,+,C,n,),这种方法是逐个计算,D,的,n,个分量。先计算,K,1,(,B,1,+,C,1,)，然后计算,D,1,A,1,K,1,。这样共出现,n,次数据相关和2,n,次功能部件的切换，不适合向量流水处理。,2.纵向加工,也称为垂直加工法，它是先进行所有纵向,B,+,C,的操作，中间结果暂存到中间向量,K,中，然后再进行所有纵向乘法操作,A,K,，如图,5.2,所示。,用向量指令的形式表示，形式如下：,K,=,B,+,C,D,=,K,A,采用这种方法，数据相关仅在向量指令间发生一次，流水线功能部件的切换也仅有一次。但是需要使用一个中间向量,K,。,图5.2 纵向加工方法,3.纵横向加工,当参加运算的向量长度,n,大于向量寄存器的长度,N,时，需要分段进行，这样就产生了纵横向加工方式。段内纵向加工，段间横向加工，表示如下：,第一段计算：,K,1N=,B,1N+,C,1N,D,1N=,K,1N,A,1N,第二段计算：,K,N+12N=,B,N+12N+,C,N+12N,D,N+12N=,K,N+12N,A,N+12N,显然每一段两条向量指令、一次数据相关和两次流水线功能部件切换，中间向量寄存器长度为,N,。,5.2.2 增强向量处理性能的方法,在向量处理机中一般都采用多个独立的功能部件，以完成不同的操作。例如,CRAY,-,1,巨型机设有,4,组,12,个单功能流水部件，其中第一组是向量操作部件，包括向量加、移位和逻辑运算三个部分；第二组是浮点运算部件，包括浮点加、乘法运算和迭代求倒数三个部分；第三组是标量功能部件，包括标量加、移位、逻辑运算和数“,1,”,/,计数四个部分；第四组是地址运算部件，包括整数加和整数乘两个部分。其逻辑组成如图,5.3,所示。,1.多功能部件的并行操作,图5.3 CRAY-1处理机结构示意图,图5.3中，