流水线问题系统结构

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

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

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

4、，即t1=t2，都为，都为t。则从指令执行。则从指令执行 部件的输出端看，每间隔一个部件的输出端看，每间隔一个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、必须是连续的任务，只有连 续不断地提供任务才能充分发挥流水线的效率。续不断地提供任务才能充分发挥流水线的效率。 把一个任务（一条指令或一个操作）分解为几把一个任务（一条指令或一个操作）分解为几 个有联系的子任务，每个子任务由一个专门的功个有联系的子任务，每个子任务由一个专门的功 能部件来实现。能部件来实现。 在流水线的每一个功能部件的后面都要有一个在流水线的每一个功能部件的后面都要有一个 缓冲寄存器，用于保存本段的执行结果。当某一缓冲寄存器，用于保存本段的执行结果。当某一 个功能段的执行时间变化范围比较大时，要设置个功能段的执行时间变化范围比较大时，要设置 多个缓冲寄存器。多个缓冲寄存器。 1

8、0 流水线中各段的时间应尽量相等，否则将引起流水线中各段的时间应尽量相等，否则将引起 “堵塞堵塞”、“断流断流”等。执行时间长的一段将成等。执行时间长的一段将成 为整个流水线的为整个流水线的“瓶颈瓶颈”，这时，流水线中的各，这时，流水线中的各 个功能部件将不能充分发挥作用。因此，在流水个功能部件将不能充分发挥作用。因此，在流水 线设计中，当遇到线设计中，当遇到“瓶颈瓶颈”时，必须采取办法解时，必须采取办法解 决。决。 流水线需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间”。 只有流水线完全充满时，整个流水线的效率才能只有流水线完全充满时，整个流水线的效率才能 得到充分发挥。得到充

9、分发挥。 二、流水线的分类二、流水线的分类 线性流水线与非线性流水线线性流水线与非线性流水线 按照流水线的各个功能段之间是否有按照流水线的各个功能段之间是否有 11 反馈信号，可以把流水线分为线性流水线和非线反馈信号，可以把流水线分为线性流水线和非线 性流水线两类。性流水线两类。 线性流水线是将流水线的各段逐个串接起来。输线性流水线是将流水线的各段逐个串接起来。输 入数据从流水线的一端进入，从另一端输出。数入数据从流水线的一端进入，从另一端输出。数 据在流水线中的各个功能段流过时，每一个功能据在流水线中的各个功能段流过时，每一个功能 段都流过一次，且仅流过一次。段都流过一次，且仅流过一次。 非

10、线性流水线：在流水线的各个功能段之间除了非线性流水线：在流水线的各个功能段之间除了 有串行的连接之外，还有反馈回路。如图有串行的连接之外，还有反馈回路。如图5.28所示。所示。 12 表示非线性流水线的工作情况除了要有流水线的表示非线性流水线的工作情况除了要有流水线的 连接图之外，还需要一张连接图之外，还需要一张“预约表预约表”，两者共同，两者共同 来表示流水线的工作情况。如图来表示流水线的工作情况。如图5.29所示。所示。 13 图中用图中用“”表示这一个功能段在相应的这一段时表示这一个功能段在相应的这一段时 间内有效，即任务经过了这一个功能段。间内有效，即任务经过了这一个功能段。 一条非线

11、性流水线可以对应有很多张预约表，一一条非线性流水线可以对应有很多张预约表，一 张预约表实际上仅表示一条非线性流水线的一种张预约表实际上仅表示一条非线性流水线的一种 工作方式。工作方式。 线性流水线实际上也有预约表，只不过它的预约线性流水线实际上也有预约表，只不过它的预约 表是确定的。表是确定的。 首先，预约表的水平方向与垂直方向的格数是相首先，预约表的水平方向与垂直方向的格数是相 等的，其次，预约表从左上角到右下角所有格子等的，其次，预约表从左上角到右下角所有格子 全部有效，即是打全部有效，即是打“”的；预约表的其余部分一的；预约表的其余部分一 定是空白的。定是空白的。 因此，在描述线性流水线

12、时，一般不给出预约表。因此，在描述线性流水线时，一般不给出预约表。 14 流水线的级别流水线的级别 按照流水线使用的不同级别，可把流水线分为功按照流水线使用的不同级别，可把流水线分为功 能部件级、处理机级和处理机间级等多种类型。能部件级、处理机级和处理机间级等多种类型。 处理机级流水线又称为指令流水线。它把一条指处理机级流水线又称为指令流水线。它把一条指 令的执行过程分解为多个子过程，每个子过程在令的执行过程分解为多个子过程，每个子过程在 一个独立的功能部件中完成。一个独立的功能部件中完成。 前面介绍的一次重叠执行方式就是一种简单的指前面介绍的一次重叠执行方式就是一种简单的指 令流水线。令流水

13、线。 在采用先行控制器的处理机中，组成先行控制器在采用先行控制器的处理机中，组成先行控制器 的各个部件实际上也构成了一条流水线。如图的各个部件实际上也构成了一条流水线。如图5.30 所所示。 15 16 在先行控制器中，一条指令的执行过程被分解为在先行控制器中，一条指令的执行过程被分解为5 个子过程，每个子过程在一个专用的功能部件中个子过程，每个子过程在一个专用的功能部件中 执行。执行。 由于各种指令在同一个功能部件中执行的时间往由于各种指令在同一个功能部件中执行的时间往 往相差很大，因此，在每一个功能段之间要设置往相差很大，因此，在每一个功能段之间要设置 多个缓冲寄存器，以平滑流水线中各个功

14、能部件多个缓冲寄存器，以平滑流水线中各个功能部件 的操作。的操作。 每个部件内部还可以采用流水线来实现。如对于每个部件内部还可以采用流水线来实现。如对于 一些复杂的运算操作部件，象浮点加法器等一般一些复杂的运算操作部件，象浮点加法器等一般 要采用多级流水线来实现。后行写数栈和先行读要采用多级流水线来实现。后行写数栈和先行读 数栈也可以采用多级流水线来实现。这种流水线数栈也可以采用多级流水线来实现。这种流水线 称为部件级流水线，或功能部件级流水线。称为部件级流水线，或功能部件级流水线。 17 功能部件级流水线也称为运算操作流水线。功能部件级流水线也称为运算操作流水线。 把指令执行部件中采用了流水

15、线的处理机称为流把指令执行部件中采用了流水线的处理机称为流 水线处理机或超流水线处理机，把指令执行部件水线处理机或超流水线处理机，把指令执行部件 中设置有多个操作部件的处理机称为多操作部件中设置有多个操作部件的处理机称为多操作部件 处理机或超标量处理机。处理机或超标量处理机。 处理机间流水线又称为宏流水线，如图处理机间流水线又称为宏流水线，如图5.31所示。所示。 18 这种流水线由两个或两个以上处理机通过存储器这种流水线由两个或两个以上处理机通过存储器 串行连接起来，每个处理机对同一个数据流的不串行连接起来，每个处理机对同一个数据流的不 同部分分别进行处理。前一个处理机的输出结果同部分分别进

16、行处理。前一个处理机的输出结果 存入存储器中，作为后一个处理机的输入，每个存入存储器中，作为后一个处理机的输入，每个 处理机完成整个任务的一部分。处理机完成整个任务的一部分。 一台大型计算机系统通常由多个同型号的或不同一台大型计算机系统通常由多个同型号的或不同 型号的处理机构成，每个处理机有不同的分工。型号的处理机构成，每个处理机有不同的分工。 例如，由多个用高级语言编写的程序需要在机器例如，由多个用高级语言编写的程序需要在机器 上运行，则程序和数据的输入、编译、连接、执上运行，则程序和数据的输入、编译、连接、执 行、执行结果输出等可分别在不同的处理机上完行、执行结果输出等可分别在不同的处理机

17、上完 成，这些处理机就构成了一条宏流水线。成，这些处理机就构成了一条宏流水线。 单功能与多功能流水线单功能与多功能流水线 19 一条流水线只能完成一种固定的功能，这种流水一条流水线只能完成一种固定的功能，这种流水 线称为单功能流水线。线称为单功能流水线。 多功能流水线是指流水线的各段可以进行不同的多功能流水线是指流水线的各段可以进行不同的 连接。在不同时间内，或在同一时间内，通过不连接。在不同时间内，或在同一时间内，通过不 同的连接方式实现不同的功能。同的连接方式实现不同的功能。 20 21 静态流水线与动态流水线静态流水线与动态流水线 在多功能流水线中，按照在同一时间内是否能够在多功能流水线

18、中，按照在同一时间内是否能够 连接成多种方式，同时执行多种功能，可以把多连接成多种方式，同时执行多种功能，可以把多 功能流水线分为静态流水线和动态流水线两种。功能流水线分为静态流水线和动态流水线两种。 静态流水线是指在同一时间内，多功能流水线中静态流水线是指在同一时间内，多功能流水线中 的各个功能段只能按照一种固定的方式连接，实的各个功能段只能按照一种固定的方式连接，实 现一种固定的功能。只有当按照这种连接方式工现一种固定的功能。只有当按照这种连接方式工 作的所有任务都流出流水线之后，多功能流水线作的所有任务都流出流水线之后，多功能流水线 才能重新进行连接，以实现其它功能。才能重新进行连接，以

19、实现其它功能。 例如，图例如，图5.32的多功能流水线，如果按照图的多功能流水线，如果按照图5.33所所 示的时空图工作，就是一种静态流水线。示的时空图工作，就是一种静态流水线。 22 23 动态流水线是指在同一段时间内，多功能流水线动态流水线是指在同一段时间内，多功能流水线 中的各段可以按照不同的方式连接，同时执行多中的各段可以按照不同的方式连接，同时执行多 种功能。种功能。 当然，同时实现多种连接方式是有条件的，即流当然，同时实现多种连接方式是有条件的，即流 水线中的各个功能部件之间不能发生冲突。如图水线中的各个功能部件之间不能发生冲突。如图 5.34所示。所示。 在一般情况下，动态流水线

20、的效率和功能部件的在一般情况下，动态流水线的效率和功能部件的 利用率要比静态流水线高，但动态流水线的控制利用率要比静态流水线高，但动态流水线的控制 比静态流水线要复杂得多，目前，在大多数处理比静态流水线要复杂得多，目前，在大多数处理 机中均采用静态流水线。机中均采用静态流水线。 24 25 按照不同的数据表示方式，可以把流水线分为标按照不同的数据表示方式，可以把流水线分为标 量流水线和向量流水线。量流水线和向量流水线。 在线性流水线中，根据对流水线的控制方式不同，在线性流水线中，根据对流水线的控制方式不同， 可以把流水线分为同步流水线和异步流水线两类。可以把流水线分为同步流水线和异步流水线两类

21、。 一般的宏流水线多采用异步流水线方式。如图一般的宏流水线多采用异步流水线方式。如图5.35 所示。在异步流水线中，当所示。在异步流水线中，当Si功能段要向功能段要向Si1功功 能段传送数据时，首先发出就绪信号，能段传送数据时，首先发出就绪信号， Si1功能功能 段收到就绪信号后，向段收到就绪信号后，向Si功能段回送一个回答信号。功能段回送一个回答信号。 26 27 按照流水线输出端流出的任务与流水线输入端流按照流水线输出端流出的任务与流水线输入端流 入的任务的顺序是否相同，可以把流水线分为顺入的任务的顺序是否相同，可以把流水线分为顺 序流水线与乱序流水线两种。序流水线与乱序流水线两种。 在顺

22、序流水线中，流水线输出端的任务流出顺序在顺序流水线中，流水线输出端的任务流出顺序 与输入端的任务流入顺序完全相同，每个任务在与输入端的任务流入顺序完全相同，每个任务在 流水线的各个功能段中是一个跟着一个顺序流动流水线的各个功能段中是一个跟着一个顺序流动 的。的。 乱序流水线输出端流出任务的顺序与输入端流入乱序流水线输出端流出任务的顺序与输入端流入 任务的顺序可以不一样。每个任务在流水线中并任务的顺序可以不一样。每个任务在流水线中并 不是按照输入的顺序一个跟着一个流动的。不是按照输入的顺序一个跟着一个流动的。 三、线性流水线的性能分析三、线性流水线的性能分析 28 衡量流水线性能的主要指标有吞吐

23、率、加速比和衡量流水线性能的主要指标有吞吐率、加速比和 效率。效率。 吞吐率吞吐率 流水线的吞吐率是指在单位时间内流水线所完成流水线的吞吐率是指在单位时间内流水线所完成 的任务数量或输出结果数量。的任务数量或输出结果数量。 其中，其中，n为任务数，为任务数，Tk是处理完成是处理完成n个任务所用的个任务所用的 时间。时间。 以下讨论满足某种特殊情况的流水线吞吐率。以下讨论满足某种特殊情况的流水线吞吐率。 流水线各段执行时间相等，输入到流水线中的任流水线各段执行时间相等，输入到流水线中的任 务是连续的。如图务是连续的。如图5.36所示。所示。 29 30 一条一条k段线性流水线完成段线性流水线完成

24、n个连续任务需要的总时个连续任务需要的总时 间为：间为： 其中，其中，t为时钟周期。为时钟周期。 实际吞吐率为：实际吞吐率为： 最大吞吐率为：最大吞吐率为： 31 最大吞吐率与实际吞吐率的关系是：最大吞吐率与实际吞吐率的关系是： 当流水线中各段的执行时间不完全相等时，流水当流水线中各段的执行时间不完全相等时，流水 线中就存在有线中就存在有“瓶颈瓶颈”。如图。如图5.37所示。所示。 32 33 流水线各段执行时间不相等情况下的实际吞吐率：流水线各段执行时间不相等情况下的实际吞吐率： 此时流水线的最大吞吐率为：此时流水线的最大吞吐率为： 对于图对于图5.37所示的例子，流水线的最大吞吐率为：所示

25、的例子，流水线的最大吞吐率为： 34 可以看出，当流水线中各个功能段的执行时间不可以看出，当流水线中各个功能段的执行时间不 完全相等时，流水线的最大吞吐率与实际吞吐率完全相等时，流水线的最大吞吐率与实际吞吐率 主要是由流水线中执行时间最长的那个功能段来主要是由流水线中执行时间最长的那个功能段来 决定的，这个功能段就成了整个流水线的决定的，这个功能段就成了整个流水线的“瓶瓶 颈颈”。 解决流水线解决流水线“瓶颈瓶颈”问题的方法主要有两种。问题的方法主要有两种。 是将流水线的是将流水线的“瓶颈瓶颈”部分再细分。如图部分再细分。如图5.38所所 示。示。 35 通过重复设置瓶颈功能段，让多个瓶颈功能

26、段通过重复设置瓶颈功能段，让多个瓶颈功能段 并行工作。但这种方法，其控制逻辑比较复杂。并行工作。但这种方法，其控制逻辑比较复杂。 如图如图5.39所示。所示。 加速比加速比 完成一批任务，不使用流水线所用的时间与使用完成一批任务，不使用流水线所用的时间与使用 流水线所用的时间之比称为流水线的加速比。流水线所用的时间之比称为流水线的加速比。 如果不使用流水线，即顺序执行所用的时间为如果不使用流水线，即顺序执行所用的时间为T0， 使用流水线的执行时间为使用流水线的执行时间为Tk，则流水线的加速比，则流水线的加速比 为：为： 36 37 各个功能段执行时间均相等的一条各个功能段执行时间均相等的一条k

27、段流水线完成段流水线完成 n个连续任务时的实际加速比为：个连续任务时的实际加速比为： 此时的最大加速比为：此时的最大加速比为： 38 可以看出，流水线的最大加速比等于流水线的段可以看出，流水线的最大加速比等于流水线的段 数。数。 是否流水线的段数越多越好呢是否流水线的段数越多越好呢? 实际上，当流水线的段数很多时，为了使流水线实际上，当流水线的段数很多时，为了使流水线 能够充分发挥效率，要求连续输入的任务数能够充分发挥效率，要求连续输入的任务数n也就也就 很多。很多。 图图5.40给出连续任务个数给出连续任务个数n与加速比与加速比S的关系。的关系。 当任务个数很小时，加速比可能很差，当当任务个

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

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

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

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

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

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

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

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

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

37、迟时间都为假设每一个功能段的延迟时间都为t，则流水线，则流水线 的吞吐率的吞吐率TP为：为： 52 如果采用顺序执行方式，完成一次乘法用如果采用顺序执行方式，完成一次乘法用4个个t， 完成一次加法用完成一次加法用6个个t，则完成全部运算要用：，则完成全部运算要用： T044t36t34t 则流水线的加速比则流水线的加速比S为：为： 整个流水线共有整个流水线共有8段，流水线效率段，流水线效率E为：为： 53 54 四、非线性流水线的调度技术四、非线性流水线的调度技术 在非线性流水线中，由于存在有反馈回路，当一在非线性流水线中，由于存在有反馈回路，当一 个任务在流水线中流过时，在同一个功能段中可个

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

39、线的各周期向流水线输入一个新任务才能使流水线的各 个功能段都不发生冲突，这就是非线性流水线的个功能段都不发生冲突，这就是非线性流水线的 调度问题。调度问题。 55 在许多非线性流水线中，间隔的周期数往往不是在许多非线性流水线中，间隔的周期数往往不是 一个常数，而是一串周期变化的数字。一个常数，而是一串周期变化的数字。 因此，非线性流水线调度的任务是要找出一个最因此，非线性流水线调度的任务是要找出一个最 小的循环周期，按照这个周期向流水线输入新任小的循环周期，按照这个周期向流水线输入新任 务，流水线的各个功能段都不会发生冲突，而且务，流水线的各个功能段都不会发生冲突，而且 流水线的吞吐率和效率最

40、高。流水线的吞吐率和效率最高。 下面，先介绍非线性流水线的表示方法，然后分下面，先介绍非线性流水线的表示方法，然后分 析非线性流水线中的冲突情况，并介绍无冲突调析非线性流水线中的冲突情况，并介绍无冲突调 度方法，最后介绍非线性流水线的优化调度方法。度方法，最后介绍非线性流水线的优化调度方法。 非线性流水线的表示非线性流水线的表示 一条非线性流水线一般需要一个各功能段之间的一条非线性流水线一般需要一个各功能段之间的 连接图和一张预约表共同来表示，如图连接图和一张预约表共同来表示，如图5.44(a)和和 5.44(b)所示。所示。 56 57 预约表的横坐标表示流水线工作的时钟周期，纵预约表的横坐

41、标表示流水线工作的时钟周期，纵 坐标表示流水线的功能段，中间有坐标表示流水线的功能段，中间有“”的表示该的表示该 功能段在这一个时钟周期处于工作状态，即在这功能段在这一个时钟周期处于工作状态，即在这 个时钟周期有任务通过这个功能段，空白的地方个时钟周期有任务通过这个功能段，空白的地方 表示该功能段在这个时钟周期不工作。表示该功能段在这个时钟周期不工作。 一行中可以由多个一行中可以由多个“”，其含义是一个任务在不，其含义是一个任务在不 同时钟周期重复使用了同一个功能段，一列中有同时钟周期重复使用了同一个功能段，一列中有 多个多个“”是指在同一个时钟周期同时使用了多个是指在同一个时钟周期同时使用了

42、多个 功能段。功能段。 预约表的行数就是非线性流水线的段数，预约表预约表的行数就是非线性流水线的段数，预约表 的列数是指一个任务从进入流水线到从流水线中的列数是指一个任务从进入流水线到从流水线中 输出所经过的时钟周期数。输出所经过的时钟周期数。 有时把预约表的列数称为流水线的功能求值时间有时把预约表的列数称为流水线的功能求值时间 或流水线的装入时间等。或流水线的装入时间等。 58 一张非线性流水线的预约表可能与多个非线性流一张非线性流水线的预约表可能与多个非线性流 水线连接图相对应，如图水线连接图相对应，如图5.45就是图就是图5.44(b)所示所示 预约表的另一种连接图。预约表的另一种连接图

43、。 59 产生这种情况的原因是：在预约表的同一列中可产生这种情况的原因是：在预约表的同一列中可 能有多个能有多个“”，即在这个时钟周期有多个功能段，即在这个时钟周期有多个功能段 有输出，从而造成下一个功能段的输入可能有多有输出，从而造成下一个功能段的输入可能有多 种来源，从而对应有多个流水线的连接图。种来源，从而对应有多个流水线的连接图。 同样，一个非线性流水线的连接图也可能对应有同样，一个非线性流水线的连接图也可能对应有 多张预约表。如图多张预约表。如图5.46就是图就是图5.44(a)所示流水线所示流水线 连接图的另一张预约表。连接图的另一张预约表。 60 61 造成这种情况的原因是：在非

44、线性流水线的有些造成这种情况的原因是：在非线性流水线的有些 功能段可能有多个输出端，也有些功能段可能有功能段可能有多个输出端，也有些功能段可能有 多个输入端，这些输出端与输入端之间连接的先多个输入端，这些输出端与输入端之间连接的先 后次序就形成了多张预约表。后次序就形成了多张预约表。 非线性流水线的冲突非线性流水线的冲突 向一条非线性流水线的输入端连续输入两个任务向一条非线性流水线的输入端连续输入两个任务 之间的时间间隔称为非线性流水线的启动距离或之间的时间间隔称为非线性流水线的启动距离或 等待时间。等待时间。 启动距离通常用时钟周期数来表示，它是一个正启动距离通常用时钟周期数来表示，它是一个

45、正 整数。整数。 62 当以某一个启动距离向一条非线性流水线连续输当以某一个启动距离向一条非线性流水线连续输 入任务时，可能在某一个功能段或某几个功能段入任务时，可能在某一个功能段或某几个功能段 中发生有几个任务同时争用同一个功能段的情况，中发生有几个任务同时争用同一个功能段的情况， 这种情况就是非线性流水线中的冲突。这种情况就是非线性流水线中的冲突。 如图如图5.44所示的非线性流水线，当启动距离为所示的非线性流水线，当启动距离为3时，时， 有关功能段的冲突情况如图有关功能段的冲突情况如图5.47所示。所示。 63 64 同样，图同样，图5.44所示的非线性流水线，当启动距离为所示的非线性流

46、水线，当启动距离为 2时，冲突情况如图时，冲突情况如图5.48所示。所示。 65 引起非线性流水线功能段冲突的启动距离称为禁引起非线性流水线功能段冲突的启动距离称为禁 止启动距离。如图止启动距离。如图5.44所示的非线性流水线，启动所示的非线性流水线，启动 距离距离2和启动距离和启动距离3都是禁止启动距离。都是禁止启动距离。 有些启动距离在非线性流水线的所有功能段，在有些启动距离在非线性流水线的所有功能段，在 任何时间都不会发生冲突。如图任何时间都不会发生冲突。如图5.44的非线性流水的非线性流水 线，当启动距离为线，当启动距离为5时的预约表如图时的预约表如图5.49所示。所示。 66 67

47、在非线性流水线中，不发生冲突的启动距离不一在非线性流水线中，不发生冲突的启动距离不一 定是一个常数，在一般情况下是一个循环数列。定是一个常数，在一般情况下是一个循环数列。 例如，图例如，图5.44所示的非线性流水线当启动距离为所示的非线性流水线当启动距离为1、 7、1、7、交替循环时，任何一个功能段在任何交替循环时，任何一个功能段在任何 一个时钟周期也都不发生冲突，如图一个时钟周期也都不发生冲突，如图5.50所示。所示。 68 69 这种使非线性流水线的任何一个功能段在任何一这种使非线性流水线的任何一个功能段在任何一 个时钟周期都不发生冲突的循环数列称为非线性个时钟周期都不发生冲突的循环数列称

48、为非线性 流水线的启动循环。流水线的启动循环。 图图5.50中的启动循环记作（中的启动循环记作（1，7）。图）。图5.49中的中的 不发生冲突的启动距离也可以认为是一个循环数不发生冲突的启动距离也可以认为是一个循环数 列，可以记作（列，可以记作（5）。这种只有一个启动距离的启）。这种只有一个启动距离的启 动循环又称为恒定循环。动循环又称为恒定循环。 要正确调度一条非线性流水线，首先要找出流水要正确调度一条非线性流水线，首先要找出流水 线的所有禁止启动距离。线的所有禁止启动距离。 把一条非线性流水线的所有禁止启动距离组合在把一条非线性流水线的所有禁止启动距离组合在 一起就形成一个数列，通常把这个

49、数列称为非线一起就形成一个数列，通常把这个数列称为非线 性流水线的禁止向量。性流水线的禁止向量。 70 由预约表得到禁止向量的方法很简单，只要把预由预约表得到禁止向量的方法很简单，只要把预 约表的每一行中任意两个约表的每一行中任意两个“”之间的距离都计算之间的距离都计算 出来，去掉重复的，由这种数组成的一个数列就出来，去掉重复的，由这种数组成的一个数列就 是这条非线性流水线的禁止向量。是这条非线性流水线的禁止向量。 例图例图5.44所示的非线性流水线的禁止向量为（所示的非线性流水线的禁止向量为（3， 4，6）。）。 把一个启动循环内的所有启动距离相加再除以这把一个启动循环内的所有启动距离相加再

50、除以这 个启动循环内的启动距离个数就得到这个启动循个启动循环内的启动距离个数就得到这个启动循 环的平均启动距离。环的平均启动距离。 例如，启动循环（例如，启动循环（1，7）的平均启动距离是）的平均启动距离是4，而，而 恒定循环（恒定循环（5）的平均启动距离就是它本身的启动）的平均启动距离就是它本身的启动 距离距离5。 无冲突的调度方法无冲突的调度方法 71 非线性流水线无冲突调度的主要目标是要找出具非线性流水线无冲突调度的主要目标是要找出具 有最小平均启动距离的启动循环，按照这样的启有最小平均启动距离的启动循环，按照这样的启 动循环向非线性流水线的输入端输入任务，流水动循环向非线性流水线的输入

51、端输入任务，流水 线的工作速度最快，而且所有功能段在任何时间线的工作速度最快，而且所有功能段在任何时间 都没有冲突。都没有冲突。 根据一张预约表的禁止向量可以很容易得到冲突根据一张预约表的禁止向量可以很容易得到冲突 向量。向量。 冲突向量用一个冲突向量用一个m位的二进制数表示，其中位的二进制数表示，其中m是禁是禁 止向量中的最大值。对于一张止向量中的最大值。对于一张k列的预约表，有列的预约表，有 mk1。一般的冲突向量用。一般的冲突向量用C(CmCm1C2 C1)来表示。如果在在禁止向量中，则来表示。如果在在禁止向量中，则Ci 1，否，否 则则Ci 0。其中。其中, Cm一定为一定为1，因为，

52、因为m必定在禁止必定在禁止 向量中。向量中。 72 例如，对于图例如，对于图5.44(b)所示预约表，冲突向量所示预约表，冲突向量C (101100)。 由冲突向量可以构造一张状态图。由冲突向量可以构造一张状态图。 把冲突向量把冲突向量C作为初始冲突向量送入一个作为初始冲突向量送入一个m位逻辑位逻辑 右移移位器，当从移位器移出的位为右移移位器，当从移位器移出的位为0时，用移位时，用移位 器中的值与初始冲突向量作器中的值与初始冲突向量作“按位或按位或”运算，得运算，得 到一个新的冲突向量；若移位器移出的位为到一个新的冲突向量；若移位器移出的位为1，不，不 做任何处理；移位器继续右移，如此重复做任

53、何处理；移位器继续右移，如此重复m次。次。 在初始冲突向量和所有新形成的冲突向量之间用在初始冲突向量和所有新形成的冲突向量之间用 带箭头的线连接，表示各种状态之间的转换关系。带箭头的线连接，表示各种状态之间的转换关系。 线边注上数字线边注上数字n，表示初始冲突向量经过，表示初始冲突向量经过n次右移次右移 产生新冲突向量。产生新冲突向量。 73 对于中间形成的每一个新的冲突向量，也按这一对于中间形成的每一个新的冲突向量，也按这一 方法进行处理。方法进行处理。 当形成的新冲突向量出现重复时，可合并到一起。当形成的新冲突向量出现重复时，可合并到一起。 由图由图5.44所示非线性流水线构成的状态图如图

54、所示非线性流水线构成的状态图如图5.51 所示。所示。 74 75 当初始冲突向量确定之后，状态图就是唯一的，当初始冲突向量确定之后，状态图就是唯一的， 因此，与一张预约表相对应，只有唯一的一个状因此，与一张预约表相对应，只有唯一的一个状 态图。但是，由于不同的预约表可能产生相同的态图。但是，由于不同的预约表可能产生相同的 初始冲突向量，因此，不同的预约表也可能有相初始冲突向量，因此，不同的预约表也可能有相 同的状态图。所以，从预约表可以画出状态图，同的状态图。所以，从预约表可以画出状态图， 但从状态图不能得到预约表。但从状态图不能得到预约表。 在状态图中可以找到无穷多个不发生功能段冲突在状态

55、图中可以找到无穷多个不发生功能段冲突 的启动循环。因为非线性流水线调度的主要目标的启动循环。因为非线性流水线调度的主要目标 是要找出平均启动距离最小的启动循环，因此，是要找出平均启动距离最小的启动循环，因此， 在这些无穷多个启动循环中，一般只要找出简单在这些无穷多个启动循环中，一般只要找出简单 循环即可。循环即可。 所谓简单循环是指状态图中各种冲突向量只经过所谓简单循环是指状态图中各种冲突向量只经过 一次的启动循环。一次的启动循环。 76 状态图状态图5.51中的所有简单循环如表中的所有简单循环如表5.1所示，表中所示，表中 还给出了简单循环的平均启动距离还给出了简单循环的平均启动距离。 77

56、 从表中可以找到平均启动距离最小的启动循环，从表中可以找到平均启动距离最小的启动循环， 这样的启动循环被称为最小启动循环。这样的启动循环被称为最小启动循环。 上例中，最小启动循环为（上例中，最小启动循环为（1，1，7），平均启动），平均启动 距离为：距离为：（1 1 7）/33。 图图5.44所示非线性流水线按照最小启动循环（所示非线性流水线按照最小启动循环（1， 1，7）工作时，流水线预约表如图）工作时，流水线预约表如图5.52所示。所示。 78 79 优化调度方法优化调度方法 按照前面介绍的调度方法得到的最小启动循环，按照前面介绍的调度方法得到的最小启动循环， 有时并不能使非线性流水线充分

57、发挥效率。有时并不能使非线性流水线充分发挥效率。 下面将介绍非线性流水线的优化调度方法，按照下面将介绍非线性流水线的优化调度方法，按照 这种方法调度非线性流水线，流水线的工作效率这种方法调度非线性流水线，流水线的工作效率 最高，即流水线的吞吐率、加速比和效率最好。最高，即流水线的吞吐率、加速比和效率最好。 预约表中预约表中“”最多的一行所对应的功能段一定是最多的一行所对应的功能段一定是 整个流水线的瓶颈功能段。要使整个流水线充分整个流水线的瓶颈功能段。要使整个流水线充分 发挥效率，瓶颈功能段必须不间断工作，不能有发挥效率，瓶颈功能段必须不间断工作，不能有 空闲。空闲。 80 因此，非线性流水线

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

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

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