1,第五章 向量流水处理,2,第一节 向量流水处理,提高标量流水线性能方法： 增加流水线段数，以减少t； 每个时钟同时启动多条指令； 减少相关，减少功能变换次数，增加处理指令条数。,向量操作特点： 向量元素间操作相互独立，无数据相关； 向量元素间操作相同，无功能变换； 相当于标量循环，对指令访问带宽的要求不高。 向量操作很适合于流水处理或并行处理。,3,一、向量处理方式 以向量操作D=A(B+C)为例。,1、横向处理方式 循环处理di=ai(bi+ci)。 特点：产生N次相关、2N次功能变换；不宜用于向量处理。,2、纵向处理方式 循环处理ei=bi+ci，再循环处理di=aiei。 特点：产生1次相关、1次功能变换，适合用于向量处理。,思考：针对不同的N，硬件可采用哪些结构实现？,纵向处理方式只适合于MEM-MEM型结构的处理方式。,4,3、纵横处理方式 对向量分组(n个元素)，组内纵向处理、组间横向处理。 特点：产生N/n次相关、N/n次功能变换； 很适合于REG-REG型结构的处理方式。,思考：如何确定向量寄存器中元素个数n？,5,二、向量指令,1、 R-R型的向量指令类型 向量-向量类：ViVjVk或VjVk,向量-标量类：SiVjVk ViVjSk或VjSk(向量规约),向量-MEM类： MVk或ViM； MVlVA或VlVAM(压缩与还原),回下页,6,2、 M-M型的向量指令类型 向量-向量类：M1(1:n)M2(1:n)M(1:n) 或M1(1:n)M(1:n) 向量-标量类：SiM1(1:n)M(1:n) M1(1:n)M2(1:n)Sk,3、 向量指令操作特点 向量指令是各分量之间的流水操作； 标量指令是各指令之间的流水操作； SIMD指令是各指令内部的操作并行。,转上页,7,三、向量访问模式与处理带宽问题,1、向量访问模式 向量一般按行、或按列存储。 向量访问各分量时步长可变，一般有按行、按列、或按对角线等方式访问。,2、向量存取指令与处理带宽 向量存取指令按访问模式存取相关分量从/到向量寄存器或向量缓冲器的相邻分量中； 要求存储器带宽较大，必须解决多个分量流水访问的冲突问题(如多个相邻分量在同一存储体内)。,8,第二节 向量处理机结构,一、M-M向量处理机结构,1、 向量处理机结构,M-M结构对存储系统带宽要求较高： 若向量处理部件流水间隔为t，存储系统带宽应达到3/t； 若读/写操作为2t，则存储系统带宽应达到6/t。,9,2、 存储系统设计 （1）提高存储系统带宽,存储器与三条总线连接， 同时只能被一条总线访问。,（2）提高向量存取性能 向量存取采用流水方式(左图)，不同向量并行存取(右图)。,回下页,10,（3）解决向量访问冲突 向量采用错位方式存储，解决按行、列、对角线访问时流水操作的存储体冲突；,增加可变延迟器，可解决访问的操作冲突。,转上页,11,二、R-R向量处理机结构,1、 向量处理机结构,指令处理部件：标量指令直接控制，向量指令传递控制； 向量寄存器：V； 向量存取部件：设置多级缓冲器，缓冲主存与向量寄存器速度差，M-M型向量处理机简单得多(只需缓冲几个分量)。,12,2、 存储系统设计 （1）提高存储系统带宽 对MEM的带宽需求相对M-M型向量处理机要低得多； 一般采用单总线即可。,（2）提高向量存取性能 向量存储从无序到错位存储，提高向量存取性能； 设置指令、数据缓冲器，减少存取频率； （见下页图） 设置地址缓冲器，实现成组交换，提高存取性能。,（3）解决向量访问冲突 向量采用错位存储，从空间上解决访问的存储体冲突； 增加可变延迟器，从时间上解决访问的存储体冲突； 设置向量存取指令，指令串行执行可解决访问的操作冲突。,转下页,转下二页,13,中间缓冲器： 地址寄存器A(824bit)，中间寄存器B (6424bit)， 中间寄存器T(64个64bit)。,回上页,14,第三节 增强向量处理性能方法,一、多功能部件并行操作 使向量机中多个功能部件能并行操作，提高向量处理性能。,并行操作条件：,(1)不存在向量寄存器使用冲突 不允许出现RAW、WAR、WAW、RAR相关。,例如：V4V1+V2 V5V2V3,(2)不存在功能部件使用冲突 每种功能部件一般只设置一个。,例如：V3V1V2 V6V4V5,15,二、链接技术 采用“相关专用通路”思想，解决向量寄存器的RAW相关。,例：执行指令V3A，V2V0+V1，V4V2V3,访存与浮点加可并行操作；,访存和浮点加与浮点乘有RAW相关性，链接技术可解决RAW相关，进行流水操作，以减少执行时间。,因同步要求，数据进入、流出功能部件需1拍时间。,回下页,16,链接条件：,(1)不存在功能部件使用冲突；,(2)共用向量寄存器的向量长度、起始地址、偏移量、步长均相等；,(3)参与链接的先行指令产生结果周期相同(链接指令为多操作数时，若某操作数为Vi时可认为周期相同)；,(4)只有在先行指令产生第一结果分量的那个时钟方可链接，否则不行。,上例时间分析： 全串行：2*(1+6+1)+N-1+(1+7+1)+N-1=3N+22； 并行加串行：(1+6+1)+N-1+(1+7+1)+N-1=2N+15； 并行加链接：(1+6+1)+(1+7+1)+N-1=N+16。,注意：不同向量机对向量指令的链接要求有所不同。,转上页,17,三、条件语句和稀疏向量的加速处理,1、加速条件语句 标量循环语句向量化，可提高流水线效率。,条件语句循环向量化方法：利用向量屏蔽控制技术实现。 即用条件语句循环生成VM，用带VM向量指令实现,向量屏蔽控制技术的系统支持：,增加VM置位和复位指令，增加带VM运算命令。,2、加速稀疏矩阵处理,存储：压缩向量和位向量； 操作：带VM运算指令。,系统支持：带VM的存取指令、运算指令。,18,四、加速向量归约操作,应用需求：,常规方法： C=AB； -向量流水操作 对C进行递归折叠求和。-标量循环(n次)操作,加速方法： C=AB； -向量流水操作 s= C。 -向量归约操作,向量归约操作的实现方法： 向量归约部件和向量归约指令； 可归约的向量加法部件+对部分分量折叠求和。,回下页,19,可归约的向量加法部件的实现方法： 常规向量加法-V0V1+V2，源和目标向量各不相同； 带归约向量加法V0V0+V1，源和目标向量相同。,实现 （见下页图，设加法部件需8个时钟周期） 置V0各分量为0(乘法为1)，V0和V1计数器均为0； V0计数器为0，V1计数器每时钟加1，直到第一个结果分量出来； V0和V1计数器每时钟加1，直到V1计数器等于向量计算长度为止，V0的最后8个分量为V10至V163之和。,转上页,回下页,20,常规方法与加速方法性能比较： 常规方法- T=p*(n/2+1)，上例T=8*63； 加速方法- T=p+n+p*(n/2p+1)，上例T=8+64+8*7。,转上页,21,五、向量化编译技术,1、通用优化方法 公共子表达式消除、常数调入、复制语句传递等。,2、循环体优化 固定表达式移出、归约变量消除，向量指令表示等。,3、向量寄存器优化分配 重新分配向量寄存器，减少向量寄存器使用冲突。,4、向量指令并行化 重新排序向量指令，减少流水功能转换频率，争取功能部件操作并行、向量指令链接。,22,六、向量指令性能分析,1、向量执行时间 Tvp=Tst+nIr Tst -启动时间，Ir -启动率，n向量长度,对M-M型结构，Tst为取数等待及流水线深度时间； 对R-R型结构，Tst仅为流水线深度时间。,影响因素： 向量长度、向量指令间功能和数据相关性。 向量流水线深度对Tvp的影响较小。,提高性能方法： 增加n，可提高流水效率，减小Tst对Tvp影响； 尽量减小Tst，提高短向量的处理性能。,23,2、最大性能R 用于衡量向量流水线的峰值性能。,例：机器时钟频率200MHz，存取、加、乘指令分别需12、6、7个时钟周期，计算Y=aX+Y需指令MxV0；F0V0V1；MyV2；V1+V2V3；V3My。,指令可编成和、和、共3队，各队串行执行； 向量启动开销=12+7+12+6+12=49Tc； 执行标量代码开销(归入向量启动开销)设为15Tc；,回下页,24,3、半性能向量长度n1/2 衡量向量流水线建立时间对处理性能的影响。,上例：设n1/264，,转上页,回下页,25,4、向量流水优于标量的向量长度nv 衡量向量流水建立时间、标量和向量速度比对处理性能的影响。,上例：标量循环一次T=10+49=59Tc，10为建立循环时间；,则64+3nv=59nv； nv=64/562。,三种性能指标关系示意图：,转上页,