[整理]向量流水处理机教学讲义PPT课件 58页

向量流水处理机\n向量处理的基本概念向量流水处理机的结构提高向量流水处理机性能的方法2\n向量处理的基本概念从数学的概念上讲，标量是指单个量，而向量是指一组标量。例如，有一个数组A＝（a1，a2，a3，…，an），其中括号内的每一个元素ai就是一个标量。而A称为向量，它由一组标量组成。一条向量指令可以处理N个或N对操作数。我们把这N个互相独立的数叫做向量，对这样一组数的运算叫做向量处理。因此，向量指令的处理效率要比标量指令的处理效率高得多。3\n\n\n\n纵向处理法向量计算是按列的方式自上而下纵向地进行。即先是所有B和C向量元素对的相加运算，中间结果暂存到k1～kN中；然后再纵向加工所有对应元素的乘法运算。（b1＋c1）（b2＋c2）d1＝a1×d2＝a2×:dN＝aN×（bN＋cN）k1k2kN7\n纵向处理法用向量指令形式来表示，则变成：K＝B＋C  D＝K×A只需要两条指令就能实现VADDB，C，KVMULK，A，D显然，当采用流水方式计算时，数据相关在两条向量指令间仅有1次，而流水线加、乘功能的切换只需1次。因此，纵向处理方法可获得较高的吞吐率，适合于在向量处理机中应用。8\n纵横处理法当向量长度N大于向量寄存器长度n时，需要分组处理。分成k组，组内采用纵向处理方式，组间采用横向处理方式。分组方法：n=k*m+r其中：m为每组长度，r为第k+1组剩余分量Bi+CiKi(1到m)Ki*AiDi(1到m)……Bi+CiKi(m+1到2m)Ki*AiDi(m+1到2m)……9\n纵横处理法每组用两条向量指令，每组发生相关两次，其中组内发生数据相关一次，组间切换时发生相关一次。主要优点：减少访问主存储器的次数例如：中间变量K不写入主存储器10\n向量处理的基本概念向量流水处理机的结构提高向量流水处理机性能的方法11\n基本结构主存标量寄存器标量功能部件向量功能部件向量寄存器/向量缓冲器向量指令控制部件向量存取部件指令处理部件向量功能部件向量功能部件···控制部分：控制部件和缓冲部件（中间REG）标量流水：功能部件和标量寄存器(S)向量流水：功能、存取部件和寄存器(V、VM、VL)向量流水处理机的结构12\n向量流水处理机的结构按向量元素和结果存放分M-M和R-R两类。存储器－存储器结构多个独立的存储器模块并行工作处理机结构简单对存储系统的访问速度要求很高寄存器－寄存器结构运算通过向量寄存器进行需要大量高速寄存器对存储系统访问速度的要求降低13\n存储器-存储器结构向量处理机的基本思想是把两个向量的对应分量进行计算，产生一个结果向量。参加运算的向量数据在存储器中，运算的结果也送到存储器中，其结构与数据流的示意图如下图所示。如果以向量加法为例子：C=A+BABC流水线运算部件多端口存储系统一种能实现两个向量相加的流水结构的加法器14\n加法流水线部件M1M2M6AB1234C=A+Ba1b1M3M4M5c1M7M8A、B、C的向量长度为8，加法流水线分为4个功能段，主存储器采取了8个存储体多模块存储器系统的向量处理机15\n向量计算C=A+B的时空图假设一个存取周期等于两个时钟周期，并假设向量A、B、C各有8个，那么理想实现C＝A＋B向量计算的时空图如图所示。为了不发生读写冲突，各向量元素在存储模块中的位置是有意安排的。由于运算流水线分为4段，因此输入数据进入流水线4个时钟周期之后才能产生相应的输出值。当数据充满后，流水线就一直处于忙碌状态。16\n功能部件4功能部件3功能部件2功能部件1存储体M8存储体M7存储体M6存储体M5存储体M4存储体M3存储体M2存储体M10123456789101112131415t12345678123456781234567812345678RB6RB6RA8RA8WC4WC4RB5RB5RA7RA7WC3WC3RB4RB4RA6RA6WC2WC2RB3RB3RA5RA5WC1WC1RB2RB2RA4RA4RB1RB1RA3RA3RA2RA2RA1RA1WC8WC8WC7WC7WC6WC6WC5WC5RB8RB8RB7RB7C=A+B向量处理时序图17\n具有延迟缓冲器的向量流水线结构然而实际情况并非总和上述理想化的情况一样。假如结果向量C的第一个元素C1不是存放在我们想存放的模块M5而是在模块M6，那么将出现存储模块的读写冲突。为了消除争用存储器的现象，可在运算流水线的输入端和输出端增加可变延迟缓冲器，如图所示。显然，有了输入输出缓冲器，可以实现向量操作无冲突地进行存储系统可变延迟器流水处理部件可变延迟器先启动读A，再启动读B，A延迟2个时钟进入加法器18\n寄存器--寄存器结构使主存有较高带宽的另一种方法是由一级或多级中间存储器形成一个层次结构的存储器系统，其中带宽最高的这一级存储器安排在离处理器最近的位置。当处理器需要向量时，把向量从主存送到速度最快的这一级存储器。反之，运算结果也先送到速度最快的中间存储器。由于中间级存储器起着数据的中间存储作用，功能上相当于寄存器，因此称为寄存器-寄存器型向量处理机。19\n主存储器地址部件标量部件浮点部件向量部件向量寄存器V0-V7标量寄存器S0-S7地址寄存器A0-A7地址乘(6级)地址加(2级)移位(2~3级)逻辑(1级)1计数(3级)整数加(3级)浮点倒数(14级)浮点乘(7级)浮点加(6级)逻辑(2级)位移(4级)整数加(3级)Cray-1向量机结构20\n对于向量运算来说，中间存储器是8个向量寄存器(V)，每个向量寄存器有64个分量，每个分量为一个64位寄存器。执行向量指令时，流水结构运算器在一个时钟周期内从两个V寄存器得到一对操作数，完成某种操作后用一个时钟周期时间把结果送入另一个V寄存器。注意，此处的向量运算流水线是从向量寄存器而不是从主存储器获得数据。同样，从流水线输出的结果向量也是送回向量寄存器。而另一方面，主存储器与V寄存器之间的数据传送以成组传送方式进行。对标量运算来说，有两级中间存储器。速度很快的一级是8个64位的S寄存器，它是标量寄存器。主存与T寄存器之间以成组传送方式进行数据交换。21\n中间存储器的优点这种中间存储器与Cache相比的一大优点是速度快。因为CRAY-1流水运算器通过寄存器寻址方式访问中间存储器，而访问Cache必须查Cache表，这需要较长时间。22\n向量处理的基本概念向量流水处理机的结构提高向量流水处理机性能的方法23\n提高向量流水处理机性能的方法一、多功能部件并行操作二、链接技术三、分段开采技术四、向量递归技术24\n一、多功能部件并行操作对向量机中多个功能部件，使其能并行操作。并行操作条件：(1)不存在向量寄存器使用冲突不允许出现RAW、WAR、WAW、RAR相关。如：V4←V1+V2V5←V1＋V2V5←V2×V3V5←V3∧V4(2)不存在功能部件使用冲突每种功能部件一般只设置一个。如：V3←V1×V2V6←V4×V525\n二、链接技术利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术。实质上，链接技术是标量流水定向传送方法在向量寄存器中的应用。例如下面的向量加、向量乘操作：ADDV    V1，V2，V3            ；V1←V2＋V3MULV    V4，V1，V5            ；V4←V1×V526\n由于这两条指令间对V1向量寄存器存在先写后读相关，通常必须等加法指令做完后才可开始乘法指令。但如果使向量寄存器V1在同一时钟周期内，既接收一个功能部件送来的运算结果，又可把这一结果作为下一个向量指令运算所需的源操作数传送给另一个功能部件，那就可使这两个部件链接起来进行操作。通常把这种链接称为超级向量操作。当链接进入充分流水操作状态后，在1个时钟周期就可同时获取两个操作结果。27\n链接条件：(1)不存在功能部件使用冲突；(2)共用向量寄存器中向量长度、起始地址、偏移量、步长均相等；(3)参与链接的先行指令产生结果周期相同；(4)只有在先行指令产生第一结果分量的那个时钟方可链接，否则不行。适用情况：即第1条指令的结果，是第2条指令的操作数，这时，所得到的第1条指令的中间结果不必要等待全部向量元素都执行完才进行第二条指令的操作，可以将从一个流水线部件得到的结果直接送入下一个功能流水线部件的向量寄存器，形成两条指令的链接注意：不同向量机对向量指令的链接方法有所不同28\n例：用链接技术进行向量运算：D＝A×(B＋C)   假设向量长度≤64，且向量B、C已由存储器取至V0和V1。解：用下面3条向量指令可完成上述运算：LV       V3，M(A)        ；V3←A                   ADDV     V2，V0，V1      ；V2←V0＋V1                   MULV     V４，V2，V3     ；V４←V2×V3第1、2条指令无向量寄存器使用冲突，也无功能部件使用冲突，因而可以并行执行。第3条指令与第1、2条指令均存在先写后读相关冲突，因而可将第3条指令与第1、2条指令链接执行。由于同步的要求，数据进入、流出每个功能部件，包括访问储存器，都需1个时钟周期时间。29\n访存与浮点加并行，再与浮点乘链接LDV3，AADDVV2，V0，V1MULVV4，V2，V3V0V4V1V2V3132456132456浮点加浮点乘DBC访存存储器A并行和链接操作图132467530\n浮点加访存浮点乘6543216543217654321启动流出启动第一个结果流出1234567891011121314151617一个数据处理时间17第一，二条指令并行与第三条链接························31\n若三条指令串行执行，即每次只有前条指令结束，才执行后继指令，那么三条指令执行的总时间为：[(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(拍)可以看出采用并行与链接后，可以很有效的改善性能。32\n三、分段开采技术处理长向量的程序结构称为向量循环。当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段。分段开采技术一次处理一个向量段。将长向量分段成循环是系统硬件和软件控制完成的，程序员看不到这种向量分段为循环的过程，即对程序员是透明的。每经过一次循环，就处理长向量的一个段。一般在进入循环以前，根据向量长度计算出循环计数值。33\n例：A和B为长度N的向量。for(i=1;i=N/64;i++){4：VoB将B向量读入向量寄存器5：V1S1VoB数组的每个分量乘常数6：V2S2＋V1C和5B(x)相加7：AV2将结果向量存入A数组}35\n前面所讲的三种技术措施都是在单处理机结构的向量计算机上实现的。为了更有效地提高向量处理性能，新型向量机采用了多处理机系统结构。在确定的应用背景下，向量处理机系统性能应该随处理机数目的增加而线性地提高。但是系统规模的扩展性不仅涉及CPU，还涉及存储器和I／O资源，另外还要考虑价格和效率。因此，在系统设计时，力求做到处理速度、存储容量和I／O吞吐能力三者之间的平衡。否则会出现瓶颈，整个系统的效率得不到发挥。采用多处理机系统结构36\n加速向量归约操作应用举例：实现方法一：（正常方法）(1)C=A×B；--流水（向量）操作(2)对C进行递归折叠求和。--串行（循环）操作实现方法二：（加速方法）(1)C=V3×V4--流水（向量）操作(2)V0=V0+C--归约操作37\n归约实现方法：（V0←V0+C)(1)置V0各分量为0，V0和C的计数器C0、C1均为0；(2)计数器C0在t8之前保持为0，C1在每个时钟周期后加1，直到第一个结果分量出来。（8个时钟周期）（3）计数器C0在t8之后每个时钟周期加1，直到等于向量计算长度为止。38\nV00,C0V00=C0V00,C1V01=C1V00,C7V07=C7V00,C8V08=C0+C8V01,C9V09=C1+C9V07,C15V015=C7+C15V048,C56V056=C0+C8+…+C56V049,C57V057=C1+C9+…+C57V055,C63V063=C7+C15+…+C63…………t0t8t16t63…结果：V0的最后8个分量为C0至C63之和。39\n向量化编译技术一、向量化基本功能1.并行性检测是否可用向量表示。是否存在相关、条件语句、操作数的间接访问等。2.并行性表示与开发用向量指令代替循环，用屏蔽向量实现条件判断。指令系统具有向量功能，编译程序支持向量操作。40\n向量化编译技术二、向量化编译优化1.通用优化方法公共子表达式消除、常数调入、复制语句传递等。2.循环体优化固定表达式移出、归约变量消除，向量指令表示等。3.向量寄存器优化分配重新分配向量寄存器，减少向量寄存器使用冲突。4.向量指令并行化重新排序向量指令，减少流水功能转换频率，争取功能部件并行操作、向量指令链接。41\n向量处理机实例向量处理机主要出自美国和日本。美国著名的向量计算机公司有：CRAY、CDC、TI等日本公司有：NEC、Fujitsu、Hitachi等42\n向量计算机系统结构的主要优点向量计算机系统结构的主要优点(1)通过流水线方式有效提高了存储器带宽(2)流水结构的运算器有很高的性能价格比(3)非常简单的机制就能满足通信和同步要求向量处理机通常以Mflops作为速度单位。一般认为，在标量计算机中，执行一次浮点运算需要２～５条指令，平均需３条指令。43\n向量计算机系统结构的发展趋势向量计算机系统结构的发展趋势是：(1)提供多种向量运算指令。(2)除具有向量处理功能外还有其它功能。(3)采用多层次的存储器系统。(4)流水线技术与并行技术相结合。向量计算机系统结构要解决的六个技术问题(1)处理机带宽，有两条途径：运算部件采用流水线结构。用多个运算器构成并行系统。44\n(2)存储器带宽，多种解决方法：用多个独立的存储体构造大容量存储器系统。采用多层次的存储器系统提高访问速度。采用Cache和可寻址的寄存器组效果最好。采用流水线技术，存储系统的速度快5～20倍(3)输入／输出带宽，有10～29个DMA通道。(4)通信带宽，共享存储器或互连网络。(5)同步系统，多流水线结构通过控制程序使所有流水线能够同步工作。(6)多用途，例如，能够处理非数值计算问题45\n作业5.165.1746\n4．如图1－2－11所示，已知四边形ABCD是正方形，四边形ACEF是矩形，M是线段EF的中点．求证：AM∥平面BDE.\n【证明】设AC与BD的交点为O，连接OE.∵O，M分别是AC，EF的中点，四边形ACEF是矩形，∴四边形AOEM是平行四边形．∴AM∥OE.又∵OE⊂平面BDE，AM⊄平面BDE，∴AM∥平面BDE.\n如图1－2－30，在正方体ABCD－A1B1C1D1中，E，F分别是棱AB，BC的中点，O是底面ABCD的中心，求证：EF⊥平面BB1O.\n【证明】∵ABCD为正方形，∴AC⊥BO.又∵BB1⊥平面ABCD，AC⊂平面ABCD，∴AC⊥BB1，又∵BO∩BB1＝B，∴AC⊥平面BB1O，又EF是△ABC的中位线，∴EF∥AC，∴EF⊥平面BB1O.\n如图1－2－41，AB是⊙O的直径，PA垂直于⊙O所在的平面，C是圆周上异于A、B的任意一点，求证：平面PAC⊥平面PBC.\n【思路探究】由C是圆周上异于直径AB的点―→AC⊥BC―→由PA垂直于⊙O所在的平面―→PA⊥BC―→BC⊥平面PAC―→平面PAC⊥平面PBC.\n【自主解答】连接AC，BC，则BC⊥AC，又PA⊥平面ABC，∴PA⊥BC，而PA∩AC＝A，∴BC⊥平面PAC，又BC⊂平面PBC，∴平面PAC⊥平面PBC.\n面面垂直的判定定理是证明面面垂直的常用方法，即要证面面垂直，只需转证线面垂直，关键是在其中一个平面内寻找一直线与另一个平面垂直．\n如图1－2－42，在四棱锥P－ABCD中，底面为正方形，侧棱PA＝PC.求证：平面PAC⊥平面PBD.\n【证明】设AC∩BD＝O，连接PO，因为PA＝PC，所以PO⊥AC，又因为四边形ABCD为正方形，所以BD⊥AC，因为PO，BD⊂平面PBD，PO∩BD＝O，所以AC⊥平面PBD.因为AC⊂平面PAC，所以平面PAC⊥平面PBD.\n4．如图1－2－47，四棱锥P－ABCD中，PA⊥平面ABCD，底面ABCD为直角梯形，AB⊥AD，CD⊥AD，求证：平面PDC⊥平面PAD.\n【证明】∵PA⊥平面ABCD，∴PA⊥CD，又CD⊥AD，PA∩AD＝A，∴CD⊥平面PAD.又CD⊂平面PDC，∴平面PDC⊥平面PAD.