1、. 5.2 流水线处理机流水线处理机教学目标：掌握流水线的基本原理、特点、分类、教学目标：掌握流水线的基本原理、特点、分类、性能分析，非线性流水线的调度问题，及局部相关性能分析，非线性流水线的调度问题，及局部相关和全局相关的处理方法。和全局相关的处理方法。一、流水线工作原理一、流水线工作原理 流水线方式是把一个重复的过程分解为若干个流水线方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其他子过程同时进行。子过程，每个子过程可以与其他子过程同时进行。 在处理机的各个部分几乎都可以采用流水方式在处理机的各个部分几乎都可以采用流水方式工作。工作。 指令的执行过程可以采用流水线，称为指令流指
2、令的执行过程可以采用流水线，称为指令流水线。水线。. 运算器中的操作部件，如浮点加法器等可以采运算器中的操作部件，如浮点加法器等可以采用流水线，称为操作部件流水线。用流水线，称为操作部件流水线。从重叠到流水线从重叠到流水线 一次重叠方式就是一种简单的流水线。一次重叠方式就是一种简单的流水线。 在计算机中，一条指令的执行过程分解为在计算机中，一条指令的执行过程分解为“分分析析”和和“执行执行”两个子过程，这两个子过程分别在两个子过程，这两个子过程分别在指令分析器和指令执行部件中完成，如图指令分析器和指令执行部件中完成，如图5.23所示。所示。. 指令分析器和指令执行部件的输出端各有一个指令分析器
3、和指令执行部件的输出端各有一个锁存器，可分别保存指令锁存器，可分别保存指令“分析分析”和指令和指令“执行执行”的结果，因此，指令分析器和指令执行部件能成为的结果，因此，指令分析器和指令执行部件能成为两个完全独立的功能部件，可同时并行工作。指令两个完全独立的功能部件，可同时并行工作。指令分析器分析器“分析分析k1”与指令执行部件与指令执行部件“执行执行k”可同可同时进行。时进行。 如果指令分析器分析一条指令所需要的时间如果指令分析器分析一条指令所需要的时间t1与指令执行部件执行一条指令所需要的时间与指令执行部件执行一条指令所需要的时间t2相等，即相等，即t1=t2，都为，都为t。则从指令执行。则
4、从指令执行部件的输出端看，每间隔一个部件的输出端看，每间隔一个t就执行完成一条就执行完成一条指令，并输出一个运算结果。因此，处理机指令，并输出一个运算结果。因此，处理机.执行指令的速度提高了一倍。执行指令的速度提高了一倍。 如果把执行一条指令的过程分得更细，如图如果把执行一条指令的过程分得更细，如图5.24所示，分为所示，分为6个子过程。每一个部件的输出端个子过程。每一个部件的输出端都要有一个锁存器。都要有一个锁存器。.在图在图5.24中的每一个子过程还可以再进一步分解成中的每一个子过程还可以再进一步分解成更小的子过程，即在功能部件的内部也采用流水线更小的子过程，即在功能部件的内部也采用流水线
5、方式工作。如，一个浮点加法的执行过程可采用方式工作。如，一个浮点加法的执行过程可采用4级流水线，如图级流水线，如图5.25所示。如果各个部件的执行时所示。如果各个部件的执行时间均相等，处理机执行浮点加法的速度能够提高间均相等，处理机执行浮点加法的速度能够提高3倍。倍。.时空图时空图 描述流水线的工作，最常用的方法是采用描述流水线的工作，最常用的方法是采用“时空图时空图”。 图图5.23所示的流水线，采用时空图表示如图所示的流水线，采用时空图表示如图5.26所示。所示。.在时空图中，横坐标表示时间，就是输入到流水线在时空图中，横坐标表示时间，就是输入到流水线中的各个任务在流水线中所经过的时间。纵
6、坐标表中的各个任务在流水线中所经过的时间。纵坐标表示空间，即流水线的各个子过程。示空间，即流水线的各个子过程。在时空图中，流水线的一个子过程通常称为在时空图中，流水线的一个子过程通常称为“功能功能段段”。图图5.27是一个是一个4段浮点加法器流水线的时空图。段浮点加法器流水线的时空图。.流水线的特点流水线的特点在处理机中采用流水线方式与采用传统的串行方在处理机中采用流水线方式与采用传统的串行方式相比，具有如下特点：式相比，具有如下特点：在流水线中处理的必须是连续的任务，只有连在流水线中处理的必须是连续的任务，只有连续不断地提供任务才能充分发挥流水线的效率。续不断地提供任务才能充分发挥流水线的效
7、率。把一个任务（一条指令或一个操作）分解为几把一个任务（一条指令或一个操作）分解为几个有联系的子任务，每个子任务由一个专门的功个有联系的子任务，每个子任务由一个专门的功能部件来实现。能部件来实现。在流水线的每一个功能部件的后面都要有一个在流水线的每一个功能部件的后面都要有一个缓冲寄存器，用于保存本段的执行结果。当某一缓冲寄存器，用于保存本段的执行结果。当某一个功能段的执行时间变化范围比较大时，要设置个功能段的执行时间变化范围比较大时，要设置多个缓冲寄存器。多个缓冲寄存器。.流水线中各段的时间应尽量相等，否则将引起流水线中各段的时间应尽量相等，否则将引起“堵塞堵塞”、“断流断流”等。执行时间长的
8、一段将成为等。执行时间长的一段将成为整个流水线的整个流水线的“瓶颈瓶颈”，这时，流水线中的各个功，这时，流水线中的各个功能部件将不能充分发挥作用。因此，在流水线设计能部件将不能充分发挥作用。因此，在流水线设计中，当遇到中，当遇到“瓶颈瓶颈”时，必须采取办法解决。时，必须采取办法解决。流水线需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间”。只。只有流水线完全充满时，整个流水线的效率才能得到有流水线完全充满时，整个流水线的效率才能得到充分发挥。充分发挥。二、流水线的分类二、流水线的分类线性流水线与非线性流水线线性流水线与非线性流水线 按照流水线的各个功能段之间是否有按照流水线的各个功
9、能段之间是否有.反馈信号，可以把流水线分为线性流水线和非线性反馈信号，可以把流水线分为线性流水线和非线性流水线两类。流水线两类。线性流水线是将流水线的各段逐个串接起来。输入线性流水线是将流水线的各段逐个串接起来。输入数据从流水线的一端进入，从另一端输出。数据在数据从流水线的一端进入，从另一端输出。数据在流水线中的各个功能段流过时，每一个功能段都流流水线中的各个功能段流过时，每一个功能段都流过一次，且仅流过一次。过一次，且仅流过一次。非线性流水线：在流水线的各个功能段之间除了有非线性流水线：在流水线的各个功能段之间除了有串行的连接之外，还有反馈回路。如图串行的连接之外，还有反馈回路。如图5.28
10、所示。所示。.表示非线性流水线的工作情况除了要有流水线的连表示非线性流水线的工作情况除了要有流水线的连接图之外，还需要一张接图之外，还需要一张“预约表预约表”，两者共同来表，两者共同来表示流水线的工作情况。如图示流水线的工作情况。如图5.29所示。所示。.图中用图中用“”表示这一个功能段在相应的这一段时表示这一个功能段在相应的这一段时间内有效，即任务经过了这一个功能段。间内有效，即任务经过了这一个功能段。一条非线性流水线可以对应有很多张预约表，一张一条非线性流水线可以对应有很多张预约表，一张预约表实际上仅表示一条非线性流水线的一种工作预约表实际上仅表示一条非线性流水线的一种工作方式。方式。线性
11、流水线实际上也有预约表，只不过它的预约表线性流水线实际上也有预约表，只不过它的预约表是确定的。是确定的。首先，预约表的水平方向与垂直方向的格数是相等首先，预约表的水平方向与垂直方向的格数是相等的，其次，预约表从左上角到右下角所有格子全部的，其次，预约表从左上角到右下角所有格子全部有效，即是打有效，即是打“”的；预约表的其余部分一定是的；预约表的其余部分一定是空白的。空白的。因此，在描述线性流水线时，一般不给出预约表。因此，在描述线性流水线时，一般不给出预约表。.流水线的级别流水线的级别按照流水线使用的不同级别，可把流水线分为功能按照流水线使用的不同级别，可把流水线分为功能部件级、处理机级和处理
12、机间级等多种类型。部件级、处理机级和处理机间级等多种类型。处理机级流水线又称为指令流水线。它把一条指令处理机级流水线又称为指令流水线。它把一条指令的执行过程分解为多个子过程，每个子过程在一个的执行过程分解为多个子过程，每个子过程在一个独立的功能部件中完成。独立的功能部件中完成。前面介绍的一次重叠执行方式就是一种简单的指令前面介绍的一次重叠执行方式就是一种简单的指令流水线。流水线。在采用先行控制器的处理机中，组成先行控制器的在采用先行控制器的处理机中，组成先行控制器的各个部件实际上也构成了一条流水线。如图各个部件实际上也构成了一条流水线。如图5.30所所示。.在先行控制器中，一条指令的执行过程被
13、分解为在先行控制器中，一条指令的执行过程被分解为5个子过程，每个子过程在一个专用的功能部件中执个子过程，每个子过程在一个专用的功能部件中执行。行。由于各种指令在同一个功能部件中执行的时间往往由于各种指令在同一个功能部件中执行的时间往往相差很大，因此，在每一个功能段之间要设置多个相差很大，因此，在每一个功能段之间要设置多个缓冲寄存器，以平滑流水线中各个功能部件的操作。缓冲寄存器，以平滑流水线中各个功能部件的操作。每个部件内部还可以采用流水线来实现。如对于一每个部件内部还可以采用流水线来实现。如对于一些复杂的运算操作部件，象浮点加法器等一般要采些复杂的运算操作部件，象浮点加法器等一般要采用多级流水
14、线来实现。后行写数栈和先行读数栈也用多级流水线来实现。后行写数栈和先行读数栈也可以采用多级流水线来实现。这种流水线称为部件可以采用多级流水线来实现。这种流水线称为部件级流水线，或功能部件级流水线。级流水线，或功能部件级流水线。.功能部件级流水线也称为运算操作流水线。功能部件级流水线也称为运算操作流水线。把指令执行部件中采用了流水线的处理机称为流水把指令执行部件中采用了流水线的处理机称为流水线处理机或超流水线处理机，把指令执行部件中设线处理机或超流水线处理机，把指令执行部件中设置有多个操作部件的处理机称为多操作部件处理机置有多个操作部件的处理机称为多操作部件处理机或超标量处理机。或超标量处理机。
15、处理机间流水线又称为宏流水线，如图处理机间流水线又称为宏流水线，如图5.31所示。所示。.这种流水线由两个或两个以上处理机通过存储器串这种流水线由两个或两个以上处理机通过存储器串行连接起来，每个处理机对同一个数据流的不同部行连接起来，每个处理机对同一个数据流的不同部分分别进行处理。前一个处理机的输出结果存入存分分别进行处理。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入，每个处理机完储器中，作为后一个处理机的输入，每个处理机完成整个任务的一部分。成整个任务的一部分。一台大型计算机系统通常由多个同型号的或不同型一台大型计算机系统通常由多个同型号的或不同型号的处理机构成，每个处理机有不
16、同的分工。例如，号的处理机构成，每个处理机有不同的分工。例如，由多个用高级语言编写的程序需要在机器上运行，由多个用高级语言编写的程序需要在机器上运行，则程序和数据的输入、编译、连接、执行、执行结则程序和数据的输入、编译、连接、执行、执行结果输出等可分别在不同的处理机上完成，这些处理果输出等可分别在不同的处理机上完成，这些处理机就构成了一条宏流水线。机就构成了一条宏流水线。单功能与多功能流水线单功能与多功能流水线.一条流水线只能完成一种固定的功能，这种流水线一条流水线只能完成一种固定的功能，这种流水线称为单功能流水线。称为单功能流水线。多功能流水线是指流水线的各段可以进行不同的连多功能流水线是指
17、流水线的各段可以进行不同的连接。在不同时间内，或在同一时间内，通过不同的接。在不同时间内，或在同一时间内，通过不同的连接方式实现不同的功能。连接方式实现不同的功能。.静态流水线与动态流水线静态流水线与动态流水线在多功能流水线中，按照在同一时间内是否能够连在多功能流水线中，按照在同一时间内是否能够连接成多种方式，同时执行多种功能，可以把多功能接成多种方式，同时执行多种功能，可以把多功能流水线分为静态流水线和动态流水线两种。流水线分为静态流水线和动态流水线两种。静态流水线是指在同一时间内，多功能流水线中的静态流水线是指在同一时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一各个功
18、能段只能按照一种固定的方式连接，实现一种固定的功能。只有当按照这种连接方式工作的所种固定的功能。只有当按照这种连接方式工作的所有任务都流出流水线之后，多功能流水线才能重新有任务都流出流水线之后，多功能流水线才能重新进行连接，以实现其它功能。进行连接，以实现其它功能。例如，图例如，图5.32的多功能流水线，如果按照图的多功能流水线，如果按照图5.33所所示的时空图工作，就是一种静态流水线。示的时空图工作，就是一种静态流水线。.动态流水线是指在同一段时间内，多功能流水线中动态流水线是指在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功的各段可以按照不同的方式连接，同时执行多
19、种功能。能。当然，同时实现多种连接方式是有条件的，即流水当然，同时实现多种连接方式是有条件的，即流水线中的各个功能部件之间不能发生冲突。如图线中的各个功能部件之间不能发生冲突。如图5.34所示。所示。在一般情况下，动态流水线的效率和功能部件的利在一般情况下，动态流水线的效率和功能部件的利用率要比静态流水线高，但动态流水线的控制比静用率要比静态流水线高，但动态流水线的控制比静态流水线要复杂得多，目前，在大多数处理机中均态流水线要复杂得多，目前，在大多数处理机中均采用静态流水线。采用静态流水线。.按照不同的数据表示方式，可以把流水线分为标量按照不同的数据表示方式，可以把流水线分为标量流水线和向量流
20、水线。流水线和向量流水线。在线性流水线中，根据对流水线的控制方式不同，在线性流水线中，根据对流水线的控制方式不同，可以把流水线分为同步流水线和异步流水线两类。可以把流水线分为同步流水线和异步流水线两类。一般的宏流水线多采用异步流水线方式。如图一般的宏流水线多采用异步流水线方式。如图5.35所示。在异步流水线中，当所示。在异步流水线中，当Si功能段要向功能段要向Si1功功能段传送数据时，首先发出就绪信号，能段传送数据时，首先发出就绪信号， Si1功能功能段收到就绪信号后，向段收到就绪信号后，向Si功能段回送一个回答信号。功能段回送一个回答信号。.按照流水线输出端流出的任务与流水线输入端流入按照流
21、水线输出端流出的任务与流水线输入端流入的任务的顺序是否相同，可以把流水线分为顺序流的任务的顺序是否相同，可以把流水线分为顺序流水线与乱序流水线两种。水线与乱序流水线两种。在顺序流水线中，流水线输出端的任务流出顺序与在顺序流水线中，流水线输出端的任务流出顺序与输入端的任务流入顺序完全相同，每个任务在流水输入端的任务流入顺序完全相同，每个任务在流水线的各个功能段中是一个跟着一个顺序流动的。线的各个功能段中是一个跟着一个顺序流动的。乱序流水线输出端流出任务的顺序与输入端流入任乱序流水线输出端流出任务的顺序与输入端流入任务的顺序可以不一样。每个任务在流水线中并不是务的顺序可以不一样。每个任务在流水线中
22、并不是按照输入的顺序一个跟着一个流动的。按照输入的顺序一个跟着一个流动的。三、线性流水线的性能分析三、线性流水线的性能分析.衡量流水线性能的主要指标有吞吐率、加速比和效衡量流水线性能的主要指标有吞吐率、加速比和效率。率。吞吐率吞吐率流水线的吞吐率是指在单位时间内流水线所完成的流水线的吞吐率是指在单位时间内流水线所完成的任务数量或输出结果数量。任务数量或输出结果数量。其中，其中，n为任务数，为任务数，Tk是处理完成是处理完成n个任务所用的个任务所用的时间。时间。以下讨论满足某种特殊情况的流水线吞吐率。以下讨论满足某种特殊情况的流水线吞吐率。流水线各段执行时间相等，输入到流水线中的任务流水线各段执
23、行时间相等，输入到流水线中的任务是连续的。如图是连续的。如图5.36所示。所示。.一条一条k段线性流水线完成段线性流水线完成n个连续任务需要的总时个连续任务需要的总时间为：间为：其中，其中，t为时钟周期。为时钟周期。实际吞吐率为：实际吞吐率为：最大吞吐率为：最大吞吐率为：.最大吞吐率与实际吞吐率的关系是：最大吞吐率与实际吞吐率的关系是：当流水线中各段的执行时间不完全相等时，流水线当流水线中各段的执行时间不完全相等时，流水线中就存在有中就存在有“瓶颈瓶颈”。如图。如图5.37所示。所示。.流水线各段执行时间不相等情况下的实际吞吐率：流水线各段执行时间不相等情况下的实际吞吐率：此时流水线的最大吞吐
24、率为：此时流水线的最大吞吐率为：对于图对于图5.37所示的例子，流水线的最大吞吐率为：所示的例子，流水线的最大吞吐率为：.可以看出，当流水线中各个功能段的执行时间不完可以看出，当流水线中各个功能段的执行时间不完全相等时，流水线的最大吞吐率与实际吞吐率主要全相等时，流水线的最大吞吐率与实际吞吐率主要是由流水线中执行时间最长的那个功能段来决定的，是由流水线中执行时间最长的那个功能段来决定的，这个功能段就成了整个流水线的这个功能段就成了整个流水线的“瓶颈瓶颈”。解决流水线解决流水线“瓶颈瓶颈”问题的方法主要有两种。问题的方法主要有两种。是将流水线的是将流水线的“瓶颈瓶颈”部分再细分。如图部分再细分。
25、如图5.38所所示。示。.通过重复设置瓶颈功能段，让多个瓶颈功能段并通过重复设置瓶颈功能段，让多个瓶颈功能段并行工作。但这种方法，其控制逻辑比较复杂。如图行工作。但这种方法，其控制逻辑比较复杂。如图5.39所示。所示。加速比加速比完成一批任务，不使用流水线所用的时间与使用流完成一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。水线所用的时间之比称为流水线的加速比。如果不使用流水线，即顺序执行所用的时间为如果不使用流水线，即顺序执行所用的时间为T0，使用流水线的执行时间为使用流水线的执行时间为Tk，则流水线的加速比，则流水线的加速比为：为：.各个功能段执行时间均相等的
26、一条各个功能段执行时间均相等的一条k段流水线完成段流水线完成n个连续任务时的实际加速比为：个连续任务时的实际加速比为：此时的最大加速比为：此时的最大加速比为：.可以看出，流水线的最大加速比等于流水线的段数。可以看出，流水线的最大加速比等于流水线的段数。是否流水线的段数越多越好呢是否流水线的段数越多越好呢?实际上，当流水线的段数很多时，为了使流水线能实际上，当流水线的段数很多时，为了使流水线能够充分发挥效率，要求连续输入的任务数够充分发挥效率，要求连续输入的任务数n也就很也就很多。多。图图5.40给出连续任务个数给出连续任务个数n与加速比与加速比S的关系。的关系。当任务个数很小时，加速比可能很差
27、，当当任务个数很小时，加速比可能很差，当n=1时，时，加速比加速比S的值最小为的值最小为1。当流水线的段数。当流水线的段数K增大时，增大时，可以获得比较好的加速比。当可以获得比较好的加速比。当n=64时，一条时，一条4段流段流水线的加速比为水线的加速比为3.8，一条，一条8段流水线的加速比可以段流水线的加速比可以达到达到7.2。.但是，一方面，由于一般程序中存在数据相关、转但是，一方面，由于一般程序中存在数据相关、转移、中断等情况，连续输入的任务数移、中断等情况，连续输入的任务数n受到很大的受到很大的限制。另一方面，由于控制的复杂性、电路实现及限制。另一方面，由于控制的复杂性、电路实现及组装技
28、术、实现成本等方面的限制，流水线的段数组装技术、实现成本等方面的限制，流水线的段数也不可能很多。也不可能很多。.当流水线的各个功能段的执行时间不相等时，一条当流水线的各个功能段的执行时间不相等时，一条k段线性流水线完成段线性流水线完成n个连续任务的实际加速比为：个连续任务的实际加速比为：效率效率流水线的效率是指流水线的设备利用率。流水线的效率是指流水线的设备利用率。在时空图上，流水线的效率定义为在时空图上，流水线的效率定义为n个任务占用的个任务占用的时空区与时空区与k个功能段总的时空区之比。个功能段总的时空区之比。.其中，其中，T0为为n个任务顺序执行的时间，个任务顺序执行的时间，Tk为流水线
29、为流水线完成完成n个任务的时间，个任务的时间，k为功能段数。为功能段数。如果流水线各段执行时间均相等，输入如果流水线各段执行时间均相等，输入n个任务是个任务是连续的，则一条连续的，则一条k段流水线的效率为：段流水线的效率为：.此时，流水线的最高效率为：此时，流水线的最高效率为：如果流水线的各段执行时间不相等，则连续执行如果流水线的各段执行时间不相等，则连续执行n个任务的流水线效率为：个任务的流水线效率为：.此时，流水线除了瓶颈功能段之外，其它各个功能此时，流水线除了瓶颈功能段之外，其它各个功能段都有空闲时间，这些功能段的效率没有得到充分段都有空闲时间，这些功能段的效率没有得到充分发挥，因此，整
30、个流水线的效率发挥，因此，整个流水线的效率E也比较低。也比较低。在上面给出的所有流水线时空图中，都默认每个功在上面给出的所有流水线时空图中，都默认每个功能段的设备量或设备的价格都是相等的。对于可能能段的设备量或设备的价格都是相等的。对于可能出现的每一个功能段的设备量或功能段的价格不等出现的每一个功能段的设备量或功能段的价格不等的情况，应该根据各个功能段所用的设备量或设备的情况，应该根据各个功能段所用的设备量或设备价格在流水线总设备中所占的比例，分别赋予不同价格在流水线总设备中所占的比例，分别赋予不同的的“权权”值值Pi。此时流水线的效率为：。此时流水线的效率为：.流水线最佳段数的选择流水线最佳
31、段数的选择从上面的分析可看出，增加流水线的段数，流水从上面的分析可看出，增加流水线的段数，流水线的吞吐率和加速比都能提高。但由于在每个功线的吞吐率和加速比都能提高。但由于在每个功能段的输出端都必须设置一个锁存器，因此，当能段的输出端都必须设置一个锁存器，因此，当流水线的段数增多时，锁存器的总延迟时间也将流水线的段数增多时，锁存器的总延迟时间也将增加，另外，增加锁存器数量，流水线的价格也增加，另外，增加锁存器数量，流水线的价格也增加。所以，在设计流水线时，要综合各方面的增加。所以，在设计流水线时，要综合各方面的因素，根据最佳性能价格比的要求来选择流水线因素，根据最佳性能价格比的要求来选择流水线的
32、最佳段数。的最佳段数。假设在非流水线的机器上采用顺序执行方式完成假设在非流水线的机器上采用顺序执行方式完成一个任务所需要的时间为一个任务所需要的时间为t，则在同等速度的有，则在同等速度的有k段流水线的机器上执行一个任务需要的时间为：段流水线的机器上执行一个任务需要的时间为：.tkd，d为锁存器延迟时间。为锁存器延迟时间。则流水线的最大吞吐率为：则流水线的最大吞吐率为：流水线的总价格为：流水线的总价格为：Cabk a为所有功能为所有功能段本身的总价格，段本身的总价格，b为每个锁存器的价格为每个锁存器的价格则性能价格比则性能价格比PCR定义为：定义为：.可以通过对自变量可以通过对自变量k求导，得到
33、性能价格比求导，得到性能价格比PCR的的极值，这个极值也是最大值，如图极值，这个极值也是最大值，如图5.41所示。所示。.当性能价格比当性能价格比PCR取得最大值时，它所对应的流取得最大值时，它所对应的流水线的段数就是最佳段数水线的段数就是最佳段数k：一般处理机中的流水线段数在一般处理机中的流水线段数在2段至段至10段之间，极段之间，极少有超过少有超过15段的流水线。段的流水线。流水线性能分析举例流水线性能分析举例例例5.1单功能、线性流水线，输入任务是不连续的单功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。情况，计算流水线的吞吐率、加速比和效率。用图用图5.25
34、所示的一条所示的一条4段浮点加法器流水线计算段浮点加法器流水线计算8个浮点数的和：个浮点数的和：.ZABCDEFGH由于存在数据相关，将上式变换为：由于存在数据相关，将上式变换为：Z(AB) (CD) (EF) (GH)8个浮点数求和的流水线时空图如图个浮点数求和的流水线时空图如图5.42所示。所示。假设每一个功能段的延迟时间均相等，都为假设每一个功能段的延迟时间均相等，都为t。.例例5.2多功能、线性流水线，输入任务是不连续的多功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。情况，计算流水线的吞吐率、加速比和效率。用图用图5.32所示的多功能静态流水线计算两个向量
35、的所示的多功能静态流水线计算两个向量的点积：点积：ZABCDEFGH为了尽量减少数据相关性，充分发挥流水线的作用，为了尽量减少数据相关性，充分发挥流水线的作用，计算的顺序应该是先做计算的顺序应该是先做4个乘法：个乘法：AB、CD、EF和和GH，然后做两个加法，然后做两个加法ABCD和和EFGH，最后，最后求总的结果求总的结果Z。流水线的时空图如图。流水线的时空图如图5.43所示。所示。假设每一个功能段的延迟时间都为假设每一个功能段的延迟时间都为t，则流水线，则流水线的吞吐率的吞吐率TP为：为：.如果采用顺序执行方式，完成一次乘法用如果采用顺序执行方式，完成一次乘法用4个个t，完成一次加法用完成
36、一次加法用6个个t，则完成全部运算要用：，则完成全部运算要用：T044t36t34t则流水线的加速比则流水线的加速比S为：为：整个流水线共有整个流水线共有8段，流水线效率段，流水线效率E为：为：.四、非线性流水线的调度技术四、非线性流水线的调度技术在非线性流水线中，由于存在有反馈回路，当一个在非线性流水线中，由于存在有反馈回路，当一个任务在流水线中流过时，在同一个功能段中可能要任务在流水线中流过时，在同一个功能段中可能要经过多次。因此，就不能每一个时钟周期向流水线经过多次。因此，就不能每一个时钟周期向流水线输入一个新任务，否则会发生在同一个时刻有几个输入一个新任务，否则会发生在同一个时刻有几个
37、任务争用同一个功能段的情况。这种情况称为功能任务争用同一个功能段的情况。这种情况称为功能部件冲突，或流水线冲突。部件冲突，或流水线冲突。为避免流水线发生冲突，一般采用延迟输入新任务为避免流水线发生冲突，一般采用延迟输入新任务的方法。的方法。在非线性流水线的输入端，究竟每隔多少个时钟周在非线性流水线的输入端，究竟每隔多少个时钟周期向流水线输入一个新任务才能使流水线的各个功期向流水线输入一个新任务才能使流水线的各个功能段都不发生冲突，这就是非线性流水线的调度问能段都不发生冲突，这就是非线性流水线的调度问题。题。.在许多非线性流水线中，间隔的周期数往往不是一在许多非线性流水线中，间隔的周期数往往不是
38、一个常数，而是一串周期变化的数字。个常数，而是一串周期变化的数字。因此，非线性流水线调度的任务是要找出一个最小因此，非线性流水线调度的任务是要找出一个最小的循环周期，按照这个周期向流水线输入新任务，的循环周期，按照这个周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。的吞吐率和效率最高。下面，先介绍非线性流水线的表示方法，然后分析下面，先介绍非线性流水线的表示方法，然后分析非线性流水线中的冲突情况，并介绍无冲突调度方非线性流水线中的冲突情况，并介绍无冲突调度方法，最后介绍非线性流水线的优化调度方法。法，最后介绍非
39、线性流水线的优化调度方法。非线性流水线的表示非线性流水线的表示一条非线性流水线一般需要一个各功能段之间的连一条非线性流水线一般需要一个各功能段之间的连接图和一张预约表共同来表示，如图接图和一张预约表共同来表示，如图5.44(a)和和5.44(b)所示。所示。.预约表的横坐标表示流水线工作的时钟周期，纵坐预约表的横坐标表示流水线工作的时钟周期，纵坐标表示流水线的功能段，中间有标表示流水线的功能段，中间有“”的表示该功的表示该功能段在这一个时钟周期处于工作状态，即在这个时能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段，空白的地方表示该钟周期有任务通过这个功能段，空白的地方表
40、示该功能段在这个时钟周期不工作。功能段在这个时钟周期不工作。一行中可以由多个一行中可以由多个“”，其含义是一个任务在不，其含义是一个任务在不同时钟周期重复使用了同一个功能段，一列中有多同时钟周期重复使用了同一个功能段，一列中有多个个“”是指在同一个时钟周期同时使用了多个功是指在同一个时钟周期同时使用了多个功能段。能段。预约表的行数就是非线性流水线的段数，预约表的预约表的行数就是非线性流水线的段数，预约表的列数是指一个任务从进入流水线到从流水线中输出列数是指一个任务从进入流水线到从流水线中输出所经过的时钟周期数。所经过的时钟周期数。有时把预约表的列数称为流水线的功能求值时间或有时把预约表的列数称
41、为流水线的功能求值时间或流水线的装入时间等。流水线的装入时间等。.一张非线性流水线的预约表可能与多个非线性流水一张非线性流水线的预约表可能与多个非线性流水线连接图相对应，如图线连接图相对应，如图5.45就是图就是图5.44(b)所示预所示预约表的另一种连接图。约表的另一种连接图。.产生这种情况的原因是：在预约表的同一列中可能产生这种情况的原因是：在预约表的同一列中可能有多个有多个“”，即在这个时钟周期有多个功能段有，即在这个时钟周期有多个功能段有输出，从而造成下一个功能段的输入可能有多种来输出，从而造成下一个功能段的输入可能有多种来源，从而对应有多个流水线的连接图。源，从而对应有多个流水线的连
42、接图。同样，一个非线性流水线的连接图也可能对应有多同样，一个非线性流水线的连接图也可能对应有多张预约表。如图张预约表。如图5.46就是图就是图5.44(a)所示流水线连所示流水线连接图的另一张预约表。接图的另一张预约表。.造成这种情况的原因是：在非线性流水线的有些功造成这种情况的原因是：在非线性流水线的有些功能段可能有多个输出端，也有些功能段可能有多个能段可能有多个输出端，也有些功能段可能有多个输入端，这些输出端与输入端之间连接的先后次序输入端，这些输出端与输入端之间连接的先后次序就形成了多张预约表。就形成了多张预约表。非线性流水线的冲突非线性流水线的冲突向一条非线性流水线的输入端连续输入两个
43、任务之向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离或等待间的时间间隔称为非线性流水线的启动距离或等待时间。时间。启动距离通常用时钟周期数来表示，它是一个正整启动距离通常用时钟周期数来表示，它是一个正整数。数。.当以某一个启动距离向一条非线性流水线连续输入当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能段的情况，这种生有几个任务同时争用同一个功能段的情况，这种情况就是非线性流水线中的冲突。情况就是非线性流水线中的冲突。如图如图5.44所示的非线性
44、流水线，当启动距离为所示的非线性流水线，当启动距离为3时，时，有关功能段的冲突情况如图有关功能段的冲突情况如图5.47所示。所示。.同样，图同样，图5.44所示的非线性流水线，当启动距离为所示的非线性流水线，当启动距离为2时，冲突情况如图时，冲突情况如图5.48所示。所示。.引起非线性流水线功能段冲突的启动距离称为禁止引起非线性流水线功能段冲突的启动距离称为禁止启动距离。如图启动距离。如图5.44所示的非线性流水线，启动距所示的非线性流水线，启动距离离2和启动距离和启动距离3都是禁止启动距离。都是禁止启动距离。有些启动距离在非线性流水线的所有功能段，在任有些启动距离在非线性流水线的所有功能段，
45、在任何时间都不会发生冲突。如图何时间都不会发生冲突。如图5.44的非线性流水线，的非线性流水线，当启动距离为当启动距离为5时的预约表如图时的预约表如图5.49所示。所示。.在非线性流水线中，不发生冲突的启动距离不一定在非线性流水线中，不发生冲突的启动距离不一定是一个常数，在一般情况下是一个循环数列。例如，是一个常数，在一般情况下是一个循环数列。例如，图图5.44所示的非线性流水线当启动距离为所示的非线性流水线当启动距离为1、7、1、7、交替循环时，任何一个功能段在任何一个时交替循环时，任何一个功能段在任何一个时钟周期也都不发生冲突，如图钟周期也都不发生冲突，如图5.50所示。所示。.这种使非线
46、性流水线的任何一个功能段在任何一个这种使非线性流水线的任何一个功能段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。线的启动循环。图图5.50中的启动循环记作（中的启动循环记作（1，7）。图）。图5.49中的不中的不发生冲突的启动距离也可以认为是一个循环数列，发生冲突的启动距离也可以认为是一个循环数列，可以记作（可以记作（5）。这种只有一个启动距离的启动循）。这种只有一个启动距离的启动循环又称为恒定循环。环又称为恒定循环。要正确调度一条非线性流水线，首先要找出流水线要正确调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。的
47、所有禁止启动距离。把一条非线性流水线的所有禁止启动距离组合在一把一条非线性流水线的所有禁止启动距离组合在一起就形成一个数列，通常把这个数列称为非线性流起就形成一个数列，通常把这个数列称为非线性流水线的禁止向量。水线的禁止向量。.由预约表得到禁止向量的方法很简单，只要把预约由预约表得到禁止向量的方法很简单，只要把预约表的每一行中任意两个表的每一行中任意两个“”之间的距离都计算出之间的距离都计算出来，去掉重复的，由这种数组成的一个数列就是这来，去掉重复的，由这种数组成的一个数列就是这条非线性流水线的禁止向量。条非线性流水线的禁止向量。例图例图5.44所示的非线性流水线的禁止向量为（所示的非线性流水
48、线的禁止向量为（3，4，6）。）。把一个启动循环内的所有启动距离相加再除以这个把一个启动循环内的所有启动距离相加再除以这个启动循环内的启动距离个数就得到这个启动循环的启动循环内的启动距离个数就得到这个启动循环的平均启动距离。平均启动距离。例如，启动循环（例如，启动循环（1，7）的平均启动距离是）的平均启动距离是4，而，而恒定循环（恒定循环（5）的平均启动距离就是它本身的启动）的平均启动距离就是它本身的启动距离距离5。无冲突的调度方法无冲突的调度方法.非线性流水线无冲突调度的主要目标是要找出具有非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动循最小平均启动距
49、离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲作速度最快，而且所有功能段在任何时间都没有冲突。突。根据一张预约表的禁止向量可以很容易得到冲突向根据一张预约表的禁止向量可以很容易得到冲突向量。量。冲突向量用一个冲突向量用一个m位的二进制数表示，其中位的二进制数表示，其中m是禁是禁止向量中的最大值。对于一张止向量中的最大值。对于一张k列的预约表，有列的预约表，有mk1。一般的冲突向量用。一般的冲突向量用C(CmCm1C2 C1)来表示。如果在在禁止向量中，则来表示。如果在在禁止向量中
50、，则Ci 1，否，否则则Ci 0。其中。其中, Cm一定为一定为1，因为，因为m必定在禁止必定在禁止向量中。向量中。.例如，对于图例如，对于图5.44(b)所示预约表，冲突向量所示预约表，冲突向量C(101100)。由冲突向量可以构造一张状态图。由冲突向量可以构造一张状态图。把冲突向量把冲突向量C作为初始冲突向量送入一个作为初始冲突向量送入一个m位逻辑位逻辑右移移位器，当从移位器移出的位为右移移位器，当从移位器移出的位为0时，用移位时，用移位器中的值与初始冲突向量作器中的值与初始冲突向量作“按位或按位或”运算，得到运算，得到一个新的冲突向量；若移位器移出的位为一个新的冲突向量；若移位器移出的位
