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

1、1 5.2 流水线处理机流水线处理机教学目标：掌握流水线的基本原理、特点、分类、性能分析，非线性流水线的调度问题，及局部相教学目标：掌握流水线的基本原理、特点、分类、性能分析，非线性流水线的调度问题，及局部相关和全局相关的处理方法。关和全局相关的处理方法。一、流水线工作原理一、流水线工作原理 流水线方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其他子过程同时进行。流水线方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其他子过程同时进行。 在处理机的各个部分几乎都可以采用流水方式工作。在处理机的各个部分几乎都可以采用流水方式工作。 指令的执行过程可以采用流水线，称为指令流水

2、线。指令的执行过程可以采用流水线，称为指令流水线。2 运算器中的操作部件，如浮点加法器等可以采用流水线，称为操作部件流水线。运算器中的操作部件，如浮点加法器等可以采用流水线，称为操作部件流水线。从重叠到流水线从重叠到流水线 一次重叠方式就是一种简单的流水线。一次重叠方式就是一种简单的流水线。 在计算机中，一条指令的执行过程分解为在计算机中，一条指令的执行过程分解为“分析分析”和和“执行执行”两个子过程，这两个子过程分别在两个子过程，这两个子过程分别在指令分析器和指令执行部件中完成，如图指令分析器和指令执行部件中完成，如图5.23所示。所示。34 指令分析器和指令执行部件的输出端各有一个锁存器，

3、可分别保存指令指令分析器和指令执行部件的输出端各有一个锁存器，可分别保存指令“分析分析”和指令和指令“执行执行”的结果，因此，指令分析器和指令执行部件能成为两个完全独立的功能部件，可同时并行工作。指的结果，因此，指令分析器和指令执行部件能成为两个完全独立的功能部件，可同时并行工作。指令分析器令分析器“分析分析k1”与指令执行部件与指令执行部件“执行执行k”可同时进行。可同时进行。 如果指令分析器分析一条指令所需要的时间如果指令分析器分析一条指令所需要的时间t1与指令执行部件执行一条指令所需要的时间与指令执行部件执行一条指令所需要的时间t2相等，即相等，即t1=t2，都为，都为t。则从指令执行部

4、件的输出端看，每间隔一个。则从指令执行部件的输出端看，每间隔一个t就执行完成一条指令，就执行完成一条指令，并输出一个运算结果。因此，处理机并输出一个运算结果。因此，处理机5执行指令的速度提高了一倍。执行指令的速度提高了一倍。 如果把执行一条指令的过程分得更细，如图如果把执行一条指令的过程分得更细，如图5.24所示，分为所示，分为6个子过程。每一个部件的输出端都个子过程。每一个部件的输出端都要有一个锁存器。要有一个锁存器。6在图在图5.24中的每一个子过程还可以再进一步分解成更小的子过程，即在功能部件的内部也采用流水中的每一个子过程还可以再进一步分解成更小的子过程，即在功能部件的内部也采用流水线

5、方式工作。如，一个浮点加法的执行过程可采用线方式工作。如，一个浮点加法的执行过程可采用4级流水线，如图级流水线，如图5.25所示。如果各个部件的执行所示。如果各个部件的执行时间均相等，处理机执行浮点加法的速度能够提高时间均相等，处理机执行浮点加法的速度能够提高3倍。倍。7时空图时空图 描述流水线的工作，最常用的方法是采用描述流水线的工作，最常用的方法是采用“时空图时空图”。 图图5.23所示的流水线，采用时空图表示如图所示的流水线，采用时空图表示如图5.26所示。所示。8在时空图中，横坐标表示时间，就是输入到流水线中的各个任务在流水线中所经过的时间。纵坐标在时空图中，横坐标表示时间，就是输入到

6、流水线中的各个任务在流水线中所经过的时间。纵坐标表示空间，即流水线的各个子过程。表示空间，即流水线的各个子过程。在时空图中，流水线的一个子过程通常称为在时空图中，流水线的一个子过程通常称为“功能段功能段”。图图5.27是一个是一个4段浮点加法器流水线的时空图。段浮点加法器流水线的时空图。9流水线的特点流水线的特点在处理机中采用流水线方式与采用传统的串行方式相比，具有如下特点：在处理机中采用流水线方式与采用传统的串行方式相比，具有如下特点：在流水线中处理的必须是连续的任务，只有连续不断地提供任务才能充分发挥流水线的效率。在流水线中处理的必须是连续的任务，只有连续不断地提供任务才能充分发挥流水线的

7、效率。把一个任务（一条指令或一个操作）分解为几个有联系的子任务，每个子任务由一个专门的功能把一个任务（一条指令或一个操作）分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。部件来实现。在流水线的每一个功能部件的后面都要有一个缓冲寄存器，用于保存本段的执行结果。当某一个在流水线的每一个功能部件的后面都要有一个缓冲寄存器，用于保存本段的执行结果。当某一个功能段的执行时间变化范围比较大时，要设置多个缓冲寄存器。功能段的执行时间变化范围比较大时，要设置多个缓冲寄存器。10流水线中各段的时间应尽量相等，否则将引起流水线中各段的时间应尽量相等，否则将引起“堵塞堵塞”、“断流断流”等。执行时间

8、长的一段将成为等。执行时间长的一段将成为整个流水线的整个流水线的“瓶颈瓶颈”，这时，流水线中的各个功能部件将不能充分发挥作用。因此，在流水线设，这时，流水线中的各个功能部件将不能充分发挥作用。因此，在流水线设计中，当遇到计中，当遇到“瓶颈瓶颈”时，必须采取办法解决。时，必须采取办法解决。流水线需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间”。只有流水线完全充满时，整个流水线的效率才能得。只有流水线完全充满时，整个流水线的效率才能得到充分发挥。到充分发挥。二、流水线的分类二、流水线的分类线性流水线与非线性流水线线性流水线与非线性流水线 按照流水线的各个功能段之间是否有按照流水线的各

9、个功能段之间是否有11反馈信号，可以把流水线分为线性流水线和非线性流水线两类。反馈信号，可以把流水线分为线性流水线和非线性流水线两类。线性流水线是将流水线的各段逐个串接起来。输入数据从流水线的一端进入，从另一端输出。数据线性流水线是将流水线的各段逐个串接起来。输入数据从流水线的一端进入，从另一端输出。数据在流水线中的各个功能段流过时，每一个功能段都流过一次，且仅流过一次。在流水线中的各个功能段流过时，每一个功能段都流过一次，且仅流过一次。非线性流水线：在流水线的各个功能段之间除了有串行的连接之外，还有反馈回路。如图非线性流水线：在流水线的各个功能段之间除了有串行的连接之外，还有反馈回路。如图5

10、.28所示。所示。12表示非线性流水线的工作情况除了要有流水线的连接图之外，还需要一张表示非线性流水线的工作情况除了要有流水线的连接图之外，还需要一张“预约表预约表”，两者共同来，两者共同来表示流水线的工作情况。如图表示流水线的工作情况。如图5.29所示。所示。13图中用图中用“”表示这一个功能段在相应的这一段时间内有效，即任务经过了这一个功能段。表示这一个功能段在相应的这一段时间内有效，即任务经过了这一个功能段。一条非线性流水线可以对应有很多张预约表，一张预约表实际上仅表示一条非线性流水线的一种工一条非线性流水线可以对应有很多张预约表，一张预约表实际上仅表示一条非线性流水线的一种工作方式。作

11、方式。线性流水线实际上也有预约表，只不过它的预约表是确定的。线性流水线实际上也有预约表，只不过它的预约表是确定的。首先，预约表的水平方向与垂直方向的格数是相等的，其次，预约表从左上角到右下角所有格子全首先，预约表的水平方向与垂直方向的格数是相等的，其次，预约表从左上角到右下角所有格子全部有效，即是打部有效，即是打“”的；预约表的其余部分一定是空白的。的；预约表的其余部分一定是空白的。因此，在描述线性流水线时，一般不给出预约表。因此，在描述线性流水线时，一般不给出预约表。14流水线的级别流水线的级别按照流水线使用的不同级别，可把流水线分为功能部件级、处理机级和处理机间级等多种类型。按照流水线使用

12、的不同级别，可把流水线分为功能部件级、处理机级和处理机间级等多种类型。处理机级流水线又称为指令流水线。它把一条指令的执行过程分解为多个子过程，每个子过程在一处理机级流水线又称为指令流水线。它把一条指令的执行过程分解为多个子过程，每个子过程在一个独立的功能部件中完成。个独立的功能部件中完成。前面介绍的一次重叠执行方式就是一种简单的指令流水线。前面介绍的一次重叠执行方式就是一种简单的指令流水线。在采用先行控制器的处理机中，组成先行控制器的各个部件实际上也构成了一条流水线。如图在采用先行控制器的处理机中，组成先行控制器的各个部件实际上也构成了一条流水线。如图5.30所所示。1516在先行控制器中，一

13、条指令的执行过程被分解为在先行控制器中，一条指令的执行过程被分解为5个子过程，每个子过程在一个专用的功能部件中执个子过程，每个子过程在一个专用的功能部件中执行。行。由于各种指令在同一个功能部件中执行的时间往往相差很大，因此，在每一个功能段之间要设置多由于各种指令在同一个功能部件中执行的时间往往相差很大，因此，在每一个功能段之间要设置多个缓冲寄存器，以平滑流水线中各个功能部件的操作。个缓冲寄存器，以平滑流水线中各个功能部件的操作。每个部件内部还可以采用流水线来实现。如对于一些复杂的运算操作部件，象浮点加法器等一般要每个部件内部还可以采用流水线来实现。如对于一些复杂的运算操作部件，象浮点加法器等一

14、般要采用多级流水线来实现。后行写数栈和先行读数栈也可以采用多级流水线来实现。这种流水线称为采用多级流水线来实现。后行写数栈和先行读数栈也可以采用多级流水线来实现。这种流水线称为部件级流水线，或功能部件级流水线。部件级流水线，或功能部件级流水线。17功能部件级流水线也称为运算操作流水线。功能部件级流水线也称为运算操作流水线。把指令执行部件中采用了流水线的处理机称为流水线处理机或超流水线处理机，把指令执行部件中把指令执行部件中采用了流水线的处理机称为流水线处理机或超流水线处理机，把指令执行部件中设置有多个操作部件的处理机称为多操作部件处理机或超标量处理机。设置有多个操作部件的处理机称为多操作部件处

15、理机或超标量处理机。处理机间流水线又称为宏流水线，如图处理机间流水线又称为宏流水线，如图5.31所示。所示。18这种流水线由两个或两个以上处理机通过存储器串行连接起来，每个处理机对同一个数据流的不同这种流水线由两个或两个以上处理机通过存储器串行连接起来，每个处理机对同一个数据流的不同部分分别进行处理。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入，每个处理部分分别进行处理。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入，每个处理机完成整个任务的一部分。机完成整个任务的一部分。一台大型计算机系统通常由多个同型号的或不同型号的处理机构成，每个处理机有不同的分工。例一台大型计

16、算机系统通常由多个同型号的或不同型号的处理机构成，每个处理机有不同的分工。例如，由多个用高级语言编写的程序需要在机器上运行，则程序和数据的输入、编译、连接、执行、如，由多个用高级语言编写的程序需要在机器上运行，则程序和数据的输入、编译、连接、执行、执行结果输出等可分别在不同的处理机上完成，这些处理机就构成了一条宏流水线。执行结果输出等可分别在不同的处理机上完成，这些处理机就构成了一条宏流水线。单功能与多功能流水线单功能与多功能流水线19一条流水线只能完成一种固定的功能，这种流水线称为单功能流水线。一条流水线只能完成一种固定的功能，这种流水线称为单功能流水线。多功能流水线是指流水线的各段可以进行

17、不同的连接。在不同时间内，或在同一时间内，通过不同多功能流水线是指流水线的各段可以进行不同的连接。在不同时间内，或在同一时间内，通过不同的连接方式实现不同的功能。的连接方式实现不同的功能。2021静态流水线与动态流水线静态流水线与动态流水线在多功能流水线中，按照在同一时间内是否能够连接成多种方式，同时执行多种功能，可以把多功在多功能流水线中，按照在同一时间内是否能够连接成多种方式，同时执行多种功能，可以把多功能流水线分为静态流水线和动态流水线两种。能流水线分为静态流水线和动态流水线两种。静态流水线是指在同一时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现静态流水线是指在同一时

18、间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能。只有当按照这种连接方式工作的所有任务都流出流水线之后，多功能流水线才能一种固定的功能。只有当按照这种连接方式工作的所有任务都流出流水线之后，多功能流水线才能重新进行连接，以实现其它功能。重新进行连接，以实现其它功能。例如，图例如，图5.32的多功能流水线，如果按照图的多功能流水线，如果按照图5.33所示的时空图工作，就是一种静态流水线。所示的时空图工作，就是一种静态流水线。2223动态流水线是指在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种动态流水线是指在同一段时间内，多功能流水线中的各段

19、可以按照不同的方式连接，同时执行多种功能。功能。当然，同时实现多种连接方式是有条件的，即流水线中的各个功能部件之间不能发生冲突。如图当然，同时实现多种连接方式是有条件的，即流水线中的各个功能部件之间不能发生冲突。如图5.34所示。所示。在一般情况下，动态流水线的效率和功能部件的利用率要比静态流水线高，但动态流水线的控制比在一般情况下，动态流水线的效率和功能部件的利用率要比静态流水线高，但动态流水线的控制比静态流水线要复杂得多，目前，在大多数处理机中均采用静态流水线。静态流水线要复杂得多，目前，在大多数处理机中均采用静态流水线。2425按照不同的数据表示方式，可以把流水线分为标量流水线和向量流水

20、线。按照不同的数据表示方式，可以把流水线分为标量流水线和向量流水线。在线性流水线中，根据对流水线的控制方式不同，可以把流水线分为同步流水线和异步流水线两类。在线性流水线中，根据对流水线的控制方式不同，可以把流水线分为同步流水线和异步流水线两类。一般的宏流水线多采用异步流水线方式。如图一般的宏流水线多采用异步流水线方式。如图5.35所示。在异步流水线中，当所示。在异步流水线中，当Si功能段要向功能段要向Si1功功能段传送数据时，首先发出就绪信号，能段传送数据时，首先发出就绪信号， Si1功能段收到就绪信号后，向功能段收到就绪信号后，向Si功能段回送一个回答信号。功能段回送一个回答信号。2627按

21、照流水线输出端流出的任务与流水线输入端流入的任务的顺序是否相同，可以把流水线分为顺序按照流水线输出端流出的任务与流水线输入端流入的任务的顺序是否相同，可以把流水线分为顺序流水线与乱序流水线两种。流水线与乱序流水线两种。在顺序流水线中，流水线输出端的任务流出顺序与输入端的任务流入顺序完全相同，每个任务在流在顺序流水线中，流水线输出端的任务流出顺序与输入端的任务流入顺序完全相同，每个任务在流水线的各个功能段中是一个跟着一个顺序流动的。水线的各个功能段中是一个跟着一个顺序流动的。乱序流水线输出端流出任务的顺序与输入端流入任务的顺序可以不一样。每个任务在流水线中并不乱序流水线输出端流出任务的顺序与输入

22、端流入任务的顺序可以不一样。每个任务在流水线中并不是按照输入的顺序一个跟着一个流动的。是按照输入的顺序一个跟着一个流动的。三、线性流水线的性能分析三、线性流水线的性能分析28衡量流水线性能的主要指标有吞吐率、加速比和效率。衡量流水线性能的主要指标有吞吐率、加速比和效率。吞吐率吞吐率流水线的吞吐率是指在单位时间内流水线所完成的任务数量或输出结果数量。流水线的吞吐率是指在单位时间内流水线所完成的任务数量或输出结果数量。其中，其中，n为任务数，为任务数，Tk是处理完成是处理完成n个任务所用的时间。个任务所用的时间。以下讨论满足某种特殊情况的流水线吞吐率。以下讨论满足某种特殊情况的流水线吞吐率。流水线

23、各段执行时间相等，输入到流水线中的任务是连续的。如图流水线各段执行时间相等，输入到流水线中的任务是连续的。如图5.36所示。所示。2930一条一条k段线性流水线完成段线性流水线完成n个连续任务需要的总时间为：个连续任务需要的总时间为：其中，其中，t为时钟周期。为时钟周期。实际吞吐率为：实际吞吐率为：最大吞吐率为：最大吞吐率为：31最大吞吐率与实际吞吐率的关系是：最大吞吐率与实际吞吐率的关系是：当流水线中各段的执行时间不完全相等时，流水线中就存在有当流水线中各段的执行时间不完全相等时，流水线中就存在有“瓶颈瓶颈”。如图。如图5.37所示。所示。3233流水线各段执行时间不相等情况下的实际吞吐率：

24、流水线各段执行时间不相等情况下的实际吞吐率：此时流水线的最大吞吐率为：此时流水线的最大吞吐率为：对于图对于图5.37所示的例子，流水线的最大吞吐率为：所示的例子，流水线的最大吞吐率为：34可以看出，当流水线中各个功能段的执行时间不完全相等时，流水线的最大吞吐率与实际吞吐率主可以看出，当流水线中各个功能段的执行时间不完全相等时，流水线的最大吞吐率与实际吞吐率主要是由流水线中执行时间最长的那个功能段来决定的，这个功能段就成了整个流水线的要是由流水线中执行时间最长的那个功能段来决定的，这个功能段就成了整个流水线的“瓶颈瓶颈”。解决流水线解决流水线“瓶颈瓶颈”问题的方法主要有两种。问题的方法主要有两种

25、。是将流水线的是将流水线的“瓶颈瓶颈”部分再细分。如图部分再细分。如图5.38所示。所示。35通过重复设置瓶颈功能段，让多个瓶颈功能段并行工作。但这种方法，其控制逻辑比较复杂。如通过重复设置瓶颈功能段，让多个瓶颈功能段并行工作。但这种方法，其控制逻辑比较复杂。如图图5.39所示。所示。加速比加速比完成一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。完成一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。如果不使用流水线，即顺序执行所用的时间为如果不使用流水线，即顺序执行所用的时间为T0，使用流水线的执行时间为，使用流水线的执行时间为Tk，

26、则流水线的加速比，则流水线的加速比为：为：3637各个功能段执行时间均相等的一条各个功能段执行时间均相等的一条k段流水线完成段流水线完成n个连续任务时的实际加速比为：个连续任务时的实际加速比为：此时的最大加速比为：此时的最大加速比为：38可以看出，流水线的最大加速比等于流水线的段数。可以看出，流水线的最大加速比等于流水线的段数。是否流水线的段数越多越好呢是否流水线的段数越多越好呢?实际上，当流水线的段数很多时，为了使流水线能够充分发挥效率，要求连续输入的任务数实际上，当流水线的段数很多时，为了使流水线能够充分发挥效率，要求连续输入的任务数n也就很也就很多。多。图图5.40给出连续任务个数给出连

27、续任务个数n与加速比与加速比S的关系。的关系。当任务个数很小时，加速比可能很差，当当任务个数很小时，加速比可能很差，当n=1时，加速比时，加速比S的值最小为的值最小为1。当流水线的段数。当流水线的段数K增大时，增大时，可以获得比较好的加速比。当可以获得比较好的加速比。当n=64时，一条时，一条4段流水线的加速比为段流水线的加速比为3.8，一条，一条8段流水线的加速比可以段流水线的加速比可以达到达到7.2。39但是，一方面，由于一般程序中存在数据相关、转移、中断等情况，连续输入的任务数但是，一方面，由于一般程序中存在数据相关、转移、中断等情况，连续输入的任务数n受到很大的受到很大的限制。另一方面

28、，由于控制的复杂性、电路实现及组装技术、实现成本等方面的限制，流水线的段限制。另一方面，由于控制的复杂性、电路实现及组装技术、实现成本等方面的限制，流水线的段数也不可能很多。数也不可能很多。40当流水线的各个功能段的执行时间不相等时，一条当流水线的各个功能段的执行时间不相等时，一条k段线性流水线完成段线性流水线完成n个连续任务的实际加速比为：个连续任务的实际加速比为：效率效率流水线的效率是指流水线的设备利用率。流水线的效率是指流水线的设备利用率。在时空图上，流水线的效率定义为在时空图上，流水线的效率定义为n个任务占用的时空区与个任务占用的时空区与k个功能段总的时空区之比。个功能段总的时空区之比

29、。41其中，其中，T0为为n个任务顺序执行的时间，个任务顺序执行的时间，Tk为流水线完成为流水线完成n个任务的时间，个任务的时间，k为功能段数。为功能段数。如果流水线各段执行时间均相等，输入如果流水线各段执行时间均相等，输入n个任务是连续的，则一条个任务是连续的，则一条k段流水线的效率为：段流水线的效率为：42此时，流水线的最高效率为：此时，流水线的最高效率为：如果流水线的各段执行时间不相等，则连续执行如果流水线的各段执行时间不相等，则连续执行n个任务的流水线效率为：个任务的流水线效率为：43此时，流水线除了瓶颈功能段之外，其它各个功能段都有空闲时间，这些功能段的效率没有得到充此时，流水线除了

30、瓶颈功能段之外，其它各个功能段都有空闲时间，这些功能段的效率没有得到充分发挥，因此，整个流水线的效率分发挥，因此，整个流水线的效率E也比较低。也比较低。在上面给出的所有流水线时空图中，都默认每个功能段的设备量或设备的价格都是相等的。对于可在上面给出的所有流水线时空图中，都默认每个功能段的设备量或设备的价格都是相等的。对于可能出现的每一个功能段的设备量或功能段的价格不等的情况，应该根据各个功能段所用的设备量或能出现的每一个功能段的设备量或功能段的价格不等的情况，应该根据各个功能段所用的设备量或设备价格在流水线总设备中所占的比例，分别赋予不同的设备价格在流水线总设备中所占的比例，分别赋予不同的“权

31、权”值值Pi。此时流水线的效率为：。此时流水线的效率为：4445流水线最佳段数的选择流水线最佳段数的选择从上面的分析可看出，增加流水线的段数，流水线的吞吐率和加速比都能提高。但由于在每个功能从上面的分析可看出，增加流水线的段数，流水线的吞吐率和加速比都能提高。但由于在每个功能段的输出端都必须设置一个锁存器，因此，当流水线的段数增多时，锁存器的总延迟时间也将增加，段的输出端都必须设置一个锁存器，因此，当流水线的段数增多时，锁存器的总延迟时间也将增加，另外，增加锁存器数量，流水线的价格也增加。所以，在设计流水线时，要综合各方面的因素，根另外，增加锁存器数量，流水线的价格也增加。所以，在设计流水线时

32、，要综合各方面的因素，根据最佳性能价格比的要求来选择流水线的最佳段数。据最佳性能价格比的要求来选择流水线的最佳段数。假设在非流水线的机器上采用顺序执行方式完成一个任务所需要的时间为假设在非流水线的机器上采用顺序执行方式完成一个任务所需要的时间为t，则在同等速度的有，则在同等速度的有k段段流水线的机器上执行一个任务需要的时间为：流水线的机器上执行一个任务需要的时间为：46tkd，d为锁存器延迟时间。为锁存器延迟时间。则流水线的最大吞吐率为：则流水线的最大吞吐率为：流水线的总价格为：流水线的总价格为：Cabk a为所有功能段本身的总价格，为所有功能段本身的总价格，b为每个锁存器的价格为每个锁存器的

33、价格则性能价格比则性能价格比PCR定义为：定义为：47可以通过对自变量可以通过对自变量k求导，得到性能价格比求导，得到性能价格比PCR的极值，这个极值也是最大值，如图的极值，这个极值也是最大值，如图5.41所示。所示。48当性能价格比当性能价格比PCR取得最大值时，它所对应的流水线的段数就是最佳段数取得最大值时，它所对应的流水线的段数就是最佳段数k：一般处理机中的流水线段数在一般处理机中的流水线段数在2段至段至10段之间，极少有超过段之间，极少有超过15段的流水线。段的流水线。流水线性能分析举例流水线性能分析举例例例5.1单功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和

34、效率。单功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。用图用图5.25所示的一条所示的一条4段浮点加法器流水线计算段浮点加法器流水线计算8个浮点数的和：个浮点数的和：49ZABCDEFGH由于存在数据相关，将上式变换为：由于存在数据相关，将上式变换为：Z(AB) (CD) (EF) (GH)8个浮点数求和的流水线时空图如图个浮点数求和的流水线时空图如图5.42所示。所示。假设每一个功能段的延迟时间均相等，都为假设每一个功能段的延迟时间均相等，都为t。5051例例5.2多功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。多功能、线性流水线，

35、输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。用图用图5.32所示的多功能静态流水线计算两个向量的点积：所示的多功能静态流水线计算两个向量的点积：ZABCDEFGH为了尽量减少数据相关性，充分发挥流水线的作用，计算的顺序应该是先做为了尽量减少数据相关性，充分发挥流水线的作用，计算的顺序应该是先做4个乘法：个乘法：AB、CD、EF和和GH，然后做两个加法，然后做两个加法ABCD和和EFGH，最后求总的结果，最后求总的结果Z。流水线的时空图如图。流水线的时空图如图5.43所示。所示。假设每一个功能段的延迟时间都为假设每一个功能段的延迟时间都为t，则流水线的吞吐率，则流水线的吞吐率TP为

36、：为：52如果采用顺序执行方式，完成一次乘法用如果采用顺序执行方式，完成一次乘法用4个个t，完成一次加法用，完成一次加法用6个个t，则完成全部运算要用：，则完成全部运算要用：T044t36t34t则流水线的加速比则流水线的加速比S为：为：整个流水线共有整个流水线共有8段，流水线效率段，流水线效率E为：为：5354四、非线性流水线的调度技术四、非线性流水线的调度技术在非线性流水线中，由于存在有反馈回路，当一个任务在流水线中流过时，在同一个功能段中可能在非线性流水线中，由于存在有反馈回路，当一个任务在流水线中流过时，在同一个功能段中可能要经过多次。因此，就不能每一个时钟周期向流水线输入一个新任务，

37、否则会发生在同一个时刻有要经过多次。因此，就不能每一个时钟周期向流水线输入一个新任务，否则会发生在同一个时刻有几个任务争用同一个功能段的情况。这种情况称为功能部件冲突，或流水线冲突。几个任务争用同一个功能段的情况。这种情况称为功能部件冲突，或流水线冲突。为避免流水线发生冲突，一般采用延迟输入新任务的方法。为避免流水线发生冲突，一般采用延迟输入新任务的方法。在非线性流水线的输入端，究竟每隔多少个时钟周期向流水线输入一个新任务才能使流水线的各个在非线性流水线的输入端，究竟每隔多少个时钟周期向流水线输入一个新任务才能使流水线的各个功能段都不发生冲突，这就是非线性流水线的调度问题。功能段都不发生冲突，

38、这就是非线性流水线的调度问题。55在许多非线性流水线中，间隔的周期数往往不是一个常数，而是一串周期变化的数字。在许多非线性流水线中，间隔的周期数往往不是一个常数，而是一串周期变化的数字。因此，非线性流水线调度的任务是要找出一个最小的循环周期，按照这个周期向流水线输入新任务，因此，非线性流水线调度的任务是要找出一个最小的循环周期，按照这个周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。下面，先介绍非线性流水线的表示方法，然后分析非线性流水线中的冲突情况，并介绍无冲突调度下面，先介绍非线性流水线

39、的表示方法，然后分析非线性流水线中的冲突情况，并介绍无冲突调度方法，最后介绍非线性流水线的优化调度方法。方法，最后介绍非线性流水线的优化调度方法。非线性流水线的表示非线性流水线的表示一条非线性流水线一般需要一个各功能段之间的连接图和一张预约表共同来表示，如图一条非线性流水线一般需要一个各功能段之间的连接图和一张预约表共同来表示，如图5.44(a)和和5.44(b)所示。所示。5657预约表的横坐标表示流水线工作的时钟周期，纵坐标表示流水线的功能段，中间有预约表的横坐标表示流水线工作的时钟周期，纵坐标表示流水线的功能段，中间有“”的表示该功的表示该功能段在这一个时钟周期处于工作状态，即在这个时钟

40、周期有任务通过这个功能段，空白的地方表示能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段，空白的地方表示该功能段在这个时钟周期不工作。该功能段在这个时钟周期不工作。一行中可以由多个一行中可以由多个“”，其含义是一个任务在不同时钟周期重复使用了同一个功能段，一列中有多，其含义是一个任务在不同时钟周期重复使用了同一个功能段，一列中有多个个“”是指在同一个时钟周期同时使用了多个功能段。是指在同一个时钟周期同时使用了多个功能段。预约表的行数就是非线性流水线的段数，预约表的列数是指一个任务从进入流水线到从流水线中输预约表的行数就是非线性流水线的段数，预约表的列数是指一个任务从进入流

41、水线到从流水线中输出所经过的时钟周期数。出所经过的时钟周期数。有时把预约表的列数称为流水线的功能求值时间或流水线的装入时间等。有时把预约表的列数称为流水线的功能求值时间或流水线的装入时间等。58一张非线性流水线的预约表可能与多个非线性流水线连接图相对应，如图一张非线性流水线的预约表可能与多个非线性流水线连接图相对应，如图5.45就是图就是图5.44(b)所示预所示预约表的另一种连接图。约表的另一种连接图。59产生这种情况的原因是：在预约表的同一列中可能有多个产生这种情况的原因是：在预约表的同一列中可能有多个“”，即在这个时钟周期有多个功能段有，即在这个时钟周期有多个功能段有输出，从而造成下一个

42、功能段的输入可能有多种来源，从而对应有多个流水线的连接图。输出，从而造成下一个功能段的输入可能有多种来源，从而对应有多个流水线的连接图。同样，一个非线性流水线的连接图也可能对应有多张预约表。如图同样，一个非线性流水线的连接图也可能对应有多张预约表。如图5.46就是图就是图5.44(a)所示流水线连所示流水线连接图的另一张预约表。接图的另一张预约表。6061造成这种情况的原因是：在非线性流水线的有些功能段可能有多个输出端，也有些功能段可能有多造成这种情况的原因是：在非线性流水线的有些功能段可能有多个输出端，也有些功能段可能有多个输入端，这些输出端与输入端之间连接的先后次序就形成了多张预约表。个输

43、入端，这些输出端与输入端之间连接的先后次序就形成了多张预约表。非线性流水线的冲突非线性流水线的冲突向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离或等向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离或等待时间。待时间。启动距离通常用时钟周期数来表示，它是一个正整数。启动距离通常用时钟周期数来表示，它是一个正整数。62当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能段的情况，

44、这种情况就是非线性流水线中的冲突。发生有几个任务同时争用同一个功能段的情况，这种情况就是非线性流水线中的冲突。如图如图5.44所示的非线性流水线，当启动距离为所示的非线性流水线，当启动距离为3时，有关功能段的冲突情况如图时，有关功能段的冲突情况如图5.47所示。所示。6364同样，图同样，图5.44所示的非线性流水线，当启动距离为所示的非线性流水线，当启动距离为2时，冲突情况如图时，冲突情况如图5.48所示。所示。65引起非线性流水线功能段冲突的启动距离称为禁止启动距离。如图引起非线性流水线功能段冲突的启动距离称为禁止启动距离。如图5.44所示的非线性流水线，启动所示的非线性流水线，启动距离距

45、离2和启动距离和启动距离3都是禁止启动距离。都是禁止启动距离。有些启动距离在非线性流水线的所有功能段，在任何时间都不会发生冲突。如图有些启动距离在非线性流水线的所有功能段，在任何时间都不会发生冲突。如图5.44的非线性流水的非线性流水线，当启动距离为线，当启动距离为5时的预约表如图时的预约表如图5.49所示。所示。6667在非线性流水线中，不发生冲突的启动距离不一定是一个常数，在一般情况下是一个循环数列。例在非线性流水线中，不发生冲突的启动距离不一定是一个常数，在一般情况下是一个循环数列。例如，图如，图5.44所示的非线性流水线当启动距离为所示的非线性流水线当启动距离为1、7、1、7、交替循环

46、时，任何一个功能段在任何交替循环时，任何一个功能段在任何一个时钟周期也都不发生冲突，如图一个时钟周期也都不发生冲突，如图5.50所示。所示。6869这种使非线性流水线的任何一个功能段在任何一个时钟周期都不发生冲突的循环数列称为非线性流这种使非线性流水线的任何一个功能段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。水线的启动循环。图图5.50中的启动循环记作（中的启动循环记作（1，7）。图）。图5.49中的不发生冲突的启动距离也可以认为是一个循环数列，中的不发生冲突的启动距离也可以认为是一个循环数列，可以记作（可以记作（5）。这种只有一个启动距离的启动循环又称为恒定循环。）

47、。这种只有一个启动距离的启动循环又称为恒定循环。要正确调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。要正确调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。把一条非线性流水线的所有禁止启动距离组合在一起就形成一个数列，通常把这个数列称为非线性把一条非线性流水线的所有禁止启动距离组合在一起就形成一个数列，通常把这个数列称为非线性流水线的禁止向量。流水线的禁止向量。70由预约表得到禁止向量的方法很简单，只要把预约表的每一行中任意两个由预约表得到禁止向量的方法很简单，只要把预约表的每一行中任意两个“”之间的距离都计算出之间的距离都计算出来，去掉重复的，由这种数组成的一个数列就是这

48、条非线性流水线的禁止向量。来，去掉重复的，由这种数组成的一个数列就是这条非线性流水线的禁止向量。例图例图5.44所示的非线性流水线的禁止向量为（所示的非线性流水线的禁止向量为（3，4，6）。）。把一个启动循环内的所有启动距离相加再除以这个启动循环内的启动距离个数就得到这个启动循环把一个启动循环内的所有启动距离相加再除以这个启动循环内的启动距离个数就得到这个启动循环的平均启动距离。的平均启动距离。例如，启动循环（例如，启动循环（1，7）的平均启动距离是）的平均启动距离是4，而恒定循环（，而恒定循环（5）的平均启动距离就是它本身的启动）的平均启动距离就是它本身的启动距离距离5。无冲突的调度方法无冲

49、突的调度方法71非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。有冲突。根据一张预约表的禁止向量可以很容易得到冲突向量。根据一张预约表的禁止向量可以很容易得到冲突向量。冲突向量用一个冲突向量用一个m位的二进制数表示，其中位的二进制数表示，其中m是禁止向量中的最大值。对于一张是禁止向量中的最大值。

50、对于一张k列的预约表，有列的预约表，有mk1。一般的冲突向量用。一般的冲突向量用C(CmCm1C2 C1)来表示。如果在在禁止向量中，则来表示。如果在在禁止向量中，则Ci 1，否，否则则Ci 0。其中。其中, Cm一定为一定为1，因为，因为m必定在禁止向量中。必定在禁止向量中。72例如，对于图例如，对于图5.44(b)所示预约表，冲突向量所示预约表，冲突向量C(101100)。由冲突向量可以构造一张状态图。由冲突向量可以构造一张状态图。把冲突向量把冲突向量C作为初始冲突向量送入一个作为初始冲突向量送入一个m位逻辑右移移位器，当从移位器移出的位为位逻辑右移移位器，当从移位器移出的位为0时，用移位

51、时，用移位器中的值与初始冲突向量作器中的值与初始冲突向量作“按位或按位或”运算，得到一个新的冲突向量；若移位器移出的位为运算，得到一个新的冲突向量；若移位器移出的位为1，不做，不做任何处理；移位器继续右移，如此重复任何处理；移位器继续右移，如此重复m次。次。在初始冲突向量和所有新形成的冲突向量之间用带箭头的线连接，表示各种状态之间的转换关系。在初始冲突向量和所有新形成的冲突向量之间用带箭头的线连接，表示各种状态之间的转换关系。线边注上数字线边注上数字n，表示初始冲突向量经过，表示初始冲突向量经过n次右移产生新冲突向量。次右移产生新冲突向量。73对于中间形成的每一个新的冲突向量，也按这一方法进行

52、处理。对于中间形成的每一个新的冲突向量，也按这一方法进行处理。当形成的新冲突向量出现重复时，可合并到一起。当形成的新冲突向量出现重复时，可合并到一起。由图由图5.44所示非线性流水线构成的状态图如图所示非线性流水线构成的状态图如图5.51所示。所示。7475当初始冲突向量确定之后，状态图就是唯一的，因此，与一张预约表相对应，只有唯一的一个状态当初始冲突向量确定之后，状态图就是唯一的，因此，与一张预约表相对应，只有唯一的一个状态图。但是，由于不同的预约表可能产生相同的初始冲突向量，因此，不同的预约表也可能有相同的图。但是，由于不同的预约表可能产生相同的初始冲突向量，因此，不同的预约表也可能有相同

53、的状态图。所以，从预约表可以画出状态图，但从状态图不能得到预约表。状态图。所以，从预约表可以画出状态图，但从状态图不能得到预约表。在状态图中可以找到无穷多个不发生功能段冲突的启动循环。因为非线性流水线调度的主要目标是在状态图中可以找到无穷多个不发生功能段冲突的启动循环。因为非线性流水线调度的主要目标是要找出平均启动距离最小的启动循环，因此，在这些无穷多个启动循环中，一般只要找出简单循环要找出平均启动距离最小的启动循环，因此，在这些无穷多个启动循环中，一般只要找出简单循环即可。即可。所谓简单循环是指状态图中各种冲突向量只经过一次的启动循环。所谓简单循环是指状态图中各种冲突向量只经过一次的启动循环

54、。76状态图状态图5.51中的所有简单循环如表中的所有简单循环如表5.1所示，表中还给出了简单循环的平均启动距离所示，表中还给出了简单循环的平均启动距离。77从表中可以找到平均启动距离最小的启动循环，这样的启动循环被称为最小启动循环。从表中可以找到平均启动距离最小的启动循环，这样的启动循环被称为最小启动循环。上例中，最小启动循环为（上例中，最小启动循环为（1，1，7），平均启动距离为：），平均启动距离为：（1 1 7）/33。图图5.44所示非线性流水线按照最小启动循环（所示非线性流水线按照最小启动循环（1，1，7）工作时，流水线预约表如图）工作时，流水线预约表如图5.52所示。所示。7879

55、优化调度方法优化调度方法按照前面介绍的调度方法得到的最小启动循环，有时并不能使非线性流水线充分发挥效率。按照前面介绍的调度方法得到的最小启动循环，有时并不能使非线性流水线充分发挥效率。下面将介绍非线性流水线的优化调度方法，按照这种方法调度非线性流水线，流水线的工作效率最下面将介绍非线性流水线的优化调度方法，按照这种方法调度非线性流水线，流水线的工作效率最高，即流水线的吞吐率、加速比和效率最好。高，即流水线的吞吐率、加速比和效率最好。预约表中预约表中“”最多的一行所对应的功能段一定是整个流水线的瓶颈功能段。要使整个流水线充分发最多的一行所对应的功能段一定是整个流水线的瓶颈功能段。要使整个流水线充

56、分发挥效率，瓶颈功能段必须不间断工作，不能有空闲。挥效率，瓶颈功能段必须不间断工作，不能有空闲。80因此，非线性流水线调度的关键是充分使用瓶颈功能段，只要让瓶颈功能段不空闲，则非线性流水因此，非线性流水线调度的关键是充分使用瓶颈功能段，只要让瓶颈功能段不空闲，则非线性流水线的吞吐率、加速比和效率必然是最好的。按照这种方法调度流水线，流水线的平均启动距离也一线的吞吐率、加速比和效率必然是最好的。按照这种方法调度流水线，流水线的平均启动距离也一定是最小的。定是最小的。采用预留算法来调度非线性流水线，可以达到最优调度。具体方法如下：采用预留算法来调度非线性流水线，可以达到最优调度。具体方法如下：确定

57、流水线的最小平均启动距离。确定流水线的最小平均启动距离。最小平均启动距离等于预约表中任意一行中最小平均启动距离等于预约表中任意一行中“”的最多个数。的最多个数。确定最小启动循环。确定最小启动循环。81相对于同一个最小平均启动距离可能有多个最小启动循环，其中有一个恒定循环。为了简化控制逻相对于同一个最小平均启动距离可能有多个最小启动循环，其中有一个恒定循环。为了简化控制逻辑，一般选择恒定循环作为最小启动循环。辑，一般选择恒定循环作为最小启动循环。结合流水线预约表和连接图，采用预留算法，通过插入非计算延迟功能段实现最小启动循环。结合流水线预约表和连接图，采用预留算法，通过插入非计算延迟功能段实现最

58、小启动循环。以下，结合图以下，结合图5.44的例子，具体说明调度方法。的例子，具体说明调度方法。用预留算法调度的预约表、连接图如图用预留算法调度的预约表、连接图如图5.53所示。所示。与图与图5.53相对应的流水线状态图如图相对应的流水线状态图如图5.54所示。所示。按照最小启动循环（按照最小启动循环（3）工作的流水线预约表如图）工作的流水线预约表如图5.55所示。每间隔所示。每间隔3个时钟周期，可以向流水线个时钟周期，可以向流水线82输入一个新任务。此时，流水线的任何一个功能段在任何一个时钟周期都不发生冲突。另外，从时输入一个新任务。此时，流水线的任何一个功能段在任何一个时钟周期都不发生冲突

59、。另外，从时钟周期钟周期7开始，瓶颈功能段开始，瓶颈功能段S1就一直忙碌，没有一个时钟周期是空闲的，因此，采用这种调度方法能就一直忙碌，没有一个时钟周期是空闲的，因此，采用这种调度方法能使流水线的吞吐率、加速比和效率达到最优。使流水线的吞吐率、加速比和效率达到最优。83848586五、局部相关五、局部相关按照对程序执行过程可能造成的影响来划分，可以把相关划分为局部相关和全局相关两类。按照对程序执行过程可能造成的影响来划分，可以把相关划分为局部相关和全局相关两类。如图如图5.56所示，如果程序内有一个两路的条件分支操作指令，它把程序划分为三部分所示，如果程序内有一个两路的条件分支操作指令，它把程

60、序划分为三部分B0、B1和和B2，在每一部分内部不再有分支操作指令，通常把这样的一个部分称为一个基本块。在每一部分内部不再有分支操作指令，通常把这样的一个部分称为一个基本块。87在同一个基本块内部的相关称为局部相关，在基本块之间的相关称为全局相关。在同一个基本块内部的相关称为局部相关，在基本块之间的相关称为全局相关。在指令流水线中，局部相关主要有三种：在指令流水线中，局部相关主要有三种：“先写后读先写后读”数据相关，简称数据相关，简称“写读写读”相关；相关；“先读后写先读后写”数据相关，简称数据相关，简称“读写读写”相关；相关；“写写-写写”相关。相关。顺序流动与乱序流动顺序流动与乱序流动从流