六章向量处理机.ppt

第六章 向量处理机,6.1 向量处理的基本概念,什么是向量处理？ 例如：一个简单的C语言程序如下： for (i = 1; i n; i+) ai = bi +ci ; bi =2*a i+1 ; 在标量处理机上用下述指令实现：,A、B、C分别是向量a、b、c在内存中的起始地址： INITIALIZE I=1 10 if (iN ) GOTO 20 read bI read cI add bI+cI store aIbI+cI read aI+1 multiply 2*aI+1 store bI 2*aI+1 increment I I+1 goto 10 20 Stop,常量2，a，b，c中每一个元素都称为一个标量。该指令序列称为标量指令序列，执行过程为标量处理过程，每一条指令只处理一个或一对数据。,上述程序用向量化指令序列实现为： a1:n=b1:n+c1:n temp1:n=a2:n+1 b1:n=2*temp1:n 将n个独立的数构成的整体称为向量，对这一组数的运算称为向量处理。一条向量处理指令可以处理n个或n对操作数。,1）向量处理机是解决数值计算问题的一种高性能计算机结构 2）由于向量内各个元素间很少相关，而且对向量中各元素一般又是执行同一操作，向量处理机一般都采用流水线结构，有多条流水线并行工作 3）一条向量指令对应一个循环的数组运算，一条向量指令包含大量的数据运算 4）向量处理机通常属大型或巨型机，也可以用微机加一台向量协处理器组成 5）一般向量计算机中包括有一台高性能标量处理机 6）必须把要解决的问题转化为向量运算，向量处理机才能充分发挥作用,向量处理机与标量处理机比较： 向量操作比一串标量指令操作更快 向量流水处理机还可使访存和有效地址计算流水化 通过设置多个向量运算部件并且允许多个向量操作同时进行，可开发对不同元素进行多个向量操作的并行性,向量处理方式 要根据向量运算的特点和向量处理机的类型选择向量的处理方式。 有三种处理方式： 1横向处理方式，又称为水平处理方式，横向加工方式等。向量计算是按行的方式从左至右横向地进行。 2纵向处理方式，又称为垂直处理方式，纵向加工方式等。向量计算是按列的方式自上而下纵向地进行。 3纵横处理方式，又称为分组处理方式，纵横向加工方式等。横向处理和纵向处理相结合的方式。 以一个简单的C语言编写的程序为例，说明向量的三种处理方式的工作原理。 for (i = 1；i = n；i+) yi = ai ×( bi + ci );,横向处理方式 也称为水平处理方式，横向加工方式等 逐个分量进行处理：假设中间结果为TI 计算第1个分量： T1 B1C1 Y1 A1×T1 计算第2个分量： T2 B2C2 Y2 A2×T2 最后一个分量： TN BNCN YNAN×TN 存在两个问题： 在计算向量的每个分量时，都发生写读数据相关。流水线效率低 如果采用多功能流水线，必须频繁进行流水线切换 横向处理方式对向量处理机不适合 即使在标量处理机中，也经常通过编译器进行指令流调度。,纵向处理 也称为垂直处理方式，纵向加工方式等 T1 = B1 + C1 T2 = B2 + C2 Tn = Bn + Cn Y1 = A1×T1 Y2 = A2×T2 YN = AN ×TN 采用向量指令只需要2条： VADD B， C， T VMUL A， T， Y 这种处理方式适用于向量处理机，数据相关不影响流水线连续工作。不同的运算操作只需要切换1次。,纵横处理方式 将长度为n的向量分成若干组，每组长度为m，组内按纵向方式处理，依次处理各组。 用于寄存器-寄存器结构的向量处理机中 向量寄存器的长度是有限的，例如，每个向量寄存器有64个寄存器。当向量长度N大于向量寄存器长度n时，需要分组处理。 分组方法：nK·m+r，其中：r为余数，共分k+1组。 组内采用纵向处理方式，组间采用横向处理方式。因此，也称为分组处理方式，纵横向加工方式等。,6.2 向量处理机结构,向量处理机的基本思想是把两个向量的对应分量进行运算，产生一个结果向量。最关键问题是存储器系统能够满足运算部件带宽的要求。 主要采用两种方法： 1. 存储器存储器结构 多个独立的存储器模块并行工作 处理机结构简单，对存储系统的访问速度要求很高 2. 寄存器寄存器结构 运算通过向量寄存器进行 需要大量高速寄存器，对存储系统访问速度的要求降低,存储器存储器结构,下图说明一个具有8个存储体的向量处理机：,M,M,流水结构加法器,A,B,C=A+B,三条互相独立的数据通路，可并行工作，同一个存储模块同时只能为一个通路服务,M,M,M,M,M,M,向量处理示例1：求C=A+B，设A、B、C的存储形式如图：,C4,B6,A0,C5,B7,A1,C6,B0,A2,C7,B1,A3,C0,B2,A4,C2,B3,A5,C3,B4,A6,C4,B5,A7,A、B、C在主存储器中的存放情况,两个向量在流水线方式下分量相加的时序图,时间（时钟周期）,在流水线的输入端和输出端增加缓冲器可以消除争用存储器现象。,W0,RB8,RB8,RA8,RA8,RB0,RB0,RA0,RA0,RB9,RB9,RA9,RA9,RB1,RB1,RA1,RA1,RB10,RA10,RA10,RB2,RB2,RA2,RA2,RA11,RA11,RB3,RB3,RA3,RA3,RA12,RB4,RB4,RA4,RA4,RB5,RB5,RA5,RA5,RB6,RB6,RA6,RA6,RB7,RB7,RA7,RA7,7,6,5,4,3,2,1,0,7,6,5,4,3,2,1,0,6,5,4,3,2,1,0,5,4,3,2,1,0,M0,M1,M2,M3,M4,M5,M6,M7,0 1 2 3 4 5 6 7 8 9 10 11 12,存储器发生冲突时两个向量相加的时序图,寄存器-寄存器结构,把存储器-存储器结构中的缓冲栈改为向量寄存器，运算部件需要的操作数从向量寄存器中读取，运算的中间结果也写到向量寄存器中。 向量寄存器与标量寄存器的主要差别是： 一个向量寄存器能够保存一个向量， 例如：64个64位寄存器。 连续访问一个向量的各个分量。 需要有标量寄存器和地址寄存器等。 采用寄存器-寄存器结构的主要优点：降低主存储器的流量。例如：采用寄存器-寄存器结构的CRAY-1与采用存储器-存储器结构的STAR-100比较，运算速度高3倍多，而主存流量低2.5倍。 STAR-100的主存储器流量：32×8W/1.28us=200MW/S CRAY-1的主存储器流量： 4W/50ns=80MW/S,V7,V6,V5,CRAY-1向量处理机结构,存储器,V4,3,2,1,0,V3,V2,V1,V0,S7,S6,S5,S4,S3,S2,S1,S0,A7,A6,A5,A4,A3,A2,A1,A0,标量缓冲 寄存器,地址缓冲 寄存器,加1记数,移位,逻辑运算,整数加 标量部件,整数乘,整数加 地址部件,移位,逻辑运算,整数加 向量部件,迭代求倒,浮点乘,浮点加 向量部件,VM（向量屏蔽）,RTC（实时时钟计数器）,XA,VL,P,NIP,CIP,LIP,执行指令,执行缓冲 寄存器,+1,0 1 . 15,T0 . T63,B0 . B63,0 . . 63,向量控制,向量控制 （向量长度）,交换控制,标量寄存器,地址寄存器,向量寄存器,Vi,Vj,Vk,. . .,Vi,. . .,Vj,1,2,. . .,n,. . .,Vk,. . .,Vi,Sj,. . .,Vk,存储器,. . .,Vk,. . .,Vi,存储器,功能部件,功能部件,功能部件,功能部件,1,2,. . .,n,1,2,. . .,n,1,2,. . .,n,第1种 向量-向量指令,第2种 向量-标量指令,第3种 向量-存储器指令,CRAY-1的四种向量指令,运算流水线,第4种 向量-存储器指令,向量归约指令（vector reduction instruction）:操作数来自寄存器，操作结果为标量数据，如从一个向量中找出最大值、最小值和中间值等。 聚集-散射指令（gather and scatter instruction）:将两个向量寄存器（分别存放数据和变址值）聚集分布在存储器中的向量元素，或者把向量元素散射到存储器中。聚集指令根据变址值把存储器中某个稀疏向量的非0元素取出放到向量寄存器中。散射指令进行相反的操作，把一个向量以稀疏向量的形式存入存储器中，其0项由变址值指出。 屏蔽指令（masking instruction）:利用屏蔽向量将一个向量压缩或者展开成一个较短或较长的索引向量。,1.向量处理机系统结构的设计目标 2.提高向量处理机性能的常用技术,6.3 提高向量处理机性能的办法,向量处理机系统结构的设计目标,较好地维持向量/标量性能平衡 向量平衡点（vector balance point)定义为：为了使向量硬件设备和标量硬件设备的利用率相等，一个程序中向量代码所占的百分比。 例如：系统在向量模式下能够达到9Mflops，在标量模式下能够达到1Mflops的运算速度，假设代码的90%是向量运算，10%是标量运算，这样花在两种模式上的计算时间相等，那么向量平衡点为0.9。,几种超级计算机的向量性能和标量性能 （了解）,可扩展性随处理机数目的增加而提高 可扩展性的三个目标：规模可扩展性、换代可扩展性、问题可扩展性。 提供高性能的I/O和易访问的网络,提高向量处理机性能的常用技术,多功能部件的并行操作 向量寄存器冲突（Vi冲突） 功能部件冲突 向量寄存器冲突（Vi冲突）：并行工作的各向量指令的源向量或者结果向量使用相同的Vi。包括源向量冲突、结果向量冲突、先读后写的向量冲突和源目向量相关。 V3 ¬ V1V2 V3 ¬ V1V2 V6 ¬ V1*V5 V3 ¬ V4 * V5 源向量冲突 结果向量冲突 V3 ¬ V1V2 V3 ¬ V1V2 V1 ¬ V4*V5 V5 ¬ V3 * V4 先读后写的向量冲突 源目向量相关 发生源目向量相关的两条指令在不发生其它Vi冲突和功能部件冲突的前提下，可通过链接机构将两条向量指令的处理过程链接起来，实现两条指令的流水处理。,功能部件冲突：指同一功能部件被一条以上的要求并行工作的向量指令所使用。如下面两条指令由于都使用了向量加法部件，因此，存在向量加法部件使用冲突。 V3 ¬ V1V2 V6 ¬ V4 +V5 向量链接技术(chaining) 指在不出现向量寄存器冲突和功能部件冲突时，通过链接机构将有源目向量相关的前后两条或多条向量指令进行链接而实现并行处理的技术。 机器会自动检查每一条向量指令是否可能与它前一条或两条向量指令（两个向量长度相同且首元素时间对准时）存在源目向量相关（同时无向量寄存器冲突和功能部件冲突），若存在，则在前一条或两条指令的第一个结果分量都到达向量寄存器组且可以作为本条向量指令的源操作数时，立即启动本条指令工作而形成链。有了链接技术，就可以使一些存在源目向量相关的指令也能并行处理。CRAY-1共有8个向量寄存器组，一般可以有2-5个功能部件链接在一起工作。,例如：求向量运算D=A*（B+C），若向量的长度N=64，向量的分量为浮点熟，且向量B、C已取到V0、V1中。试分析采用下述三条指令实现功能而采用的链接技术。 V3 ¬ A /访存取A向量/ V2 ¬ V0V1 /B向量和C向量相加/ V4 ¬ V2×V3 /浮点乘，存D向量/ 分析：第一、二条指令没有向量寄存器冲突和功能部件冲突，故这两条向量指令可以并行执行；第三条指令与第一、二条指令均无功能部件冲突，但存在向量寄存器冲突，由于向量寄存器冲突属于源目向量相关，因此只要第一条指令中的结果V3的第一个分量与第二条指令的结果响亮V2的第一个分量均产生，就可以通过链接机构将这一对分量直接送往浮点乘功能部件，链接执行第三条指令。 如下页图所示，访存与浮点加并行执行，再与浮点乘链接执行，执行上述三条指令，获得第一个结果分量并存入V4，所需要的拍数（也称为链接流水线的流水时间）为：,. . .,V0,. . .,V1,1,2,. . .,6,. . .,V2,存储器,. . .,V3,浮点加,访存,1,2,. . .,6,并行与潋接操作过程图,1,2,. . .,7,. . .,V4,浮点乘,实现链接的条件： (1) 没有向量寄存器冲突和运算部件冲突。 (2) 只有第一个结果送入向量寄存器的那一个周期可以链接。 (3) 先行的两条指令产生运算结果的时间必须相等。 (4) 两条向量指令的向量长度必须相等。,例：在CRAY-1机上，设向量的长度均为64；所用浮点功能部件的执行时间分别为：相加需6拍，相乘需7拍，从存储器读数需6拍，存入寄存器及启动功能部件各需1拍。问下列各指令组中，组内哪些指令可以链接？哪些指令不可以链接？不能链接的原因是什么？并分别计算出下列各指令组全部完成所需要的拍数。 （1） V2¬V0*V1 V3¬存储器 V4¬V3+V5 （2） V0¬存储器 V1¬V2+V3 V4¬V5*V6 （3） V0¬存储器 V2¬V0*V1 V3¬V0+V4 解:(1)第三条向量指令与第二条向量指令有源目向量相关，可以链接执行；第一条向量指令与第二、三条向量指令无关，可以与它们并行执行。,(2)三条向量指令都无关，所以，三条向量指令可以并行执行。,(3)第二条向量指令与第一条向量指令有源目向量相关，可以链接执行；第三条向量指令与第二条向量指令有源向量冲突，故只能等到第二条向量指令执行完毕后，才能执行第三条向量指令。,注意：1）在分析向量指令的处理时，特别关注无关向量指令的并行执行，源目向量相关的向量指令的链接执行，除源目向量相关外其它发生向量寄存器冲突的向量指令的串行执行，功能部件冲突的向量指令的串行执行以及向量内部各分量流水处理之间的区别。 2）启动、输出延迟（各1拍）,加快稀疏矩阵的执行速度 稀疏矩阵：许多元素为0的矩阵。 解决办法：稀疏向量 程序段 DO 10 I=1，N A（K（I）=A（K（I）B（K（I） 完成对稀疏向量A和B求和，其中K、M为指标向量，指明A、B中的非0元素。,4,100,4,2,5,1,600,400,250,200,0,200,400,0,600,250,0,100 101 102 103 104 105 106,1 2 3 4,1 2 3 4,I=,I=,存储器地址,稠密向量寄存器 A（K（I）,稀疏向量A（I）,指标向量寄存器 K（I）,VL寄存器,基址寄存器,聚合操作,4,100,4,2,5,1,600,400,250,200,0,200,400,0,600,250,0,100 101 102 103 104 105 106,1 2 3 4,1 2 3 4,I=,I=,存储器地址,稠密向量寄存器 A（K（I）,稀疏向量A（I）,指标向量寄存器 K（I）,VL寄存器,基址寄存器,散射操作,当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，采用循环结构处理这个长向量，这种技术称为向量循环开采技术，也称为向量分段开采技术。 例如：A和B为长度N的向量。 for (i=1; iN; i+) ai=5*b(i)+c; 当N为当N为64或更小时，产生A数组的7条指令序列是： 1：S1¬5.0 在标量寄存器内设置常数 2：S2¬C 将常数C装入标量寄存器 3：VL¬N 在VL寄存器内设置向量长度 4：Vo¬B 将B向量读入向量寄存器 5：V1¬S1* Vo B数组的每个分量和常数相乘 6：V2¬S2V1 C和5*B(x)相加 7：A¬V2 将结果向量存入A数组,向量循环开采技术,6.5 向量处理机的性能评价,衡量向量处理机性能的主要指标有： 向量指令处理时间Tvp 最大性能R¥ 半性能向量长度n1/2 向量方式的工作速度优于标量串行工作时所需的向量长度的临界值 1、向量指令处理时间Tvp 执行一条向量长度为n的向量指令的时间Tvp，Ts为向量流水线的建立时间，包括向量起始地址设置、计数器加1、条件转移指令执行等， Tvf第一对向量元素通过流水线的时间，t为流水线时钟周期，则有： TvpTs+Tvf+(n-1)t=s + e + (n - 1) t 其中：s为向量流水线建立时间所需的时钟周期数。e为完成第一对向量元素操作所需的子操作数。,把几条能在一个时钟周期内同时开始执行的向量指令称为一个编队，同一个编队中的指令一定不存在功能部件冲突和数据相关。 例1：假设一台向量处理机中功能部件的启动开销为：取数和存数部件为12个时钟周期、乘法部件为7个时钟周期、加法部件为6个时钟周期。先把序列向量操作分成编队，然后计算每个编队的开始时间、获得第一个结果元素的时间和获得最后一个结果元素的时间。 LV V1， Rx ；取向量x MULTSV V2， F0， V1 ；向量和标量相乘 LV V3， Ry ；取向量Y ADDV V4， V2， V3 ；加法 SV Ry， V4 ；存结果 解：第一条指令LV为第一个编队。MULTSV指令和第二条LV指令为第二个编队。ADDV指令为第三个编队。SV指令为第四个编队。,如果采用向量链接技术（不考虑访问存储器的冲突），需要： 12 + 7 + 6 + 12 + n 136 + n个周期。 如果考虑向量长度大于向量寄存器长度时，则需要分段开采。 向量长度为n的一组向量操作的整个执行时间为： 其中：Tloop为执行标量代码的开销， Tstart为每个编队的向量启动开销，MVL是向量寄存器的长度。 Tloop可以看作是一个常数，Cray 1机的 Tloop 约等于15。,例2：在一台向量处理机上实现AB×s操作，其中A和B是长度为200的向量，s是一个标量。向量寄存器长度为64。各功能部件的启动时间与上例相同。求总的执行时间。 解：因为向量长度超过了向量寄存器的长度，所以要采取分段开采方法。每次循环主要由下面三条向量指令组成： LV V1， Rb ；取向量B MULTVS V2， V1， Fs ；向量和标量相乘 SV Ra， V2 ；存向量 假设A和B的分别放在Ra和Rb之中，s在Fs中。 三条指令之间存在有写读数据相关，因此必须把它们分成3个编队，Tchime= 3。 T2004×(15 + Tstart) + 200×3 60（4×Tstart）+ 600 660（4×Tstart） 其中：Tstart=12 + 7 + 12 = 31， 因此，T200660 + 4×31784 每个结果元素的平均这些时间为：768/200 3.9个周期。,例3：在某台向量处理机上执行代码代码如下： 1：LV V1， Rx ；取向量x 2：MULTSV V2， F0， V1 ；向量和标量相乘 3：LV V3， Ry ；取向量Y 4：ADDV V4， V2， V3 ；加法 5：SV Ry， V4 ；存结果 考虑访问存储器冲突，向量寄存器长度为n、各功能部件的启动时间与上例相同。求总的执行时间。 解：指令1、2，指令3、4和指令5分成三个编队，前两个编队中两条指令采用向链接技术执行。 Tchime=3，Tloop=15，Tstart=12+7+12+6+12=49，VL=64。,2、最大性能R¥ R¥表示当向量长度为无穷大时的向量流水线的最大性能。 常在评价峰值性能时使用，单位为MFLOPS。 最大性能R¥ 表示为： 其中：n为向量长度； Tn为一组向量操作的整个执行时间。 对于例3，假设时钟频率为200MHZ。每个循环有2个浮点操作：,3、半性能向量长度n1/2 为达到一半R¥值所需的向量长度称为半性能向量长度n1/2。 主要评价向量流水线建立时间对性能的影响。 CRAY-1的n1/21020，CYBER 205的n1/2100。 由MFLOPS定义可知： 对于例3，如果向量处理机的时钟频率为200MHz。 因为：R¥=100MFLOPS，因此有： 1002 2 n1/2Tn1/2×200 假设：n1/2 £ 64，因此：Tn1/2 64 + 3 n1/2 解得：1002 2 n1/2(64 + 3 n1/2)×200 n1/212.8 所以：n1/213,4、向量和标量的平衡点nv 向量和标量的平衡点nv表示向量流水方式的工作速度优于标量串行方式时所需的向量长度临界值。若向量的长度nnv，则表示向量流水方式的工作速度优于标量串行方式；反之，则表示采用标量串行方式处理各元素时，速度优于向量流水方式。 例：某向量处理机其向量流水方式的执行速率RV=10MFLOPS，标量方式执行速率RS=1MFLOPS，设a是程序中可向量化的百分比。要求： 推导该向量机的平均执行速率Ra的公式 为使平均执行速率Ra=7.5MFLOPS，则a的值应取何值？ 解： 1),a0.963,2),