计算机系统结构.ppt

《计算机系统结构.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构.ppt（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第六章第六章 向量流水处理向量流水处理 6.1 向量流水机的基本系统结构向量流水机的基本系统结构 向量流水处理的主要特点向量流水处理的主要特点 向量机的基本系统结构向量机的基本系统结构 向量启动时间和启动率向量启动时间和启动率6.2向量操作长度控制和向量访问步长向量操作长度控制和向量访问步长6.3 向量处理方法向量处理方法6.4增强向量处理性能的方法增强向量处理性能的方法 多功能部件的并行操作多功能部件的并行操作 链接技术链接技术 条件执行语句和稀疏矩阵和加速处理方法条件执行语句和稀疏矩阵和加速处理方法 向量归约操作的加速方法向量归约操作的加速方法6.5向量处理性能的评估参数和方法向量处理性能

2、的评估参数和方法6.6向量化编译技术向量化编译技术16.1 向量流水机的基本系统结构向量流水机的基本系统结构 前面所介绍的标量流水机在实际应用中要使性能进一步前面所介绍的标量流水机在实际应用中要使性能进一步提高，提高，通常要受到以下两个因素的约束：通常要受到以下两个因素的约束：流水线的工作时钟不可能取得很短。流水线的工作时钟不可能取得很短。取指与译码的速率受到限制，即在一个时钟周期内最取指与译码的速率受到限制，即在一个时钟周期内最多只能启动一条指令，通常称为多只能启动一条指令，通常称为Flynn瓶颈。瓶颈。6.1.1 向量流水处理的主要特点：向量流水处理的主要特点：由于每一个由于每一个当前当前

3、结果向量元素的计算结果向量元素的计算与以前与以前结果向量结果向量元素的计算是元素的计算是相互独立的相互独立的，这就允许向量流水线有较深的，这就允许向量流水线有较深的深度。深度。一条向量流水指令相当于一个标量循环，从而可降低一条向量流水指令相当于一个标量循环，从而可降低对指令访问带宽的要求，同时也消除了由循环转移起的控对指令访问带宽的要求，同时也消除了由循环转移起的控制相关。制相关。2 若向量指令所要访问的向量元素均相邻，则可以在若向量指令所要访问的向量元素均相邻，则可以在交交叉存储体叉存储体中依次访问它们。由于一个向量中通常含有多个中依次访问它们。由于一个向量中通常含有多个元素，因此对存储器访

4、问的延迟平均到每个元素上其访存元素，因此对存储器访问的延迟平均到每个元素上其访存等待时间开销较小。等待时间开销较小。由以上这些特点：由以上这些特点：向量流水机对相同数量的数据项进行操作时，要比一向量流水机对相同数量的数据项进行操作时，要比一 串标量指令操作更快。串标量指令操作更快。向量流水机还可使访存和有效地址计算流水化。向量流水机还可使访存和有效地址计算流水化。高档向量机还允许多个向量操作同时进行，从而可开高档向量机还允许多个向量操作同时进行，从而可开发对不同元素进行多个向量操作的并行性。发对不同元素进行多个向量操作的并行性。6.1.2 向量机的基本系统结构向量机的基本系统结构 向量机系统结

5、构按向量操作对象及结果主要存入在寄存向量机系统结构按向量操作对象及结果主要存入在寄存器中还是存放在存储器中，可分为器中还是存放在存储器中，可分为RR工作方式向量机和工作方式向量机和MM工作方式向量机两大类工作方式向量机两大类。3 MM方式是源向量来自于方式是源向量来自于M，结果，结果M。R R方式是源向量来自于方式是源向量来自于R，结果，结果R。不管是哪一种计算机，其典型结构见不管是哪一种计算机，其典型结构见P112图图6.1 设：设：Y=a X+Y其中其中X和和Y为向量，初始为向量，初始值放在值放在MM 中，中，a为标为标量。量。根椐表达式求解是根椐表达式求解是单单精度精度还是还是双精度操作

6、双精度操作，分别称为分别称为SAXPY或或DAXPY循环，表示单或循环，表示单或双精度的双精度的a乘以乘以X后再加后再加Y(这是一个常用循环。这是一个常用循环。设向量长度为设向量长度为64，元素，元素长度为长度为8)。4 LD F0，a ；标量；标量a装入装入F0 ADDI R4，Rx，#512 ；将向量元素的末地址装入；将向量元素的末地址装入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(R

7、y)，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为为向量取向量取指令指令 MULTV V2，F0，V1 ；向量；向量X与标量与标量a相乘相乘 LV V3

8、，RY ；装入向量；装入向量Y ADDV V4，V2，V3 ；向量加；向量加aX+Y SV RY，V4 ；存结果向量，；存结果向量，SV为为向量存向量存指令指令循循环环体体共共有有9条条指指令令5 对两程序比较，可见对两程序比较，可见 标量机共需要执行标量机共需要执行9 64+2=578条指令，而向量机仅有条指令，而向量机仅有6条指令条指令即可完成。即可完成。标量流水机中，流水线联锁标量流水机中，流水线联锁(相关停顿相关停顿)的频率远高于向量机，的频率远高于向量机，标量机中每一个元素都有标量机中每一个元素都有ADD等待等待MUL及及SD等待等待ADD的情况。而的情况。而向量机每条指令只需停顿一

9、次。向量机每条指令只需停顿一次。6.1.3 向量启动时间和启动率向量启动时间和启动率 设有一条向量指令所需时间设有一条向量指令所需时间TVP为为 TVP=Tst+n Ir (6.1)Tst：流水线启动时间；：流水线启动时间；(包括流水线固有的延迟时间包括流水线固有的延迟时间)以便设置为完以便设置为完成向量操作所需的相应参数成向量操作所需的相应参数(如向量长度等如向量长度等)。n：向量长度；：向量长度；Ir：启动率。表示一旦向量指令开始运行后，：启动率。表示一旦向量指令开始运行后，即向量流水线填满后，即向量流水线填满后，每流出一个结果所需的时间。每流出一个结果所需的时间。6 对于对于RR方式来说

10、，流水线的启动时间主要取决于功能部件流水方式来说，流水线的启动时间主要取决于功能部件流水的深度的深度。每个结果需要的钟周期数每个结果需要的钟周期数例：例：设一个向量乘法流水部件的启动时间为设一个向量乘法流水部件的启动时间为10个时钟周期，启动率个时钟周期，启动率Ir为为1，则对于长度为，则对于长度为64的向量乘法产生每个向量元素结果所需要的的向量乘法产生每个向量元素结果所需要的钟周期数为钟周期数为76.2向量操作长度控制和向量访问步长向量操作长度控制和向量访问步长 向量寄存器型向量寄存器型的向量机具有一个的向量机具有一个自然向量长度自然向量长度，即每个，即每个向量寄存器中的向量元素个数，例向量

11、寄存器中的向量元素个数，例 Cray-1机为机为64。但实。但实际程序中的向量长度往往不会与此长度相等。一个具体的际程序中的向量长度往往不会与此长度相等。一个具体的向量操作长度在编译时也常常是未知的，例如：向量操作长度在编译时也常常是未知的，例如：do 10 i=1，n10 y(i)=a x(i)+y(i)在向量长度寄存器中存放的长度值在向量长度寄存器中存放的长度值向量寄存器的长度向量寄存器的长度(MVL)的向量均可放入向量寄存器。的向量均可放入向量寄存器。向量长度向量长度向量寄存器长度时，就必须将向量长度按向向量寄存器长度时，就必须将向量长度按向量寄存器长度分段。分段后的向量长度即是每次向量

12、操作量寄存器长度分段。分段后的向量长度即是每次向量操作的长度，必须的长度，必须向量寄存器长度。向量寄存器长度。例子见例子见P148中间程序。中间程序。8 low=1 VL=(n mod MVL)*找出零头长度值找出零头长度值 do 20 j=0，(n/MVL)*外循环外循环 do 10 i=low，low+VL-1 *以长度以长度VL操作操作 V(i)=a X(i)+Y(i)*主要操作主要操作 10 continue low=low+VL *下一向量的开始下一向量的开始 VL=MVL *将长度恢复成将长度恢复成MVL 20 continue内内循循环环例例：有两个有两个100 100元素的矩阵

13、元素的矩阵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)9 向量由向量由MMR向向，则在，则在MM中中间隔间隔存放的元素在存放的元素在R向向中便成为逻中便成为逻辑上相连续的，辑上相连续的，如果向量机支持对向量的跨步访问，则称这种向量如果向量机支持对向量的跨步访问，则称这种向量机为支持完全的一维数据显式访问机为支持完全的一维数据显式访问。因为它能以行、列，甚至以对。因为它能以行、列，甚至以对角线访问这些方向上的元素，角线访问这些方向上的元

14、素，Cray-1巨型机就是这种向量机。巨型机就是这种向量机。而而MM工作方式的工作方式的Cyber205巨型机中巨型机中，则，则不支持不支持这种完全一维这种完全一维数据显式访问，它只能以连续方式访存。如果要进行跨步访问运算，数据显式访问，它只能以连续方式访存。如果要进行跨步访问运算，则必须先将这些在则必须先将这些在MM中不连续存放的向量元素，先经过运算部件中不连续存放的向量元素，先经过运算部件进行依次排序，然后再送入进行依次排序，然后再送入MM使它们相邻连续存放，最后再从使它们相邻连续存放，最后再从MM中连续取出进行运算，显然这将大降低运算性能。中连续取出进行运算，显然这将大降低运算性能。通常

15、向量机，为了增加访存速率，通常向量机，为了增加访存速率，大都采用大都采用低位地址低位地址多体交叉多体交叉MM，当向量机支持跨步长度访问时，就可能出现，当向量机支持跨步长度访问时，就可能出现对同一存储体对同一存储体访问间隔时间访问间隔时间访存周期时间访存周期时间，若使得上一次对某一存储体的访问，若使得上一次对某一存储体的访问结束前，对结束前，对同一同一存储体提出了新的访问要求，从而存储体提出了新的访问要求，从而加剧访存冲突加剧访存冲突。4010 例例：设有：设有16个存储体，访问时间为个存储体，访问时间为12个时钟周期，共要访问个时钟周期，共要访问64 个个向量元素。向量元素。对于步长为对于步长

16、为1的访问的访问，除了第一次被访问的存储体需要，除了第一次被访问的存储体需要12个周个周期外，以后每个存储体依次间隔期外，以后每个存储体依次间隔1个周期就可进行一次访问，故共个周期就可进行一次访问，故共需要需要12+63=75 个时钟周期。个时钟周期。当步长为当步长为16的倍数时的倍数时，由于每次对存储器访问将与前一次访问，由于每次对存储器访问将与前一次访问发生冲突时，因此，每一个元素的访问都需要发生冲突时，因此，每一个元素的访问都需要12 个周期，这样个周期，这样64个个元素就需要元素就需要64 12=768个周期。个周期。例：例：对于对于64个存储体个存储体，步长为，步长为32时，每隔一次

17、访问时，每隔一次访问(即两次访问即两次访问后后)就会发生一次冲突。步长为就会发生一次冲突。步长为8 时，每隔时，每隔7次访问次访问(即即8 次访问后次访问后)才会发生冲突。才会发生冲突。此外，增加存储体数目，通常也可减少产生访问冲突的频率此外，增加存储体数目，通常也可减少产生访问冲突的频率。为了使访存不发生冲突应设法使跨步和存储体数互为质数。为了使访存不发生冲突应设法使跨步和存储体数互为质数。例：存储体数为例：存储体数为17，而跨步长为，而跨步长为16。113126.3 向量处理方法向量处理方法 例例:D=A(B+C)的向量运算，的向量运算，A、D、C都是长度为都是长度为n的向量。有的向量。有

18、下列三种加工方式。下列三种加工方式。普遍采用的方法是按向量顺序计算的普遍采用的方法是按向量顺序计算的横向横向加工加工d1=a1(b1+c1)d2=a2(b2+c2)dn=an(bn+cn)这里每一步都要先进行这里每一步都要先进行bi+cik的运算，的运算，然后进行然后进行k ai di运算，运算，这就要产生数据相关。这就要产生数据相关。另一种方法是另一种方法是垂直垂直加工加工：先进行纵向加工所有先进行纵向加工所有B和和C中的元素的对应加法，即中的元素的对应加法，即bi+ciki 再进行纵向加工的乘法操作，即再进行纵向加工的乘法操作，即ki ai di13 此时向量指令表示形式变成此时向量指令表

19、示形式变成K=B+CD=A K 由此可见，由此可见，纵向加工具有较高的吞吐率纵向加工具有较高的吞吐率，但需要一个中间向量但需要一个中间向量K(具有具有k1 kn共共n个分量个分量)，在，在MM工作方式中都采用这种方式。工作方式中都采用这种方式。称为称为纵横向纵横向加工加工(或称为分组加工或称为分组加工)，以，以RR工作方式的向量机工作方式的向量机均采用此加工方式均采用此加工方式。14设设 N：向量长度：向量长度 n：向量寄存器可表示的最大限度为，则：向量寄存器可表示的最大限度为，则 N=k n+r nN，r n，k、n、r均为正整数。均为正整数。k为组数，为组数，r为余数为余数(余下的部分也作

20、为一组处理余下的部分也作为一组处理)。加工方式是加工方式是：组内纵向加工，组间为横向加工。：组内纵向加工，组间为横向加工。第一组计算第一组计算k1 n=b1 n+c1 n d1 n=a1 n k1 n 第二组计算第二组计算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个中间向量寄存器单元个中间向量寄存器单元k1 n，Cray1与一与一些小巨型机都采用这种加工方式。些小巨型机都采用这

21、种加工方式。156.4增强向量处理性能的方法增强向量处理性能的方法 共有共有4种改善向量机性能的方法。种改善向量机性能的方法。采用多功能部件，使它们并行工作采用多功能部件，使它们并行工作。加快一串相关向量指令的操作速度加快一串相关向量指令的操作速度。又称。又称链接技术链接技术，首先在，首先在Cray-1巨型机上得到应用，目前的向量机都支持这种技术。巨型机上得到应用，目前的向量机都支持这种技术。另外两种方法另外两种方法主要是为了增加以向量方式操作的循环类型主要是为了增加以向量方式操作的循环类型。这两这两种方法在许多向量机上采用种方法在许多向量机上采用。多功能部件的并行操作多功能部件的并行操作 如

22、如Cray-1巨型机中，共有巨型机中，共有4组组12个单功能流水部件，见个单功能流水部件，见P151图图6.3。第一组为向量功能部件，有向量加，移，逻辑运算第一组为向量功能部件，有向量加，移，逻辑运算3个功能部件。个功能部件。16 第二组为浮点部件，第二组为浮点部件，FADD，FMUL，浮点倒数。，浮点倒数。第三组为标量功能部件，标量，逻辑运算第三组为标量功能部件，标量，逻辑运算 移位移位 数数/计数计数4个部件。个部件。延时延时17 第四组为地址功能部件，地址加和地址乘。第四组为地址功能部件，地址加和地址乘。这些功能部件都是独立的，只要满足一定的约束条件，这些功能部件都是独立的，只要满足一定

23、的约束条件，它们可以它们可以并行操作，约束条件是并行操作，约束条件是：不存在不存在使用使用R向向的冲突的冲突。不存在不存在功能部件使用的冲突功能部件使用的冲突。R向向使用冲突使用冲突：指并行工作的向量指令中的源向量或结果向量使：指并行工作的向量指令中的源向量或结果向量使用相同的用相同的R向向。例：例：V4V1+V2 V5V2V3 功能部件冲突功能部件冲突：指多条并行工作的向量指令：指多条并行工作的向量指令共用了同一共用了同一 个功能部个功能部件。件。例：例：V3V1+V2 V6V4+V5 理想情况，若有理想情况，若有m个部件并行工作，可使运行速度提高个部件并行工作，可使运行速度提高m倍，由倍，

24、由于实际程序并行度有限和可能发生上述冲突，因此，于实际程序并行度有限和可能发生上述冲突，因此，能完全工作的能完全工作的功能部件的总数总是功能部件的总数总是m。18例例 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 而第三条指令而第三条指令与第一、二条指令均存在与第一、二条指令均存在先写后读先写后读的相关冲突，因的相关冲突，因而可将第三条指令与第一，二条指令链接执行而可将第三条指令与第一，二条指令链接执行 见图见图6.46.

25、4.2 链接技术链接技术 利用向量指令间存在的利用向量指令间存在的先写后读先写后读的数据相关性来加快指令序列执的数据相关性来加快指令序列执行速度的技术行速度的技术称为链接技术称为链接技术。19 采用采用并行和链接加速并行和链接加速技术，当被加工向量的长度为技术，当被加工向量的长度为N时，则执时，则执行时间：行时间：T=(1+6+1)+(1+7+1)+(N-1)=N+16拍拍加法和访存的延时乘法延时充满后连续流水结果数产生第1个结果的延时桌面3920 这三条指令这三条指令全部用串行方法全部用串行方法执行时则需要执行时则需要 T=(1+6+1)+N-1 2+(1+7+1)+N-1=3N+22拍拍

26、前两条并行前两条并行,第三条指令串行执行时需要第三条指令串行执行时需要 T=(1+6+1)+N-1+(1+7+1)+N-1=2N+15拍拍要指出的是要指出的是，当一条向量指令的两个源操作数分别是两条先行指，当一条向量指令的两个源操作数分别是两条先行指令的结果令的结果R向向时：时：要求先行两条指令产生的运算结果的时间必须相等要求先行两条指令产生的运算结果的时间必须相等(即有关功即有关功能部件的延迟时间相等能部件的延迟时间相等)。上例中访存和浮点加的延时均为。上例中访存和浮点加的延时均为6个时间个时间单位。单位。还要求这两条向量指令的向量长度必须相等还要求这两条向量指令的向量长度必须相等，否则就不

27、可能链，否则就不可能链接。接。可见并行加链接技术的加速效率还是较高的。可见并行加链接技术的加速效率还是较高的。要实现链接，除了要实现链接，除了前述条件之外，还有前述条件之外，还有时间上的要求时间上的要求，即：只有当前一条指令的第一，即：只有当前一条指令的第一结果分量结果分量R向向的那一个时钟周期可链接，错过该时刻，就无法进行的那一个时钟周期可链接，错过该时刻，就无法进行链接链接，只有等前一向量指令全部执行完毕，释放只有等前一向量指令全部执行完毕，释放R向向资源后，才能执资源后，才能执行后面指令。行后面指令。21 针对不同的向量机，可能还有其他特殊的限制。针对不同的向量机，可能还有其他特殊的限制

28、。例例Cray-1中允许自存储器取数操作参与链接，但不允许向存储器中允许自存储器取数操作参与链接，但不允许向存储器写数操作实现链接，因为写数操作实现链接，因为Cray-1并不提供这种链接功能。并不提供这种链接功能。6.4.3 条件执行语句和稀疏矩阵和加速处理方法条件执行语句和稀疏矩阵和加速处理方法 加快条件语句执行加快条件语句执行 程序中如有条件执行语句或进行稀疏矩阵运算时，通常会使向量程序中如有条件执行语句或进行稀疏矩阵运算时，通常会使向量处理的优点不能充分发挥。处理的优点不能充分发挥。例例:do 100 i=1，n if (A(i).ne.0)then A(i)=A(i)B(i)endif

29、 100 continue 若采用向量屏蔽控制技术，使减法在只有当若采用向量屏蔽控制技术，使减法在只有当A(i)0时才执行，就时才执行，就可使上述循循环向量化。可使上述循循环向量化。其关键时要生成一个屏蔽向量，然后借助于它来控制哪些向量元其关键时要生成一个屏蔽向量，然后借助于它来控制哪些向量元素参加运算。素参加运算。22 屏蔽向量是通过测试得到的屏蔽向量是通过测试得到的。上例中是对。上例中是对A(i)=0否进行测试。否进行测试。若若A(i)=0，屏蔽向量的相应位，屏蔽向量的相应位Z“0”；A(i)0，屏蔽向量的相应位，屏蔽向量的相应位Z“1”；清零时，清零时，VM所有位所有位Z“1”，此时后所

30、有向量指令将对所有向量元，此时后所有向量指令将对所有向量元素进行操作。素进行操作。下面给出上述循环的代码，设向量下面给出上述循环的代码，设向量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 ；将结果

31、存入；将结果存入A23 指令序列中，指令序列中，SEMSV指令为屏蔽向量生成指令；指令为屏蔽向量生成指令；CVM 为屏蔽向量寄存器为屏蔽向量寄存器Z“1”指令。指令。屏蔽向量寄存器控制向量指令执行方法的缺点是：屏蔽向量寄存器控制向量指令执行方法的缺点是：执行时间没有减少执行时间没有减少 在某些向量机中，屏蔽向量仅用来禁止向目的寄存器写入，而在某些向量机中，屏蔽向量仅用来禁止向目的寄存器写入，而相应的向量操作实际仍是进行，这会导至某些向量操作产生错误。相应的向量操作实际仍是进行，这会导至某些向量操作产生错误。例：例：if A(i)0 then B(i)=B(i)/A(i)在在A(i)=0时，仅仅

32、禁止运算结果时，仅仅禁止运算结果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)24指标向量指标向量K和和M指明指明A和和C中的非零元素中

33、的非零元素，此时要求，此时要求A和和C 中必须有中必须有相同的非零元素个数。相同的非零元素个数。除了指标向量外，也可用除了指标向量外，也可用位位向量来指明非零元素。向量来指明非零元素。支持稀疏矩阵运算的基本结构是支持稀疏矩阵运算的基本结构是指标向量的指标向量的散射散射聚合聚合操作操作(Scattergather)。聚合操作聚合操作：是概据指标向量内容选取元素，它们的地址：是概据指标向量内容选取元素，它们的地址=基址基址+指标向量中给定的相应地址偏移量获得，聚合操作后存于目的向量指标向量中给定的相应地址偏移量获得，聚合操作后存于目的向量寄存器中的结果已成为寄存器中的结果已成为稠密稠密向量。向量。

34、散射操作散射操作：借助同一指标向量将稠密向量：借助同一指标向量将稠密向量还原成稀疏还原成稀疏向量。向量。6.4.4 向量归约操作的加速方法向量归约操作的加速方法 归约归约(Reduction)操作是递推操作是递推(Recurrence)操作中的一个特殊例操作中的一个特殊例子子。归约操作一般难以向量化。归约操作一般难以向量化。例：例：25 对于上述的第二部分对于上述的第二部分递推循环递推循环，可用递归方法写出如下代码：，可用递归方法写出如下代码：len=32 do 100 j=1，6 do 200 i=1，len200 dot(i)=dot(i)+dot(i+len)len=len/2100 c

35、ontinue dot=0.0 do 10 i=1，6410 dot=dot+A(i)B(i)do 10 i=1，6410 dot(i)=A(i)B(i)应用向量乘法做应用向量乘法做MULTV dot(1:64)=A(1:64)B(1:64)dot1=0.0 do 20 i=1，6420 dot1=dot1+dot(i)递推部分递推部分37266.5向量处理性能的评估参数和方法向量处理性能的评估参数和方法 在向量流水功能部件上执行一个长度为在向量流水功能部件上执行一个长度为n的向量操作时间的向量操作时间Tvp可用可用以下公式表示：以下公式表示：Tvp=Ts+T1+(n-1)Tc=T0+n Tc

36、 (6.2)Ts：建立流水线的时间。：建立流水线的时间。T1：为第一对向量元素通过流水线时间为第一对向量元素通过流水线时间。Tc：流水线时钟周期。：流水线时钟周期。T0=Ts+T1-Tc 上式也可用下式表示：上式也可用下式表示：Tvp=sTc+lTc+(n-1)Tc=(s+l+n-1)Tc (6.3)s：建立流水线所需时钟周期数：建立流水线所需时钟周期数 l：完成每对向量元素操作所需的子操作数，即流水功能部件中的：完成每对向量元素操作所需的子操作数，即流水功能部件中的级数。级数。显然在上述流水线中，显然在上述流水线中，每对向量元素的平均执行时间是每对向量元素的平均执行时间是：27 为了表达为了

37、表达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=(s1+nl)/Rcs (6.5)Ts1：标

38、量循环建立时间。：标量循环建立时间。Tcs：标量部件工作的时钟周期。：标量部件工作的时钟周期。R：当向量长度：当向量长度时，向量流水处理的渐近性能。时，向量流水处理的渐近性能。为了衡量向量流水线中的为了衡量向量流水线中的操作有效性操作有效性，通常用半性能长度通常用半性能长度n1/2这一这一参数参数。n1/2：指为了达到向量流水线：指为了达到向量流水线最大性能值一半最大性能值一半时所需要的向量长度。时所需要的向量长度。28对于对于n个元素对，它的平均执行时间个元素对，它的平均执行时间 图图6.5给出了串行和向量流水两种操作方式的向量处理时间、处理给出了串行和向量流水两种操作方式的向量处理时间、处

39、理速率与向量长度的关系。速率与向量长度的关系。3129 在在评估评估向量流水机性能时，除了执行时间性外，向量流水机性能时，除了执行时间性外，向量长度是一个向量长度是一个很重要的参数很重要的参数。较常用的与向量长度有关的评价流水机性能的参数较常用的与向量长度有关的评价流水机性能的参数有三个有三个：R：当向量长度：当向量长度时，向量流水的渐近性能常在评价峰值时时，向量流水的渐近性能常在评价峰值时用，单位为用，单位为MFLOPS。n1/2：为达到一半为达到一半R值时所需的向量长度。是评价向量流水线值时所需的向量长度。是评价向量流水线建立时间对性能影响的参数建立时间对性能影响的参数。它表示为建立流水线

40、而导至操作损失它表示为建立流水线而导至操作损失。若若n=n1/2，表明整个向量流水线处理时间中，只有一半是有效的，表明整个向量流水线处理时间中，只有一半是有效的操作操作。通常希望向量流水线有较小的通常希望向量流水线有较小的n1/2。例：例：Cray-1向量机的向量机的 n1/2=10 20 Cyber-205向量机的向量机的 n1/2=100 表明表明Cray-1流水线建立时间比流水线建立时间比Cyber-205要小得多。要小得多。nv：表示向量流水方式的工作速度优于标量串行工作方式时，：表示向量流水方式的工作速度优于标量串行工作方式时，所需的向量长度临界值。所需的向量长度临界值。30见见P1

41、57图图6.5(a)中的中的nv值值=5。该参数既衡量建立时间，也衡量标量、向量速度比对性能的影响。该参数既衡量建立时间，也衡量标量、向量速度比对性能的影响。316.6 并行向量处理技术并行向量处理技术 并行向量处理机的通用体系结构如图并行向量处理机的通用体系结构如图6.6所示所示图图6.6 并行向量处理机的体系结构框图并行向量处理机的体系结构框图 并行向量处理机的主要特点是：并行向量处理机的主要特点是：向量处理部件数量不多，但有很向量处理部件数量不多，但有很高的处理性能；互连网络有很高的带宽和低的时延；采用大量的向高的处理性能；互连网络有很高的带宽和低的时延；采用大量的向量寄存器，而不使用量

42、寄存器，而不使用Cache；向量部件和互连网络均是定制的，价；向量部件和互连网络均是定制的，价格昂贵；向量化编程较容易。格昂贵；向量化编程较容易。32 Earth Simulator并行向量处理机由并行向量处理机由640个结点处理器组成，每个个结点处理器组成，每个结点中含有以下部件：结点中含有以下部件：8个向量处理器个向量处理器(称为称为AP，算术处理器，算术处理器)，每，每个峰值性能为个峰值性能为8 G flop/s；1个个16 GB的共享存储器；的共享存储器；1个远程访问控个远程访问控制部件制部件(RCU)；1个个I/O处理器。处理器。每个向量处理器由以下部件组成：每个向量处理器由以下部件

43、组成：1个向量部件个向量部件(内含内含8套，每套套，每套有有6个向量流水线，包括装载个向量流水线，包括装载/存储、逻辑、加存储、逻辑、加/移位、乘法、除法移位、乘法、除法以及屏蔽以及屏蔽)、72个个(256位位)向量寄存器以及向量寄存器以及17个个(256位位)屏蔽寄存器；屏蔽寄存器；1个个4路路(每个周期可发射每个周期可发射4条指令条指令)超标量处理器，配备有超标量处理器，配备有128个标量个标量寄存器以及存储容量均为寄存器以及存储容量均为64 KB的的I-Cache和和DCache；1个存储器个存储器访问控制部件。该向量处理器的结构如图访问控制部件。该向量处理器的结构如图6.7所示。所示。

44、设计并行向量处理机应遵循的要点是设计并行向量处理机应遵循的要点是：使向量和标量处理的性能使向量和标量处理的性能尽可能平衡；存储器系统应有足够的数据带宽；互连网络应有高的尽可能平衡；存储器系统应有足够的数据带宽；互连网络应有高的带宽和低的时延；应有良好的处理器规模可扩展性。带宽和低的时延；应有良好的处理器规模可扩展性。3633图图67 Earth Simulator的结点机结构的结点机结构 34 在在Earth Simulator中，每个结点中含有中，每个结点中含有32个主存部件，每个存储个主存部件，每个存储部件由部件由64个存储体组成，总的存储容量为个存储体组成，总的存储容量为16 GBps。

45、向量处理器与。向量处理器与存储部件间的数据传送速率为存储部件间的数据传送速率为32 GBps，因此一个结点机的总吞吐，因此一个结点机的总吞吐率为率为256 GBps。为了使互连网络具有高带宽和低时延，为了使互连网络具有高带宽和低时延，Earth Simulator在结点内在结点内采用带宽为采用带宽为256 GBps的单级纵横交叉开关，将的单级纵横交叉开关，将8个个AP、1个个RCU、1个个I/O部件与部件与32个个MMU(存储器部件存储器部件)互连起来。互连起来。640个结点之间用个结点之间用2 12.3GBps带宽的带宽的640 640纵横交叉开关互连。纵横交叉开关互连。Earth Simu

46、lator并行向量处理机系统的峰值性能为并行向量处理机系统的峰值性能为40.96T(1T=1万亿万亿)FLOPS(640 8 8 Gflop/s)，总的存储容量为，总的存储容量为10 TB(640 8 16 GB)，在，在TOP500排行榜的榜首位置上保持了近排行榜的榜首位置上保持了近3年年时间时间(20022005)。2003年年Cray公司推出的大规模并行向量处理机系统公司推出的大规模并行向量处理机系统CRAY x1为为了提高存储器带宽，在向量处理器和主存之间采用了了提高存储器带宽，在向量处理器和主存之间采用了Cache高速缓高速缓存。存。356.7向量化编译技术向量化编译技术 为发挥向量

47、机的功能，必须为向量机开发相应的向量化编译程序为发挥向量机的功能，必须为向量机开发相应的向量化编译程序(Vectorized Compiler)。向量化编译程序的基本功能是向量化编译程序的基本功能是：首先检测存在于循环中的并行性。首先检测存在于循环中的并行性。以相应向量指令来表示这种并行性。以相应向量指令来表示这种并行性。例：例：do 10 i=1，n A(i)=B(i)+C(i)10 continue 这在向量机中可以用一条向量加指令来等价代替这一循环。这在向量机中可以用一条向量加指令来等价代替这一循环。ADDV A(1:n)=B(1:n)+C(1:n)向量化编译器就是尽量在源程序中寻找和实

48、现这种替换向量化编译器就是尽量在源程序中寻找和实现这种替换。对条件语句这样的障碍可以用相应的控制及对条件语句这样的障碍可以用相应的控制及Where语句加以消除。语句加以消除。36 例：例：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语句的结构。语句的结构。向量化编译器也有优化问题，常用的优化方法包括向量化编译器也有优化问题，常用的优化方法包括：公共子表达式的消除及死代码的消除。公共子表达式的消除及死代码的消除。编译时调入

49、常数、复制语句传递等。编译时调入常数、复制语句传递等。除上述常规方法外，除上述常规方法外，向量化编译器还针对向量操作特征采用一些向量化编译器还针对向量操作特征采用一些特殊方法特殊方法：如：如 对对R向向进行优化分配，进行优化分配，流水链接和功能部件并行操作优化，流水链接和功能部件并行操作优化，重排执行序列以减少流水功能转换频率等。重排执行序列以减少流水功能转换频率等。对循环体的优化方法包括：对循环体的优化方法包括：将固定表达式移出循环体。将固定表达式移出循环体。归约变量消除归约变量消除和计算强度减弱和计算强度减弱(将乘法变换成加法将乘法变换成加法)等。等。37图图6.8给出了大多数向量机中所采

50、用的向量化编译优化技术。包括：给出了大多数向量机中所采用的向量化编译优化技术。包括：更高级的向量化编译器，还具有交互功能更高级的向量化编译器，还具有交互功能。允许在源程序中插入。允许在源程序中插入一些命令行以实现对诸如统计一些命令行以实现对诸如统计IF语句中语句中TRUE值的比例，从而确定值的比例，从而确定应采用压缩应采用压缩/扩展扩展(聚合聚合/扩散扩散)方法或是屏蔽控制方法来完成条件语方法或是屏蔽控制方法来完成条件语句的操作。句的操作。要说明的是要说明的是：非通用优化方法，往往是与具体向量机中所拥有的：非通用优化方法，往往是与具体向量机中所拥有的硬件资源及其功能特征有关，因此具体优化方法将