5.35.4向量机

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.5 向量机,1,标量,：常量和数组中的每一个元素都为标量。,只能对一个或一对标量操作数进行运算或操作的指令为,标量指令,。,只有标量指令系统的处理机称为标量处理机。,三种高性能指令级并行处理机：,超标量处理机,超流水线处理机,超标量超流水线计算机,2,主,存,D-cache,I-cache,译码器,2,1,指令调度,状态记录,部件,存储器操作部件,ALU部件,转移控制部件,RF,超级标量机的典型结构,3,超标量机的主要特点,配置有多个性能不同的处理部件，采用多条流水线并行处理。,能同时多若干条指令进行译码，将可执行的指令送往不同的执行部件，从而达到在每个周期启动多条指令的目的。,在程序运行期间由硬件（通常是状态记录部件和调度部件）完成指令的调度工作。,4,VLIW,机的工作原理,VLIW,机的方法在1983年由美国耶鲁大学的,Fisher,教授首先提出来的，它与超标量机的不同之处在于：它用一条长指令来实现多条操作的并行执行，减少对存储器大访问，指令字往往长达百位，甚至千位。,5,VLIW,机的主要特点,单一的控制流。只有一个控制器，每个周期启动一个长指令。,超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。,含有大量的数据通路和功能部件，由于编译器在编译时间已考虑可能出现的数据相关和资源相关，故控制硬件比较简单。,在编译阶段完成超长指令中多个可执行操作的调度。,6,VLIW,机的结构图,主,存,RF(寄存器堆),LD/ST1,LD/ST2,FADD,FMUL,VLIW,中的操作码字段:,LD/ST1 LD/ST2 FADD FMUL,7,例：,要完成如下指令：,C=A+B,K=I+J,L=M-K,Q=CK,8,源代码,操作,所需周期,C=A+B,LOAD A,LOAD B,C=A+B,STORE C,1,1,1,1,K=I+J,LOAD I,LOAD J,K=I+J,STORE K,1,1,1,1,L=M-K,LOAD M,L=M-K,STORE L,1,1,1,Q=CK,Q=CK,STORE Q,2,1,14周期,9,经,VLIW,调度后的指令,STORE Q,STORE L,Q=CK,L=M-K,STORE K,K=I+J,STORE C,LOAD M,C=A+B,LOAD J,LOAD I,LOAD B,LOAD A,6个周期,（乘2个周期）,10,比较类型,译码,并行检验完成时间,代码密度,目标,可移植性,VLIW,简单,编译,较差,不可移植,超级标量,复杂,运行,较好,可移植,VLIW,与超标量机的比较,11,VLIW,计算机曾经有过商品化的机器，如美国的,Multiflow,公司生产的,TRACE,型号机器，以及,Cydrome,公司生产的,Cydra5.,但由于性能价格比不理想等原因已停止生产,VLIW,机器，但是计算机所采用的压缩技术已广泛使用。,12,为了获取高的流水处理性能:,1、设法增加流水线中的段数，即：流水的深度。,2、设法在每个时钟周期能启动多条指令。,13,标量流水机性能的提高受到下面两个因素影响：,1、流水线工作的时钟周期不可能取得很短。,相关问题,时钟周期短将加剧时钟在流水入口和出口处的扭斜错位程度，使级间锁定变得困难，导致不能可靠工作。,2、取指及译码的速率受限。在一个时钟周期中最多只能启动一条指令 。,14,向量流水处理在一定程度上不受以上两各个因素影响。,15,一、向量流水机的基本系统结构,1.向量流水的主要特点：,一个,向量,中各个元素是互不相关的，对当前每个向量的操作结果不影响到其他向量元素。这就允许向量流水流水线有较深的深度。,16,一条向量指令相当于一个标量循环，所以可以减少指令，从而可以降低对指令访问带宽的要求。并且消除了由循环引起的控制相关。,若向量指令所要访问的向量元素均相邻，则可以在交叉存储体中高速地依次访问它们。这使得访存时间缩短。,向量操作要比一串标量指令操作更快。,17,2.向量机的系统结构按向量操作对象及结果主要存放在寄存器中还是存放在存储器中，可分为:,存储器-存储器工作方式向量机,寄存器-寄存器工作方式向量机,18,现在的向量机大多采用寄存器-寄存器工作方式，如中国的,YH,向量机等。,19,主存,标量寄存器,向量存取,部件,指令,处理部件,向量寄存器/,向量缓冲器,向量指令,控制部件,标量功能部件,向量功能部件,向量功能部件,向量功能部件,20,它主要由一个标量流水部件和一个向量流水部件组成，包含了向量功能部件、向量存取部件、向量寄存器或向量缓冲部件、标量量寄存器、标量处理部件及向量控制器等部件。也就是说，向量机兼容标量处理功能。,21,Y= aX+Y,（a,为标量，,X、Y,为向量）,标量机,LD F,0,，a,ADDI R,4，,R,X，,#512,LOOP：LD F,2 ，,0（ R,X,）,MULD F,2,， F,0,， F,2,LD F,4 ，,0（ R,Y,）,ADDD F,4,， F,2,， F,4,SD 0（ R,Y,）， F,4,ADDI R,X,， R,X,， #8,ADDI R,Y,， R,Y,， #8,SUB R,20，,R,4，,R,X,BNZ R,20，,LOOP,22,向量机,LD F,0,，a,LV V,1,， R,X,MULTV V,2,， F,0，,V,1,LV V,3,， R,Y,ADDV V,4,， V,2，,V,3,SV R,Y，,V,4,23,比较,向量机执行指令6条。,标量机执行指令（9*64+2=578）,标量机的连锁频率远高于向量机。,24,3.向量启动时间和启动率,基本的向量流水操作就是在对一条指令进行流水操作，也就是用流水的方法对向量元素进行操作。当一条向量指令开始执行时，就开启了一条向量流水线，从开始启动到流水运行结束的时间就是向量指令的,执行时间,。,25,T,vp,=T,at,+nI,r,其中：,T,at,是流水线的启动时间（包括流水线固有的延迟时间，以便设置为完成向量指令所需的相应参数）,I,r,为启动率，它表示一旦向量指令开始运行后，即向量流水线填满后，每流出一个结果所需时间。,n,是向量的长度,26,对,RR,型向量机而言,流水线的启动时间主要取决于功能部件流水线的深度，启动时间就是获得第一个流水结果的时间。,启动率取决于相应的向量功能不见能以多快的频率来接收一个操作数，当处于充分流水时可使启动率为1。,27,二、向量操作长度控制和向量访问步长,在寄存器-寄存器工作方式执行过程中，如果向量的长度大于寄存器的长度时，要把待计算的向量分成几段来计算，每次调入一段，放到寄存器中进行流水操作，完了以后再取一段。这就是,分段技术,。,28,三、向量的处理方法,向量机对向量的各种运算可以采用不同的加式方式，一种是横向加工，一种是纵向(垂直)加工，还有就是纵横向加工(分组加工)，这是分段技术在向量加工方式上的实现。如,CRAY-1,以及小巨型机基本都采用分组加工的方式。,29,D = A（B+C）,横向加工法,di=a1(b1+c1),d2=a2(b2+c2),di=ai(bi+ci),30,D = A（B+C）,纵向加工法,K = B+C,D = AK,31,D = A（B+C）,纵横向加工法（每组有两条向量指令）,K,1n,= B,1n,+C,1n,D,1n,= A,1n,K,1n,第一组：,32,四、增强向量处理性能的方法,四种增强向量处理性能的方法,其中两种方法已在所有向量机中采用：,一是采用多功能部件，并行工作；,二是加快一串相关向量指令的操作速度，即链接技术。,33,1、多功能部件的并行操作,采用多个独立的功能部件，并使它们并行工作的条件是：,(1)不存在向量寄存器使用冲突；,(2)不存在功能部件使用冲突。,34,向量寄存器使用冲突就是指多条并行工作的向量指令中的源向量或结果向量使用相同的向量寄存器。,例如：,V4V1+,V2,V5,V2,V3,35,功能部件冲突是指多条向量指令都要使用同一个功能部件，如两条向量指令都是加法运算时，浮点加的功能部件就无法同时满足，而发生冲突。,例如：,V3V1,+,V2,V6V4,+,V5,36,CRAY-1,CRAY-1,由中央处理机、诊断维护控制处理机、大容量磁盘存储子系统、前端处理机组成的功能分布异构型多处理机系统。,中央处理机的控制部分有总容量为256个16位的指令缓冲器，分成4组，每组为64个。,中央处理器的运算部分有12条可并行工作的单功能流水线。,在,CRAY-1,中每拍12.5,ns。,37,一条向量指令的执行时间主要取决于下面三个因素：,向量的长度,是否出现相关,并行执行的程度,38,能在一个时钟周期内一起开始执行的多条指令称为一个,编队,。,资源不冲突,数据不相关,39,例如：,LV V1，RX,MULTSV V2，F0，V1,LV V3，RY,ADDV V4，V2，V3,SV RY，V4,40,LV V1，RX,MULTSV V2，F0，V1,LV V3，RY,ADDV V4，V2，V3,SV RY，V4,V1,V1,41,LV V1，RX,MULTSV V2，F0，V1,LV V3，RY,ADDV V4，V2，V3,SV RY，V4,并行,42,LV V1，RX,MULTSV V2，F0，V1,LV V3，RY,ADDV V4，V2，V3,SV RY，V4,V3,V3,43,LV V1，RX,MULTSV V2，F0，V1,LV V3，RY,ADDV V4，V2，V3,SV RY，V4,V4,V4,44,四个队列,LV V1，RX,MULTSV V2，F0，V1,LV V3，RY,ADDV V4，V2，V3,SV RY，V4,45,整数加3,移位4,逻辑2,向量部件,浮点加6,浮点乘7,浮点倒数14,浮点部件,整数加3,逻辑1,移位23,数1/计数34,整数加2,整数乘6,主储存器,8个向量寄存器,每个64字，每字64位,8个标量寄存器,8个地址寄存器,指令处理器,地址运算部件,标量部件,I/O,CRAY-1,处理机,12个功能流水部件,46,2、链接技术,利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为,链接技术,。它就是标量流水中的定向传送方法在向量寄存器中的应用。,47,ADDV V,1,， V,2，,V,3,MULTV V,4,， V,1，,V,5,串行执行：,6+,n-1+7+n-1=2n+11,链接执行：,6,+7+n-1= n+12,48,使用这个技术的条件是:,1、两条指令间存在,先写后读,的数据相关性。也就是前一条指令的结果正好为后一条指令的数据源。可以在上一条指令将结果传送到结果寄存器的同时就直接传给下一指令的功能部件作为操作数进行操作，这就节省了等待时间。,49,2、时间上的要求，就是当前一指令的第一个结果分量送入结果寄存器的那一个时钟周期方可链接，若错过这一拍，就无法链接。如果一条向量指令的源操作数是前面两条并行操作指令的结果数时，只有这两条指令产生结果的时间必须相等才可进行链接。也就是说，,链接操作得丝丝入扣，一拍不差，早也不行，晚也不行，多也不行，少也不行,。,50,我们应该能够判断一串指令是否可以并行或链接，并能计算其执行时间。,51,在,CRAY-1,上执行,D=A（B+C）,设向量长度小于64，且,B,和,C,已由存储器取至,V0,和,V1，,可由下面三条指令完成上述的运算：,LD V,3 ，,A,ADDV V,2,， V,0，,V,1,MULTV V,4,， V,2，,V,3,并行,冲突,52,三条指令的不同执行方法：,全串行,（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,53,采用一个屏蔽向量来控制某些向量元素参加运算。,例如：,do 100 i=1,64,if ( A(i) .ne. 0 ) then,A(i)=A(I)-B(i),endif,100 continue,3. 条件执行语句的加速处理方法,54,LD V,1 ，,Ra,LD V,2 ，,Rb,LD F,0 ，,#0,SENSV F,0,，V,1,；,设屏蔽向量,SUBV V,1,， V,1，,V,2,CVM ；,屏蔽向量置全1,SV R,a,，V,1,55,屏蔽向量寄存器控制向量指令执行方法的缺点是：,1、执行时间没有少。（执行操作，但结果不回送）,2、可能会使某些向量指令指令操作出现错误。,例如：,if A(I) then B(i)=B(i)/A(i),解决的办法是：根据屏蔽向量既禁止将结果写入目的寄存器又禁止该操作的执行。,56,通过指标向量来指明非零元素并通过指标向量的散射-聚合操作来支持稀疏矩阵的运算。,4. 稀疏矩阵的加速处理方法,57,4.向量归约操作的加速方法，这种方法就是将标量循环的一部件加以向量化，并采用递归折叠的方法来加快向量归约操作。,58,五、向量处理性能的评估参数和方法,在向量机中，执行一个向量长度为,n,的指令所需的时间为：,T,vp,=(s+l+n-1)Tc,其中,s,为建立流水线所需时间周期数，,l,为完成每对向量元素操作所需的子操作数，即流水功能部件中的级数。,59,每对向量元素的平均执行时间为：,t,vp,=T,vp,/n,在评估向量流水机性能时，除了执行时间外，向量长度是一个很重要的评估参数。常用的评价参数有三个：,R,:,向量长度为无穷大时向量流水的渐近性能，常在评价峰值性能时使用，单位用,MFLOPS。,n,1/2,：,为达到一半,R,值时的需的向量长度。,n,v,：,它表示向量流水方式工作速度优于标量串行方式工作时所需的向量长度临界值。,60,六、向量化编译技术,采用向量化编译程序将程序中存在的可并行的循环体语句用相应向量指令来表示。向量化编译器也有优化问题，通常采用：通用优化技术、向量寄存器优化技术、流水线并行化技术以及标量循环语句向量化技术。,61,62,向量,向量运算,向量处理特点,向量 相关问题,数据相关,资源相关,提高向量处理速度,并行：不冲突，取长时间,链接：数据相关，两个操作数同时到。,63,链接技术：,利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术,。,64,向量处理方式,纵（,RR）,横（,SS）,纵横,N64,向量机结构,RR,SS,D=A*（B+C）,65,LD V3,A,LD V0,B,LD V1,C,ADD V2,V0,V1,MUL V4,V 2*V3,ST V4,D,66,向量长度,N,N64.,取数:,1+,6+(,N-1 ),+1,加: 6+(,N-1 ),乘: 7+(,N-1 ),串行：6+(,N-1 )+,6+(,N-1 )+,7+(,N-1 ),1,和2,3串: 6+(,N-1 )+,7+(,N-1 ),1,和2,3链: 6+7+（,N-1）,67,三条指令并行执行：1+7+63+1=72,1，2并行与3链接：1+7+1+63+1+6+1,1，2链接，3，4，串,1+6+1+1+7+1+63+1+6+1+63 +1+6+1+63,1+6+1+ 1+14+1+ 1+7+1+1+6+1+63,68,6.2与标量机相比向量流水的特点是什么？,答：向量流水处理的特点是：,（1）在向量操作中，每个当前结果向量元素的计算与以前结果向量元素的计算是相互独立的，这就允许向量流水线有较深的深度。,（2）一条向量指令相当于一个标量循环，从面可降低对指令访问带宽的要求。此外，这也消除了由循环转移可能引起的控制相关。,69,（3）若向量指令所要访问的向量元素均相邻，则可以在交叉存储体中高速地依次访问它们。由于一个向量中通常含有多个元素，因此对存储器访问的延迟平均到每个元素上，其访丰等待的时间开销是较小的。,与标量流水机相比，向量操作要比一串标量指令操作更快，此外，向量流水机还可使访丰和有效地址计算流水化，高档的向量机还允许多个向量操作同时进行，从而可开发对不同元素进行多个向量操作的并行性。,70,向量的工作方式有哪两种？各有何特点？,向量机系统结构按向量操作对象及结果主要存放在寄存器中还中存放在存储器中,可分为存储器-存储器工作方式向量机和寄存器-寄存器工作方式向量机两大类.前者的工作特点是向量操作的源向量都取自主存且操作生成的结果向量也存放到主存中,而后都则都取自或存放到向量寄存器中。,71,向量的加工方法有哪几种？从加工速度和需要的中间变量等方面分析各有何特点？,向量的加方法有三种:,一种普遍采用的加工方式称为横向加工,它是按向量顺序计算的.这种加工方式需要中间寄存器，在每个向量元素的加乘运算中都会发生数据相关情况，而且当用静态流水线时，还要进行多次功能转换所以这种加工方式速度慢，不适合于向量流水处理,72,另一种加工方式称为垂直加工,它是先纵向加工某两个向量中元素对的加法操作,中间结果暂存到一中间向量中,然后再纵向加工所有对应元素的乘法操作.这种方式的数据相关在两条向量指令间只有一次，流水线功能只需切换一次加获得较高的吞吐率，但需要有一个暂存中间向量存储器存储器工作方式的向量机都采用这种方式,73,第三种加工方式是纵横向加工(或称分组加工），以寄存器寄存器方式工作的向量机都采用这种加工方式，因为向量寄存器的长度有限，当向量长度超过向量寄存器可表示的最大限度时就不得不分段处理在加工时，每组内各有两条向量指令，各组内有一次数据相关，需次流水功能切换，需个中间向量寄存器单元以及小巨型机基本都采用这种加工方式,74,