第5章重叠、流水和向量处理机.ppt

第第5 5章章 重叠、流水和向量处理机重叠、流水和向量处理机5.1 5.1 重叠方式重叠方式5.2 5.2 流水方式流水方式5.3 5.3 向量的流水处理与向量流水处理机向量的流水处理与向量流水处理机5.4 5.4 指令级高度并行的超级处理机指令级高度并行的超级处理机本章重点：本章重点：流水的性能分析及时空图流水的性能分析及时空图,相关处理、流相关处理、流水线调度、向量指令流水的并行与链接。水线调度、向量指令流水的并行与链接。本章难点：本章难点：针对所要求的重叠关系，计算全部指令针对所要求的重叠关系，计算全部指令完成的时间。根据题目要求画出功能静态流完成的时间。根据题目要求画出功能静态流水时空图，计算吞吐率、效率和加速比。单水时空图，计算吞吐率、效率和加速比。单功能非线性流水线的调度。向量指令间的并功能非线性流水线的调度。向量指令间的并行、链接、串行的判断及所需拍数的计算。行、链接、串行的判断及所需拍数的计算。5.1 5.1 重叠方式重叠方式5.1.1 5.1.1 基本思想和一次重叠基本思想和一次重叠一条指令的执行过程可以分为多个阶段，一条指令的执行过程可以分为多个阶段，如：如：1.取指取指2.分析分析3.执行执行可以有多种处理方式：顺序执行、一次重叠、可以有多种处理方式：顺序执行、一次重叠、二次重叠二次重叠。1 1、顺序解释：、顺序解释：各条指令之间顺序串行地进行；每条指各条指令之间顺序串行地进行；每条指令内部的各个微操作也顺序串行地进行。令内部的各个微操作也顺序串行地进行。2 2、解释一条机器指令的微操作可归并成解释一条机器指令的微操作可归并成取指令，分析取指令，分析和执行和执行三个部份三个部份 执行执行n n条指令所用的时间为：条指令所用的时间为：如果每段时间都为如果每段时间都为t t，则执行则执行n n条指令所用的时条指令所用的时间为：间为：T=3ntT=3nt对一条机器对一条机器指令的解释指令的解释优点：优点：控制简单，节省设备。控制简单，节省设备。缺点：缺点：执行指令的速度慢，功能部件的利用率执行指令的速度慢，功能部件的利用率很低。很低。3 3、指令的重叠：、指令的重叠：是在解释第是在解释第K K条指令的操作完成条指令的操作完成之前，就可开始解释第之前，就可开始解释第K+1K+1条指令。条指令。取指令取指令k 分析分析k 执行执行k 取指令取指令k+1 分析分析k+1 执行执行k+1取指取指k+2 分析分析k+2 执行执行k+2取指取指k+1 分析分析k+1 执行执行k+1取指取指k分析分析k执行执行k重叠解释的一种方式（二次重叠）重叠解释的一种方式（二次重叠）4 4、重叠方式对计算机组成的要求、重叠方式对计算机组成的要求 解决主存冲突问题（在同一时刻同时访问第解决主存冲突问题（在同一时刻同时访问第K K条条指令的操作数和第指令的操作数和第K+1K+1条指令的指令码）：条指令的指令码）：一是把操一是把操作数和指令分别存放在两个独立的存储器；二是采用作数和指令分别存放在两个独立的存储器；二是采用多体交叉主存系统；三是增设采用先进先出方式工作多体交叉主存系统；三是增设采用先进先出方式工作的指令缓冲寄存器。的指令缓冲寄存器。5 5、一次重叠：、一次重叠：指令分析部件和指令执行部件任何时候指令分析部件和指令执行部件任何时候只有相邻两条指令在重叠解释的方法。只有相邻两条指令在重叠解释的方法。分析分析k执行执行k分析分析k+1分析分析k+2执行执行k+1执行执行k+2一次重叠工作方式一次重叠工作方式“一次重叠一次重叠”解释的优点解释的优点:省硬件省硬件,简化控制简化控制,指令的执行时间缩短指令的执行时间缩短,功能部件功能部件的利用率明显提高。的利用率明显提高。（1 1）为了实现）为了实现“执行执行 k k”与与 “分析分析k+1 k+1”，硬件还应有硬件还应有独立独立 的指令分析部件和指令执行部件；的指令分析部件和指令执行部件；以增加某些硬件为代价的。以增加某些硬件为代价的。（2 2）要解决因条件转移指令带来的重叠效率下降问题；）要解决因条件转移指令带来的重叠效率下降问题；采取延迟转移技术。采取延迟转移技术。（3 3）要解决）要解决“相关相关”问题。问题。5.1.2 5.1.2 相关处理相关处理1 1、基本概念、基本概念“相关相关”：邻近指令之间出现关联，为了防出错邻近指令之间出现关联，为了防出错 让它们不能同时解释的现象；让它们不能同时解释的现象；“数相关数相关”：邻近两条指令的数据地址有了关联；邻近两条指令的数据地址有了关联；“指令相关指令相关”：采用机器指令可修改的方法在第采用机器指令可修改的方法在第K K条指令执行后才产生第条指令执行后才产生第K+1K+1条指令的现象。条指令的现象。即：即：为了避免出错，第为了避免出错，第k k、第、第k+1k+1条指令就不能同时条指令就不能同时 解释。解释。2 2、指令相关的处理：指令相关的处理：禁止指令修改，还可另设置一条禁止指令修改，还可另设置一条执行指令来解决程序设计灵活性。执行指令来解决程序设计灵活性。3 3、主存空间数相关的处理：主存空间数相关的处理：推后读推后读 。推后读是指若出现相邻两条指令之间出现对主存推后读是指若出现相邻两条指令之间出现对主存同一单元要求先写后读的关联。同一单元要求先写后读的关联。4 4、通用寄存器组相关的处理通用寄存器组相关的处理 通用寄存器组数相关的处理方法：通用寄存器组数相关的处理方法：推后推后“分析分析k+1”k+1”和设置和设置“相关专用通路相关专用通路”，前面降低速度为代，前面降低速度为代价，后者增加硬件成本为代价。价，后者增加硬件成本为代价。设置设置“相关专用通路相关专用通路”是指第是指第K K条指令的运算结条指令的运算结果直接通有硬件专用通道回送到寄存器。果直接通有硬件专用通道回送到寄存器。通用寄存器组基址值或变址值相关的处理：通用寄存器组基址值或变址值相关的处理：方法方法同上类拟，只不推后分析的推后时间不同及设置同上类拟，只不推后分析的推后时间不同及设置“相关专用通路相关专用通路”回写是到访存操作数地址形成机构。回写是到访存操作数地址形成机构。5.2 5.2 流水方式流水方式5.2.1 5.2.1 基本概念基本概念1.1.流水是重叠的引申流水是重叠的引申流水流水是重叠的引申：把指令的解释过程分为是重叠的引申：把指令的解释过程分为更多子过程；更多子过程；取指令取指令指令译码指令译码取操作数取操作数入入出出执行执行指令解释的流水处理指令解释的流水处理1时间时间空间空间0t1t2t3t4t52345123451234512345t6t7t8取指令取指令指令译码指令译码取操作数取操作数执行执行流水处理的时空图流水处理的时空图流水的最大吞吐率流水的最大吞吐率：指流水线满负荷每隔：指流水线满负荷每隔t t流出一个结果时所达到的吞吐率；流出一个结果时所达到的吞吐率；流水的最大吞吐率是取决于流水的最大吞吐率是取决于子过程的经过时间子过程的经过时间 t t，t t越小，流水线的最大吞吐率就越高。越小，流水线的最大吞吐率就越高。时钟信号周期不得低于速度最慢子部件的经过时钟信号周期不得低于速度最慢子部件的经过时间与锁存器的存取时间之和；时间与锁存器的存取时间之和；子过程的细分会因锁存器数增多而增大任务或子过程的细分会因锁存器数增多而增大任务或指令流过流水线的时间，这在一定程度上会抵指令流过流水线的时间，这在一定程度上会抵消子过程细分使吞吐率提高的好处。消子过程细分使吞吐率提高的好处。2.2.流水线的分类流水线的分类计算机系统在不同等级上的流水线计算机系统在不同等级上的流水线（处理的级别）（处理的级别）（1 1）流水的向下扩展指的是把子过程进一步细分，让每个）流水的向下扩展指的是把子过程进一步细分，让每个子过程经过的时间都同等程度地减少，吞吐率就会进一子过程经过的时间都同等程度地减少，吞吐率就会进一步提高；步提高；部件级流水线（操作流水线）部件级流水线（操作流水线）。（2 2）流水的向上扩展可理解为在多个处理机之间的流水。）流水的向上扩展可理解为在多个处理机之间的流水。系统级流水是指构成计算机系统的多个处理机之间的系统级流水是指构成计算机系统的多个处理机之间的流水，也称为宏流水。流水，也称为宏流水。处理机级流水线处理机级流水线,又称为指令流又称为指令流水线水线 (Instruction Pipelining)(Instruction Pipelining)。处理处理机机1处理处理机机2处理处理机机n数据集数据集处理机间的流水处理处理机间的流水处理从流水线的功能的多少来分，可分为单功能流从流水线的功能的多少来分，可分为单功能流水线和多功能流水线水线和多功能流水线（流水线具有的功能）（流水线具有的功能）（1 1）单功能流水线只能实现单一功能的流水。）单功能流水线只能实现单一功能的流水。（2 2）多功能流水线指的是同一流水线的各个段）多功能流水线指的是同一流水线的各个段之间可以有多种不同的联接方式以实现多种不之间可以有多种不同的联接方式以实现多种不同的运算或功能。同的运算或功能。输输入入减减阶阶对阶移位对阶移位相相加加规格化规格化相相乘乘累累加加输输出出21543678输输入入减减阶阶对阶移位对阶移位相相加加规格化规格化输输出出21543678输输入入相相乘乘累累加加输输出出21543678（a a）流水线的）流水线的 功能段功能段（b b）浮点加减法运）浮点加减法运 算时的联接算时的联接（c c）定点乘法）定点乘法 时的联接时的联接ASCASC机器运算器的流水线机器运算器的流水线按多功能流水线的各段能否允许同时用于多种按多功能流水线的各段能否允许同时用于多种不同功能联接流水，可把流水线分为静态流水不同功能联接流水，可把流水线分为静态流水线和动态流水线线和动态流水线（1）静态流水线在某一时间内各段只能按一种功能联接）静态流水线在某一时间内各段只能按一种功能联接流水，只有等流水线全部流空后，才能切换成按另一流水，只有等流水线全部流空后，才能切换成按另一种功能联接流水。种功能联接流水。（2）动态流水线的各功能段在同一时间内可按不同运算）动态流水线的各功能段在同一时间内可按不同运算或功能联接。或功能联接。1 1时间时间空间空间0 02 2 3 3 n n1 1 2 2 3 3 n n1 1 2 2 3 3 n n1 1 2 2 3 3 n n1 1 2 2 3 3 n n1 1 2 2 3 3 n n1 1 2 2 3 3 4 4 1 1 2 2 3 3 1 1 2 2 1 1输入输入求阶差求阶差对阶对阶尾数加尾数加规格化规格化尾数乘尾数乘累加累加输出输出静态流水线时空图静态流水线时空图浮点加法浮点加法定点乘法定点乘法1 1时间时间空间空间0 02 2 3 3n n1 1 2 2 3 3n n1 1 2 2 3 3n n1 1 2 2 3 3n n1 1 2 2 3 3n n1 1 2 2 3 3n n输入输入求阶差求阶差对阶对阶尾数加尾数加规格化规格化尾数乘尾数乘累加累加输出输出动态流水线时空图动态流水线时空图1 1 2 2 3 35 54 46 61 1 2 2 3 35 54 41 1 2 2 3 3 4 41 1 2 2 3 3浮点加法浮点加法定点乘法定点乘法以机器所具有的数据表示可以把流水线处理以机器所具有的数据表示可以把流水线处理机分为标量流水机和向量流水机机分为标量流水机和向量流水机（1）标量流水机没有向量数据表示，只能用标）标量流水机没有向量数据表示，只能用标量循环方式来处理向量和数组。量循环方式来处理向量和数组。（2）向量流水机指的是机器有向量数据表示，）向量流水机指的是机器有向量数据表示，设置有向量指令和向量运算硬件，能流水地设置有向量指令和向量运算硬件，能流水地处理向量和数组中的各个元素。处理向量和数组中的各个元素。从流水线中各功能段之间是否有反馈回路，从流水线中各功能段之间是否有反馈回路，可把流水线分为线性流水和非线性流水可把流水线分为线性流水和非线性流水（1）流水线各段串行联接，各段只经过一次，没有反）流水线各段串行联接，各段只经过一次，没有反馈回路的，称为线性流水线。馈回路的，称为线性流水线。每个流水段都流过一次，每个流水段都流过一次，且仅流过一次。线性流水线能够用流水线连接图唯一表示。且仅流过一次。线性流水线能够用流水线连接图唯一表示。（2）流水线除有串行联接的通路，还有反馈回路，使）流水线除有串行联接的通路，还有反馈回路，使任务流经流水线需多次经过某个段或越过某些段，任务流经流水线需多次经过某个段或越过某些段，则称为非线性流水线。则称为非线性流水线。在流水线的某些流水段之间在流水线的某些流水段之间有反馈回路或前馈回路。有反馈回路或前馈回路。S1输入输入S2S3输出输出前馈回路前馈回路反馈回路反馈回路一种简单的非线性流水线一种简单的非线性流水线流水线的其他分类方法流水线的其他分类方法（1 1）按照控制方式：）按照控制方式：同步流水线和同步流水线和 异步流水线。异步流水线。（2 2）顺序流水线与乱序流水线顺序流水线与乱序流水线：乱序流水线又称为无序流水线、错序乱序流水线又称为无序流水线、错序流水线或异步流水线等。流水线或异步流水线等。5.2.2 5.2.2 流水线处理机的主要性能流水线处理机的主要性能 衡量流水线处理机的性能主要使吞吐率衡量流水线处理机的性能主要使吞吐率（Through Put Through Put Rate,TPRate,TP）和效率和效率（Efficiency,Efficiency,）和和加速比加速比。1.1.吞吐率吞吐率吞吐率使流水线单位时间里能流出的任务数或结吞吐率使流水线单位时间里能流出的任务数或结果数。果数。求流水线吞吐率的最基本公式：求流水线吞吐率的最基本公式：TPTP=n n/T Tk kn n为任务数为任务数,T Tk k为完成为完成n n个任务所用时间个任务所用时间各段执行时间相等，输入连续任务情况下完各段执行时间相等，输入连续任务情况下完成成n n个连续任务需要的总时间为：个连续任务需要的总时间为：T Tk k=(=(k k+n n-1)-1)D Dt t k k为流水线的段数，为流水线的段数，D Dt t为时钟周期为时钟周期1时间时间空间空间S123 n-1 nS2S3S4123 n-1 n123 n-1 n123 n-1 nk t(n-1)tn t(k-1)tT吞吐率：吞吐率：最大吞吐率为：最大吞吐率为：各段执行时间不相等、输入连续任务情况下：各段执行时间不相等、输入连续任务情况下：吞吐率为：吞吐率为：最大吞吐率为：最大吞吐率为：瓶颈子过程瓶颈子过程：流水线中经过时间最长的子过程。：流水线中经过时间最长的子过程。消除瓶颈的两种方法：消除瓶颈的两种方法：细化与并联；细化与并联；最大吞吐率：最大吞吐率：流水线各段执行时间不相等的解决办法流水线各段执行时间不相等的解决办法S1输输入入 t1=tS2 t2=3 tS3 t3=tS4 t4=t输输出出1时间时间空间空间S1S2S3S4S S ti(n-1)t2Tk23n123n123n123n一是将一是将“瓶颈瓶颈”流水段细分流水段细分(如果可分的话如果可分的话)：二是将二是将“瓶颈瓶颈”流水段重复设置（并联）：流水段重复设置（并联）：S1输入输入输出输出D DtS2-1D DtS2-2D DtS2-3D DtS3D DtS4D DtS2(3D Dt)S1输入输入输出输出D Dt1=D DtS2-1S2-1S2-1S3S4D Dt3=D DtD Dt4=D DtD Dt2=3D Dt1时间时间空间空间2 3nS1S2-14 5 614-2-1n-225n-136n1 2 3n4 5 6-2-11 2 3n4 5 6-2-1S2-2S2-3S3S4流水段重复设置的流水线流水段重复设置的流水线设一设一m m段流水线各段经过的时间均为段流水线各段经过的时间均为t t0 0，则第则第1 1条指令从流入到流出需要条指令从流入到流出需要T T0 0=m=mt t0 0的流水建立时的流水建立时间，之后每隔间，之后每隔t t0 0就可流出一条指令，这样，完成就可流出一条指令，这样，完成n n个任务共需时间个任务共需时间T=mT=mt t0 0+(n-1)+(n-1)t t0 0,流水线在这段时间里流水线在这段时间里的实际吞吐率为：的实际吞吐率为：TP=n/(TP=n/(m mt t0 0+(n-1)+(n-1)t t0 0)=1/)=1/t t0 0(1+(m-1)/n)1+(m-1)/n)=TPTPmaxmax/(1+(m-1)/n)/(1+(m-1)/n)不仅实际吞吐率总是小于最大吞吐率，而不仅实际吞吐率总是小于最大吞吐率，而且只有当且只有当nmnm时，才能使实际吞吐率接近于最时，才能使实际吞吐率接近于最大吞吐率。大吞吐率。加速比（加速比（SpeedupSpeedup）计算流水线加速比的基本公式：计算流水线加速比的基本公式：S S=顺序执行时间顺序执行时间T T0 0/流水线执行时间流水线执行时间T Tm m （1 1）各段执行时间相等，输入连续任务情况下）各段执行时间相等，输入连续任务情况下加速比为：加速比为：（2 2）最大加速比为：）最大加速比为：（3 3）各段执行时间不等，输入连续任务情况下各段执行时间不等，输入连续任务情况下实际实际加速比为：加速比为：如果线性流水线每段经过的时间如果线性流水线每段经过的时间 不等，其中瓶颈不等，其中瓶颈段的时间为段的时间为 ，则完成，则完成n n隔任务所能达到的隔任务所能达到的实际吞实际吞吐率为：吐率为：其加速比为：其加速比为：2.2.效率效率 流水线的效率流水线的效率是指是指流水线中设备的实际使用时间占流水线中设备的实际使用时间占整个运行时间之比，整个运行时间之比，也称流水线设备的时间利用率。也称流水线设备的时间利用率。如果是线性流水线且各段经过的时间相同，则在如果是线性流水线且各段经过的时间相同，则在T T时间时间里，流水线各段的效率都相同，均为里，流水线各段的效率都相同，均为0 0。即：即：整个流水线的效率：整个流水线的效率：从上式可以看出，只有当从上式可以看出，只有当nmnm时，时，才趋近于才趋近于1 1。对于。对于线性流水且每段经过的时间相等时，线性流水且每段经过的时间相等时，流水线的效率流水线的效率是正比于吞吐率的，即是正比于吞吐率的，即如果流水线各段经过的时间不等，各段的效率就会如果流水线各段经过的时间不等，各段的效率就会不等，可以得出整个流水线的效率：不等，可以得出整个流水线的效率：3.3.流水线工作举例流水线工作举例设向量设向量A A和和B B各有各有4 4个元素，在下图所示的静态双功能流个元素，在下图所示的静态双功能流水线上计算向量点积水线上计算向量点积其中，其中，1 2 3 51 2 3 5组成加法流水线，组成加法流水线，1 4 51 4 5组成乘法流水组成乘法流水线。又设每个流水线所经过的时间均为线。又设每个流水线所经过的时间均为 ，流水线输出，流水线输出可直接返回输入或暂存于相应缓冲寄存器中，其延迟时可直接返回输入或暂存于相应缓冲寄存器中，其延迟时间和功能切换时间都可忽略。请求出流水线从开始流入间和功能切换时间都可忽略。请求出流水线从开始流入到结果流出这段时间的实际吞吐率到结果流出这段时间的实际吞吐率TPTP和效率和效率。12345XYZ时间时间(t)空间空间123450 1 2 345 67 8 910 11 12 13 14 15 16a1b1a2b2a3b3a4b4ZY输入输入a1b1a2b2a3b3a4b4a1b1a2b2a3b3a4b4a1b1+a2b2a3b3+a4b4a1b1+a2b2a3b3+a4b4输出输出X流水线工作的时空图流水线工作的时空图由上图可以看出，在由上图可以看出，在1515个个 时间内流出时间内流出7 7个结果，其个结果，其实际吞吐率实际吞吐率TPTP为为7/7/（15 15 ），而顺序方式所需时间），而顺序方式所需时间为为4 3 +3 4 =24 4 3 +3 4 =24 ，因此，加速比为，因此，加速比为 S Sp p=24 /(15 )=1.6=24 /(15 )=1.6该流水线的效率可用阴影区面积和全部该流水线的效率可用阴影区面积和全部5 5个段的总时空区个段的总时空区面积之比求得，即面积之比求得，即影响效率提高的因素有：影响效率提高的因素有：1 1、静态多功能流水线按某种功能流水时，总有一些本功、静态多功能流水线按某种功能流水时，总有一些本功能用不到得段处于空闲；能用不到得段处于空闲；2 2、流水建立时，本功能要用到的某些段也有、流水建立时，本功能要用到的某些段也有部分处于空闲；部分处于空闲；3 3、功能切换时，增加了前一功能流水的排空、功能切换时，增加了前一功能流水的排空时间及后一功能流水的建立时间；时间及后一功能流水的建立时间；4 4、经常需要等待把上一步计算的结果输出回、经常需要等待把上一步计算的结果输出回授到输入，才能开始下一步的计算。授到输入，才能开始下一步的计算。5.2.3 5.2.3 流水机器的相关处理和控制机构流水机器的相关处理和控制机构 流水机器在遇到转移指令尤其是条件转移指令时，效流水机器在遇到转移指令尤其是条件转移指令时，效率也会显著下降。率也会显著下降。转移指令和其后的指令之间存在关联，使之不能同时解转移指令和其后的指令之间存在关联，使之不能同时解释，称为释，称为全局性相关全局性相关。指令相关、主存操作数相关和通用寄存器组相关及基址指令相关、主存操作数相关和通用寄存器组相关及基址或变址值相关，只影响相关的两条或几条指令，最多或变址值相关，只影响相关的两条或几条指令，最多影响流水线某些段工作的推后，不会改动指缓中预取影响流水线某些段工作的推后，不会改动指缓中预取到的指令，影响是局部的，称为到的指令，影响是局部的，称为局部性相关局部性相关。1.1.局部性相关的处理局部性相关的处理重叠机器处理局部相关的方法：重叠机器处理局部相关的方法：（1 1）推后后续指令对相关单元的读，直至在先的）推后后续指令对相关单元的读，直至在先的指令写入完成。指令写入完成。（2 2）设置相关直接通路，将运算结果经相关直接）设置相关直接通路，将运算结果经相关直接通路直接送入所需部件。通路直接送入所需部件。任务在流水线中流动顺序的安排和控制可以有两种任务在流水线中流动顺序的安排和控制可以有两种方式：方式：（1 1）同步流动方式：同步流动方式：让任务（指令）流出流水线让任务（指令）流出流水线的顺序保持与流入流水线的顺序一致。的顺序保持与流入流水线的顺序一致。（2 2）异步流动方式：异步流动方式：让流出流水线的任务（指令）让流出流水线的任务（指令）顺序可以和流入流水线的顺序步同。顺序可以和流入流水线的顺序步同。异步流动方式带来的新的相关：异步流动方式带来的新的相关：（1 1）“写写-写写”相关相关 对同一单元要求在先的指令先写入，在后的对同一单元要求在先的指令先写入，在后的指令才能写入的关联称为指令才能写入的关联称为“写写写写”相关。相关。（2 2）“先读后写先读后写”相关相关 对同一单元要求在先的指令先读出，在后的对同一单元要求在先的指令先读出，在后的指令才写入的关联称为指令才写入的关联称为“先读后写先读后写”相关。相关。（3 3）“先写后读先写后读”相关相关 对同一单元要求在先的指令先写入，在后的对同一单元要求在先的指令先写入，在后的指令才读出的关联称为指令才读出的关联称为“先写后读先写后读”相关。相关。解决方法：解决方法：推后后续指令和设置相关直接通路。推后后续指令和设置相关直接通路。举例：举例：第第142142页页IBM 360/91IBM 360/91浮点执行部件。浮点执行部件。2.2.全局性相关的处理全局性相关的处理 全局性相关全局性相关指的是已进入流水线的转移指指的是已进入流水线的转移指令（尤其是条件转移指令）和后续指令之间的令（尤其是条件转移指令）和后续指令之间的相关。相关。（1 1）猜测法）猜测法 根据历史猜测出现概率大的分支装入指缓。根据历史猜测出现概率大的分支装入指缓。当当转移的两个分支概率不均等时，宜猜高概率分支。转移的两个分支概率不均等时，宜猜高概率分支。采用猜测法时应能保证猜错时可恢复分支点的处采用猜测法时应能保证猜错时可恢复分支点的处原先的现场，一般有三种方法：原先的现场，一般有三种方法：在机器沿猜测分支解释时，应当与正常情况下的指在机器沿猜测分支解释时，应当与正常情况下的指令解释不同。令解释不同。IBM360/91IBM360/91采取对指令只译码和准备好采取对指令只译码和准备好操作数，在转移条件码出现之前不运算。操作数，在转移条件码出现之前不运算。另一种方法时让它运算完但不送回运算结果。另一种方法时让它运算完但不送回运算结果。（早期使用的这两种方法都不方便）（早期使用的这两种方法都不方便）采用后援寄存器法。采用后援寄存器法。一旦猜错，就取出后援寄存器的内容来恢一旦猜错，就取出后援寄存器的内容来恢复分支点的现场。复分支点的现场。（2 2）加快和提前形成条件码）加快和提前形成条件码 不等指令执行完成提前形成条件码。不等指令执行完成提前形成条件码。尽快、尽快、尽早获得条件码，以便提前知道流向哪个分支，尽早获得条件码，以便提前知道流向哪个分支，会有利于流水机器简化对条件转移的处理。会有利于流水机器简化对条件转移的处理。两两个方面的措施：个方面的措施：加快单条指令内部条件码的形成，不等指令执加快单条指令内部条件码的形成，不等指令执行完就提前形成反映运算结果的条件码。行完就提前形成反映运算结果的条件码。在一段程序内提前形成条件码，这特别适合在一段程序内提前形成条件码，这特别适合于循环型程序在判断循环是否继续时的转移于循环型程序在判断循环是否继续时的转移情况。情况。（3 3）采取延迟转移）采取延迟转移用软件方法将转移指令与其前面不相关用软件方法将转移指令与其前面不相关的指令交换位置。的指令交换位置。这是用软件方法进行静态这是用软件方法进行静态指令调度的技术。指令调度的技术。（4 4）加快短循环程序的处理）加快短循环程序的处理 将长度小于指缓的循环程序一次性放入将长度小于指缓的循环程序一次性放入指缓，并暂停预取指令，指缓，并暂停预取指令，避免执行循环时由避免执行循环时由于指令预取导致指缓中需循环执行的指令被于指令预取导致指缓中需循环执行的指令被冲掉，减少了访主存重复取指的次数；冲掉，减少了访主存重复取指的次数；或者让循环出口端条件转移指令恒猜循环分支，或者让循环出口端条件转移指令恒猜循环分支，减少因条件分支造成流水线断流的机会。减少因条件分支造成流水线断流的机会。3.3.流水机器的中断处理流水机器的中断处理 流水机器处理中断主要是如何处理好断点流水机器处理中断主要是如何处理好断点现场的保护和恢复，而不是如何缩短流水线的现场的保护和恢复，而不是如何缩短流水线的断流时间。断流时间。“不精确断点不精确断点”法：法：不论指令不论指令i i在流水线在流水线的哪一段发生中断，未进入流水线的后续指令的哪一段发生中断，未进入流水线的后续指令不再进入，已在流水线的指令仍继续流完，然不再进入，已在流水线的指令仍继续流完，然后才转入中断处理程序。后才转入中断处理程序。“不精确断点不精确断点”法法不利于编程和程序的排错。不利于编程和程序的排错。“精确断点精确断点”法：法：不论指令不论指令i i是在流水是在流水线中哪一段响应中断，给中断处理程序的现线中哪一段响应中断，给中断处理程序的现场全都是对应场全都是对应i i的，的，i i之后流入流水线的指令之后流入流水线的指令的原有现场都能恢复。的原有现场都能恢复。“精确断点精确断点”法法需设置很多后援寄存需设置很多后援寄存器，以保证流水线内各条指令的原有现场都器，以保证流水线内各条指令的原有现场都能保存和恢复。能保存和恢复。4.4.流水线调度流水线调度（1 1）如果每拍向流水线送入一个新的任务，非线）如果每拍向流水线送入一个新的任务，非线性流水线会出现多个任务争用同一功能段的使性流水线会出现多个任务争用同一功能段的使用冲突现象。用冲突现象。流水线调度要解决的问题：流水线调度要解决的问题：究竟间隔几拍送究竟间隔几拍送入下一个任务，才既不发生功能段使用冲突，入下一个任务，才既不发生功能段使用冲突，又能使流水线有较高的吞吐率和效率。又能使流水线有较高的吞吐率和效率。为了对流水线的任务进行优化调度和控制，为了对流水线的任务进行优化调度和控制，19711971年年E.S.DavidsonE.S.Davidson等人提出使用一个等人提出使用一个二维的二维的预约表（预约表（Reservation Table)Reservation Table)。如果有一个由如果有一个由K K段组成的单功能非线性流水线，段组成的单功能非线性流水线，每个任务通过流水线需要每个任务通过流水线需要N N拍。利用类似画时拍。利用类似画时空图的方法可以得到该任务使用流水线各段空图的方法可以得到该任务使用流水线各段的时间关系表（即预约表）。的时间关系表（即预约表）。其中拍号其中拍号n n为任务经过流水线的时钟节拍号。为任务经过流水线的时钟节拍号。如果任务再第如果任务再第n n拍要用到第拍要用到第k k段就在相应第段就在相应第n n列列和第和第k k行的交点处用行的交点处用表示。现设流水线由表示。现设流水线由5 5段组成，段号段组成，段号k k分别为分别为1515，任务经过流水线，任务经过流水线总共需总共需9 9拍，其预约表如下图所示：拍，其预约表如下图所示：1 1 2 2 3 3 4 45 5 6 6 7 7 8 8 9 91 1 2 2 3 34 4 5 5 拍号拍号n n段段号号k k（a）单功能流水线预约表举例）单功能流水线预约表举例7 71011000110110111101111011011101110111111初始初始状态状态7 72 27 72 24 43 37 74 43 37 7（b b）单功能流水线）单功能流水线 的状态转移图的状态转移图图图5.27 5.27 流水线预约表及状态图举例流水线预约表及状态图举例数格子的游戏，如上图数格子的游戏，如上图5.275.27（a a），分别数出每），分别数出每行中两个打勾之间的间隔数，然后把所有行的间行中两个打勾之间的间隔数，然后把所有行的间隔数构成一个间隔集合，就是隔数构成一个间隔集合，就是延迟禁止表延迟禁止表了。了。冲突向量（冲突向量（C CN-1N-1C Ci iCC2 2C C1 1)中第中第i i位的状态表示位的状态表示与当时相隔与当时相隔i i拍给流水线送入后续任务是否会发拍给流水线送入后续任务是否会发生功能段冲突。生功能段冲突。如果不会发生冲突，令该位为如果不会发生冲突，令该位为“0”0”，表示允许送入；否则让该位为，表示允许送入；否则让该位为“1”1”，表，表示禁止送入。示禁止送入。冲突向量取冲突向量取N-1N-1位是因为经位是因为经N N拍后，任务已流出流拍后，任务已流出流水线不会与后续的任务争用流水线功能段了。水线不会与后续的任务争用流水线功能段了。只要按流水线状态图中由初始状态出发，能构成一种只要按流水线状态图中由初始状态出发，能构成一种间隔拍数呈周期性重复的方案来进行流水线的调度，间隔拍数呈周期性重复的方案来进行流水线的调度，都不会发生功能段使用冲突。要想找出一种最佳的调都不会发生功能段使用冲突。要想找出一种最佳的调度方案使流水线的吞吐率最高，只要计算出每种调度度方案使流水线的吞吐率最高，只要计算出每种调度方案的平均间隔拍数，从中找出最小者即可。方案的平均间隔拍数，从中找出最小者即可。由下表可见，采用先隔由下表可见，采用先隔3拍后隔拍后隔4拍轮流给流水线送入拍轮流给流水线送入任务的调度方案使最佳的，平均每隔任务的调度方案使最佳的，平均每隔3.5拍即可流入一拍即可流入一个任务，吞吐率最高。尽管（个任务，吞吐率最高。尽管（4，3）调度方案平均间）调度方案平均间隔拍数也是隔拍数也是3.5拍，但若实际流入任务数不是循环所需拍，但若实际流入任务数不是循环所需任务数的整数倍时，其实际吞吐率相对会低一些，所任务数的整数倍时，其实际吞吐率相对会低一些，所以不作为最佳调度方案。以不作为最佳调度方案。这是一种不等间隔的调度策这是一种不等间隔的调度策略，比起相等间隔的调度策略在控制上要复杂一些。略，比起相等间隔的调度策略在控制上要复杂一些。调度方案调度方案平均间隔拍数平均间隔拍数（2 2，2 2，7 7）3.673.67（2 2，7 7）4.504.50（3 3，4 4）3.503.50（4 4，3 3）3.503.50（3 3，4 4，7 7）4.674.67（3 3，7 7）5.005.00（4 4，3 3，7 7）4.674.67（4 4，7 7）5.505.50（7 7）7.007.00各种调度方案的平均间隔拍数的例子各种调度方案的平均间隔拍数的例子（2 2）预约表及流水线调度过程）预约表及流水线调度过程 根据预约表写出延迟禁止表根据预约表写出延迟禁止表F F；由延迟禁止表形成冲突向量由延迟禁止表形成冲突向量C C；由所有的向量图画出状态图；由所有的向量图画出状态图；由状态图形成最佳调度方案由状态图形成最佳调度方案。练习：练习：P158习题习题5.9 延迟禁止表延迟禁止表F=1F=1，3 3，4 4，88（第一行间隔（第一行间隔8 8，第二行间隔，第二行间隔1 1，第三行间隔，第三行间隔1 1，3 3，4 4，然后，然后间隔都为间隔都为1 1，合并），合并）冲突向量为冲突向量为C C：1000110110001101（写一个（写一个8 8位两进制数，根据禁位两进制数，根据禁止表倒着写）止表倒着写）画出状态图画出状态图（如图，当第二个任务在第二拍进入时，冲（如图，当第二个任务在第二拍进入时，冲突向量突向量C1C1为为1010111110101111，又分为两种情况：当第三个任务，又分为两种情况：当第三个任务在第在第5 5拍进入时，冲突向量拍进入时，冲突向量C2C2等于等于C0C0，当第三个任务在，当第三个任务在第第7 7拍进入时，冲突向量拍进入时，冲突向量C2C2也等于也等于C0C0），这时你就可以），这时你就可以画出最右边的三条线。以此类推，画出所有连线，这题画出最右边的三条线。以此类推，画出所有连线，这题倒也简单，一共有两个冲突向量，比例子好多了。）倒也简单，一共有两个冲突向量，比例子好多了。）写出各种方案的平均延迟表：写出各种方案的平均延迟表：（2 2，7 7）4.5 (2,5)3.5 (6,7)6.5 4.5 (2,5)3.5 (6,7)6.5 (6,5)5.5 (5)5 (7)7(6,5)5.5 (5)5 (7)7 从第一个向量出发，找出所有回路，把回从第一个向量出发，找出所有回路，把回路上的拍数按顺序写下来，并求出这些拍数的路上的拍数按顺序写下来，并求出这些拍数的平均数平均数 最小延迟调度方案为（最小延迟调度方案为（2 2，5 5）根据方案画出时空图，求效率和吞吐量根据方案画出时空图，求效率和吞吐量（这是上节的内容了，大家自己做做吧）（这是上节的内容了，大家自己做做吧）5.3 5.3 向量的流水处理与向量流向量的流水处理与向量流水处理机水处理机5.3.1 5.3.1 向量的流水处理向量的流水处理 不同的向量处理方式会对流水处理机的不同的向量处理方式会对流水处理机的结构、组成提出不同的要求，而结构和组成结构、组成提出不同的要求，而结构和组成不同的向量处理机反过来也会要求采用不同不同的向量处理机反过来也会要求采用不同的向量流水处理方式。的向量流水处理方式。举例：举例：计算计算D=A*(B+C)D=A*(B+C)，其中，其中A A、B B、C C、D D都是有都是有N N个元素的向量。个元素的向量。横向（水平）处理方式：横向（水平）处理方式：先求先求K=B+C,K=B+C,再求再求A*KA*K，然后重