计算机系统结构ppt课件

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

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

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

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

5、。的并行性。6.1.2 向量机的基本系统结构向量机的基本系统结构 向量机系统结构按向量操作对象及结果主要存入在寄存器中还是存放在存储器中，可分向量机系统结构按向量操作对象及结果主要存入在寄存器中还是存放在存储器中，可分为为RR工作方式向量机和工作方式向量机和MM工作方式向量机两大类。工作方式向量机两大类。4 MM方式是源向量来自于方式是源向量来自于M，结果，结果M。 R R方式是源向量来自于方式是源向量来自于R，结果，结果R。 不管是哪一种计算机，其典型结构见不管是哪一种计算机，其典型结构见P112图图6.1 设：设：Y= a X+Y其中其中X和和Y为向量，初始值放在为向量，初始值放在MM 中

6、，中，a为标量。为标量。 根椐表达式求解是单精度还根椐表达式求解是单精度还是双精度操作，分别称为是双精度操作，分别称为SAXPY或或DAXPY循环，表示单循环，表示单或双精度的或双精度的a乘以乘以X后再加后再加Y(这是这是一个常用循环。设向量长度为一个常用循环。设向量长度为64，元素长度为元素长度为8)。5 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) ；取向量元素

7、；取向量元素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，L

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

9、量机中每一个元素都有有ADD等待等待MUL及及SD等待等待ADD的情况。而向量机每条指令只需停顿一次。的情况。而向量机每条指令只需停顿一次。6.1.3 向量启动时间和启动率向量启动时间和启动率 设有一条向量指令所需时间设有一条向量指令所需时间TVP为为 TVP=Tst+n Ir (6.1)Tst：流水线启动时间；：流水线启动时间； (包括流水线固有的延迟时间包括流水线固有的延迟时间)以便设置为完成向量操作所需的相应以便设置为完成向量操作所需的相应参数参数(如向量长度等如向量长度等)。 n：向量长度；：向量长度；Ir：启动率。表示一旦向量指令开始运行后，即向量流水线填满后，每流出一个结果所需：启

10、动率。表示一旦向量指令开始运行后，即向量流水线填满后，每流出一个结果所需的时间。的时间。 7 对于对于RR方式来说，流水线的启动时间主要取决于功能部件流水的深度。方式来说，流水线的启动时间主要取决于功能部件流水的深度。每个结果需要的钟周期数每个结果需要的钟周期数1616464106464.ITrst 向向量量长长度度总总的的执执行行时时间间例：设一个向量乘法流水部件的启动时间为例：设一个向量乘法流水部件的启动时间为10个时钟周期，启动率个时钟周期，启动率Ir为为1，则对于长度为，则对于长度为64的向量乘法产生每个向量元素结果所需要的钟周期数为的向量乘法产生每个向量元素结果所需要的钟周期数为86

11、.2向量操作长度控制和向量访问步长向量操作长度控制和向量访问步长 向量寄存器型的向量机具有一个自然向量长度，即每个向量寄存器中的向量元素个数，向量寄存器型的向量机具有一个自然向量长度，即每个向量寄存器中的向量元素个数，例例 Cray- -1机为机为64。但实际程序中的向量长度往往不会与此长度相等。一个具体的向量操。但实际程序中的向量长度往往不会与此长度相等。一个具体的向量操作长度在编译时也常常是未知的，例如：作长度在编译时也常常是未知的，例如： do 10 i=1，n10 y(i)=a x(i)+y(i) 在向量长度寄存器中存放的长度值在向量长度寄存器中存放的长度值向量寄存器的长度向量寄存器的

12、长度(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)=a X(i)+Y(i)

13、* 主要操作主要操作 10 continue low=low+VL * 下一向量的开始下一向量的开始 VL=MVL * 将长度恢复成将长度恢复成MVL 20 continue内循内循环环例：例： 有两个有两个100 100元素的矩阵元素的矩阵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向向中便成为逻辑上相连续的，如果中便成为逻辑上相连续的，如果向量机支

14、持对向量的跨步访问，则称这种向量机为支持完全的一维数据显式访问。因为它向量机支持对向量的跨步访问，则称这种向量机为支持完全的一维数据显式访问。因为它能以行、列，甚至以对角线访问这些方向上的元素，能以行、列，甚至以对角线访问这些方向上的元素， Cray- -1巨型机就是这种向量机。巨型机就是这种向量机。 而而MM工作方式的工作方式的Cyber205巨型机中，则不支持这种完全一维数据显式访问，它只能巨型机中，则不支持这种完全一维数据显式访问，它只能以连续方式访存。如果要进行跨步访问运算，则必须先将这些在以连续方式访存。如果要进行跨步访问运算，则必须先将这些在MM中不连续存放的向中不连续存放的向量元

15、素，先经过运算部件进行依次排序，然后再送入量元素，先经过运算部件进行依次排序，然后再送入MM使它们相邻连续存放，最后再使它们相邻连续存放，最后再从从MM中连续取出进行运算，显然这将大降低运算性能。中连续取出进行运算，显然这将大降低运算性能。 通常向量机，为了增加访存速率，大都采用通常向量机，为了增加访存速率，大都采用低位地址低位地址多体交叉多体交叉MM ，当向量机支持跨，当向量机支持跨步长度访问时，就可能出现对同一存储体访问间隔时间步长度访问时，就可能出现对同一存储体访问间隔时间访存周期时间，若使得上一次对访存周期时间，若使得上一次对某一存储体的访问结束前，对同一存储体提出了新的访问要求，从而

16、加剧访存冲突。某一存储体的访问结束前，对同一存储体提出了新的访问要求，从而加剧访存冲突。4011 例：设有例：设有16个存储体，访问时间为个存储体，访问时间为12个时钟周期，共要访问个时钟周期，共要访问64 个向量元素。个向量元素。 对于步长为对于步长为1的访问，除了第一次被访问的存储体需要的访问，除了第一次被访问的存储体需要12个周期外，以后每个存储体个周期外，以后每个存储体依次间隔依次间隔1个周期就可进行一次访问，故共需要个周期就可进行一次访问，故共需要12+63=75 个时钟周期。个时钟周期。 当步长为当步长为16的倍数时，由于每次对存储器访问将与前一次访问发生冲突时，因此，的倍数时，由

17、于每次对存储器访问将与前一次访问发生冲突时，因此，每一个元素的访问都需要每一个元素的访问都需要12 个周期，这样个周期，这样64个元素就需要个元素就需要64 12=768个周期。个周期。 例：例：对于对于64个存储体个存储体，步长为，步长为32时，每隔一次访问时，每隔一次访问(即两次访问后即两次访问后)就会发生一次冲突。就会发生一次冲突。步长为步长为8 时，每隔时，每隔7次访问次访问(即即8 次访问后次访问后)才会发生冲突。才会发生冲突。 此外，增加存储体数目，通常也可减少产生访问冲突的频率。此外，增加存储体数目，通常也可减少产生访问冲突的频率。 为了使访存不发生冲突应设法使跨步和存储体数互为

18、质数。为了使访存不发生冲突应设法使跨步和存储体数互为质数。 例：存储体数为例：存储体数为17，而跨步长为，而跨步长为16。 123136.3 向量处理方法向量处理方法 例例: D=A (B+C)的向量运算，的向量运算，A、D、C都是长度为都是长度为n的向量。有下列三种加工方式。的向量。有下列三种加工方式。 普遍采用的方法是按向量顺序计算的横向加工普遍采用的方法是按向量顺序计算的横向加工d1=a1 (b1+c1)d2=a2 (b2+c2)dn=an (bn+cn) 这里每一步都要先进行这里每一步都要先进行bi+cik的运算，的运算，然后进行然后进行k ai di运算，运算，这就要产生数据相关。这

19、就要产生数据相关。 另一种方法是垂直加工：另一种方法是垂直加工： 先进行纵向加工所有先进行纵向加工所有B和和C中的元素的对应加法，即中的元素的对应加法，即bi+ciki 再进行纵向加工的乘法操作，即再进行纵向加工的乘法操作，即ki ai di14 此时向量指令表示形式变成此时向量指令表示形式变成K=B+CD=A K 由此可见，纵向加工具有较高的吞吐率，但需要一个中间向量由此可见，纵向加工具有较高的吞吐率，但需要一个中间向量K(具有具有k1 kn共共n个分量个分量)，在在MM工作方式中都采用这种方式。工作方式中都采用这种方式。 称为纵横向加工称为纵横向加工(或称为分组加工或称为分组加工)，以，以

20、RR工作方式的向量机均采用此加工方式。工作方式的向量机均采用此加工方式。15设设 N：向量长度：向量长度 n：向量寄存器可表示的最大限度为，则：向量寄存器可表示的最大限度为，则 N=k n+r nN， r n，k、n、r均为正整数。均为正整数。 k为组数，为组数，r为余数为余数(余下的部分也作为一组处理余下的部分也作为一组处理)。 加工方式是：组内纵向加工，组间为横向加工。加工方式是：组内纵向加工，组间为横向加工。 第一组计算第一组计算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)

21、 2n =a(n+1) 2n k(n+1) 2n 由此可知，每组内各有两条向量指令，各组内有一次数据相关需由此可知，每组内各有两条向量指令，各组内有一次数据相关需2次流水功能切换，只次流水功能切换，只需需n个中间向量寄存器单元个中间向量寄存器单元k1 n，Cray1与一些小巨型机都采用这种加工方式。与一些小巨型机都采用这种加工方式。166.4增强向量处理性能的方法增强向量处理性能的方法 共有共有4种改善向量机性能的方法。种改善向量机性能的方法。 采用多功能部件，使它们并行工作。采用多功能部件，使它们并行工作。 加快一串相关向量指令的操作速度。又称链接技术，首先在加快一串相关向量指令的操作速度。

22、又称链接技术，首先在Cray- -1巨型机上得到应巨型机上得到应用，目前的向量机都支持这种技术。用，目前的向量机都支持这种技术。 另外两种方法主要是为了增加以向量方式操作的循环类型。这两种方法在许多向量机上另外两种方法主要是为了增加以向量方式操作的循环类型。这两种方法在许多向量机上采用。采用。6.4.1多功能部件的并行操作多功能部件的并行操作 如如Cray- -1巨型机中，共有巨型机中，共有4组组12个单功能流水部件，见个单功能流水部件，见P151图图6.3。 第一组为向量功能部件，有向量加，移，逻辑运算第一组为向量功能部件，有向量加，移，逻辑运算3个功能部件。个功能部件。17 第二组为浮点部

23、件，第二组为浮点部件，FADD，FMUL，浮点倒数。，浮点倒数。 第三组为标量功能部件，标量，逻辑运算第三组为标量功能部件，标量，逻辑运算 移位移位 数数/计数计数4个部件。个部件。延时延时18 第四组为地址功能部件，地址加和地址乘。第四组为地址功能部件，地址加和地址乘。 这些功能部件都是独立的，只要满足一定的约束条件，它们可以并行操作，约束条件是：这些功能部件都是独立的，只要满足一定的约束条件，它们可以并行操作，约束条件是： 不存在使用不存在使用R向向的冲突。的冲突。 不存在功能部件使用的冲突。不存在功能部件使用的冲突。 R向向使用冲突：指并行工作的向量指令中的源向量或结果向量使用相同的使用

24、冲突：指并行工作的向量指令中的源向量或结果向量使用相同的R向向。 例：例： V4V1+V2 V5V2V3 功能部件冲突：指多条并行工作的向量指令共用了同一功能部件冲突：指多条并行工作的向量指令共用了同一 个功能部件。个功能部件。 例：例： V3V1+V2 V6V4+V5 理想情况，若有理想情况，若有m个部件并行工作，可使运行速度提高个部件并行工作，可使运行速度提高m倍，由于实际程序并行度有限倍，由于实际程序并行度有限和可能发生上述冲突，因此，能完全工作的功能部件的总数总是和可能发生上述冲突，因此，能完全工作的功能部件的总数总是m。19例例 ADDV V1，V2，V3 MULTV V4，V1，V

25、5例例 D=A (B+C) 设向量长度设向量长度64，B和和C已由已由MMV0和和V1，则，则 LD V3，A ADDV V2，V0，V1 MULTV V4，V2，V3 而第三条指令而第三条指令与第一、二条指令均存在与第一、二条指令均存在先写后读的相关冲突，因而可将第三条指令与第先写后读的相关冲突，因而可将第三条指令与第一，二条指令链接执行一，二条指令链接执行 见图见图6.46.4.2 链接技术链接技术 利用向量指令间存在的先写后读的数据相关性来加快指令序列执行速度的技术称为链接利用向量指令间存在的先写后读的数据相关性来加快指令序列执行速度的技术称为链接技术。技术。20 采用并行和链接加速技术

26、，当被加工向量的长度为采用并行和链接加速技术，当被加工向量的长度为N时，则执行时间：时，则执行时间： T=(1+6+1)+(1+7+1)+(N- -1)=N+16拍拍加法和访存的延时乘法延时充满后连续流水结果数产生第1个结果的延时桌面3921 这三条指令全部用串行方法执行时则需要这三条指令全部用串行方法执行时则需要 T=(1+6+1)+N-1 2+(1+7+1)+N-1=3N+22拍拍 前两条并行前两条并行,第三条指令串行执行时需要第三条指令串行执行时需要 T=(1+6+1)+N-1+(1+7+1)+N-1=2N+15拍拍要指出的是，当一条向量指令的两个源操作数分别是两条先行指令的结果要指出的

27、是，当一条向量指令的两个源操作数分别是两条先行指令的结果R向向时：时： 要求先行两条指令产生的运算结果的时间必须相等要求先行两条指令产生的运算结果的时间必须相等(即有关功能部件的延迟时间相等即有关功能部件的延迟时间相等)。上例中访存和浮点加的延时均为上例中访存和浮点加的延时均为6个时间单位。个时间单位。 还要求这两条向量指令的向量长度必须相等，否则就不可能链接。还要求这两条向量指令的向量长度必须相等，否则就不可能链接。 可见并行加链接技术的加速效率还是较高的。要实现链接，除了前述条件之外，还有可见并行加链接技术的加速效率还是较高的。要实现链接，除了前述条件之外，还有时间上的要求时间上的要求，即

28、：只有当前一条指令的第一结果分量，即：只有当前一条指令的第一结果分量R向向的那一个时钟周期可链接，的那一个时钟周期可链接，错过该时刻，就无法进行链接，只有等前一向量指令全部执行完毕，释放错过该时刻，就无法进行链接，只有等前一向量指令全部执行完毕，释放R向向资源后，才资源后，才能执行后面指令。能执行后面指令。 22 针对不同的向量机，可能还有其他特殊的限制。针对不同的向量机，可能还有其他特殊的限制。 例例Cray- -1中允许自存储器取数操作参与链接，但不允许向存储器写数操作实现链接，中允许自存储器取数操作参与链接，但不允许向存储器写数操作实现链接，因为因为Cray- -1并不提供这种链接功能。

29、并不提供这种链接功能。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时才执行，就可使上述循循环向量化。时才执行，就可使上述循循环向量化。其

30、关键时要生成一个屏蔽向量，然后借助于它来控制哪些向量元素参加运算。其关键时要生成一个屏蔽向量，然后借助于它来控制哪些向量元素参加运算。23 屏蔽向量是通过测试得到的。上例中是对屏蔽向量是通过测试得到的。上例中是对A(i)=0否进行测试。否进行测试。 若若A(i)=0，屏蔽向量的相应位，屏蔽向量的相应位Z“0”； A(i) 0，屏蔽向量的相应位，屏蔽向量的相应位Z“1”； 清零时，清零时，VM所有位所有位Z“1”，此时后所有向量指令将对所有向量元素进行操作。，此时后所有向量指令将对所有向量元素进行操作。 下面给出上述循环的代码，设向量下面给出上述循环的代码，设向量A和和B的起始地址放在的起始地址

31、放在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 ；将结果存入；将结果存入A24 指令序列中，指令序列中，SEMSV指令为屏蔽向量生成指令；指令为屏蔽向量生成指令； CVM 为屏蔽向量寄存器为屏蔽向量寄存器Z“1”指令。指令。 屏

32、蔽向量寄存器控制向量指令执行方法的缺点是：屏蔽向量寄存器控制向量指令执行方法的缺点是： 执行时间没有减少执行时间没有减少 在某些向量机中，屏蔽向量仅用来禁止向目的寄存器写入，而相应的向量操作实际仍在某些向量机中，屏蔽向量仅用来禁止向目的寄存器写入，而相应的向量操作实际仍是进行，这会导至某些向量操作产生错误。是进行，这会导至某些向量操作产生错误。 例：例： if A(i) 0 then B(i)=B(i)/A(i) 在在A(i)= =0时，仅仅禁止运算结果时，仅仅禁止运算结果B(i)/A(i) B(i)，但没有禁止，但没有禁止B(i)/A(i)运算的进行，这就运算的进行，这就导致除数为导致除数为

33、0的非法运算。的非法运算。 比较好的方案是：根椐禁止向量，既禁止将结果写入目的寄存器，也禁止该操作执行。比较好的方案是：根椐禁止向量，既禁止将结果写入目的寄存器，也禁止该操作执行。 加快稀疏矩阵执行速度例：加快稀疏矩阵执行速度例： 例：有一个典型的稀疏矩阵运算，常见如下代码段：例：有一个典型的稀疏矩阵运算，常见如下代码段： do 100 i=1，n 100 A(K(i)=A(K(i)+C(M(i) 25指标向量指标向量K和和M指明指明A和和C中的非零元素，此时要求中的非零元素，此时要求A和和C 中必须有相同的非零元素个数。中必须有相同的非零元素个数。 除了指标向量外，也可用位向量来指明非零元素

34、。除了指标向量外，也可用位向量来指明非零元素。 支持稀疏矩阵运算的基本结构是支持稀疏矩阵运算的基本结构是指标向量的散射指标向量的散射聚合操作聚合操作(Scattergather)。 聚合操作：是概据指标向量内容选取元素，它们的地址聚合操作：是概据指标向量内容选取元素，它们的地址=基址基址+指标向量中给定的相指标向量中给定的相应地址偏移量获得，聚合操作后存于目的向量寄存器中的结果已成为稠密向量。应地址偏移量获得，聚合操作后存于目的向量寄存器中的结果已成为稠密向量。 散射操作：借助同一指标向量将稠密向量还原成稀疏向量。散射操作：借助同一指标向量将稠密向量还原成稀疏向量。6.4.4 向量归约操作的加

35、速方法向量归约操作的加速方法 归约归约(Reduction)操作是递推操作是递推(Recurrence)操作中的一个特殊例子。归约操作一般难以向操作中的一个特殊例子。归约操作一般难以向量化。量化。 例：例：26 对于上述的第二部分递推循环，可用递归方法写出如下代码：对于上述的第二部分递推循环，可用递归方法写出如下代码： len=32 do 100 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) do 10 i=1，641

36、0 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)递推部分递推部分3727nTnlsnTtcvpvp)1( 6.5向量处理性能的评估参数和方法向量处理性能的评估参数和方法 在向量流水功能部件上执行一个长度为在向量流水功能部件上执行一个长度为n的向量操作时间的向量操作时间Tvp可用以下公式表示：可用以下公式表示： Tvp=Ts+T1+(n- -1) Tc=T0 +n Tc (6.2) Ts：建立流水线的时间。：建立流水线的时间。 T1：为

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

38、/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 =(

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

40、时间、处理速率与向量长度的关给出了串行和向量流水两种操作方式的向量处理时间、处理速率与向量长度的关系。系。31cscscscslT，n，nTtt 显然30 在评估向量流水机性能时，除了执行时间性外，向量长度是一个很重要的参数。较常用在评估向量流水机性能时，除了执行时间性外，向量长度是一个很重要的参数。较常用的与向量长度有关的评价流水机性能的参数有三个：的与向量长度有关的评价流水机性能的参数有三个： R：当向量长度：当向量长度时，向量流水的渐近性能常在评价峰值时用，单位为时，向量流水的渐近性能常在评价峰值时用，单位为MFLOPS。 n1/2：为达到一半：为达到一半R值时所需的向量长度。是评价向量

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

42、串行工作方式时，所需的向量长度临界：表示向量流水方式的工作速度优于标量串行工作方式时，所需的向量长度临界值。值。31见见P157图图6.5(a)中的中的nv值值=5。 该参数既衡量建立时间，也衡量标量、向量速度比对性能的影响。该参数既衡量建立时间，也衡量标量、向量速度比对性能的影响。326.6 并行向量处理技术并行向量处理技术 并行向量处理机的通用体系结构如图并行向量处理机的通用体系结构如图6.6所示所示图图6.6 并行向量处理机的体系结构框图并行向量处理机的体系结构框图 并行向量处理机的主要特点是：向量处理部件数量不多，但有很高的处理性能；互连网并行向量处理机的主要特点是：向量处理部件数量不

43、多，但有很高的处理性能；互连网络有很高的带宽和低的时延；采用大量的向量寄存器，而不使用络有很高的带宽和低的时延；采用大量的向量寄存器，而不使用Cache；向量部件和互连；向量部件和互连网络均是定制的，价格昂贵；向量化编程较容易。网络均是定制的，价格昂贵；向量化编程较容易。 33 Earth Simulator并行向量处理机由并行向量处理机由640个结点处理器组成，每个结点中含有以下部件：个结点处理器组成，每个结点中含有以下部件：8个向量处理器个向量处理器(称为称为AP，算术处理器，算术处理器)，每个峰值性能为，每个峰值性能为8 G flop/s；1个个16 GB的共享存储的共享存储器；器；1个

44、远程访问控制部件个远程访问控制部件(RCU)；1个个I/O处理器。处理器。 每个向量处理器由以下部件组成：每个向量处理器由以下部件组成：1个向量部件个向量部件(内含内含8套，每套有套，每套有6个向量流水线，包括个向量流水线，包括装载装载/存储、逻辑、加存储、逻辑、加/移位、乘法、除法以及屏蔽移位、乘法、除法以及屏蔽)、72个个(256位位)向量寄存器以及向量寄存器以及17个个(256位位)屏蔽寄存器；屏蔽寄存器；1个个4路路(每个周期可发射每个周期可发射4条指令条指令)超标量处理器，配备有超标量处理器，配备有128个标量寄存器个标量寄存器以及存储容量均为以及存储容量均为64 KB的的I-Cac

45、he和和DCache；1个存储器访问控制部件。该向量处理器个存储器访问控制部件。该向量处理器的结构如图的结构如图6.7所示。所示。 设计并行向量处理机应遵循的要点是：使向量和标量处理的性能尽可能平衡；存储器系设计并行向量处理机应遵循的要点是：使向量和标量处理的性能尽可能平衡；存储器系统应有足够的数据带宽；互连网络应有高的带宽和低的时延；应有良好的处理器规模可扩统应有足够的数据带宽；互连网络应有高的带宽和低的时延；应有良好的处理器规模可扩展性。展性。3634图图67 Earth Simulator的结点机结构的结点机结构 35 在在Earth Simulator中，每个结点中含有中，每个结点中含

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

47、来。640个结点之间用个结点之间用2 12.3GBps带宽的带宽的640 640纵横交叉开关互连。纵横交叉开关互连。 Earth Simulator并行向量处理机系统的峰值性能为并行向量处理机系统的峰值性能为40.96T(1T=1万亿万亿) FLOPS(640 8 8 Gflop/s)，总的存储容量为，总的存储容量为10 TB(640 8 16 GB)，在，在TOP500排行榜的榜首位置上保持了近排行榜的榜首位置上保持了近3年时间年时间(20022005)。 2003年年Cray公司推出的大规模并行向量处理机系统公司推出的大规模并行向量处理机系统CRAY x1为了提高存储器带宽，在为了提高存储

48、器带宽，在向量处理器和主存之间采用了向量处理器和主存之间采用了Cache高速缓存。高速缓存。 366.7向量化编译技术向量化编译技术 为发挥向量机的功能，必须为向量机开发相应的向量化编译程序为发挥向量机的功能，必须为向量机开发相应的向量化编译程序(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) 向量化编译器就是尽量在源程序中寻找和实现这种替换。向量化编译器就是尽量在源程序中寻找和实现这种替换。 对条件语句这样的障碍可以用相应的控制及对条件语句这样的障碍可以用相应的控制及Where语句加以消除。语