5.35.4向量机.ppt

2.5 向量机向量机华中师范大学计算机科学系陈 利n标量：常量和数组中的每一个元素都为标量。n只能对一个或一对标量操作数进行运算或操作的指令为标量指令。n只有标量指令系统的处理机称为标量处理机。n三种高性能指令级并行处理机：n超标量处理机n超流水线处理机n超标量超流水线计算机主存D-cacheI-cache译码器21指令调度状态记录 部件存储器操作部件ALU部件转移控制部件RF超级标量机的典型结构超级标量机的典型结构超标量机的主要特点超标量机的主要特点n配置有多个性能不同的处理部件，采用多配置有多个性能不同的处理部件，采用多条流水线并行处理。条流水线并行处理。n能同时多若干条指令进行译码，将可执行能同时多若干条指令进行译码，将可执行的指令送往不同的执行部件，从而达到在的指令送往不同的执行部件，从而达到在每个周期启动多条指令的目的。每个周期启动多条指令的目的。n在程序运行期间由硬件（通常是状态记录在程序运行期间由硬件（通常是状态记录部件和调度部件）完成指令的调度工作。部件和调度部件）完成指令的调度工作。VLIW机的工作原理机的工作原理nVLIW机的方法在机的方法在1983年由美国耶鲁大学的年由美国耶鲁大学的Fisher教授首先提出来的，它与超标量机教授首先提出来的，它与超标量机的不同之处在于：它用一条长指令来实现的不同之处在于：它用一条长指令来实现多条操作的并行执行，减少对存储器大访多条操作的并行执行，减少对存储器大访问，指令字往往长达百位，甚至千位。问，指令字往往长达百位，甚至千位。VLIW机的主要特点机的主要特点n单一的控制流。只有一个控制器，每个周期单一的控制流。只有一个控制器，每个周期启动一个长指令。启动一个长指令。n超长指令字被分成多个控制字段，每个字段超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。直接独立地控制每个功能部件。n含有大量的数据通路和功能部件，由于编译含有大量的数据通路和功能部件，由于编译器在编译时间已考虑可能出现的数据相关和器在编译时间已考虑可能出现的数据相关和资源相关，故控制硬件比较简单。资源相关，故控制硬件比较简单。n在编译阶段完成超长指令中多个可执行操作在编译阶段完成超长指令中多个可执行操作的调度。的调度。VLIW机的结构图机的结构图主存 RF(寄存器堆)LD/ST1LD/ST2FADDFMULVLIW中的操作码字段中的操作码字段:LD/ST1 LD/ST2 FADD FMUL例：例：n要完成如下指令：C=A+BK=I+JL=M-KQ=CK源代码源代码操作操作所需周期所需周期C=A+BLOAD ALOAD BC=A+BSTORE C1111K=I+JLOAD ILOAD JK=I+JSTORE K1111L=M-KLOAD ML=M-KSTORE L111Q=CKQ=CKSTORE Q2114周期周期经经VLIW调度后的指令调度后的指令STORE QSTORE LQ=CKL=M-KSTORE KK=I+JSTORE CLOAD MC=A+BLOAD JLOAD ILOAD BLOAD A6个周期个周期（乘（乘2个周期）个周期）比较类型译码并行检验完成时间代码密度目标可移植性VLIW简单编译较差不可移植超级标量复杂运行较好可移植VLIW与超标量机的比较与超标量机的比较VLIW计算机曾经有过商品化的机计算机曾经有过商品化的机器，如美国的器，如美国的 Multiflow 公司生产公司生产的的TRACE型号机器，以及型号机器，以及Cydrome 公司生产的公司生产的Cydra5.但由但由于性能价格比不理想等原因已停止于性能价格比不理想等原因已停止生产生产VLIW机器，但是计算机所采机器，但是计算机所采用的压缩技术已广泛使用。用的压缩技术已广泛使用。为了获取高的流水处理性能为了获取高的流水处理性能:1、设法增加流水线中的段数，即：、设法增加流水线中的段数，即：流水的深度。流水的深度。2、设法在每个时钟周期能启动多条、设法在每个时钟周期能启动多条指令。指令。标量流水机性能的提高受到下面两个因素影响：标量流水机性能的提高受到下面两个因素影响：1、流水线工作的时钟周期不可能取得很短。、流水线工作的时钟周期不可能取得很短。n 相关问题相关问题n 时钟周期短将加剧时钟在流水入口和出口时钟周期短将加剧时钟在流水入口和出口处的扭斜错位程度，使级间锁定变得困难，处的扭斜错位程度，使级间锁定变得困难，导致不能可靠工作。导致不能可靠工作。2、取指及译码的速率受限。在一个时钟周、取指及译码的速率受限。在一个时钟周期中最多只能启动一条指令期中最多只能启动一条指令。向量流水处理在一定程度上不受以上两向量流水处理在一定程度上不受以上两各个因素影响。各个因素影响。一、向量流水机的基本系统结构1.向量流水的主要特点：向量流水的主要特点：n一个一个向量向量中各个元素是互不相关的，对当中各个元素是互不相关的，对当前每个向量的操作结果不影响到其他向量前每个向量的操作结果不影响到其他向量元素。这就允许向量流水流水线有较深的元素。这就允许向量流水流水线有较深的深度。深度。n一条向量指令相当于一个标量循环，所以一条向量指令相当于一个标量循环，所以可以减少指令，从而可以降低对指令访问可以减少指令，从而可以降低对指令访问带宽的要求。并且消除了由循环引起的控带宽的要求。并且消除了由循环引起的控制相关。制相关。n若向量指令所要访问的向量元素均相邻，若向量指令所要访问的向量元素均相邻，则可以在交叉存储体中高速地依次访问它则可以在交叉存储体中高速地依次访问它们。这使得访存时间缩短。们。这使得访存时间缩短。向量操作要比一串标量指令操作更快。向量操作要比一串标量指令操作更快。2.向量机的系统结构按向量操作对象及结向量机的系统结构按向量操作对象及结果主要存放在寄存器中还是存放在存储果主要存放在寄存器中还是存放在存储器中，可分为器中，可分为:存储器存储器-存储器工作方式向量机存储器工作方式向量机 寄存器寄存器-寄存器工作方式向量机寄存器工作方式向量机n现在的向量机大多采用寄存器现在的向量机大多采用寄存器-寄存器寄存器工作方式，如中国的工作方式，如中国的YH向量机等。向量机等。主存标量寄存器向量存取 部件 指令处理部件向量寄存器/向量缓冲器向量指令控制部件标量功能部件向量功能部件向量功能部件向量功能部件n 它主要由一个标量流水部件和一个向量流水部件组成，包含了向量功能部件、向量存取部件、向量寄存器或向量缓冲部件、标量量寄存器、标量处理部件及向量控制器等部件。也就是说，向量机兼容标量处理功能。Y=aX+Y（a为标量，为标量，X、Y为向量）为向量）n标量机 LD F0，a ADDI R4，RX，#512LOOP：LD F2，0（RX）MULD F2，F0，F2 LD F4，0（RY）ADDD F4，F2，F4 SD 0（RY），F4 ADDI RX，RX，#8 ADDI RY，RY，#8 SUB R20，R4，RX BNZ R20，LOOP n向量机 LD F0，a LV V1，RX MULTV V2，F0，V1 LV V3，RY ADDV V4，V2，V3 SV RY，V4 比较比较n向量机执行指令向量机执行指令6条。条。标量机执行指令（标量机执行指令（9*64+2=578）n标量机的连锁频率远高于向量机。标量机的连锁频率远高于向量机。3.向量启动时间和启动率向量启动时间和启动率 基本的向量流水操作就是在对一条基本的向量流水操作就是在对一条指令进行流水操作，也就是用流水的指令进行流水操作，也就是用流水的方法对向量元素进行操作。当一条向方法对向量元素进行操作。当一条向量指令开始执行时，就开启了一条向量指令开始执行时，就开启了一条向量流水线，从开始启动到流水运行结量流水线，从开始启动到流水运行结束的时间就是向量指令的束的时间就是向量指令的执行时间执行时间。nTvp=Tat+nIr 其中：其中：Tat是流水线的启动时间（包括流水线固有的延迟是流水线的启动时间（包括流水线固有的延迟时间，以便设置为完成向量指令所需的相应参数）时间，以便设置为完成向量指令所需的相应参数）Ir为启动率，它表示一旦向量指令开始运行后，即为启动率，它表示一旦向量指令开始运行后，即向量流水线填满后，每流出一个结果所需时间。向量流水线填满后，每流出一个结果所需时间。n是向量的长度是向量的长度n对对RR型向量机而言型向量机而言 流水线的启动时间主要取决于功能部流水线的启动时间主要取决于功能部件流水线的深度，启动时间就是获得第一件流水线的深度，启动时间就是获得第一个流水结果的时间。个流水结果的时间。启动率取决于相应的向量功能不见能启动率取决于相应的向量功能不见能以多快的频率来接收一个操作数，当处于以多快的频率来接收一个操作数，当处于充分流水时可使启动率为充分流水时可使启动率为1。二、向量操作长度控制和向量访问步长n 在寄存器在寄存器-寄存器工作方式执行过程中，寄存器工作方式执行过程中，如果向量的长度大于寄存器的长度时，要如果向量的长度大于寄存器的长度时，要把待计算的向量分成几段来计算，每次调把待计算的向量分成几段来计算，每次调入一段，放到寄存器中进行流水操作，完入一段，放到寄存器中进行流水操作，完了以后再取一段。这就是了以后再取一段。这就是分段技术分段技术。三、向量的处理方法 向量机对向量的各种运算可以采用不同的向量机对向量的各种运算可以采用不同的加式方式，一种是横向加工，一种是纵向加式方式，一种是横向加工，一种是纵向(垂直垂直)加工，还有就是纵横向加工加工，还有就是纵横向加工(分组加分组加工工)，这是分段技术在向量加工方式上的实，这是分段技术在向量加工方式上的实现。如现。如CRAY-1以及小巨型机基本都采用分以及小巨型机基本都采用分组加工的方式。组加工的方式。D=A（B+C）n横向加工法 di=a1(b1+c1)d2=a2(b2+c2)di=ai(bi+ci)D=A（B+C）n纵向加工法 K=B+CD=AKD=A（B+C）n纵横向加工法（每组有两条向量指令）K 1n=B 1n+C 1n D 1n=A 1n K 1n 第一组：四、增强向量处理性能的方法四种增强向量处理性能的方法四种增强向量处理性能的方法其中两种方法已在所有向量机中采用：其中两种方法已在所有向量机中采用：一是采用多功能部件，并行工作；一是采用多功能部件，并行工作；二是加快一串相关向量指令的操作速二是加快一串相关向量指令的操作速度，即链接技术。度，即链接技术。1、多功能部件的并行操作采用多个独立的功能部件，并使它们并采用多个独立的功能部件，并使它们并行工作的条件是：行工作的条件是：(1)不存在向量寄存器使用冲突；不存在向量寄存器使用冲突；(2)不存在功能部件使用冲突。不存在功能部件使用冲突。n向量寄存器使用冲突就是指多条并行向量寄存器使用冲突就是指多条并行工作的向量指令中的源向量或结果向工作的向量指令中的源向量或结果向量使用相同的向量寄存器。量使用相同的向量寄存器。例如：例如：V4V1+V2 V5V2 V3n功能部件冲突是指多条向量指令都要功能部件冲突是指多条向量指令都要使用同一个功能部件，如两条向量指使用同一个功能部件，如两条向量指令都是加法运算时，浮点加的功能部令都是加法运算时，浮点加的功能部件就无法同时满足，而发生冲突。件就无法同时满足，而发生冲突。例如：例如：V3V1+V2 V6V4+V5CRAY-1nCRAY-1由中央处理机、诊断维护控制处理机、大容量磁盘存储子系统、前端处理机组成的功能分布异构型多处理机系统。n中央处理机的控制部分有总容量为256个16位的指令缓冲器，分成4组，每组为64个。n中央处理器的运算部分有12条可并行工作的单功能流水线。n在CRAY-1中每拍12.5ns。n一条向量指令的执行时间主要取决于下面三个因素：n向量的长度n是否出现相关n并行执行的程度n能在一个时钟周期内一起开始执行能在一个时钟周期内一起开始执行的多条指令称为一个的多条指令称为一个编队编队。n资源不冲突资源不冲突n数据不相关数据不相关例如：例如：LV V1，RXMULTSV V2，F0，V1LV V3，RYADDV V4，V2，V3SV RY，V4LV V1，RXMULTSV V2，F0，V1LV V3，RYADDV V4，V2，V3SV RY，V4V1V1LV V1，RXMULTSV V2，F0，V1LV V3，RYADDV V4，V2，V3SV RY，V4并行并行 LV V1，RXMULTSV V2，F0，V1LV V3，RYADDV V4，V2，V3SV RY，V4V3V3 LV V1，RXMULTSV V2，F0，V1LV V3，RYADDV V4，V2，V3SV RY，V4V4V4四个队列四个队列 LV V1，RXMULTSV V2，F0，V1LV V3，RYADDV V4，V2，V3SV RY，V4整数加3移位4逻辑2向量部件浮点加6浮点乘7浮点倒数14浮点部件整数加3逻辑1移位23数1/计数34整数加2整数乘6主储存器8个向量寄存器每个64字，每字64位8个标量寄存器8个地址寄存器指令处理器地址运算部件标量部件I/OCRAY-1处理机处理机12个功能流水部件个功能流水部件2、链接技术、链接技术n利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术链接技术。它就是标量流水中的定向传送方法在向量寄存器中的应用。ADDV V1，V2，V3MULTV V4，V1，V5串行执行：6+n-1+7+n-1=2n+11链接执行：6+7+n-1=n+12 使用这个技术的条件是使用这个技术的条件是:1、两条指令间存在、两条指令间存在先写后读先写后读的数据相关性。的数据相关性。也就是前一条指令的结果正好为后一条指也就是前一条指令的结果正好为后一条指令的数据源。可以在上一条指令将结果传令的数据源。可以在上一条指令将结果传送到结果寄存器的同时就直接传给下一指送到结果寄存器的同时就直接传给下一指令的功能部件作为操作数进行操作，这就令的功能部件作为操作数进行操作，这就节省了等待时间。节省了等待时间。2、时间上的要求，就是当前一指令的第一个结果分量送入结果寄存器的那一个时钟周期方可链接，若错过这一拍，就无法链接。如果一条向量指令的源操作数是前面两条并行操作指令的结果数时，只有这两条指令产生结果的时间必须相等才可进行链接。也就是说，链接操作得丝丝入扣，一拍不差，早也不行，晚也不行，多也不行，少也不行。n我们应该能够判断一串指令是我们应该能够判断一串指令是否可以并行或链接，并能计算否可以并行或链接，并能计算其执行时间。其执行时间。在在CRAY-1上执行上执行D=A（B+C）n设向量长度小于64，且B和C已由存储器取至V0和V1，可由下面三条指令完成上述的运算：LD V3，AADDV V2，V0，V1MULTV V4，V2，V3并行并行冲突三条指令的不同执行方法：三条指令的不同执行方法：n全串行（1+6+1）+N-1+（1+6+1）+N-1+（1+7+1）+N-1=3N+22n前两条并后一条串（1+6+1）+N-1+（1+7+1）+N-1=2N+15n前两条并后一条链（1+6+1）+（1+7+1）+N-1=N+16采用一个屏蔽向量来控制某些向量元素参加采用一个屏蔽向量来控制某些向量元素参加运算。运算。例如：例如：do 100 i=1,64if(A(i).ne.0)thenA(i)=A(I)-B(i)endif100 continue3.条件执行语句的加速处理方法条件执行语句的加速处理方法 LD V1，Ra LD V2，Rb LD F0，#0SENSV F0，V1 ；设屏蔽向量SUBV V1，V1，V2CVM ；屏蔽向量置全1 SV Ra，V1屏蔽向量寄存器控制向量指令执行方法的缺点是：屏蔽向量寄存器控制向量指令执行方法的缺点是：1、执行时间没有少。（执行操作，但结果不、执行时间没有少。（执行操作，但结果不回送）回送）2、可能会使某些向量指令指令操作出现错误。、可能会使某些向量指令指令操作出现错误。例如：例如：if A(I)then B(i)=B(i)/A(i)解决的办法是：根据屏蔽向量既禁止将结果写解决的办法是：根据屏蔽向量既禁止将结果写入目的寄存器又禁止该操作的执行。入目的寄存器又禁止该操作的执行。n通过指标向量来指明非零元素并通过通过指标向量来指明非零元素并通过指标向量的散射指标向量的散射-聚合操作来支持稀聚合操作来支持稀疏矩阵的运算。疏矩阵的运算。4.稀疏矩阵的加速处理方法稀疏矩阵的加速处理方法4.向量归约操作的加速方法，这种方法向量归约操作的加速方法，这种方法就是将标量循环的一部件加以向量化，就是将标量循环的一部件加以向量化，并采用递归折叠的方法来加快向量归并采用递归折叠的方法来加快向量归约操作。约操作。五、向量处理性能的评估参数和方法在向量机中，执行一个向量长度为n的指令所需的时间为：Tvp=(s+l+n-1)Tc 其中s为建立流水线所需时间周期数，l为完成每对向量元素操作所需的子操作数，即流水功能部件中的级数。每对向量元素的平均执行时间为：每对向量元素的平均执行时间为：tvp=Tvp/n在评估向量流水机性能时，除了执行时间外，向量在评估向量流水机性能时，除了执行时间外，向量长度是一个很重要的评估参数。常用的评价参数长度是一个很重要的评估参数。常用的评价参数有三个：有三个：R:向量长度为无穷大时向量流水的渐近性能，常向量长度为无穷大时向量流水的渐近性能，常在评价峰值性能时使用，单位用在评价峰值性能时使用，单位用MFLOPS。n1/2：为达到一半为达到一半R值时的需的向量长度。值时的需的向量长度。nv：它表示向量流水方式工作速度优于标量串行方它表示向量流水方式工作速度优于标量串行方式工作时所需的向量长度临界值。式工作时所需的向量长度临界值。六、向量化编译技术 采用向量化编译程序将程序中存在的可并行的循环体语句用相应向量指令来表示。向量化编译器也有优化问题，通常采用：通用优化技术、向量寄存器优化技术、流水线并行化技术以及标量循环语句向量化技术。n向量n向量运算n向量处理特点n向量 相关问题n数据相关n资源相关n提高向量处理速度n并行：不冲突，取长时间n链接：数据相关，两个操作数同时到。n链接技术：利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术。n向量处理方式n纵（RR）n横（SS）n纵横 N64n向量机结构nRRnSSD=A*（B+C）LD V3,ALD V0,BLD V1,CADD V2,V0,V1MUL V4,V 2*V3ST V4,Dn向量长度N,N64.n取数:1+6+(N-1)+1n加:6+(N-1)n乘:7+(N-1)n串行：6+(N-1)+6+(N-1)+7+(N-1)n1和2,3串:6+(N-1)+7+(N-1)n1和2,3链:6+7+（N-1）n三条指令并行执行：1+7+63+1=72n1，2并行与3链接：1+7+1+63+1+6+1n1，2链接，3，4，串1+6+1+1+7+1+63+1+6+1+63+1+6+1+63n1+6+1+1+14+1+1+7+1+1+6+1+636.2与标量机相比向量流水的特点是什么？答：向量流水处理的特点是：（1）在向量操作中，每个当前结果向量元素的计算与以前结果向量元素的计算是相互独立的，这就允许向量流水线有较深的深度。（2）一条向量指令相当于一个标量循环，从面可降低对指令访问带宽的要求。此外，这也消除了由循环转移可能引起的控制相关。（3）若向量指令所要访问的向量元素均相邻，则可以在交叉存储体中高速地依次访问它们。由于一个向量中通常含有多个元素，因此对存储器访问的延迟平均到每个元素上，其访丰等待的时间开销是较小的。与标量流水机相比，向量操作要比一串标量指令操作更快，此外，向量流水机还可使访丰和有效地址计算流水化，高档的向量机还允许多个向量操作同时进行，从而可开发对不同元素进行多个向量操作的并行性。向量的工作方式有哪两种？各有何向量的工作方式有哪两种？各有何特点？特点？n向量机系统结构按向量操作对象及结果主要存放在寄存器中还中存放在存储器中,可分为存储器-存储器工作方式向量机和寄存器-寄存器工作方式向量机两大类.前者的工作特点是向量操作的源向量都取自主存且操作生成的结果向量也存放到主存中,而后都则都取自或存放到向量寄存器中。向量的加工方法有哪几种？从加工速度和需要的中间向量的加工方法有哪几种？从加工速度和需要的中间变量等方面分析各有何特点？变量等方面分析各有何特点？n向量的加方法有三种:n一种普遍采用的加工方式称为横向加工,它是按向量顺序计算的.这种加工方式需要中间寄存器，在每个向量元素的加乘运算中都会发生数据相关情况，而且当用静态流水线时，还要进行多次功能转换所以这种加工方式速度慢，不适合于向量流水处理n另一种加工方式称为垂直加工,它是先纵向加工某两个向量中元素对的加法操作,中间结果暂存到一中间向量中,然后再纵向加工所有对应元素的乘法操作.这种方式的数据相关在两条向量指令间只有一次，流水线功能只需切换一次加获得较高的吞吐率，但需要有一个暂存中间向量存储器存储器工作方式的向量机都采用这种方式n第三种加工方式是纵横向加工(或称分组加工），以寄存器寄存器方式工作的向量机都采用这种加工方式，因为向量寄存器的长度有限，当向量长度超过向量寄存器可表示的最大限度时就不得不分段处理在加工时，每组内各有两条向量指令，各组内有一次数据相关，需次流水功能切换，需个中间向量寄存器单元以及小巨型机基本都采用这种加工方式