第3章流水线技术

1、n3.1 重叠方式重叠方式n3.2 流水线的基本概念流水线的基本概念n3.3 流水线的性能指标流水线的性能指标n3.4 标量流水机的相关处理标量流水机的相关处理n3.5 非线性流水线的调度非线性流水线的调度n3.6 指令级高度并行的超级处理机指令级高度并行的超级处理机n3.7 流水线的实现流水线的实现第第3章章 流水线技术流水线技术n3.1 重叠方式重叠方式n3.1.1 重叠原理与一次重叠重叠原理与一次重叠n3.1.2 相关处理相关处理第第3章章 流水线技术流水线技术3.1 重叠方式重叠方式n重叠方式是最简单的流水方式。重叠方式是最简单的流水方式。n3.1.1 重叠原理与一次重叠重叠原理与一次

2、重叠n解释一条机器指令的微操作可归并成取指令、分析和解释一条机器指令的微操作可归并成取指令、分析和执行三部分，时间关系如图所示。执行三部分，时间关系如图所示。n取指令取指令是按指令计数器的内容访主存，取出该指令送到是按指令计数器的内容访主存，取出该指令送到指令寄存器。指令寄存器。n指令的指令的分析分析是对指令的操作码进行译码，按寻址方式和是对指令的操作码进行译码，按寻址方式和地址字段形成操作数真地址，并用此真地址去取操作数地址字段形成操作数真地址，并用此真地址去取操作数（可能访主存，也可能访寄存器），为取下一条指令还（可能访主存，也可能访寄存器），为取下一条指令还要形成下一条指令的地址。要形成

3、下一条指令的地址。n指令的指令的执行执行则是对操作数进行运算、处理，或存储运算则是对操作数进行运算、处理，或存储运算结果（可能要访主存）。结果（可能要访主存）。3.1 重叠方式重叠方式 顺序解释顺序解释指的是各条指令之间顺序串行指的是各条指令之间顺序串行(执执行完一条指令后才取下条指令行完一条指令后才取下条指令)地进行，每条地进行，每条指令内部的各个微操作也顺序串行地进行。指令内部的各个微操作也顺序串行地进行。优点：优点：控制简单，转入下条指令的时间易于控制简单，转入下条指令的时间易于控制。控制。缺点：缺点：上一步操作未完成，下一步操作便不上一步操作未完成，下一步操作便不能开始，速度上不去，机

4、器各部件的利能开始，速度上不去，机器各部件的利用率低。用率低。3.1 重叠方式重叠方式 指令的指令的重叠解释重叠解释是在解释第是在解释第K指令的操作指令的操作完成之前，就开始解释第完成之前，就开始解释第K+1条指令。条指令。3.1 重叠方式重叠方式n实现指令的重叠解释必须在计算机组成上满足以下几点要求：实现指令的重叠解释必须在计算机组成上满足以下几点要求：n1. 要解决访主存的冲突。要解决访主存的冲突。n取指取指k+1与分析与分析k在时间上重叠，易出现访主存冲突。在时间上重叠，易出现访主存冲突。n解决办法：解决办法：让操作数和指令分别存放于两个独立编址且可同时让操作数和指令分别存放于两个独立编

5、址且可同时访问的存储器中，这有利于实现指令的保护，但是访问的存储器中，这有利于实现指令的保护，但是增加了主存总线控制的复杂性及软件设计的麻烦。增加了主存总线控制的复杂性及软件设计的麻烦。另一种办法仍维持指令和操作数混存，但采用多体另一种办法仍维持指令和操作数混存，但采用多体交叉主存结构，只要第交叉主存结构，只要第k k条指令的操作数与第条指令的操作数与第k k+1+1条条指令不在同一个体内，仍可在一个主存周期取得，指令不在同一个体内，仍可在一个主存周期取得，从而实现从而实现“分析分析k k”与与“取指取指k k+1+1”重叠。然而，这重叠。然而，这两者若正好共存于一个体内时就无法重叠。两者若正

6、好共存于一个体内时就无法重叠。3.1 重叠方式重叠方式第三种办法是增设采用先进先出方式工作的指令缓第三种办法是增设采用先进先出方式工作的指令缓冲寄存器冲寄存器(简称指缓简称指缓)。 由于大量中间结果只存于通用寄存器中，因此主存由于大量中间结果只存于通用寄存器中，因此主存并不是满负荷工作的。设置指缓就可乘主存有空时并不是满负荷工作的。设置指缓就可乘主存有空时，预取下一条或下几条指令存于指缓中。这样，预取下一条或下几条指令存于指缓中。这样，“分析分析k”与与“取指取指k+1”就能重叠了。就能重叠了。 这种指令分析部件和指令执行部件任何时候都只有这种指令分析部件和指令执行部件任何时候都只有相邻两条指

7、令在重叠解释的方式为相邻两条指令在重叠解释的方式为“一次重叠一次重叠”。3.1 重叠方式重叠方式n 一次重叠工作方式：如果每次都可以从指缓中取得指一次重叠工作方式：如果每次都可以从指缓中取得指令，则令，则“取指取指k+1”的时间很短，就可把这个微操作合的时间很短，就可把这个微操作合并到并到“分析分析k+1”内，从而由原先的内，从而由原先的“取指取指k+2”、“分分析析k+1”、“执行执行k”重叠变成只是重叠变成只是“分析分析k+1”与与“执行执行k”的重叠，如图所示。的重叠，如图所示。 3.1 重叠方式重叠方式n2. 要解决要解决“分析分析”与与“执行执行”操作的并行。操作的并行。 为了实现为

8、了实现 “执行执行k”与与“分析分析k+1”一次重叠，一次重叠，硬件硬件上还应有独立的指令分析部件和指令执行部件上还应有独立的指令分析部件和指令执行部件。以。以加法器为例，分析部件要有单独的地址加法器用于加法器为例，分析部件要有单独的地址加法器用于地址计算，执行部件也要有单独的加法器完成操作地址计算，执行部件也要有单独的加法器完成操作数的相加运算。这是以增加某些硬件为代价的。数的相加运算。这是以增加某些硬件为代价的。3.1 重叠方式重叠方式n3. 要解决要解决“分析分析”与与“执行执行”操作控制上的操作控制上的同步。同步。n实际上实际上“分析分析”和和“执行执行”所需的时间常不相同所需的时间常

9、不相同，还需在硬件上解决控制上的同步，保证任何时还需在硬件上解决控制上的同步，保证任何时候都只是候都只是“执行执行k”与与“分析分析k+1”重叠。重叠。n就是说，即使就是说，即使“分析分析k+1”比比“执行执行k”提前结束，提前结束，“执行执行k+1”也不紧接在也不紧接在“分析分析k+1”之后与之后与“执行执行k”重叠重叠进行；同样，即使进行；同样，即使“执行执行k”比比“分析分析k+1”提前结提前结束，束，“分析分析k+2”也不紧接在也不紧接在“执行执行k”之后与之后与“分分析析k+1”重叠进行。重叠进行。n4. 要解决指令间各种相关的处理。要解决指令间各种相关的处理。3.1 重叠方式重叠方

10、式n5.1.2 相关处理相关处理1. 转移指令的处理转移指令的处理 2. 主存空间数相关的处理主存空间数相关的处理3. 指令相关的处理指令相关的处理 4. 通用寄存器组相关的处理通用寄存器组相关的处理3.1 重叠方式重叠方式n1. 转移指令的处理转移指令的处理n如：第如：第k条指令是按其执行结果进行转移的条指令是按其执行结果进行转移的条件转移指令，若成功则转移到条件转移指令，若成功则转移到m单元。单元。3.1 重叠方式重叠方式n转移指令的处理：通过转移指令的处理：通过延迟转移技术延迟转移技术来解决来解决由编译程序生成目标程序时，将转移指令与由编译程序生成目标程序时，将转移指令与条件转移无关的第

11、条件转移无关的第k-1k-1条指令交换一下位置，条指令交换一下位置，这样，即使条件转移成功也不会使重叠效率下这样，即使条件转移成功也不会使重叠效率下降。降。3.1 重叠方式重叠方式当第k条指令是条件转移且转移成功时，传统做法与延迟转移做法的比较 3.1 重叠方式重叠方式n2. 2. 主存空间数相关的处理：主存空间数相关的处理：n推后推后“分析分析k+1”的读的读主存空间数相关是相邻两条指令之间出现对主存同主存空间数相关是相邻两条指令之间出现对主存同一单元要求先写而后读的关联一单元要求先写而后读的关联，如图所示。，如图所示。 如果让如果让“执行执行k k”与与“分析分析k k+1+1”在时间上重

12、叠，就会使在时间上重叠，就会使“分析分析k k+1+1”读出的数不是第读出的数不是第k k条指令执行完应写入的结条指令执行完应写入的结果而出错。要想不出错，只有果而出错。要想不出错，只有推后推后“分析分析k+1”的读的读。 3.1 重叠方式重叠方式主存空间数相关的处理(a)主存数相关的时间关系;(b)由存控推后“分析k+1”的读 3.1 重叠方式重叠方式n 3. 3.指令相关的处理指令相关的处理n如果采用机器指令可修改的办法经第如果采用机器指令可修改的办法经第k条指令的执条指令的执行来形成第行来形成第k+1条指令条指令n由于在由于在“执行执行k”的末尾才形成第的末尾才形成第k+1条指令，按照条

13、指令，按照一次重叠的时间关系，一次重叠的时间关系，“分析分析k+1”所分析的是早已所分析的是早已取进指缓的第取进指缓的第k+1条指令的旧内容，这就会出错。条指令的旧内容，这就会出错。为了避免出错，第为了避免出错，第k、k+1条指令就不能同时解释，条指令就不能同时解释，我们称此时这两条指令之间发生了我们称此时这两条指令之间发生了“指令相关指令相关”。3.1 重叠方式重叠方式n解决方案：解决方案：如果规定在程序运行过程中不准修改指令，指令相关如果规定在程序运行过程中不准修改指令，指令相关就不可能发生。就不可能发生。不准修改指令还可以实现程序的可再不准修改指令还可以实现程序的可再入和程序的递归调用。

14、入和程序的递归调用。为满足程序设计灵活性的需要，在程序运行过程中有为满足程序设计灵活性的需要，在程序运行过程中有时希望修改指令，这时可设置一条时希望修改指令，这时可设置一条“执行执行”指令来解指令来解决决。 3.1 重叠方式重叠方式n“执行执行”指令最初是研制指令最初是研制IBM370IBM370机时专门设计的，其机时专门设计的，其形式为形式为执行R1X2B2D20 8 12 16 20 31当 执 行 到当 执 行 到 “ 执 行执 行 ” 指 令 时 ， 按 第 二 操 作 数指 令 时 ， 按 第 二 操 作 数 ( (X X2 2)+()+(B B2 2)+)+D D2 2地址取出操作

15、数区中单元的地址取出操作数区中单元的内容作为指内容作为指令来执行令来执行，见图。，见图。 所执行的指令的第所执行的指令的第8 81515位可与位可与( (R R1 1)24)243131位内位内容进行逻辑或，以进一步提高指令修改的灵活性。容进行逻辑或，以进一步提高指令修改的灵活性。3.1 重叠方式重叠方式 IBM370“执行”指令的执行 由于被修改的指令是以“执行”指令的操作数形式出现的，将将指令相关转化成了指令相关转化成了数相关，只需统一数相关，只需统一按数按数相关处理即可相关处理即可。3.1 重叠方式重叠方式n4.通用寄存器组数相关的处理通用寄存器组数相关的处理 一般的机器中，通用寄存器除

16、了放一般的机器中，通用寄存器除了放源操作数、运算源操作数、运算结果外，结果外，也可能放形成访存操作数物理地址的也可能放形成访存操作数物理地址的变址变址值或基址值值或基址值，因此，通用寄存器组的相关又分为：，因此，通用寄存器组的相关又分为：操作数的相关操作数的相关变址值变址值/ /基址值的相关基址值的相关3.1 重叠方式重叠方式设机器的基本指令格式为 操作码L1L3B2d2或 操作码L1L3L2L L1 1、L L3 3分别指明存放分别指明存放第一操作数第一操作数和和结果数的通用结果数的通用寄存器寄存器号，号，B B2 2为形成第二操作数地址的基址值为形成第二操作数地址的基址值所所在通用寄存器号

17、，在通用寄存器号，d d2 2为相对位移量为相对位移量。3.1 重叠方式重叠方式n在指令解释过程中，使用通用寄存器作不同用途所需微在指令解释过程中，使用通用寄存器作不同用途所需微操作的时间是不同的。下图操作的时间是不同的。下图示意出它们的时间关系。示意出它们的时间关系。 基址值或变址基址值或变址值一般是在“分析”周期的前半段取用前半段取用； 操作数操作数是在“分析”周期的后半段取出后半段取出，到“执行”周期的前半段才用； 运算结果是在运算结果是在“执行执行”周期末尾形成并存入通用寄存器中周期末尾形成并存入通用寄存器中。 正因为时间关系不同，所以通用寄存器的数相关和基址值或正因为时间关系不同，所

18、以通用寄存器的数相关和基址值或变址值相关的处理方法不同。变址值相关的处理方法不同。 3.1 重叠方式重叠方式 （1）通用寄存器组数相关的处理。）通用寄存器组数相关的处理。 假设正常情况下，假设正常情况下，“分析分析”和和“执行执行”的周期与主存周期一的周期与主存周期一样都是样都是4 4拍拍。“执行执行k k”与与“分析分析k k+1+1”访问通用寄存器组的时间访问通用寄存器组的时间关系如图。关系如图。 当程序执行过程中出现了当程序执行过程中出现了L L1(1(k k+1)+1)= =L L3 3( (k k) )时就发生了时就发生了L L1 1相关，而相关，而当当L L2 2( (k k+1)

19、=+1)=L L3(3(k k) )时就发生了时就发生了L L2 2相关。相关。 一旦发生相关，如果仍一旦发生相关，如果仍维持让维持让“执行执行k k”和和“分分析析k k+1+1”一次重叠，从图一次重叠，从图中的时间关系可以看出，中的时间关系可以看出，“分析分析k k+1+1”取来的取来的( (L L1 1) )或或( (L L2 2) )并不是并不是“执行执行k k”的的真正结果，从而会出错。真正结果，从而会出错。 3.1 重叠方式重叠方式n通用寄存器组数相关通用寄存器组数相关解决办法：推后读，解决办法：推后读，增设增设“相关专相关专用通路用通路”n一种办法是靠推后读。一种办法是靠推后读。

20、 可以与前述处理主存空间数相关的一样，推后可以与前述处理主存空间数相关的一样，推后 “分析分析k k+1+1”到到“执行执行k k”结束时开始。结束时开始。一次重叠变成了完全的顺序一次重叠变成了完全的顺序串行。串行。 推后推后 “分析分析k+1使使“分析分析k k+1+1”在取在取( (L L1 1) )或或( (L L2 2) )时能取到即时能取到即可。相邻两条指令的解释仍有部分重叠，可以减少速度可。相邻两条指令的解释仍有部分重叠，可以减少速度损失，但控制要复杂一些。损失，但控制要复杂一些。 这两种办法都是靠推后读，牺牲速度来避免相关时出这两种办法都是靠推后读，牺牲速度来避免相关时出错。错。

21、3.1 重叠方式重叠方式n增设增设“相关专用通路相关专用通路”n在运算器的输出到在运算器的输出到B或或C输输入之间入之间增设增设“相关专用通相关专用通路路”，如图，则在发生，如图，则在发生L1或或L2相关时，接通相应的相关时，接通相应的相关专用通路，相关专用通路，“执行执行k”时就可以在将运算结果送时就可以在将运算结果送入通用寄存器完成其应有入通用寄存器完成其应有的功能的同时，直接将运的功能的同时，直接将运算结果回送到算结果回送到B或或C寄存寄存器。器。3.1 重叠方式重叠方式尽管原先将通用寄存器的旧内容经数据总线分别在尽管原先将通用寄存器的旧内容经数据总线分别在“分分析析k+1”的第的第3拍

22、或第拍或第4拍末送入了操作数寄存器拍末送入了操作数寄存器B或或C中，但中，但之后经相关专用通路在之后经相关专用通路在“执行执行k+1”真正用它之前，操作数真正用它之前，操作数寄存器寄存器B或或C重新获得第重新获得第k条指令送来的新结果。条指令送来的新结果。 这样，既保证相关时不用推后这样，既保证相关时不用推后“分析分析k+1”，重叠效率不，重叠效率不下降，又可以保证指令重叠解释时数据不出错。下降，又可以保证指令重叠解释时数据不出错。 推后推后“分析分析k k+1+1”和设置和设置“相关专用通路相关专用通路”是解决重叠方式是解决重叠方式相关处理的两种基本方法。前者是以降低速度为代价，相关处理的两

23、种基本方法。前者是以降低速度为代价，使设备基本上不增加。后者是以增加设备为代价，使重使设备基本上不增加。后者是以增加设备为代价，使重叠效率不下降。叠效率不下降。3.1 重叠方式重叠方式n（2）通用寄存器组基址值）通用寄存器组基址值(或变址值或变址值)相关的处理。相关的处理。n一次相关和二次相关的问题：基址值相关一次相关和二次相关的问题：基址值相关(B相关相关)就不止会出现一次相关，还会出现二次相关。如图就不止会出现一次相关，还会出现二次相关。如图3.1 重叠方式重叠方式在在“执行执行k”得到的、送入通用寄存器的运算结果是来得到的、送入通用寄存器的运算结果是来不及为不及为“分析分析k+2”作基址

24、值用，更不用说为作基址值用，更不用说为“分析分析k+1”作基址值用。作基址值用。 即即B(k+1)=L3(k)时发生时发生B一次相关一次相关,B(k+2)=L3(k)时发生时发生B二次相关。二次相关。 这里所谓的一次和二次指的是相关指令相隔的指这里所谓的一次和二次指的是相关指令相隔的指令条数令条数3.1 重叠方式重叠方式n通用寄存器组基址值相关的处理解决方法通用寄存器组基址值相关的处理解决方法推后分析推后分析设置相关专用通路设置相关专用通路3.1 重叠方式重叠方式B一次与二次相关的推后处理(a)B二次相关的推后处理；(b)B一次相关的推后处理 推后处理推后处理3.1 重叠方式重叠方式B相关专用

25、通路法 设置相关专用通路设置相关专用通路3.1 重叠方式重叠方式n 要实现两条指令在时间上重叠解释的代价要实现两条指令在时间上重叠解释的代价 首先要付出空间的代价：增设数据总线、控制总首先要付出空间的代价：增设数据总线、控制总线、指令缓冲器、地址加法器、相关专用通路，将分线、指令缓冲器、地址加法器、相关专用通路，将分析部件和指令执行部件功能分开、单独设置，主存采析部件和指令执行部件功能分开、单独设置，主存采用多体交叉存取等。用多体交叉存取等。 其次，要处理好指令之间可能其次，要处理好指令之间可能 存在的关联。如转存在的关联。如转移处理、指令相关、主存空间数相关、通用寄存器组移处理、指令相关、主

26、存空间数相关、通用寄存器组数相关和基址值或变址值相关的处理。数相关和基址值或变址值相关的处理。第第3章章 流水线技术流水线技术n3.2 流水线的基本概念流水线的基本概念n3.2.1 什么是流水线什么是流水线n工业生产流水线工业生产流水线n流水线技术流水线技术n把一个重复的过程分解为若干个子过程，每个把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。子过程由专门的功能部件来实现。n把多个处理过程在时间上错开，依次通过各功把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其它的子过能段，这样，每个子过程就可以与其它的子过程并行进行。程并行进行。n流水线中的每

27、个子过程及其功能部件称为流水线中的每个子过程及其功能部件称为流水流水线的级或段线的级或段，段与段相互连接形成流水线。流，段与段相互连接形成流水线。流水线的段数称为水线的段数称为流水线的深度。流水线的深度。3.2 流水线的基本概念流水线的基本概念n指令流水线指令流水线n把指令的解释过程分解为把指令的解释过程分解为分析分析和和执行执行两个子过程，两个子过程，并让这两个子过程分别用独立的分析部件和执行并让这两个子过程分别用独立的分析部件和执行部件来实现。部件来实现。理想情况：理想情况：速度提高一倍速度提高一倍n4 4段指令流水线段指令流水线 取指令取指令 译译 码码 执执 行行 存结果存结果 入入

28、出出 流水与重叠在概念上没有什么差别，可以看成是重叠的引申。差别只在于“一次重叠”是把一条指令分为两个子过程，而流水是分为更多个子过程。前者同时解释两条指令，后者可同时多条指令。3.2 流水线的基本概念流水线的基本概念n浮点加法流水线浮点加法流水线n把流水线技术应用于运算的执行过程，就把流水线技术应用于运算的执行过程，就形成了形成了运算操作流水线，运算操作流水线，也称为也称为部件级流部件级流水线。水线。n把浮点加法的全过程分解为把浮点加法的全过程分解为求阶差、对阶、求阶差、对阶、尾数相加、规格化尾数相加、规格化四个子过程。四个子过程。 理想情况：理想情况：速度提高速度提高3 3倍倍 求阶差求阶

29、差 对对 阶阶 尾数相加尾数相加 规格化规格化 t t t t 入入 出出 3.2 流水线的基本概念流水线的基本概念n时空图时空图n时空图从时空图从时间时间和和空间空间两个方面描述了流水两个方面描述了流水线的工作过程。时空图中，横坐标代表时线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。间，纵坐标代表流水线的各个段。 n浮点加法流水线的时空图浮点加法流水线的时空图 尾数相加尾数相加 规格化规格化 对对 阶阶 求阶差求阶差 空间空间 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3 3 4 4 1 1 2 2 3

30、 3 4 4 5 5 6 6 7 7 t tn n- -1 1 t tn n 时间时间 n n n n n n n n 0 0 t tn n+1 t tn n+3 t tn+2n+2 通过时间通过时间 排空时间排空时间 3.2 流水线的基本概念流水线的基本概念n流水技术的特点流水技术的特点n流水线把一个处理过程分解为若干个子过程流水线把一个处理过程分解为若干个子过程（段），每个子过程由一个专门的功能部件来实（段），每个子过程由一个专门的功能部件来实现。现。n流水线中各段的时间应尽可能相等，否则将引起流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。流水线堵塞、断流。 时间最长的段将成

31、为时间最长的段将成为流水线的瓶颈。流水线的瓶颈。n流水线每一个段的后面都要有一个缓冲寄存器流水线每一个段的后面都要有一个缓冲寄存器（锁存器），称为（锁存器），称为流水寄存器。流水寄存器。n作用：作用：在相邻的两段之间传送数据，以保证提供在相邻的两段之间传送数据，以保证提供后面要用到的信息，并把各段的处理工作相互隔后面要用到的信息，并把各段的处理工作相互隔离。离。3.2 流水线的基本概念流水线的基本概念n流水技术适合于大量重复的时序过程，只有流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流在输入端不断地提供任务，才能充分发挥流水线的效率。水线的效率。n 流水线需要有流

32、水线需要有通过时间和排空时间通过时间和排空时间。n通过时间：通过时间：第一个任务从进入流水线到流出结果第一个任务从进入流水线到流出结果 所需的时间。所需的时间。n排空时间：排空时间：最后一个任务从进入流水线到流出结最后一个任务从进入流水线到流出结 果所需的时间。果所需的时间。3.2 流水线的基本概念流水线的基本概念n3.2.2 流水线的分类流水线的分类从不同的角度和观点，把流水线分成多种不同的种类。从不同的角度和观点，把流水线分成多种不同的种类。1.部件级、处理机级及处理机间流水线部件级、处理机级及处理机间流水线（按照流水技术用于计算机系统的等级不同）（按照流水技术用于计算机系统的等级不同）n

33、部件级流水线部件级流水线（运算操作流水线）：把处理机中的部（运算操作流水线）：把处理机中的部件分段，再把这些分段相互连接起来，使得各种类型件分段，再把这些分段相互连接起来，使得各种类型的运算操作能够按流水方式进行。的运算操作能够按流水方式进行。n处理机级流水线处理机级流水线（指令流水线）：把指令的执行过程（指令流水线）：把指令的执行过程按照流水方式处理。把一条指令的执行过程分解为若按照流水方式处理。把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。干个子过程，每个子过程在独立的功能部件中执行。 3.2 流水线的基本概念流水线的基本概念n系统级流水线系统级流水线（宏流水线

34、）：把多台处理（宏流水线）：把多台处理机串行连接起来，对同一数据流进行处理，机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。每个处理机完成整个任务中的一部分。 数据流数据流 处理机处理机 1 处理机处理机 2 处理机处理机 n 存储器存储器 存储器存储器 存储器存储器 任务任务 1 任务任务 2 任务任务 n 3.2 流水线的基本概念流水线的基本概念2.单功能流水线与多功能流水线单功能流水线与多功能流水线 （按照流水线所完成的功能来分类）（按照流水线所完成的功能来分类）n单功能流水线：单功能流水线：只能完成一种固定功能的只能完成一种固定功能的流水线。流水线。n多功能流水

35、线：多功能流水线：流水线的各段可以进行不流水线的各段可以进行不同的连接，以实现不同的功能。同的连接，以实现不同的功能。例：例： ASCASC的多功能流水线的多功能流水线（当要进行浮点加、减时，连接成图（当要进行浮点加、减时，连接成图（b）所示的形式，）所示的形式，当要进行定点乘法运算时，连接成图（当要进行定点乘法运算时，连接成图（c）所示的形）所示的形式。除此之外，它还可以有数十种其他不同的连接，式。除此之外，它还可以有数十种其他不同的连接，可实现多种其他功能。）可实现多种其他功能。）3.2 流水线的基本概念流水线的基本概念 求求 阶阶 差差 对对 阶阶 相相 加加 规规格格化化 相相 乘乘

36、累累 加加 输输 出出 1 2 3 4 6 5 7 8 输输 入入 输输 入入 相相 加加 规规格格化化 输输 出出 输输 出出 累累 加加 相相 乘乘 输输 入入 求求 阶阶 差差 对对 阶阶 2 3 4 5 6 7 8 6 7 8 （b）浮浮点点连连接接 （a）分分段段 （c）定定乘乘连连接接 1 1 2 3 4 5 3.2 流水线的基本概念流水线的基本概念3.静态流水线与动态流水线静态流水线与动态流水线（按多功能流水线的各段能否允许同时用于多种不同功能连接（按多功能流水线的各段能否允许同时用于多种不同功能连接流水分）流水分）n静态流水线：静态流水线：在同一时间内，多功能流水在同一时间内，

37、多功能流水线中的各段只能按同一种功能的连接方式线中的各段只能按同一种功能的连接方式工作。工作。n对于静态流水线来说，只有当输入的是一串相同对于静态流水线来说，只有当输入的是一串相同的运算任务时，流水的效率才能得到充分的发挥。的运算任务时，流水的效率才能得到充分的发挥。例如：例如：ASCASC的的8 8段流水线段流水线3.2 流水线的基本概念流水线的基本概念n动态流水线：动态流水线：在同一时间内，多功能流水在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同线中的各段可以按照不同的方式连接，同时执行多种功能。时执行多种功能。 n优点优点 灵活，能够提高流水线各段的使用率，从灵活，能够提高

38、流水线各段的使用率，从而提高处理速度。而提高处理速度。n缺点缺点 控制复杂。控制复杂。n静、动态流水线时空图的对比静、动态流水线时空图的对比3.2 流水线的基本概念流水线的基本概念3.2 流水线的基本概念流水线的基本概念4.线性流水线与非线性流水线线性流水线与非线性流水线（按照流水线中是否有反馈回路来进行分类）（按照流水线中是否有反馈回路来进行分类）n线性流水线：线性流水线：流水线的各段串行连接，没流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。每一个段最多只流过一次。n非线性流水线：非线性流水线：流水线中除了有串行的

39、连流水线中除了有串行的连接外，还有反馈回路。接外，还有反馈回路。 n非线性流水线的非线性流水线的调度问题调度问题n确定什么时候向流水线引进新的任务，才能使该确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突任务不会与先前进入流水线的任务发生冲突争用流水段。争用流水段。 3.2 流水线的基本概念流水线的基本概念3.2 流水线的基本概念流水线的基本概念5.顺序流水线与乱序流水线顺序流水线与乱序流水线（根据任务流入和流出的顺序是否相同来进行分类（根据任务流入和流出的顺序是否相同来进行分类）n顺序流水线：顺序流水线：流水线输出端任务流出的顺流水线输出端任务流出的顺序与输入

40、端任务流入的顺序完全相同。每序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中是一个跟着一一个任务在流水线的各段中是一个跟着一个顺序流动的。个顺序流动的。n乱序流水线：乱序流水线：流水线输出端任务流出的顺流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同，允序与输入端任务流入的顺序可以不同，允许后进入流水线的任务先完成（从输出端许后进入流水线的任务先完成（从输出端流出）。流出）。 也称为无序流水线、错序流水线、异步流水线也称为无序流水线、错序流水线、异步流水线3.2 流水线的基本概念流水线的基本概念6.标量处理机与向量流水处理机标量处理机与向量流水处理机 n把指令执行部件中采用

41、了流水线的处理机把指令执行部件中采用了流水线的处理机称为称为流水线处理机。流水线处理机。n标量处理机：标量处理机：处理机不具有向量数据表示处理机不具有向量数据表示和向量指令，仅对标量数据进行流水处理。和向量指令，仅对标量数据进行流水处理。n向量流水处理机：向量流水处理机：具有向量数据表示和向具有向量数据表示和向量指令的处理机。量指令的处理机。 向量数据表示和流水技术的结合。向量数据表示和流水技术的结合。第第3章章 流水线技术流水线技术n3.3 流水线的性能指标流水线的性能指标n吞吐率吞吐率n流水线的加速比流水线的加速比n流水线的效率流水线的效率3.3 流水线的性能指标流水线的性能指标n3.3.

42、1 吞吐率吞吐率吞吐率：吞吐率：在单位时间内流水线所完成的任务在单位时间内流水线所完成的任务数量或输出结果的数量。数量或输出结果的数量。kTnTP n：任务数Tk：处理完成n个任务所用的时间3.3 流水线的性能指标流水线的性能指标n各段时间均相等的流水线各段时间均相等的流水线n各段时间均相等的流水线各段时间均相等的流水线时空图时空图 S1 S2 S3 S4 空间空间 时间时间 1 （单位：单位：t） 1 1 1 2 2 2 2 3 3 3 3 n-1 n-1 n-1 n-1 n n n n kt (n-1)t Tk 3.3 流水线的性能指标流水线的性能指标n流水线完成流水线完成n个连续任务所需

43、要的总时间为：个连续任务所需要的总时间为：（假设一条（假设一条k k段段线性流水线）线性流水线）T Tk kktkt(n(n1)t1)t(k(kn n1)t1)t n流水线的流水线的实际吞吐率实际吞吐率tnknTP) 1(ttnknTPn11limmax最大吞吐率最大吞吐率3.3 流水线的性能指标流水线的性能指标n最大吞吐率与实际吞吐率的关系最大吞吐率与实际吞吐率的关系 max1TPnknTPq流水线的实际吞吐率小于最大吞吐率，它流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线除了与每个段的时间有关外，还与流水线的段数的段数k k以及输入到流水线中的任务数以及输入到流水

44、线中的任务数n n等等有关。有关。q只有当只有当nknk时，才有时，才有TPTPTPTPmaxmax。 3.3 流水线的性能指标流水线的性能指标2.各段时间不完全相等的流水线各段时间不完全相等的流水线 n各段时间不等的流水线及其时空图各段时间不等的流水线及其时空图 举例举例1（时空图时空图）n一条一条4 4段段的流水线的流水线nS1S1，S3S3，S4S4各段的时间：各段的时间：ttnS2S2的时间：的时间：3t 3t （瓶颈段）瓶颈段）流水线中这种时间最长的段称为流水线的流水线中这种时间最长的段称为流水线的瓶颈段。瓶颈段。 3.3 流水线的性能指标流水线的性能指标3.3 流水线的性能指标流水

45、线的性能指标举例举例2：一条一条5 5段段的流水线的流水线nS S1 1，S S2 2，S S3 3，S S5 5各段的时间：各段的时间：ttnS S4 4的时间：的时间：3t 3t （瓶颈段）瓶颈段） 段段 t t1 1= =t t 入入 出出 S S1 1 t t2 2= =t t S S2 2 t t3 3= =t t S S3 3 t t4 4=3=3t t S S4 4 t t5 5= =t t S S5 5 （a a）流水线）流水线 S S1 1 S S2 2 S S3 3 S S4 4 S S5 5 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3

46、3 3 3 3 3 3 3 3 n n 2 2 n n n n n n n n 时间时间 ti i=1 5 （n1）t4 （b b）时空图）时空图 3.3 流水线的性能指标流水线的性能指标n各段时间不等的流水线的各段时间不等的流水线的实际吞吐率实际吞吐率为：为：（ tti i为第为第i i段的时间，共有段的时间，共有k k个段个段 ）kikitttntnTP121),max() 1(流水线的流水线的最大吞吐率最大吞吐率为：为： ),max(121maxktttTP对前面举例对前面举例2中的中的5段流水线段流水线最大吞吐率为：最大吞吐率为： tTP31max3.3 流水线的性能指标流水线的性能指

47、标3.3.解决流水线瓶颈问题的常用方法解决流水线瓶颈问题的常用方法n细分瓶颈段细分瓶颈段 例如：例如：对前面的对前面的5 5段段流水线流水线把瓶颈段把瓶颈段S S4 4细分为细分为3 3个子流水线段：个子流水线段：S S4-14-1，S S4-24-2，S S4-34-3改进后的流水线的吞吐率改进后的流水线的吞吐率 ：tTP1max t t 入入 S S1 1 t t S S2 2 t t S S3 3 t t S S4 4- -1 1 t t S S4 4- -2 2 出出 t t S S4 4- -3 3 t t S S5 5 3.3 流水线的性能指标流水线的性能指标n重复设置瓶颈段重复设

48、置瓶颈段n举例：举例：时时- -空图空图n缺点：缺点：控制逻辑比较复杂，所需的硬件增加了。控制逻辑比较复杂，所需的硬件增加了。例如：例如：对前面的对前面的5 5段流水线段流水线 重复设置瓶颈段重复设置瓶颈段S S4 4：S S4a4a，S S4b4b，S S4c4c t t1 1= =t t 入入 出出 S S1 1 t t2 2= =t t S S2 2 t t3 3= =t t S S3 3 t t4 4=3=3t t S S4b4b t t5 5= =t t S S5 5 S S4a4a S S4c4c 3.3 流水线的性能指标流水线的性能指标 段段 S S1 1 S S2 2 S S3

49、 3 S S4a4a S S4b4b 1 1 1 1 1 1 1 1 1 1 2 2 2 2 4 4 2 2 3 3 3 3 3 3 7 7 3 3 n n 2 2 n n n n n n n- -2 2 时间时间 S S4c4c S S5 5 2 2 5 5 8 8 3 3 6 6 9 9 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 n n- -1 1 n n- -2 2 n n n n- -1 1 重复设置瓶颈段后的时空图重复设置瓶颈段后的时空图3

50、.3 流水线的性能指标流水线的性能指标n3.3.2 流水线的加速比流水线的加速比加速比：加速比：完成同样一批任务，不使用流水线所用的时完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比。间与使用流水线所用的时间之比。假设：不使用流水线（即顺序执行）所用的时假设：不使用流水线（即顺序执行）所用的时间为间为T Ts s，使用流水线后所用的时间为，使用流水线后所用的时间为T Tk k，则该，则该流水线的加速比为：流水线的加速比为：ksTTS 3.3 流水线的性能指标流水线的性能指标n流水线各段时间相等（都是流水线各段时间相等（都是t t）n一条一条k k段流水线完成段流水线完成n n

51、个连续任务个连续任务 所需要的时间为：所需要的时间为： Tk = (kn1)tn顺序执行顺序执行n n个个任务任务 所需要的时间：所需要的时间： Ts= nktn流水线的实际加速比为：流水线的实际加速比为：1nknkS3.3 流水线的性能指标流水线的性能指标n最大加速比最大加速比knknkSn1limmax当当nknk时，时，S S k k思考：思考：流水线的段数愈多愈好？流水线的段数愈多愈好？ 3.3 流水线的性能指标流水线的性能指标2.流水线的各段时间不完全相等时流水线的各段时间不完全相等时n一条一条k k段流水线完成段流水线完成n n个连续任务的实际加速比为：个连续任务的实际加速比为：

52、kikikiitttnttnS1211),max() 1(3.3 流水线的性能指标流水线的性能指标n3.3.3 流水线的效率流水线的效率 流水线的效率：流水线的效率：流水线中的设备实际使用时间与整个流水线中的设备实际使用时间与整个运行时间的比值，即流水线设备的利用率。运行时间的比值，即流水线设备的利用率。 由于流水线有通过时间和排空时间，所以在连由于流水线有通过时间和排空时间，所以在连续完成续完成n n个个任务的时间内，各段并不是满负荷地任务的时间内，各段并不是满负荷地工作。工作。1.各段时间相等各段时间相等n各段的效率各段的效率e ei i相同相同121nknTtneeekk3.3 流水线的

53、性能指标流水线的性能指标n整条流水线的效率为：整条流水线的效率为：kkkTtknkkekeeeE1211nknE11limmaxnknEn式中，分母式中，分母kTk是时空图中是时空图中k个段和流水总时间个段和流水总时间Tk所围成的所围成的面积，分子面积，分子knt是时空图中是时空图中n个任务实际使用的面积。因个任务实际使用的面积。因此，从时空图上看，效率实际上就是此，从时空图上看，效率实际上就是n个任务占用的时空区个任务占用的时空区面积和面积和k个段总的时空区面积之比。个段总的时空区面积之比。 可以写成：可以写成： 最高效率为：最高效率为： 当当nknk时，时，E1E1。 3.3 流水线的性能

54、指标流水线的性能指标n当流水线各段时间相等时，流水线的效率与吞吐当流水线各段时间相等时，流水线的效率与吞吐率成正比。率成正比。 E=TPE=TPt t 2.2.流水线的效率流水线的效率是流水线的实际加速比是流水线的实际加速比S S与它的最大加与它的最大加速比速比k k的比值。的比值。 kSE 当当E=1E=1时，时，S=kS=k，实际加速比达到最大。，实际加速比达到最大。3.3 流水线的性能指标流水线的性能指标3.3.当各段时间不相等时：当各段时间不相等时：kikikiitttntktnE1211),max() 1(ktTPkii13.3 流水线的性能指标流水线的性能指标n3.3.4 流水线的

55、性能分析举例流水线的性能分析举例 例例3.13.1 设在下图所示的静态流水线上计算：设在下图所示的静态流水线上计算： 流水线的输出可以直接返回输入端或暂存于相应的流流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，试计算其吞吐率、加速比和效率。水寄存器中，试计算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘法乘法 加减法加减法 6 7 8 ( (每段的时间都为每段的时间都为t t) )3.3 流水线的性能指标流水线的性能指标解：解：（1 1）选择适合于流水线工作的算法）选择适合于流水线工作的算法n先计算先计算A A1 1+B+B1 1、A A2 2+B+B2 2、A

56、 A3 3+B+B3 3和和A A4 4+B+B4 4；n再计算再计算(A(A1 1+B+B1 1) )(A(A2 2+B+B2 2) )和和(A(A3 3+B+B3 3) )(A(A4 4+B+B4 4) )；n然后求总的乘积结果。然后求总的乘积结果。（2 2）画出时空图）画出时空图 3.3 流水线的性能指标流水线的性能指标 时间 段 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 输 入 A1 B1 A2 B2 A3 B3 A4 B4 A B C D A B C D AB CD AB CD ABCD A=A1+B

57、1 B=A2+B2 C=A3+B3 D=A4+B4 tTP18721836ttS25. 01884364E3.3 流水线的性能指标流水线的性能指标n可以看出，在求解此问题时，该流水线的效率不高。可以看出，在求解此问题时，该流水线的效率不高。 n主要原因主要原因n多功能流水线在做某一种运算时，总有一些段是多功能流水线在做某一种运算时，总有一些段是空闲的；空闲的；n静态流水线在进行功能切换时，要等前一种运算静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算；全部流出流水线后才能进行后面的运算；n运算之间存在关联，后面有些运算要用到前面运运算之间存在关联，后面有些运算要用到

58、前面运算的结果；算的结果；n流水线的工作过程有建立与排空部分。流水线的工作过程有建立与排空部分。 3.3 流水线的性能指标流水线的性能指标 例例3.2 3.2 有一条动态多功能流水线由有一条动态多功能流水线由5 5段组成，加法用段组成，加法用1 1、3 3、4 4、5 5段，乘法用段，乘法用1 1、2 2、5 5段，第段，第4 4段的时间为段的时间为2 2t t，其余各段时间均为其余各段时间均为t t，而且流水线的输出可以直接，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算水线上计算: : 试计算其吞吐率、加速比和

59、效率。试计算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘法乘法 加法加法 t t t 2t t 3.3 流水线的性能指标流水线的性能指标解解: (1) : (1) 选择适合于流水线工作的算法选择适合于流水线工作的算法p应先计算应先计算A A1 1B B1 1、A A2 2B B2 2、A A3 3B B3 3和和A A4 4B B4 4；p再计算再计算(A(A1 1B B1 1) )(A(A2 2B B2 2) ) (A (A3 3B B3 3) )(A(A4 4B B4 4) )；p然后求总的累加结果。然后求总的累加结果。(2) (2) 画出时空图画出时空图(3) (3

60、) 计算性能计算性能3.3 流水线的性能指标流水线的性能指标 时间 段 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 输 入 A1 B1 A2 B2 A3 B3 A4 B4 A B C D A B C D AB CD AB CD ABCD A=A1B1 B=A2B2 C=A3B3 D=A4B4 69. 16172ttStTP617383 . 01655334E3.3 流水线的性能指标流水线的性能指标n3.3.5 流水线设计中的若干问题流水线设计中的若干问题1.瓶颈问题瓶颈问题n理想情况下，流水线在工作时，其中的任务理想情况下，流水线在工作