《计算机系统结构.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构.ppt（41页珍藏版）》请在三一办公上搜索。
1、1,第六章 向量流水处理 6.1 向量流水机的基本系统结构 向量流水处理的主要特点 向量机的基本系统结构 向量启动时间和启动率6.2向量操作长度控制和向量访问步长6.3 向量处理方法6.4增强向量处理性能的方法 多功能部件的并行操作 链接技术 条件执行语句和稀疏矩阵和加速处理方法 向量归约操作的加速方法6.5向量处理性能的评估参数和方法6.6向量化编译技术,2,6.1 向量流水机的基本系统结构 前面所介绍的标量流水机在实际应用中要使性能进一步提高，通常要受到以下两个因素的约束：流水线的工作时钟不可能取得很短。取指与译码的速率受到限制，即在一个时钟周期内最多只能启动一条指令，通常称为Flynn瓶
2、颈。6.1.1 向量流水处理的主要特点：由于每一个当前结果向量元素的计算与以前结果向量元素的计算是相互独立的，这就允许向量流水线有较深的深度。一条向量流水指令相当于一个标量循环，从而可降低对指令访问带宽的要求，同时也消除了由循环转移起的控制相关。,3,若向量指令所要访问的向量元素均相邻，则可以在交叉存储体中依次访问它们。由于一个向量中通常含有多个元素，因此对存储器访问的延迟平均到每个元素上其访存等待时间开销较小。由以上这些特点：向量流水机对相同数量的数据项进行操作时，要比一 串标量指令操作更快。向量流水机还可使访存和有效地址计算流水化。高档向量机还允许多个向量操作同时进行，从而可开发对不同元素
3、进行多个向量操作的并行性。6.1.2 向量机的基本系统结构 向量机系统结构按向量操作对象及结果主要存入在寄存器中还是存放在存储器中，可分为RR工作方式向量机和MM工作方式向量机两大类。,4,MM方式是源向量来自于M，结果M。R R方式是源向量来自于R，结果R。不管是哪一种计算机，其典型结构见P112图6.1,设：Y=aX+Y其中X和Y为向量，初始值放在MM 中，a为标量。根椐表达式求解是单精度还是双精度操作，分别称为SAXPY或DAXPY循环，表示单或双精度的a乘以X后再加Y(这是一个常用循环。设向量长度为64，元素长度为8)。,5,LD F0，a；标量a装入F0 ADDI R4，Rx，#51
4、2；将向量元素的末地址装入R4中LOOP：LD F2，0(Rx)；取向量元素x(i)MULD F2，F0，F2；a与x(i)相乘 LD F4，0(Ry)；取向量元素y(i)ADDD F4，F2，F4；ax(i)与y(i)相加 SD 0(Ry)，F4；存结果向量元素 ADDI Rx，Rx，#8；增量向量元素x下标 ADDI Ry，Ry，#8；增量向量元素y下标 SUB R20，R4，Rx；R4-RxR20，计算是否到达限界值 BNZ R20，LOOP；若循环未结束，转LOOP 若用向量机来完成同样操作，则有：LD F0，a；标量a装入F0 LV V1，Rx；装入向量X，LV为向量取指令 MULT
5、V V2，F0，V1；向量X与标量a相乘 LV V3，RY；装入向量Y ADDV V4，V2，V3；向量加aX+Y SV RY，V4；存结果向量，SV为向量存指令,6,对两程序比较，可见 标量机共需要执行964+2=578条指令，而向量机仅有6条指令即可完成。标量流水机中，流水线联锁(相关停顿)的频率远高于向量机，标量机中每一个元素都有ADD等待MUL及SD等待ADD的情况。而向量机每条指令只需停顿一次。6.1.3 向量启动时间和启动率 设有一条向量指令所需时间TVP为 TVP=Tst+nIr(6.1)Tst：流水线启动时间；(包括流水线固有的延迟时间)以便设置为完成向量操作所需的相应参数(如
6、向量长度等)。n：向量长度；Ir：启动率。表示一旦向量指令开始运行后，即向量流水线填满后，每流出一个结果所需的时间。,7,对于RR方式来说，流水线的启动时间主要取决于功能部件流水的深度。,每个结果需要的钟周期数,例：设一个向量乘法流水部件的启动时间为10个时钟周期，启动率Ir为1，则对于长度为64的向量乘法产生每个向量元素结果所需要的钟周期数为,8,6.2向量操作长度控制和向量访问步长 向量寄存器型的向量机具有一个自然向量长度，即每个向量寄存器中的向量元素个数，例 Cray-1机为64。但实际程序中的向量长度往往不会与此长度相等。一个具体的向量操作长度在编译时也常常是未知的，例如：do 10
7、i=1，n10 y(i)=ax(i)+y(i)在向量长度寄存器中存放的长度值向量寄存器的长度(MVL)的向量均可放入向量寄存器。向量长度向量寄存器长度时，就必须将向量长度按向量寄存器长度分段。分段后的向量长度即是每次向量操作的长度，必须向量寄存器长度。例子见P148中间程序。,9,low=1 VL=(n mod MVL)*找出零头长度值 do 20 j=0，(n/MVL)*外循环 do 10 i=low，low+VL-1*以长度VL操作 V(i)=aX(i)+Y(i)*主要操作 10 continue low=low+VL*下一向量的开始 VL=MVL*将长度恢复成MVL 20 continu
8、e,内循环,例：有两个100100元素的矩阵A和B相乘的程序段如下：do 10 i=1，100 do 10 j=1，100C(i，j)=0.0 do 10 k=1，100 10 C(i，j)=C(i，j)+A(i，k)B(k，j),10,向量由MMR向，则在MM中间隔存放的元素在R向中便成为逻辑上相连续的，如果向量机支持对向量的跨步访问，则称这种向量机为支持完全的一维数据显式访问。因为它能以行、列，甚至以对角线访问这些方向上的元素，Cray-1巨型机就是这种向量机。而MM工作方式的Cyber205巨型机中，则不支持这种完全一维数据显式访问，它只能以连续方式访存。如果要进行跨步访问运算，则必须先
9、将这些在MM中不连续存放的向量元素，先经过运算部件进行依次排序，然后再送入MM使它们相邻连续存放，最后再从MM中连续取出进行运算，显然这将大降低运算性能。通常向量机，为了增加访存速率，大都采用低位地址多体交叉MM，当向量机支持跨步长度访问时，就可能出现对同一存储体访问间隔时间访存周期时间，若使得上一次对某一存储体的访问结束前，对同一存储体提出了新的访问要求，从而加剧访存冲突。,40,11,例：设有16个存储体，访问时间为12个时钟周期，共要访问64 个向量元素。对于步长为1的访问，除了第一次被访问的存储体需要12个周期外，以后每个存储体依次间隔1个周期就可进行一次访问，故共需要12+63=75
10、 个时钟周期。当步长为16的倍数时，由于每次对存储器访问将与前一次访问发生冲突时，因此，每一个元素的访问都需要12 个周期，这样64个元素就需要6412=768个周期。例：对于64个存储体，步长为32时，每隔一次访问(即两次访问后)就会发生一次冲突。步长为8 时，每隔7次访问(即8 次访问后)才会发生冲突。此外，增加存储体数目，通常也可减少产生访问冲突的频率。,为了使访存不发生冲突应设法使跨步和存储体数互为质数。,例：存储体数为17，而跨步长为16。,12,3,13,6.3 向量处理方法 例:D=A(B+C)的向量运算，A、D、C都是长度为n的向量。有下列三种加工方式。普遍采用的方法是按向量顺
11、序计算的横向加工d1=a1(b1+c1)d2=a2(b2+c2),dn=an(bn+cn)这里每一步都要先进行bi+cik的运算，然后进行kai di运算，这就要产生数据相关。另一种方法是垂直加工：先进行纵向加工所有B和C中的元素的对应加法，即bi+ciki 再进行纵向加工的乘法操作，即kiai di,14,此时向量指令表示形式变成K=B+CD=AK,由此可见，纵向加工具有较高的吞吐率，但需要一个中间向量K(具有k1kn共n个分量)，在MM工作方式中都采用这种方式。,称为纵横向加工(或称为分组加工)，以RR工作方式的向量机均采用此加工方式。,15,设 N：向量长度 n：向量寄存器可表示的最大限
12、度为，则 N=kn+r nN，r n，k、n、r均为正整数。k为组数，r为余数(余下的部分也作为一组处理)。加工方式是：组内纵向加工，组间为横向加工。第一组计算k1n=b1n+c1n d1n=a1nk1n 第二组计算k(n+1)2n=b(n+1)2n+c(n+1)2n d(n+1)2n=a(n+1)2n k(n+1)2n,由此可知，每组内各有两条向量指令，各组内有一次数据相关需2次流水功能切换，只需n个中间向量寄存器单元k1n，Cray1与一些小巨型机都采用这种加工方式。,16,6.4增强向量处理性能的方法 共有4种改善向量机性能的方法。采用多功能部件，使它们并行工作。加快一串相关向量指令的操
13、作速度。又称链接技术，首先在Cray-1巨型机上得到应用，目前的向量机都支持这种技术。另外两种方法主要是为了增加以向量方式操作的循环类型。这两种方法在许多向量机上采用。多功能部件的并行操作 如Cray-1巨型机中，共有4组12个单功能流水部件，见P151图6.3。第一组为向量功能部件，有向量加，移，逻辑运算3个功能部件。,17,第二组为浮点部件，FADD，FMUL，浮点倒数。第三组为标量功能部件，标量，逻辑运算 移位 数/计数4个部件。,延时,18,第四组为地址功能部件，地址加和地址乘。这些功能部件都是独立的，只要满足一定的约束条件，它们可以并行操作，约束条件是：不存在使用R向的冲突。不存在功
14、能部件使用的冲突。R向使用冲突：指并行工作的向量指令中的源向量或结果向量使用相同的R向。例：V4V1+V2 V5V2V3 功能部件冲突：指多条并行工作的向量指令共用了同一 个功能部件。例：V3V1+V2 V6V4+V5,理想情况，若有m个部件并行工作，可使运行速度提高m倍，由于实际程序并行度有限和可能发生上述冲突，因此，能完全工作的功能部件的总数总是m。,19,例 ADDV V1，V2，V3 MULTV V4，V1，V5例 D=A(B+C)设向量长度64，B和C已由MMV0和V1，则 LD V3，A ADDV V2，V0，V1 MULTV V4，V2，V3 而第三条指令与第一、二条指令均存在先
15、写后读的相关冲突，因而可将第三条指令与第一，二条指令链接执行 见图6.4,6.4.2 链接技术,利用向量指令间存在的先写后读的数据相关性来加快指令序列执行速度的技术称为链接技术。,20,采用并行和链接加速技术，当被加工向量的长度为N时，则执行时间：T=(1+6+1)+(1+7+1)+(N-1)=N+16拍,加法和访存的延时,乘法延时,充满后连续流水结果数,产生第1个结果的延时,桌面,39,21,这三条指令全部用串行方法执行时则需要 T=(1+6+1)+N-12+(1+7+1)+N-1=3N+22拍 前两条并行,第三条指令串行执行时需要 T=(1+6+1)+N-1+(1+7+1)+N-1=2N+
16、15拍,要指出的是，当一条向量指令的两个源操作数分别是两条先行指令的结果R向时：要求先行两条指令产生的运算结果的时间必须相等(即有关功能部件的延迟时间相等)。上例中访存和浮点加的延时均为6个时间单位。还要求这两条向量指令的向量长度必须相等，否则就不可能链接。,可见并行加链接技术的加速效率还是较高的。要实现链接，除了前述条件之外，还有时间上的要求，即：只有当前一条指令的第一结果分量R向的那一个时钟周期可链接，错过该时刻，就无法进行链接，只有等前一向量指令全部执行完毕，释放R向资源后，才能执行后面指令。,22,针对不同的向量机，可能还有其他特殊的限制。例Cray-1中允许自存储器取数操作参与链接，
17、但不允许向存储器写数操作实现链接，因为Cray-1并不提供这种链接功能。6.4.3 条件执行语句和稀疏矩阵和加速处理方法 加快条件语句执行 程序中如有条件执行语句或进行稀疏矩阵运算时，通常会使向量处理的优点不能充分发挥。例:do 100 i=1，n if(A(i).ne.0)then A(i)=A(i)B(i)endif 100 continue 若采用向量屏蔽控制技术，使减法在只有当A(i)0时才执行，就可使上述循循环向量化。,其关键时要生成一个屏蔽向量，然后借助于它来控制哪些向量元素参加运算。,23,屏蔽向量是通过测试得到的。上例中是对A(i)=0否进行测试。若A(i)=0，屏蔽向量的相应
18、位Z“0”；A(i)0，屏蔽向量的相应位Z“1”；清零时，VM所有位Z“1”，此时后所有向量指令将对所有向量元素进行操作。下面给出上述循环的代码，设向量A和B的起始地址放在Ra和Rb中。LV V1，Ra；将向量A装入V1 LV V2，Rb；将向量B装入V2 LD F0，#0；将浮点0装入F0 SENSV F0，V1；若V1(i)F0，则将VMi置为1 SUBV V1，V1，V2；在屏蔽向量控制下进行减法操作 CVM；将屏蔽向量寄存器置为全1 SV Ra，V1；将结果存入A,24,指令序列中，SEMSV指令为屏蔽向量生成指令；CVM 为屏蔽向量寄存器Z“1”指令。屏蔽向量寄存器控制向量指令执行方
19、法的缺点是：执行时间没有减少 在某些向量机中，屏蔽向量仅用来禁止向目的寄存器写入，而相应的向量操作实际仍是进行，这会导至某些向量操作产生错误。例：if A(i)0 then B(i)=B(i)/A(i)在A(i)=0时，仅仅禁止运算结果B(i)/A(i)B(i)，但没有禁止B(i)/A(i)运算的进行，这就导致除数为0的非法运算。比较好的方案是：根椐禁止向量，既禁止将结果写入目的寄存器，也禁止该操作执行。加快稀疏矩阵执行速度例：例：有一个典型的稀疏矩阵运算，常见如下代码段：do 100 i=1，n 100 A(K(i)=A(K(i)+C(M(i),25,指标向量K和M指明A和C中的非零元素，此
20、时要求A和C 中必须有相同的非零元素个数。除了指标向量外，也可用位向量来指明非零元素。支持稀疏矩阵运算的基本结构是指标向量的散射聚合操作(Scattergather)。聚合操作：是概据指标向量内容选取元素，它们的地址=基址+指标向量中给定的相应地址偏移量获得，聚合操作后存于目的向量寄存器中的结果已成为稠密向量。散射操作：借助同一指标向量将稠密向量还原成稀疏向量。6.4.4 向量归约操作的加速方法 归约(Reduction)操作是递推(Recurrence)操作中的一个特殊例子。归约操作一般难以向量化。例：,26,对于上述的第二部分递推循环，可用递归方法写出如下代码：len=32 do 100
21、j=1，6 do 200 i=1，len200 dot(i)=dot(i)+dot(i+len)len=len/2100 continue,dot=0.0 do 10 i=1，6410 dot=dot+A(i)B(i),37,27,6.5向量处理性能的评估参数和方法 在向量流水功能部件上执行一个长度为n的向量操作时间Tvp可用以下公式表示：Tvp=Ts+T1+(n-1)Tc=T0+n Tc(6.2)Ts：建立流水线的时间。T1：为第一对向量元素通过流水线时间。Tc：流水线时钟周期。T0=Ts+T1-Tc 上式也可用下式表示：Tvp=sTc+lTc+(n-1)Tc=(s+l+n-1)Tc(6.3
22、)s：建立流水线所需时钟周期数 l：完成每对向量元素操作所需的子操作数，即流水功能部件中的级数。,显然在上述流水线中，每对向量元素的平均执行时间是：,28,为了表达n1/2的含义，可将Tvp改成 Tvp=(n1/2+n)Tc=(n1/2+n)/R(6.4)由(6.2)和(6.4)两式可知 Tvp=T0+n Tc=(n1/2+n)Tc 所以 n1/2=T0/Tc 由(6.3)和(6.4)两式可知(n1/2+n)Tc=(s+l+n-1)Tc 所以 n1/2=s+l-1 因此 n1/2=T0/Tc=s+l-1 对于串行方式工作的标量处理机，完成同样的向量操作所需时间Tsp为Tsp=Ts1+nlTcs
23、=(s1+nl)/Rcs(6.5)Ts1：标量循环建立时间。Tcs：标量部件工作的时钟周期。,R：当向量长度时，向量流水处理的渐近性能。为了衡量向量流水线中的操作有效性，通常用半性能长度n1/2这一参数。,n1/2：指为了达到向量流水线最大性能值一半时所需要的向量长度。,29,对于n个元素对，它的平均执行时间,图6.5给出了串行和向量流水两种操作方式的向量处理时间、处理速率与向量长度的关系。,31,30,在评估向量流水机性能时，除了执行时间性外，向量长度是一个很重要的参数。较常用的与向量长度有关的评价流水机性能的参数有三个：R：当向量长度时，向量流水的渐近性能常在评价峰值时用，单位为MFLOP
24、S。n1/2：为达到一半R值时所需的向量长度。是评价向量流水线建立时间对性能影响的参数。它表示为建立流水线而导至操作损失。,若n=n1/2，表明整个向量流水线处理时间中，只有一半是有效的操作。,通常希望向量流水线有较小的n1/2。例：Cray-1向量机的 n1/2=1020 Cyber-205向量机的 n1/2=100 表明Cray-1流水线建立时间比Cyber-205要小得多。nv：表示向量流水方式的工作速度优于标量串行工作方式时，所需的向量长度临界值。,31,见P157图6.5(a)中的nv值=5。该参数既衡量建立时间，也衡量标量、向量速度比对性能的影响。,32,6.6 并行向量处理技术
25、并行向量处理机的通用体系结构如图6.6所示,图6.6 并行向量处理机的体系结构框图,并行向量处理机的主要特点是：向量处理部件数量不多，但有很高的处理性能；互连网络有很高的带宽和低的时延；采用大量的向量寄存器，而不使用Cache；向量部件和互连网络均是定制的，价格昂贵；向量化编程较容易。,33,Earth Simulator并行向量处理机由640个结点处理器组成，每个结点中含有以下部件：8个向量处理器(称为AP，算术处理器)，每个峰值性能为8 G flop/s；1个16 GB的共享存储器；1个远程访问控制部件(RCU)；1个I/O处理器。每个向量处理器由以下部件组成：1个向量部件(内含8套，每套
26、有6个向量流水线，包括装载/存储、逻辑、加/移位、乘法、除法以及屏蔽)、72个(256位)向量寄存器以及17个(256位)屏蔽寄存器；1个4路(每个周期可发射4条指令)超标量处理器，配备有128个标量寄存器以及存储容量均为64 KB的I-Cache和DCache；1个存储器访问控制部件。该向量处理器的结构如图6.7所示。,设计并行向量处理机应遵循的要点是：使向量和标量处理的性能尽可能平衡；存储器系统应有足够的数据带宽；互连网络应有高的带宽和低的时延；应有良好的处理器规模可扩展性。36,34,图67 Earth Simulator的结点机结构,35,在Earth Simulator中，每个结点中
27、含有32个主存部件，每个存储部件由64个存储体组成，总的存储容量为16 GBps。向量处理器与存储部件间的数据传送速率为32 GBps，因此一个结点机的总吞吐率为256 GBps。为了使互连网络具有高带宽和低时延，Earth Simulator在结点内采用带宽为256 GBps的单级纵横交叉开关，将8个AP、1个RCU、1个I/O部件与32个MMU(存储器部件)互连起来。640个结点之间用212.3GBps带宽的640640纵横交叉开关互连。Earth Simulator并行向量处理机系统的峰值性能为40.96T(1T=1万亿)FLOPS(64088 Gflop/s)，总的存储容量为10 TB
28、(640816 GB)，在TOP500排行榜的榜首位置上保持了近3年时间(20022005)。2003年Cray公司推出的大规模并行向量处理机系统CRAY x1为了提高存储器带宽，在向量处理器和主存之间采用了Cache高速缓存。,36,6.7向量化编译技术 为发挥向量机的功能，必须为向量机开发相应的向量化编译程序(Vectorized Compiler)。向量化编译程序的基本功能是：首先检测存在于循环中的并行性。以相应向量指令来表示这种并行性。例：do 10 i=1，n A(i)=B(i)+C(i)10 continue 这在向量机中可以用一条向量加指令来等价代替这一循环。ADDV A(1:n
29、)=B(1:n)+C(1:n),向量化编译器就是尽量在源程序中寻找和实现这种替换。,对条件语句这样的障碍可以用相应的控制及Where语句加以消除。,37,例：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语句的结构。,向量化编译器也有优化问题，常用的优化方法包括：公共子表达式的消除及死代码的消除。编译时调入常数、复制语句传递等。,除上述常规方法外，向量化编译器还针对向量操作特征采用一些特殊方法：如 对R向进行优化分配，流水链接和功能部件并行操作优化，重排执行
30、序列以减少流水功能转换频率等。,对循环体的优化方法包括：将固定表达式移出循环体。归约变量消除和计算强度减弱(将乘法变换成加法)等。,38,图6.8给出了大多数向量机中所采用的向量化编译优化技术。包括：,更高级的向量化编译器，还具有交互功能。允许在源程序中插入一些命令行以实现对诸如统计IF语句中TRUE值的比例，从而确定应采用压缩/扩展(聚合/扩散)方法或是屏蔽控制方法来完成条件语句的操作。要说明的是：非通用优化方法，往往是与具体向量机中所拥有的硬件资源及其功能特征有关，因此具体优化方法将因机而异。,图6.8 商品化向量机的优化编译技术,39,图6.8 商品化向量机的优化编译技术,优化目标码,40,第1个结果存入结果单元,从存储单元取数时间,中间结果存数时间,取中间结果时间,20,41,ai,j在数组中位置公式是k=(i-1)n+j。例a2,3位置k=(2-1)4+3=7,ai,j在数组中位置公式是k=(j-1)m+i。例a2,3位置k=(3-1)3+2=8,10,
