计算机系统结构-第五章(向量处理机).ppt

向量处理机,基本概念基本结构设计目标关键技术协处理器性能评价,基本概念,本章内容,向量处理机什么是向量处理向量处理方式,向量处理机,本章内容基本概念,具有向量数据表示和向量指令系统的处理机，是解决数值计算问题的一种高性能计算机结构。有两个主要优点：效率高和适用性广，一般都采用流水线结构，有多条流水线并行工作。向量处理机通常属大型或巨型机，也可以用微机加一台向量协处理器组成。一般向量计算机中包括有一台高性能标量处理机。必须把要解决的问题转化为向量运算，向量处理机才能充分发挥作用,2 之 1,向量处理机,本章内容基本概念,2 之 2,什么是向量处理 例子,本章内容基本概念,用Fortran语言编写的一个简单程序：DO 100 I=1,NA(I)=B(I)+C(I)100B(I)=2*A(I+1),3 之 1,什么是向量处理 标量处理,本章内容基本概念,INITIALIZE I=110READB(I);读数指令READC(I)ADD B(I)+C(I);运算指令STOREA(I)B(I)+C(I);存数指令READA(I+1)MULTIPLY2*A(I+1);运算指令STOREB(I)2*A(I+1);存数指令INCREMENT II+1;运算指令IF IN GOTO 10;条件转移指令STOP,3 之 2,什么是向量处理 向量处理,本章内容基本概念,A(1:N)=B(1:N)+C(1:N);并行运算指令TEMP(1:N)=A(2:N+1);并行取数指令B(1:N)=2*TEMP(1:N);并行运算指令一条向量指令处理N个操作数或N对操作数,3 之 3,向量处理方式,横向处理方式纵向处理方式纵横处理方式,C语言程序for(i=1;i=n;i+)yi=ai(bi+ci);,本章内容基本概念,采用同一例子说明,横向处理方式,本章内容基本概念向量处理方式,处理方法 又称为水平处理方式、横向加工方式等。向量计算是按行的方式从左至右横向地进行。举例 逐个分量进行处理：假设中间结果为T(I)计算第1个分量：T(1)B(1)C(1)Y(1)A(1)T(1)计算第2个分量：T(2)B(2)C(2)Y(2)A(2)T(2)计算最后一个分量：T(N)B(N)C(N)Y(N)A(N)T(N),2 之 1,横向处理方式,本章内容基本概念向量处理方式,分析 存在两个问题：在计算向量的每个分量时，都发生写读数据相关，流水线效率低；如果采用多功能流水线，还必须频繁进行流水线切换。所以横向处理方式对向量处理机不适合，即使在标量处理机中，也经常通过编译器进行指令流调度。,2 之 2,纵向处理方式,本章内容基本概念向量处理方式,处理方法 也称为垂直处理方式、纵向加工方式等。向量计算是按列的方式自上而下纵向地进行。举例T(1)=B(1)+C(1)T(2)=B(2)+C(2)T(n)=B(n)+C(n)Y(1)=A(1)T(1)Y(2)=A(2)T(2)Y(N)=A(N)T(N),2 之 1,纵向处理方式,本章内容基本概念向量处理方式,分析 因为数据相关不影响流水线连续工作，不同的运算操作只需要切换1次，所以这种处理方式适用于向量处理机。结果的存储直接面向存储器，n的大小可以不受限制，但速度受到存储器吞吐量的限制。采用向量指令只需要2条：VADDB，C，TVMULA，T，Y,2 之 2,纵横处理方式,本章内容基本概念向量处理方式,处理方法 又称为分组处理方式、纵横向加工方式等。横向处理和纵向处理相结合的方式。即：将长度为N的向量分成若干组，每组长度为n，组内采用纵向处理方式，组间采用横向处理方式。,3 之 1,纵横处理方式,本章内容基本概念向量处理方式,举例第组：T(1,n)=B(1,n)+C(1,n)Y(1,n)=A(1,n)T(1,n)第组：T(n+1,2n)=B(n+1,2n)C(n+1,2n)Y(n+1,2n)=A(n+1,2n)T(n+1,2n)最后第k+1组：T(kn+1,N)=B(kn+1,N)+C(kn+1,N)Y(kn+1,N)=A(kn+1,N)+T(kn+1,N),3 之 2,纵横处理方式,本章内容基本概念向量处理方式,分析 减少了访问主存储器的次数，降低对存储器信息流量的要求，也减少访问存储器发生冲突引起的等待时间，因而提高了处理速度。适合用于寄存器-寄存器结构的向量处理机中，因为向量寄存器的长度是有限的，例如，每个向量寄存器有64个寄存器。当向量长度N大于向量寄存器长度n时，需要分组处理。,3 之 3,基本结构,本章内容,向量处理机的最关键问题是存储器系统能够满足运算部件带宽的要求。主要采用两种方法：存储器存储器结构 多个独立的存储器模块并行工作。处理机结构简单，对存储系统的访问速度要求很高。寄存器寄存器结构 运算通过向量寄存器进行。需要大量高速寄存器，对存储系统访问速度的要求降低，而且利用高速寄存器可完成对矩阵元素的特殊运算。,存储器存储器结构,本章内容基本结构,假设A、B、C都是有8个元素的向量，现向量处理机需完成如下运算：C=A+B。,多端口存储器系统,流水结构加法器,B,A,C=A+B,3 之 1,存储器存储器结构,本章内容基本结构,3 之 2,存储器存储器结构,采用多个存储体交叉和并行访问来提高存储器速度，但应该注意解决存储器访问冲突。下面分情况进行介绍（假设一个存储周期占两个处理机周期）：,本章内容基本结构,理想情况 实际情况,3 之 3,数据存储,本章内容基本结构存储器存储器结构,2 之 1,处理时序图,本章内容基本结构存储器存储器结构,2 之 2,问题及解决,问题 实际情况与理想情况并非一样，例如：向量的元素有时不能存放在我们希望的存储体。解决 可以在流水线的输入端和输出端增加缓冲器来消除争用存储器。,本章内容基本结构存储器存储器结构,多端口存储器系统,流水结构加法器,B,A,C=A+B,3 之 1,缓冲器,缓冲器,缓冲器,处理时序图(所有向量都从模块0开始存放),本章内容基本结构存储器存储器结构,3 之 2,A延迟2,总 结,本章内容基本结构存储器存储器结构,3 之 3,操作数缓冲器和写结果缓冲器主要用于解决访问存储器冲突。主要优缺点：硬件结构简单,造价低；但速度相对较低。,寄存器寄存器结构,本章内容基本结构,把存储器-存储器结构中的缓冲器改为向量寄存器，运算部件需要的操作数从向量寄存器中读取，运算的中间结果也写到向量寄存器中。向量寄存器与标量寄存器的主要差别是：一个向量寄存器能够保存一个向量，例如：64个64位寄存器，用以实现连续访问一个向量的各个分量。需要有标量寄存器和地址寄存器等共同工作。,3 之 1,举 例 CRAY-1向量处理机结构,本章内容基本结构,8个向量寄存器(V)8个64个64bit,主存储器8MB64个个体,12个流水线结构的运算部件,缓冲寄存器(T)64个64bit,标量寄存器(S)8个64bit,缓冲寄存器(B)64个24bit,地址寄存器(A)8个24bit,指令缓冲寄存器256个16bit,指令寄存器,程序计数器,3 之 2,提 示,本章内容基本结构,3 之 3,主要向量处理机都采用寄存器寄存器结构，包括Cray处理机（Cray-1、Cray-2、X-MP、Y-MP、C90、T90和 SV1)、日本的超级计算机（NEC SX/2 SX/5、Fujitsu VP200 VPP5000、Hitachi S820 和S-8300）和小型超级计算机（Convex C-1 C-4）。第一台向量处理机（CDC）采用存储器存储器结构。从现在开始，我们集中讨论寄存器寄存器结构。,设计目标,本章内容,较好地维持向量/标量性能平衡可扩展性随处理机数目的增加而提高增加存储器系统的容量和性能提供高性能的I/O和易访问的网络,较好地维持向量/标量性能平衡,本章内容设计目标,实际的应用问题中通常既有向量计算又有标量计算，而且两类计算有一定的比例。关键问题是：希望向量硬件和标量硬件都能够充分利用，不要空闲。,3 之 1,较好地维持向量/标量性能平衡,本章内容设计目标,向量平衡点(vector balance point)：为了使向量/标量硬件设备的利用率相等，一个程序中向量代码所占的百分比。例如：一个系统的向量运算速度为90Mflops，标量运算速度为 10Mflops。如果程序的90是向量运算，10是标量运算，硬件利用率最高；则向量平衡点为0.9。,3 之 2,较好地维持向量/标量性能平衡,本章内容设计目标,向量处理机的向量平衡点必须与用户程序的向量化程度相匹配。例如：IBM向量计算机维持较低的向量与标量比例，定在35的范围之间。这种做法能够适应通用应用问题对标量和向量处理要求。但大多数超级计算机的向量平衡点在90%或更高，此时对目标代码向量化比例的依赖也大。,3 之 3,可扩展性随处理机数目的增加而提高,本章内容设计目标,可扩展性是指在确定的应用背景下，向量处理机系统要随处理机数目的增加而线性地提高。可扩展性的三个目标为：规模可扩展性、换代可扩展性和问题可扩展性。,关键技术,本章内容,链接技术向量循环/分段开采技术向量递归技术稀疏矩阵的处理技术,链接技术,本章内容关键技术,向量指令的类型向量运算中的相关和冲突向量链接技术,向量指令的类型,本章内容关键技术链接技术,以CRAY-1向量处理机为例，有四类指令：向量与向量操作：ViVj op Vk 向量与标量操作：ViSj op Vk 向量取：Vi存储器 向量存：存储器Vi,2 之 1,向量指令的类型,本章内容关键技术链接技术,2 之 2,1,2,3,4,n,Vj,Vk,Vi,1,2,3,4,n,Sj,Vk,Vi,1,2,3,4,5,6,主存,Vi,1,2,3,4,5,6,主存,Vi,（a）浮点加6拍、浮点乘7拍,（b）,（c）,（d）,向量运算中的相关和冲突,本章内容关键技术链接技术,V0V1V2V0V1V2V3V4V5V3V0V4(a)不相关的指令(b)写读数据相关V0V1V2V0V1V2V3V4V5V3V1V4(c)功能部件冲突(d)读读数据相关提示：采用顺序发射顺序完成方式。,向量链接技术 基本思想,本章内容关键技术链接技术,对于有写读数据相关的向量指令，可以采用“相关专用通道”：从一个流水线部件得到的结果直接送入另一个流水线部件的操作数寄存器，这样多条向量指令可以并行执行，这种技术称为流水线的链接技术。,7 之 1,向量链接技术 链接要求,本章内容关键技术链接技术,没有向量寄存器冲突和运算部件冲突；只有当前一条指令的第一个结果分量送入结果向量寄存器的那一个时钟周期方可链接，否则只能串行执行；若一条向量指令的两个源操作数分别是两条先行指令的结果时，要求：先行的两条指令产生结果的时间必须相等；先行的两条指令的向量长度必须相等。,7 之 2,向量链接技术 举例(要求),本章内容关键技术链接技术,若要进行向量运算：D=A(BC)，假设向量长度64，且B和C已由存储器取至V0和V1，则下面3条向量指令即可完成上述运算。V3AV2V0+V1V4V2*V3,7 之 3,向量链接技术 举例(调度一),本章内容关键技术链接技术,三条向量指令全部串行执行 所需时间为：(1+6+1)+N-1+(1+6+1)+N-1+(1+7+1)+N-1=3N+22（拍）,注意：CRAY-1启动访存、将元素送往功能部件和将结果存入Vi都需要有1拍的传送延迟。,7 之 4,向量链接技术 举例(调度二),本章内容关键技术链接技术,前两条并行执行，第三条串行执行 所需时间为：(1+6+1)+N-1+(1+7+1)+N-1=2N+15（拍）,注意：CRAY-1启动访存、将元素送往功能部件和将结果存入Vi都需要有1拍的传送延迟。,7 之 5,向量链接技术 举例(调度三),本章内容关键技术链接技术,三条向量指令采用链接技术 所需时间为：(1+6+1)+(1+7+1)+N-1=N+16（拍）,注意：CRAY-1启动访存、将元素送往功能部件和将结果存入Vi都需要有1拍的传送延迟。,7 之 6,向量链接技术 举例(调度三),本章内容关键技术链接技术,浮点加,7,1,2,3,4,5,6,Mem,V0,V1,V2,V3,V4,1,2,3,4,5,6,1,2,3,4,5,6,浮点乘,7 之 7,向量循环/分段开采技术,本章内容关键技术,当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，采用循环结构处理这个长向量，这种技术称为向量循环开采技术，也称为向量分段开采技术。这种分段和循环由系统硬件和软件控制完成，对于程序员是透明的。,3 之 1,向量循环/分段开采技术,本章内容关键技术,例如：A和B为长度N的向量。for(i=1;iN;i+)Ai=5*B(i)+C;当N为64或更小时，产生A数组的7条指令序列是：1：S15.0；在标量寄存器内设置常数2：S2C；将常数C装入标量寄存器3：VLN；在VL寄存器内设置向量长度4：V0B；将B向量读入向量寄存器5：V1S1V0；B数组的每个分量和常数相乘6：V2S2V1；C和5 B相加7：AV2；将结果向量存入A数组,3 之 2,向量循环/分段开采技术,本章内容关键技术,例如：A和B为长度N的向量。for(i=1;iN;i+)Ai=5*B(i)+C;当N超过64时，就需要采用向量循环：在进入循环以前，把N除以64，以确定循环次数。如果有余数，则在第一次循环中首先计算余数个分量。循环由第4条到第7条指令组成。4：V0B；将B向量读入向量寄存器5：V1S1V0；B数组的每个分量和常数相乘6：V2S2V1；C和5 B相加7：AV2；将结果向量存入A数组,3 之 3,向量协处理器,向量协处理器是为解决科学计算所要求的大量向量处理而设计的一种装置。它一般和中、小型计算机组合起来，作为主计算机的外围设备，承担处理向量的任务。这样，就可以得到较高的吞吐率和精度，其价格又可以为一般中、小用户所接受。,本章内容,2 之 1,向量协处理器,本章内容,处理机,主存储器,协处理机,本地存储器,高速总线,带向量协处理器的计算机结构框图,2 之 2,性能评价,向量指令处理时间Tvp最大性能R半性能向量长度n1/2向量长度临界值nv,本章内容,向量指令处理时间Tvp,本章内容性能评价,一条向量指令的处理时间一批向量指令的处理时间,一条向量指令的处理时间,本章内容性能评价向量指令处理时间Tvp,TvpTs+Tvf+(n-1)Tc 其中：Tvp为一条向量指令的处理时间；Ts为向量流水线的建立时间；Tvf为向量流水线的流过时间；Tc为流水线“瓶颈”段的执行时间；n为向量长度。,2 之 1,一条向量指令的处理时间,本章内容性能评价向量指令处理时间Tvp,2 之 2,如果每段执行时间都等于一个时钟周期，则有：Tvps+e+(n-1)其中：s为向量流水线建立时间所需的时钟周期数；e为向量流水线流过时间所需的时钟周期数；n为向量长度；为时钟周期长度。,一批向量指令的处理时间,本章内容性能评价向量指令处理时间Tvp,一组向量操作的执行时间主要取决于：向量的长度、向量操作之间是否存在流水功能部件的冲突和数据的相关性。把几条能在一个时钟周期内同时开始执行的向量指令称为一个编队；同一个编队中的指令一定不存在功能部件冲突和数据相关。将编队数记作Tchime。,2 之 1,一批向量指令的处理时间,本章内容性能评价向量指令处理时间Tvp,向量长度向量寄存器长度时向量长度向量寄存器长度时,2 之 2,向量长度向量寄存器长度时,本章内容性能评价向量指令处理时间Tvp一批向量指令的处理时间,其中：Tstart为每个编队的向量启动开销，即流水线建立时间+流过时间；Tc为流水线“瓶颈”段的执行时间；n为向量长度；Tchime为编队数。,3 之 1,举 例 问题,在某台向量处理机上执行DAXPY代码(Y=aXY)，代码如下：LV V1,Rx;取向量X MULTSV V2,F0,V1;向量和标量相乘 LV V3,Ry;取向量YADDV V4,V2,V3;加法SV Ry,V4;存结果问：这组向量操作能划分成几个编队？假设每种流水功能部件只有一个，且启动开销分别为：取数和存数部件为12个时钟周期、乘法部件为7个、加法部件为6个。请计算完成这一组向量操作所需的总时间为多少？,本章内容性能评价向量指令处理时间Tvp一批向量指令的处理时间,3 之 2,举 例 解答,本章内容性能评价向量指令处理时间Tvp一批向量指令的处理时间,3 之 3,可分成4个编队：第1条指令LV为第1个编队，MULTSV指令和第2条LV指令为第2个编队，ADDV指令为第3个编队，SV指令为第4个编队。,向量长度向量寄存器长度时,本章内容性能评价向量指令处理时间Tvp 一批向量指令的处理时间,需进行分段开采，向量长度为n的一组向量操作的整个执行时间为：其中：Tloop为执行标量代码的开销，Tstart为每个编队的向量启动开销，Tchime为编队数，MVL是向量寄存器的长度。Tloop可以看作是一个常数，Cray 1机的 Tloop约等于15。,3 之 1,举 例 问题,在某台向量处理机上执行DAXPY代码(Y=aXY)，代码如下：1：LV V1,Rx；取向量X2：MULTSV V2,F0,V1；向量和标量相乘3：LV V3,Ry；取向量Y4：ADDV V4,V2,V3；加法5：SV Ry,V4；存结果 向量寄存器长度为64，向量长度为n，各功能部件的启动时间与上例相同。求总的执行时间。,本章内容性能评价向量指令处理时间Tvp一批向量指令的处理时间,3 之 2,举 例 解答,本章内容性能评价向量指令处理时间Tvp一批向量指令的处理时间,3 之 3,指令1、2，指令3、4和指令5分成三个编队，前两个编队中两条指令如采用链接技术执行，则：Tchime=3，Tloop=15，MVL=64，Tstart=12+7+12+6+12=49。,最大性能R,本章内容性能评价,R表示当向量长度为无穷大时的向量流水线的最大性能。常在评价峰值性能时使用，单位为MFLOPS。可表示为：其中：n为向量长度；Tn为一组向量操作的整个执行时间。,2 之 1,举 例 前例,本章内容性能评价,2 之 2,假设时钟频率为500MHZ。因为每个循环有2个浮点运算操作，所以：,半性能向量长度n1/2,本章内容性能评价,为达到一半R值所需的向量长度称为半性能向量长度n1/2，主要评价向量流水线建立时间对性能的影响。通常希望向量流水线有较小的 n1/2，例如：CRAY-1的n1/2 1020，CYBER 205的n1/2 100。,2 之 1,举 例 前例,本章内容性能评价,2 之 2,因为：R=250MFLOPS，因此有：2502 2 n1/2Tn1/2 500假设：n1/264，因此：Tn1/2 64+3 n1/2代入上式解得：n1/212.8所以：n1/213,向量长度临界值nv,本章内容性能评价,nv表示向量流水方式的工作速度优于标量串行方式工作时所需得向量长度临界值。该参数既衡量建立时间，也衡量标量/向量速度比对性能的影响。,2 之 1,举 例 前例,本章内容性能评价,2 之 2,对于前例，若按标量方式工作，则一个循环的执行时间为：10（建立循环的开销）+12（取数）+7（乘法）+12（取数）+6（加法）+12（存数）=59（个时钟周期），如按向量方式工作，则总执行时间为：Tn64=3n+64。所以：59nv=3nv+64，解得：,