计算机体系结构(金星)第五章重叠、流水与向量之二VIP

流水线断流的原因,编译形成的目标程序不能发挥流水结构的作用存储系统供不上为连续流动所需的指令和操作数相关中断,4流水线相关,根据相关对程序的影响把流水线相关分为以下两类：局部相关：全局相关：,局部相关,只影响相关的两条或几条指令，最多影响流水线某段工作的推后，不会改动指缓中预取的指令，即数据相关产生的原因：一组指令中，某条指令要用到前面的指令的结果，但由于流水方式中前面指令的结果还没出来，这些指令都还在流水线中重叠执行。处理方案推后后续指令对相关单元的读，直到前面的指令写入完成。设置相关直接通路改变流动方式,同步流动与异步流动,同步流动：任务流出流水线的顺序与进入流水线的顺序相同。异步流动：任务流出流水线的顺序与进入流水线的顺序不同。,异步流动可能产生的相关,写后读相关(RAW：readafterwrite):对同一个单元，在先的指令先写入，在后的指令才能读的关联写后写相关(WAW：writeafterwrite)对同一个单元，在先的指令先写入，在后的指令才能写入的关联读后写相关(RAW：readafterwrite)对同一个单元，在先的指令先读，在后的指令才能写的关联,(2)全局相关,已进入流水线的转移指令特别是条件转移指令和其后续指令之间的相关，即控制相关产生的原因：流水线遇到分支指令和其他会改变PC值的指令。解决方案猜测法加快和提前形成条件码采用延迟转移技术加快短循环程序的处理,猜测法思路：根据历史记录，将出现概率大的分支装入指缓。,加快和提前形成条件码思路：不等指令执行完提前形成条件码加快单条指令内部条件码的形成在一段程序内部提前形成条件码,LOADR1,NUMLOOP:DECR1BNELOOPHELTNUM:N,LOADR1,NUMLOOP:DECR1BNELOOPHELTNUM:N,采用延迟转移技术,ADDR1，R2JMPNEXT2NEXT1:SUBR3，R4nNEXT2:MOVER4，A,JMPNEXT2ADDR1，R2NEXT1:SUBR3，R4nNEXT2:MOVER4，A,用软件方法将转移指令与其不相关的指令交换位置。,加快短循环程序的处理将长度小于指缓容量的短循环程序整个一次性放入指缓内，并暂停预取指令恒猜循环分支法,(3)流水机器的中断处理,不精确断点法当指令I有中断，未进入流水线的后续指令不再进入，已在流水线的指令仍继续流完，然后才转入中断处理程序。断点为目前流水线的的最后一条指令。精确断点法当指令I有中断，目前流水线中I之前的指令做完，I为断点，目前流水线中I之后的指令现场保存起来。,(4)非线性流水线的调度问题,调度问题的提出：一个任务在通过非线性流水线时对有些功能段要通过多次，所以容易与紧跟而来的后继任务发生设备争用。调度机构的作用就是合理安排前后任务进入流水线的相差时间，既要避免争用，又要使相差时间尽可能少，以提高吞吐率。,非线性流水线的表示,非线性流水线的连接图,非线性流水线的预约表,例：某非线性流水线的预约表如下所示,作禁止表F作初始冲突向量C作状态转移图作平均间隔拍数表,不改变流水线结构的调度方法步骤,第一步：作延迟禁止表F,F=1，5，6,8,将流水线中所有各段对一个任务流过时会争用同一段的节拍间隔数汇集在一起构成一个延迟禁止表,由预约表得到禁止向量的方法预约表的每一行中任意两个“”之间的距离都计算出来，去掉重复的，这种数组成的一个数列就是这条非线性流水线的禁止向量。,第二步：作初始冲突向量C,冲突向量：用m位二进制编码表示，m是禁止向量的最大距离。C=（CmCm-1C3C2C1）Ci=1表示间隔拍数为i时会冲突，Ci=0表示间隔拍数为i时不会发生冲突，长度是禁止向量的最大距离。由禁止向量F=1，5，6,8可得：冲突向量C=（C8C7C6C5C4C3C2C1）C1=C5=C6=C8=1，其余位为0冲突向量为C=(10110001),第三步：作状态转移图,冲突向量中，位=0表示不发生冲突，其位置号是不发生冲突的间隔拍数从初始状态开始，检查冲突向量中为0的位，有几个0，就会有几个新的冲突向量下一个冲突向量=上一个冲突向量右移n位or初始冲突向量逐次计算新的冲突向量，并用有图连接。有向弧上的数字表示产生新的冲突向量所需要的间隔拍数,10110001,10110111,10111101,10111111,7*,3,4,7*,2,7*,10111011,4,3,7*,2,7*,从“根结点”开始画；每个结点中有几个“0”就要发出几条边下一个结点=上一个结点右移n位or根结点,第四步：作平均间隔拍数表,a调度方案的产生：从初始状态出发，沿箭头方向，每走一个闭环，就是一个方案若中间遇到小闭环，也作为一个方案遍历初始状态中的每一个Ci=0的回路。,b计算所有调度方案的平均间隔拍数,设某方案为(t1,t2,t3)平均间隔拍数=循环周期中的各间隔拍数之和/一个周期的任务数=(t1+t2+t3)/3,c找出最优方案，计算流水线的性能,流水时间=一个任务所需的拍数+t1*间隔t1拍启动的任务数+t2*间隔t2拍启动的任务数+最大吞吐率=一个周期中的任务数/循环周期中的各间隔拍数之和=平均间隔拍数的倒数,最优方案：平均间隔拍数最少的方案,三向量的流水处理与向量流水处理机,1、向量的流水处理定义：使向量运算能充分发挥流水线的效率向量处理方式：(1)水平(横向)处理方式(2)垂直(纵向)处理方式(3)分组(纵横)处理方式,例：D=A*(B+C)，其中ABCD都是元素个数为n的向量。for(I=1,I=N,I+)kI=(bI+cI);dI=aI*kI;,(1)水平(横向)处理方式,定义：向量计算按行的方式从左至右横向地进行。处理方式：,逐个分量进行处理：假设中间结果为kI计算第1个分量：K1B1C1D1A1K1计算第2个分量：K2B2C2D2A2K2最后一个分量：KnBnCnDnAnKn,存在两个问题：在计算向量的每个分量时，都发生写读数据相关。流水线效率低如果采用多功能流水线，必须频繁进行流水线切换横向处理方式不适合向量处理机即使在标量处理机中，也经常通过编译器进行指令流调度。,(2)垂直(纵向)处理方式,定义：向量计算按列的方式自上而下纵向地进行。处理方式：,第一批：K1=B1+C1K2=B2+C2Kn=Bn+Cn第二批：D1=A1K1D2=A2K2Dn=AnKn采用向量指令只需要2条：VADDB，C，KVMULA，K，D,向量指令内无相关，指令间有一次数据相关，不同的运算操作只需要切换1次。这种处理方式适用于向量处理机,(3)分组(纵横)处理方式,定义：横向处理和纵向处理相结合的方式。用于寄存器-寄存器结构的向量处理机中，向量寄存器的长度是有限的。当向量长度n大于向量寄存器长度m时，需要分组处理。处理方式：将长度为n的向量分成若干组，每组长度为m，组内按纵向方式处理，依次处理各组。分组方法：nkm，其中：为余数，共分组。组内采用纵向处理方式，组间采用横向处理方式。因此，也称为分组处理方式，纵横加工方式等。,运算过程为：第组：V(1,m)=B(1,m)+C(1,m)D(1,m)=A(1,m)V(1,m)第组：V(1,m)=B(m+1,2m)C(m+1,2m)Y(m+1,2m)=A(m+1,2m)V(1,m)最后第k+1组：K(1,m)=B(km+1,N)+C(km+1,N)D(km+1,N)=A(km+1,N)+V(1,m),每组用两条向量指令，组内发生数据相关一次，若用静态多功能流水线，则各组要2次功能切换,2向量流水处理机,定义：具有向量数据表示和相应的向量指令的处理机。,CRAY-1向量处理机结构,向量指令的类型,以CRAY-1向量处理机为例，有四类指令，两种指令格式：(1)向量与向量操作：ViVjOPVk(2)向量与标量操作：ViSjOPVk(3)向量取：Vi存储器(4)向量存：存储器Vi,向量指令的类型：,第一类向量指令,第二类向量指令,向量运算中的相关和冲突,(1)Vi冲突(向量寄存器冲突，源向量冲突)(2)运算部件冲突。V0V1V2V0V1V2V3V4V5V3V1V4(a)功能部件冲突(b)源向量冲突,(3)写后读数据相关。V0V1V2V0V1V2V3V4V5V3V0V4(c)不相关的指令(d)写后读数据相关,向量链接技术(chaining),链接技术：只要不出现功能部件冲突和源向量冲突，有写后读数据相关的向量指令仍能重叠并行处理，这种技术称为两条流水线的链接技术。提高向量处理机性能的常用技术,用向量指令实现：D=A*(B+C),V0BV1C1：V3A2：V2V0V13：V4V2V3,分析：第1、2条指令没有数据相关和功能部件冲突第3条指令与第1、2条指令均存在写后读数据相关,1：V3A2：V2V0V13：V4V2V3,访存流水线,浮乘流水线,浮加流水线,三种执行方式比较：(1)如果向量长度为N，三条指令采用串行方法执行的时间为：(1+6+1)+N-1+(1+6+1)+N-1+(1+7+1)+N-1=3N+22拍(2)如果前两条指令并行执行，第三条指令串行执行，则执行时间为：(1+6+1)+N-1+(1+7+1)+N-1=2N+15拍(3)如果采用链接技术，则执行时间为：(1+6+1)+(1+7+1)+(N-1)=17+N-1=N+16拍,V0BV1C1：V3A2：V2V0V13：V4V2V3第1、2条指令没有数据相关和功能部件冲突，可以同时开始执行。第3条指令与第1、2条指令均存在写后读数据相关，可以链接执行。链接的时机：前一条指令的第1个结果分量送入结果向量寄存器组的那一个时钟周期为允许链接时间,用向量指令实现：D=A*(B+C),实现链接的条件：,(1)存在写后读数据相关，但没有向量寄存器冲突和运算部件冲突。(2)只有第一个结果送入向量寄存器的那一个周期可以链接。(3)先行的两条指令产生运算结果的时间必须相等。(4)两条向量指令的向量长度必须相等。,四、指令级调度并行的超级处理机,超标量处理机超流水线处理机超长指令字技术VLIW,超标量技术,工作原理：一个时钟节拍内同时发射多条指令基本结构：设置多条指令流水线，每个Dt同时流出m条指令