流水线问题系统结构PPT课件

.,5.2流水线处理机教学目标：掌握流水线的基本原理、特点、分类、性能分析，非线性流水线的调度问题，及局部相关和全局相关的处理方法。一、流水线工作原理流水线方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其他子过程同时进行。在处理机的各个部分几乎都可以采用流水方式工作。指令的执行过程可以采用流水线，称为指令流水线。,.,运算器中的操作部件，如浮点加法器等可以采用流水线，称为操作部件流水线。从重叠到流水线一次重叠方式就是一种简单的流水线。在计算机中，一条指令的执行过程分解为“分析”和“执行”两个子过程，这两个子过程分别在指令分析器和指令执行部件中完成，如图5.23所示。,.,.,指令分析器和指令执行部件的输出端各有一个锁存器，可分别保存指令“分析”和指令“执行”的结果，因此，指令分析器和指令执行部件能成为两个完全独立的功能部件，可同时并行工作。指令分析器“分析k1”与指令执行部件“执行k”可同时进行。如果指令分析器分析一条指令所需要的时间t1与指令执行部件执行一条指令所需要的时间t2相等，即t1=t2，都为t。则从指令执行部件的输出端看，每间隔一个t就执行完成一条指令，并输出一个运算结果。因此，处理机,.,执行指令的速度提高了一倍。如果把执行一条指令的过程分得更细，如图5.24所示，分为6个子过程。每一个部件的输出端都要有一个锁存器。,.,在图5.24中的每一个子过程还可以再进一步分解成更小的子过程，即在功能部件的内部也采用流水线方式工作。如，一个浮点加法的执行过程可采用4级流水线，如图5.25所示。如果各个部件的执行时间均相等，处理机执行浮点加法的速度能够提高3倍。,.,时空图描述流水线的工作，最常用的方法是采用“时空图”。图5.23所示的流水线，采用时空图表示如图5.26所示。,.,在时空图中，横坐标表示时间，就是输入到流水线中的各个任务在流水线中所经过的时间。纵坐标表示空间，即流水线的各个子过程。在时空图中，流水线的一个子过程通常称为“功能段”。图5.27是一个4段浮点加法器流水线的时空图。,.,流水线的特点在处理机中采用流水线方式与采用传统的串行方式相比，具有如下特点：在流水线中处理的必须是连续的任务，只有连续不断地提供任务才能充分发挥流水线的效率。把一个任务（一条指令或一个操作）分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。在流水线的每一个功能部件的后面都要有一个缓冲寄存器，用于保存本段的执行结果。当某一个功能段的执行时间变化范围比较大时，要设置多个缓冲寄存器。,.,流水线中各段的时间应尽量相等，否则将引起“堵塞”、“断流”等。执行时间长的一段将成为整个流水线的“瓶颈”，这时，流水线中的各个功能部件将不能充分发挥作用。因此，在流水线设计中，当遇到“瓶颈”时，必须采取办法解决。流水线需要有“装入时间”和“排空时间”。只有流水线完全充满时，整个流水线的效率才能得到充分发挥。二、流水线的分类线性流水线与非线性流水线按照流水线的各个功能段之间是否有,.,反馈信号，可以把流水线分为线性流水线和非线性流水线两类。线性流水线是将流水线的各段逐个串接起来。输入数据从流水线的一端进入，从另一端输出。数据在流水线中的各个功能段流过时，每一个功能段都流过一次，且仅流过一次。非线性流水线：在流水线的各个功能段之间除了有串行的连接之外，还有反馈回路。如图5.28所示。,.,表示非线性流水线的工作情况除了要有流水线的连接图之外，还需要一张“预约表”，两者共同来表示流水线的工作情况。如图5.29所示。,.,图中用“”表示这一个功能段在相应的这一段时间内有效，即任务经过了这一个功能段。一条非线性流水线可以对应有很多张预约表，一张预约表实际上仅表示一条非线性流水线的一种工作方式。线性流水线实际上也有预约表，只不过它的预约表是确定的。首先，预约表的水平方向与垂直方向的格数是相等的，其次，预约表从左上角到右下角所有格子全部有效，即是打“”的；预约表的其余部分一定是空白的。因此，在描述线性流水线时，一般不给出预约表。,.,流水线的级别按照流水线使用的不同级别，可把流水线分为功能部件级、处理机级和处理机间级等多种类型。处理机级流水线又称为指令流水线。它把一条指令的执行过程分解为多个子过程，每个子过程在一个独立的功能部件中完成。前面介绍的一次重叠执行方式就是一种简单的指令流水线。在采用先行控制器的处理机中，组成先行控制器的各个部件实际上也构成了一条流水线。如图5.30所示。,.,.,在先行控制器中，一条指令的执行过程被分解为5个子过程，每个子过程在一个专用的功能部件中执行。由于各种指令在同一个功能部件中执行的时间往往相差很大，因此，在每一个功能段之间要设置多个缓冲寄存器，以平滑流水线中各个功能部件的操作。每个部件内部还可以采用流水线来实现。如对于一些复杂的运算操作部件，象浮点加法器等一般要采用多级流水线来实现。后行写数栈和先行读数栈也可以采用多级流水线来实现。这种流水线称为部件级流水线，或功能部件级流水线。,.,功能部件级流水线也称为运算操作流水线。把指令执行部件中采用了流水线的处理机称为流水线处理机或超流水线处理机，把指令执行部件中设置有多个操作部件的处理机称为多操作部件处理机或超标量处理机。处理机间流水线又称为宏流水线，如图5.31所示。,.,这种流水线由两个或两个以上处理机通过存储器串行连接起来，每个处理机对同一个数据流的不同部分分别进行处理。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入，每个处理机完成整个任务的一部分。一台大型计算机系统通常由多个同型号的或不同型号的处理机构成，每个处理机有不同的分工。例如，由多个用高级语言编写的程序需要在机器上运行，则程序和数据的输入、编译、连接、执行、执行结果输出等可分别在不同的处理机上完成，这些处理机就构成了一条宏流水线。单功能与多功能流水线,.,一条流水线只能完成一种固定的功能，这种流水线称为单功能流水线。多功能流水线是指流水线的各段可以进行不同的连接。在不同时间内，或在同一时间内，通过不同的连接方式实现不同的功能。,.,.,静态流水线与动态流水线在多功能流水线中，按照在同一时间内是否能够连接成多种方式，同时执行多种功能，可以把多功能流水线分为静态流水线和动态流水线两种。静态流水线是指在同一时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能。只有当按照这种连接方式工作的所有任务都流出流水线之后，多功能流水线才能重新进行连接，以实现其它功能。例如，图5.32的多功能流水线，如果按照图5.33所示的时空图工作，就是一种静态流水线。,.,.,动态流水线是指在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。当然，同时实现多种连接方式是有条件的，即流水线中的各个功能部件之间不能发生冲突。如图5.34所示。在一般情况下，动态流水线的效率和功能部件的利用率要比静态流水线高，但动态流水线的控制比静态流水线要复杂得多，目前，在大多数处理机中均采用静态流水线。,.,.,按照不同的数据表示方式，可以把流水线分为标量流水线和向量流水线。在线性流水线中，根据对流水线的控制方式不同，可以把流水线分为同步流水线和异步流水线两类。一般的宏流水线多采用异步流水线方式。如图5.35所示。在异步流水线中，当Si功能段要向Si1功能段传送数据时，首先发出就绪信号，Si1功能段收到就绪信号后，向Si功能段回送一个回答信号。,.,.,按照流水线输出端流出的任务与流水线输入端流入的任务的顺序是否相同，可以把流水线分为顺序流水线与乱序流水线两种。在顺序流水线中，流水线输出端的任务流出顺序与输入端的任务流入顺序完全相同，每个任务在流水线的各个功能段中是一个跟着一个顺序流动的。乱序流水线输出端流出任务的顺序与输入端流入任务的顺序可以不一样。每个任务在流水线中并不是按照输入的顺序一个跟着一个流动的。三、线性流水线的性能分析,.,衡量流水线性能的主要指标有吞吐率、加速比和效率。吞吐率流水线的吞吐率是指在单位时间内流水线所完成的任务数量或输出结果数量。,其中，n为任务数，Tk是处理完成n个任务所用的时间。以下讨论满足某种特殊情况的流水线吞吐率。流水线各段执行时间相等，输入到流水线中的任务是连续的。如图5.36所示。,.,.,一条k段线性流水线完成n个连续任务需要的总时间为：,其中，t为时钟周期。实际吞吐率为：,最大吞吐率为：,.,最大吞吐率与实际吞吐率的关系是：,当流水线中各段的执行时间不完全相等时，流水线中就存在有“瓶颈”。如图5.37所示。,.,.,流水线各段执行时间不相等情况下的实际吞吐率：,此时流水线的最大吞吐率为：,对于图5.37所示的例子，流水线的最大吞吐率为：,.,可以看出，当流水线中各个功能段的执行时间不完全相等时，流水线的最大吞吐率与实际吞吐率主要是由流水线中执行时间最长的那个功能段来决定的，这个功能段就成了整个流水线的“瓶颈”。解决流水线“瓶颈”问题的方法主要有两种。是将流水线的“瓶颈”部分再细分。如图5.38所示。,.,通过重复设置瓶颈功能段，让多个瓶颈功能段并行工作。但这种方法，其控制逻辑比较复杂。如图5.39所示。加速比完成一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。如果不使用流水线，即顺序执行所用的时间为T0，使用流水线的执行时间为Tk，则流水线的加速比为：,.,.,各个功能段执行时间均相等的一条k段流水线完成n个连续任务时的实际加速比为：,此时的最大加速比为：,.,可以看出，流水线的最大加速比等于流水线的段数。是否流水线的段数越多越好呢?实际上，当流水线的段数很多时，为了使流水线能够充分发挥效率，要求连续输入的任务数n也就很多。图5.40给出连续任务个数n与加速比S的关系。当任务个数很小时，加速比可能很差，当n=1时，加速比S的值最小为1。当流水线的段数K增大时，可以获得比较好的加速比。当n=64时，一条4段流水线的加速比为3.8，一条8段流水线的加速比可以达到7.2。,.,但是，一方面，由于一般程序中存在数据相关、转移、中断等情况，连续输入的任务数n受到很大的限制。另一方面，由于控制的复杂性、电路实现及组装技术、实现成本等方面的限制，流水线的段数也不可能很多。,.,当流水线的各个功能段的执行时间不相等时，一条k段线性流水线完成n个连续任务的实际加速比为：,效率流水线的效率是指流水线的设备利用率。在时空图上，流水线的效率定义为n个任务占用的时空区与k个功能段总的时空区之比。,.,其中，T0为n个任务顺序执行的时间，Tk为流水线完成n个任务的时间，k为功能段数。如果流水线各段执行时间均相等，输入n个任务是连续的，则一条k段流水线的效率为：,.,此时，流水线的最高效率为：,如果流水线的各段执行时间不相等，则连续执行n个任务的流水线效率为：,.,此时，流水线除了瓶颈功能段之外，其它各个功能段都有空闲时间，这些功能段的效率没有得到充分发挥，因此，整个流水线的效率E也比较低。在上面给出的所有流水线时空图中，都默认每个功能段的设备量或设备的价格都是相等的。对于可能出现的每一个功能段的设备量或功能段的价格不等的情况，应该根据各个功能段所用的设备量或设备价格在流水线总设备中所占的比例，分别赋予不同的“权”值Pi。此时流水线的效率为：,.,.,流水线最佳段数的选择从上面的分析可看出，增加流水线的段数，流水线的吞吐率和加速比都能提高。但由于在每个功能段的输出端都必须设置一个锁存器，因此，当流水线的段数增多时，锁存器的总延迟时间也将增加，另外，增加锁存器数量，流水线的价格也增加。所以，在设计流水线时，要综合各方面的因素，根据最佳性能价格比的要求来选择流水线的最佳段数。假设在非流水线的机器上采用顺序执行方式完成一个任务所需要的时间为t，则在同等速度的有k段流水线的机器上执行一个任务需要的时间为：,.,tkd，d为锁存器延迟时间。则流水线的最大吞吐率为：,流水线的总价格为：Cabka为所有功能段本身的总价格，b为每个锁存器的价格则性能价格比PCR定义为：,.,可以通过对自变量k求导，得到性能价格比PCR的极值，这个极值也是最大值，如图5.41所示。,.,当性能价格比PCR取得最大值时，它所对应的流水线的段数就是最佳段数k：,一般处理机中的流水线段数在2段至10段之间，极少有超过15段的流水线。流水线性能分析举例例5.1单功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。用图5.25所示的一条4段浮点加法器流水线计算8个浮点数的和：,.,ZABCDEFGH由于存在数据相关，将上式变换为：Z(AB)(CD)(EF)(GH)8个浮点数求和的流水线时空图如图5.42所示。假设每一个功能段的延迟时间均相等，都为t。,.,.,例5.2多功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。用图5.32所示的多功能静态流水线计算两个向量的点积：ZABCDEFGH为了尽量减少数据相关性，充分发挥流水线的作用，计算的顺序应该是先做4个乘法：AB、CD、EF和GH，然后做两个加法ABCD和EFGH，最后求总的结果Z。流水线的时空图如图5.43所示。假设每一个功能段的延迟时间都为t，则流水线的吞吐率TP为：,.,如果采用顺序执行方式，完成一次乘法用4个t，完成一次加法用6个t，则完成全部运算要用：T044t36t34t则流水线的加速比S为：,整个流水线共有8段，流水线效率E为：,.,.,四、非线性流水线的调度技术在非线性流水线中，由于存在有反馈回路，当一个任务在流水线中流过时，在同一个功能段中可能要经过多次。因此，就不能每一个时钟周期向流水线输入一个新任务，否则会发生在同一个时刻有几个任务争用同一个功能段的情况。这种情况称为功能部件冲突，或流水线冲突。为避免流水线发生冲突，一般采用延迟输入新任务的方法。在非线性流水线的输入端，究竟每隔多少个时钟周期向流水线输入一个新任务才能使流水线的各个功能段都不发生冲突，这就是非线性流水线的调度问题。,.,在许多非线性流水线中，间隔的周期数往往不是一个常数，而是一串周期变化的数字。因此，非线性流水线调度的任务是要找出一个最小的循环周期，按照这个周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。下面，先介绍非线性流水线的表示方法，然后分析非线性流水线中的冲突情况，并介绍无冲突调度方法，最后介绍非线性流水线的优化调度方法。非线性流水线的表示一条非线性流水线一般需要一个各功能段之间的连接图和一张预约表共同来表示，如图5.44(a)和5.44(b)所示。,.,.,预约表的横坐标表示流水线工作的时钟周期，纵坐标表示流水线的功能段，中间有“”的表示该功能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段，空白的地方表示该功能段在这个时钟周期不工作。一行中可以由多个“”，其含义是一个任务在不同时钟周期重复使用了同一个功能段，一列中有多个“”是指在同一个时钟周期同时使用了多个功能段。预约表的行数就是非线性流水线的段数，预约表的列数是指一个任务从进入流水线到从流水线中输出所经过的时钟周期数。有时把预约表的列数称为流水线的功能求值时间或流水线的装入时间等。,.,一张非线性流水线的预约表可能与多个非线性流水线连接图相对应，如图5.45就是图5.44(b)所示预约表的另一种连接图。,.,产生这种情况的原因是：在预约表的同一列中可能有多个“”，即在这个时钟周期有多个功能段有输出，从而造成下一个功能段的输入可能有多种来源，从而对应有多个流水线的连接图。同样，一个非线性流水线的连接图也可能对应有多张预约表。如图5.46就是图5.44(a)所示流水线连接图的另一张预约表。,.,.,造成这种情况的原因是：在非线性流水线的有些功能段可能有多个输出端，也有些功能段可能有多个输入端，这些输出端与输入端之间连接的先后次序就形成了多张预约表。非线性流水线的冲突向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离或等待时间。启动距离通常用时钟周期数来表示，它是一个正整数。,.,当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能段的情况，这种情况就是非线性流水线中的冲突。如图5.44所示的非线性流水线，当启动距离为3时，有关功能段的冲突情况如图5.47所示。,.,.,同样，图5.44所示的非线性流水线，当启动距离为2时，冲突情况如图5.48所示。,.,引起非线性流水线功能段冲突的启动距离称为禁止启动距离。如图5.44所示的非线性流水线，启动距离2和启动距离3都是禁止启动距离。有些启动距离在非线性流水线的所有功能段，在任何时间都不会发生冲突。如图5.44的非线性流水线，当启动距离为5时的预约表如图5.49所示。,.,.,在非线性流水线中，不发生冲突的启动距离不一定是一个常数，在一般情况下是一个循环数列。例如，图5.44所示的非线性流水线当启动距离为1、7、1、7、交替循环时，任何一个功能段在任何一个时钟周期也都不发生冲突，如图5.50所示。,.,.,这种使非线性流水线的任何一个功能段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。图5.50中的启动循环记作（1，7）。图5.49中的不发生冲突的启动距离也可以认为是一个循环数列，可以记作（5）。这种只有一个启动距离的启动循环又称为恒定循环。要正确调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。把一条非线性流水线的所有禁止启动距离组合在一起就形成一个数列，通常把这个数列称为非线性流水线的禁止向量。,.,由预约表得到禁止向量的方法很简单，只要把预约表的每一行中任意两个“”之间的距离都计算出来，去掉重复的，由这种数组成的一个数列就是这条非线性流水线的禁止向量。例图5.44所示的非线性流水线的禁止向量为（3，4，6）。把一个启动循环内的所有启动距离相加再除以这个启动循环内的启动距离个数就得到这个启动循环的平均启动距离。例如，启动循环（1，7）的平均启动距离是4，而恒定循环（5）的平均启动距离就是它本身的启动距离5。无冲突的调度方法,.,非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。根据一张预约表的禁止向量可以很容易得到冲突向量。冲突向量用一个m位的二进制数表示，其中m是禁止向量中的最大值。对于一张k列的预约表，有mk1。一般的冲突向量用C(CmCm1C2C1)来表示。如果在在禁止向量中，则Ci1，否则Ci0。其中,Cm一定为1，因为m必定在禁止向量中。,.,例如，对于图5.44(b)所示预约表，冲突向量C(101100)。由冲突向量可以构造一张状态图。把冲突向量C作为初始冲突向量送入一个m位逻辑右移移位器，当从移位器移出的位为0时，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；若移位器移出的位为1，不做任何处理；移位器继续右移，如此重复m次。在初始冲突向量和所有新形成的冲突向量之间用带箭头的线连接，表示各种状态之间的转换关系。线边注上数字n，表示初始冲突向量经过n次右移产生新冲突向量。,.,对于中间形成的每一个新的冲突向量，也按这一方法进行处理。当形成的新冲突向量出现重复时，可合并到一起。由图5.44所示非线性流水线构成的状态图如图5.51所示。,.,.,当初始冲突向量确定之后，状态图就是唯一的，因此，与一张预约表相对应，只有唯一的一个状态图。但是，由于不同的预约表可能产生相同的初始冲突向量，因此，不同的预约表也可能有相同的状态图。所以，从预约表可以画出状态图，但从状态图不能得到预约表。在状态图中可以找到无穷多个不发生功能段冲突的启动循环。因为非线性流水线调度的主要目标是要找出平均启动距离最小的启动循环，因此，在这些无穷多个启动循环中，一般只要找出简单循环即可。所谓简单循环是指状态图中各种冲突向量只经过一次的启动循环。,.,状态图5.51中的所有简单循环如表5.1所示，表中还给出了简单循环的平均启动距离。,.,从表中可以找到平均启动距离最小的启动循环，这样的启动循环被称为最小启动循环。上例中，最小启动循环为（1，1，7），平均启动距离为：（117）/33。图5.44所示非线性流水线按照最小启动循环（1，1，7）工作时，流水线预约表如图5.52所示。,.,.,优化调度方法按照前面介绍的调度方法得到的最小启动循环，有时并不能使非线性流水线充分发挥效率。下面将介绍非线性流水线的优化调度方法，按照这种方法调度非线性流水线，流水线的工作效率最高，即流水线的吞吐率、加速比和效率最好。预约表中“”最多的一行所对应的功能段一定是整个流水线的瓶颈功能段。要使整个流水线充分发挥效率，瓶颈功能段必须不间断工作，不能有空闲。,.,因此，非线性流水线调度的关键是充分使用瓶颈功能段，只要让瓶颈功能段不空闲，则非线性流水线的吞吐率、加速比和效率必然是最好的。按照这种方法调度流水线，流水线的平均启动距离也一定是最小的。采用预留算法来调度非线性流水线，可以达到最优调度。具体方法如下：确定流水线的最小平均启动距离。最小平均启动距离等于预约表中任意一行中“”的最多个数。确定最小启动循环。,.,相对于同一个最小平均启动距离可能有多个最小启动循环，其中有一个恒定循环。为了简化控制逻辑，一般选择恒定循环作为最小启动循环。结合流水线预约表和连接图，采用预留算法，通过插入非计算延迟功能段实现最小启动循环。以下，结合图5.44的例子，具体说明调度方法。用预留算法调度的预约表、连接图如图5.53所示。与图5.53相对应的流水线状态图如图5.54所示。按照最小启动循环（3）工作的流水线预约表如图5.55所示。每间隔3个时钟周期，可以向流水线,.,输入一个新任务。此时，流水线的任何一个功能段在任何一个时钟周期都不发生冲突。另外，从时钟周期7开始，瓶颈功能段S1就一直忙碌，没有一个时钟周期是空闲的，因此，采用这种调度方法能使流水线的吞吐率、加速比和效率达到最优。,.,.,.,.,五、局部相关按照对程序执行过程可能造成的影响来划分，可以把相关划分为局部相关和全局相关两类。如图5.56所示，如果程序内有一个两路的条件分支操作指令，它把程序划分为三部分B0、B1和B2，在每一部分内部不再有分支操作指令，通常把这样的一个部分称为一个基本块。,.,在同一个基本块内部的相关称为局部相关，在基本块之间的相关称为全局相关。在指令流水线中，局部相关主要有三种：“先写后读”数据相关，简称“写读”相关；“先读后写”数据相关，简称“读写”相关；“写-写”相关。顺序流动与乱序流动从流水线的输出端看，任务流出流水线的顺序与输入端的任务流入顺序完全相同，这种控制方式称为顺序流动方式。如图5.57所示是一条6段指令流水线。,.,.,在正常情况下，6个功能段S6、S5、S1分别同时执行k、k1、k5共6条指令，如图5.58中的最下面一行。,.,若把下面一段程序输入到流水线中：,.,其中，指令k与指令k2之间有“先写后读”数据相关。若采用顺序流动方式，流水线工作情况如图5.58所示。此时，流水线就会“断流”。这将降低流水线的吞吐率和效率。当然，采用顺序流动方式，流水线的控制逻辑比较简单。为了充分发挥流水线的效率，在发生数据相关时，要允许没有数据相关的后续指令进入相关指令所占用的功能段执行，并超越相关的指令继续往前流动，这种控制方式称为乱序流动方式。从一条指令流水线的输出端看，指令流出的顺序与输入端指令输入流水线的顺序是不一样的。对上例，采用乱序流动方式，流水线工作情况如图5.59所示。,.,.,造成流水线乱序流动方式的原因不仅仅是“先写后读”数据相关，有些指令执行的时间短或经过的功能段比较少，它们要越过执行时间长或经过功能段多的指令向前流动。在乱序流动方式中，除了有“先写后读”数据相关之外，还可能发生“先读后写”数据相关和“写-写”数据相关。如下面一段程序所示：,.,测试“先写后读”数据相关的方法是：在流水线的读操作数功能段设置一个相联比较器，在指令读操作数之前，把源操作数地址与已经在流水线中的从读操作数功能段到写结果功能段之间的所有指令的目标地址进行比较，如果发现有一个地址是相等的，则表明发生了“先写后读”数据相关。测试“先读后写”数据相关和“写-写”数据相关的方法是：在流水线的写结果功能段设置相联比较器，把自己的目标操作数地址分别与已经进入流水线的指令序号比自己小的源操作数地址和目标操作数地址进行比较，如果发现与某一条指令的源操作数地址相等，则说明发生了“先读后写”数据相关；,.,如果发现与某一条指令的目标操作数地址相等，则说明发生了“写-写”数据相关。数据相关及其避免方法有三种数据相关：“先写后读”、“先读后写”、“写-写”数据相关。在处理机执行程序的过程中，只有避免了数据相关，程序执行结果的语义才是正确的。在流水线中避免发生数据相关的方法可以分为两大类：一类是延迟执行，另一类是建立专用路径。采用延迟执行方法避免数据相关的流水线工作时序如图5.58所示。,.,这种方法的优点是流水线的控制简单，缺点是流水线的吞吐率和效率低。在指令流水线中，建立专用路径的方法如图5.57所示。在采用顺序流动方式时，建立有这种专用数据路径的流水线工作时序如图5.61所示。与没有建立专用数据路径的图5.58相比，指令k2可以提前两个时钟周期执行，从而流水线的吞吐率和效率有比较大的提高。在流水线中建立专用数据路径已经成为高性能处理机普遍采用的方法。通过建立专用路经来避免数据相关的基本原理是数据重定向。,.,.,数据重定向在单条流水线中，建立专用路经的方法主要有两种。对于“先写后读”数据相关，如图5.62(a)所示。,.,经过这样的改变后，可以避免“先写后读”数据相关，或缩短发生“先写后读”数据相关的时间。对于“写-写”数据相关，如图5.62(b)所示。经过这样的改变后，就可以完全避免发生“写-写”数据相关。另外，“先读后写”数据相关一般发生在多功能流水线或有多条流水线的处理机中，在只有一个写功能段的单条流水线中一般不会发生“先读后写”数据相关。在有多条流水线的超标量处理机中，解决“先读后写”数据相关的方法是设置一个缓冲寄存器，只要把发生相关的源存储单元中的内容复制到这个缓冲寄存器中，“先读后写”数据相关就可以避免。,.,下面通过一个例子说明在程序执行过程中，如何通过数据重定向来避免数据相关的，程序如下：k：LOADF1,Ak1：FADDF1,F2k2：FMULF1,F3k3：STOREF1,B程序执行过程中数据流程如图5.63(a)所示。,.,.,根据上面介绍的数据重定向的基本原理，为了处理“先写后读”数据相关，专门设置了AFADD、FADDFMUL、FMULB三条专用路径，同时，撤销了F1FADD和F1FMUL的路径。为了处理“写-写”数据相关，撤销了AF1、FADDF1的数据传送路径。数据流程如图5.63(b)所示。在流水线处理机中，经常有多条流水线，每条流水线有多个功能段，能够同时执行多条指令。如果为每一种可能出现的数据相关都建立专门的数据路径，则不仅相关路径的数量很多，而且控制逻辑也相当复杂。为了处理流水线中可能出现的多种数据相关，提出了多种解决数据相关的算法。,.,Tomasulo动态指令调度算法（公共数据总线法、令牌法）它采用乱序流动方式来提高流水线的吞吐率和效率，并通过分散控制的办法处理数据相关。在IBM360/91处理机的浮点处理部件中，有一个浮点加法器和一个浮点乘/除法器，图图5.64所示。浮点加法器为两段流水线，在它的输入端有三个保存站A1、A2和A3，浮点乘/除法器为六段流水线，在它的输入端有两个保存站M1和M2。每个保存站采用随机访问方式工作，由保存站中的控制部件控制。当任意一个保存站中的两个源操作,.,.,数都到齐后，如果对应的浮点操作部件是空闲的，则可以把两个操作数立即送入浮点操作部件中执行。IMB360/91处理机的浮点处理部件采用先行控制方式。仍以上一节中的程序段为例，可能发生“先写后读”和“写-写”数据相关。指令K的执行结果，把一个浮点操作数从主存中读出，送入浮点先行读数站(FLB1)中，并在执行指令K1时通过(FLB1)直接送到浮点加法器的保存站A1，而不是送到浮点寄存器F1中，这就相当于建立了一条从主存到浮点加法器的专用数据路径。,.,在执行指令K1时，把浮点寄存器(F2)中的内容通过FLR总线送入浮点加法器的保存站A1中，同时把浮点先行读数站（FLB1)中的操作数通过另一条FLB总线也送入浮点加法器的保存站A1中，并启动浮点加法器开始工作。因为浮点加法器的运算结果要送入F1，因此，要把浮点加法器保存站A1的站号“10”装入浮点寄存器F1的站号中，另外，要把F1的“忙位”标志置“1”，表示浮点寄存器F1中的内容目前不能读出作为源操作数使用。由于浮点加法器要执行两个时钟周期才能出结果，当执行指令K2时，虽然可以把浮点寄存器(F3)中的内容通过FLR总线送入浮点乘/除法器的保存,.,站M1中，但另一个操作数还不能从浮点通用寄存器F1中读出，这时，改为把保存在浮点寄存器F1中的站号“10”读出来，通过控制线送入浮点乘/除法器的保存站M1中，并把F1内的站号改为浮点乘/除法器保存站号M1的站号“8”，表示改从浮点乘/除法器接收运算结果。浮点加法执行完后，把运算结果和保存站A1站号“10”都送上公共数据总线CDB。通过与所有站号中保存的内容进行相等比较，找到浮点乘/除法器的保存站M1，于是，把CDB上的数据送入M1，而不是送入浮点寄存器F1，这相当于建立了一条从浮点加法器到浮点乘/除法器的专用数据路径。,.,浮点乘/除法器收到CDB上的数据之后就开始工作。6个时钟周期后，浮点乘法的执行结果连同保存站M1的站号都送上CDB。通过与所有站号进行相等比较，把CDB上的数据送入到浮点寄存器F1中。在浮点乘/除法器刚开始工作时，指令K3开始执行。由于浮点乘法的最终运算结果还没有出来，因此，就把保存站M1的站号“8”装入后行写数站的站号中。当浮点乘法操作执行结束后，在把运算结果通过CDB送入浮点寄存器F1的同时，也送入浮点后行写数站SDB，由SDB负责把这个结果写到主存的B单元中。此时，数据的流动过程象图6.63(b)那样。,.,六、全局相关由条件转移或程序中断引起的相关被称为全局相关。转移的影响在遇到条件转移指令时，为了使流水线不“断流”通常采用“猜测法”。在条件转移指令之后，选择一个分支方向，让后续指令进入流水线执行。如图5.65所示。,.,.,第i条指令是条件转移指令，第i1、i2、条指令继续进入流水线执行。因为第i条条件转移指令的条件码由第i1条指令给出，在一条有k个功能段的流水线中，第i1条指令要等到第ik2条指令进入流水线时才能形成条件码。如果形成的条件码是对应于转移不成功的，则猜测正确，流水线的吞吐率和效率没有降低，就好像没有条件转移指令一样。如果形成的条件码是对应于转移成功的，则猜测错误，就要先作废流水线中已执行的第i1、i2、ik2条指令，然后再从分支点开始执行,.,第p、p1、条指令。这时，一条k段流水线有k2个功能段是浪费的。在流水线沿猜测方向执行第i1、i2、条指令时，一定不能破坏通用寄存器和主存中的内容。为此，目前的处理机有两种做法：只进行指令译码和准备好运算所需要的操作数，在转移条件没形成之前不执行运算。控制逻辑比较简单，但即使猜测正确，也可能造成流水线功能段的浪费。一直执行到运算完成，但不送回运算结果。为此，要设置一定数量的缓冲寄存器来存放中间运算结果，而且，控制逻辑比较复杂。,.,下面，具体分析条件转移指令对流水线性能的影响。对于一条有k个功能段的流水线，由于条件转移指令的影响，在最坏情况下，每一次条件转移将造成k1个时钟周期的“断流”。另外，假设条件转移指令在一般程序中所占的比例为p，转移成功的概率为q。对于一个由n条指令组成的程序，在执行程序的过程中，由于条件转移需要额外增加的时钟周期数是：pqn(k1)t。N条指令的总执行时间是：,.,有条件转移影响的流水线的吞吐率为：,当n时，有条件转移影响的流水线的最大吞吐率为：,没有条件转移指令时，流水线的最大吞吐率为：,由于条件转移指令的影响，流水线吞吐率下降的百分比为：,.,据统计，在一些典型程序中，转移指令所占的比例为p=20%，转移成功的概率为q=60%。对一条有8个功能段的指令流水线，流水线的最大吞吐率要下降：,对一条有10个功能段的指令流水线，流水线的最大吞吐率要下降：,.,从上面的分析可看到，条件转移指令对流水线的影响是非常大的，可能采取的措施有：延迟转移技术和指令取消技术。静态转移预测技术。所谓静态转移预测技术是指在处理机的硬件和软件设计完成之后，转移预测的方向就已经确定了，或者预测为转移不成功的方向，或是预测为转移成功的方向。在程序实际执行过程中，转移预测的方向不能改变。动态转移预测技术。根据近期转移是否成功的历史记录来预测下一次,.,转移的方向。动态转移预测方法能随程序的执行过程动态地改变转移的预测方向。提前形成条件码。动态转移预测技术动态转移预测技术的关键是要解决好两个问题：如何记录转移历史信息；如何根据所记录的转移历史信息预测转移的方向。记录转移历史信息的方法通常有三种：把最近一次或几次转移是否成功的信息记录在转移指令中；用一个小容量的高速缓冲栈保存条件转移指令的转移目标地址；,.,用Cache保存转移目标地址之后的n条指令。下面，根据三种记录转移历史信息的方法介绍三类动态转移预测技术。方法一，在指令Cache中记录转移历史信息在指令Cache中专门设置一个字段，称为“转移历史表”。在执行转移指令时，把转移成功或不成功的信息记录在这个“转移历史表”中。可以只用一个二进制位来记录最近一次转移是否成功的信息。也可以用多位二进制位来记录最近几次转移是否成功的信息。当采用只记录最近一次转移是否成功的历史信息时，每一条指令的“转移历史表”只需要一个二进制位，它的状态转换图如图5.66(a)所示。,.,.,在执行条件转移指令时，如果“转移历史表”中记录的内容是“T”，则转移预测逻辑预测转移成功，并按照转移成功的方向取指令并分析指令；如果记录的是“N”，则按照转移不成功的方向继续取下一条指令并分析指令。在转移条件实际形成后，如果与预测的转移方向相同，则预测正确，流水线没有任何“断流”损失；如果与预测的转移方向不同，则要作废已经预取和分析的指令，并从另一个方向取指令和分析指令。无论预测的转移方向与指令实际执行结果的转移方向是否相同，都要用本条转移指令实际转移是否成功的信息来修改“转移历史表”。修改的方法可以按照图5.66(a)所示状态图进行。,.,为了取得更好的转移预测效果，通常需要记录最近多次转移是否成功的历史信息，这时，“转移历史表”也需要有多个二进制位。当采用记录最近两次转移是否成功的历史信息时，它的状态转换图如图5.66(b)所示。,.,图中，修改“转移历史表”的规则是采用了一种向左移位的方法，右边新移入的就是本次执行这条转移指令时转移是否成功的信息。转移预测是偏向于转移成功的。“转移历史表”的修改规则和转移预测规则可以多种多样。当一条转移指令第一次被执行时，它还没有转移历史的记录，即“转移历史表”还是空的，可以有两种做法：,.,在“转移历史表”中预置转移历史信息；根据指令本身的偏移字段的符号来预测转移的方向。如果偏移字段的符号是负的，则预测转移成功，否则预测转移不成功。优点：不必专门设置转移缓冲栈，所记录的转移历史信息比较少。缺点：需要有专门的指令Cache和专门的指令Cache控制逻辑。方法二，转移目标地址缓冲栈用一个小容量的高速缓冲栈保存最近执行的k条转移指令的“转移历史表”和转移目标地址，如图5.67所示。,.,.,“转移指令地址”字段采用全相联方式访问。当程序中执行到一条转移指令时，把当前指令地址与转移目标缓冲栈中的所有转移指令地址进行比较。如果发现有相等的，则根据同一行中的“转移历史表”所记录的历史信息预测本次转移的方向，同时用转移目标地址预取指令。在实际转移条件形成后，可以根据某一种规则修改“转移历史表”。方法三，转移目标指令缓冲栈如图5.68所示。,.,.,动态转移预测的方法有很多种，预测的准确性除了与程序本身的特性有关之外，还主要与记录的历史信息的复杂程度有关。一般来说，记录的历史信息越复杂，其预测的准确性越高，当然，所需要的硬件代价也越大。提前形成条件码对于一般条件转移指令，转移条件码是由上一条运算型指令产生的。对于大多数情况下，可以在运算实际开始之前或在运算中间就能产生条件码，不必等到运算完成之后。因此，只要在运算部件的入口处设置一个比较器，通过比较两个操作数的符号或阶码就能提前形成结果的正负号、是否为“0”、是否溢出等条件码。,.,如果能在一个时钟之内就产生条件码，则正好可以提供给下一条条件转移指令使用。有一种用来控制循环次数的计数转移指令在条件转移指令中占有很大的比例，而且这种指令要随循环程序反复执行很多次，因此，在流水线处理机中对这种条件转移指令要作特殊处理。例如，有下面一段循环程序。LOADR1,NUMLOOP：DECR1BNELOOPHELTNUM：n,.,对于这种循环程序中的计数转移指令，前面已介绍过两种处理方法。一种是延迟转移技术，另一种是“先行控制技术”中介绍的转移预测技术。下面，介绍在流水线处理机中经常采用的一种方法。首先，要由编译程序在对原程序进行编译时发现这种计数转移指令。当程序中出现这种指令时，把“DECR1”指令提前到循环体前面。这样，上面一段程序被编译成如下程序：LOADR1,NUMLOOP：LDECR1LBNELOOPHELTNUM：n,.,程序中的“LDEC”和“LBNE”是两条专门用来控制循环次数的指令，它们使用另外一个专门的条件码寄存器CCL。CCL由“LDEC”循环次数减“1”指令设置，由“LBNE”循环出口测试指令使用。而处于这两条指令中间的循环体指令不能破坏CCL条件码寄存器中的内容。只要循环体长度不是很短，循环体中的所有指令再加上两条循环控制指令能够充满流水线，流水线就不会有“断流”情况发生。精确断点与不精确断点当正在处理机中运行的一个程序被某一个中断源中断时，因为在流水线中同时有多条指令在执行，那么，断点究竟在哪一条指令呢？,.,对于常规输入输出设备申请的输入输出中断服务，实际上不需要有精确的断点。因此，比较简单的处理方法是：让已经进入流水线的所有指令都执行完，断点就是最后进入流水线的那条指令的地址。如图5.69所示。断点地址是i5。,.,只要能够及时从主存中读入中断服务程序，流水线可以不“断流”。而且，采用不精确断点法所需要的硬件比较少，控制逻辑相对比较简单。缺点：中断响应时间稍长些。处理因为程序性错误和机器故障等产生的中断，可以有两种方法，一是采用不精确断点方法，另一种是采用精确断点方法。采用不精确断点法，中断处理过程与常规的输入输出设备相同，凡是已经进入流水线的指令都执行完，断点就是最后进入流水线的那条指令的地址。,.,采用不精确断点法可能会发生如下两个问题。程序执行的结果可能出错。例如，有如下两条指令：i：FADDR1,R2i1：FMULR3,R1当第I条指令执行到功能段S6时发现浮点加法结果溢出，于是发出中断服务申请。由于采用不精确断点法，要让已经进入流水线的第i1条指令也执行完。因为第i1条指令使用了不正确的R1中的内容作源操作数，因此，浮点乘法的执行结果是不正确的。,.,在程序调试过程中，通常要设置断点，程序员通过查看断点处的中间执行结果来判断程序编写是否正确。如果采用不精确断点法，由于程序不能准确中断在程序员所设置的断点处，因此，在这种流水线处理机上，程序员很难调试程序。精确断点法：由哪一条指令的程序性错误或故障发出的中断请求，断点就是这条指令的地址。如图5.69中，如果第i条指令发生程序性错误或故障，那么，断点就是i。为了实现精确断点法，需要把断点以前的指令的执行结果都保存下来。,.,最坏情况发生在指令执行到最后一个功能段时才发生程序性错误或故障。为此，要设置一定数量的后援寄存器，把整个流水线中所有指令的执行结果和现场都保存下来，以便在发生中断时，能够恢复到精确断点。因此，采用精确断点法所需要的硬件代价比较高，控制逻辑也比较复杂。,.,5.3超标量处理机与超流水线处理机教学目标：介绍三种指令级并行处理机，即超标量处理机、超流水线处理机和超标量超流水线处理机的基本原理、典型结构和它们的主要性能。假设以一台K段流水线的普通标量处理机为基准，超标量处理机、超流水线处理机和超标量超流水线处理机的主要性能比较如表5.2所示。,.,.,一、超标量处理机基本结构超标量处理机的典型结构是有多个操作部件，一个或几个比较大的通用寄存器堆，一个或两个高速Cache。先进的超标量处理机一般都包含有三个处理单元：定点处理单元，它由一个或多个整数处理部件组成；浮点处理单元，它由浮点加减法部件和浮点乘除法部件等组成；图形处理单元。如图5.70所示。,.,.,它有10个操作部件，其中两个整数部件可以做32位的整数运算，也包括地址运算等。整数操作是单周期执行，完成一条整数运算指令使用一条4个功能段的流水线，包括取指令IF、指令译码ID、执行指令EX和写回运算结果WR，每个时钟周期可以完成两条整数指令。浮点运算是80位字长的，包括浮点加、减、乘、除和求浮点平方根等16条指令。浮点加法部件和乘法部件都采用3级流水线，每个时钟周期可以完成一条乘法指令和一条浮点加法指令；而且，对单精度、双精度及扩展双精度指令的执行速度都一样快。,.,两个专用的图形处理部件可以直接对图形的象素进行处理，共有9条专门的图形处理指令。有两个寄存器堆，其中，整数部件使用通用寄存器堆，它由32个32位的寄存器组成；浮点部件使用扩展寄存器堆，它由32个80位的寄存器组成。每个寄存器堆有8个端口，分别与8条内部总线连接，可以同时读出8个操作数提供给各个操作部件使用。另外，在取数/存数部件中，还有一个缓冲深度为4的采用先进先出方式工作的先行读数栈和一个缓冲深度为3的也采用先进先出方式工作的后行写数栈。,.,指令和数据分别存放在两个独立的高速Cache中，指令Cache和数据Cache的容量各为8K字节。两个Cache都采用两路组相联方式工作，因此，每个时钟周期可以提供两个64位的指令和数据。设置有一个转移目标指令Cache，遇到条件转移指令时，在指令Cache和目标指令Cache分别存放两路分支上的有关指令，并且，指令分配部件在每个时钟周期分别从指令Cache和目标指令Cache中各取出两条指令同时译码，最后，根据形成的条件码决定把哪一路分支上的指令送到操作部件中去。,.,单发射与