标量流水线技术

第9章标量流水线技术本章首先介绍标量流水线的基本概念与工作原理，然后介绍流水线时空图与性能分析、流水线操作中的主要障碍与处理方法、非线性
流水线的调度策略以及实现流水线的控制方式。重点介绍流水线的时空图、流水线性能分析、非线性流水线与调度策略、流水线的实现与控制。第
9章标量流水线技术9.1概述9.2标量流水线9.3指令级流水线9.1概述传统的计算机是把程序存入计算机的
存储器中，然后逐条取出执行，是一个串行的过程。以后为了提高速度，人们希望能够有多条指令同时执行，于是产生了流水线和并行处理技术。本
章主要介绍标量流水线技术，它在执行一条指令的过程中启动下一条指令，力图使多条指令同时执行。于是，出现了一些新的概念。1．程序执行
过程中的重叠操作在计算机运行的过程中，经常存在不同设备、不同部件或者同一部件中的不同操作在时间上重叠的情况，例如，CPU与打印机
重叠，CPU与DMA数据传送重叠，取指令与执行指令重叠等。通过使用这些内在的重叠，可提高计算机运行的速度。流水线技术就是建立在这些
重叠操作的基础上的。目前就指令的解释与执行过程，有顺序、重叠和流水。图9.1顺序执行方式(9.1)1）顺序解释方式顺序解
释是最简单的解释方式，它是一条指令执行完后再取下一条。早期的计算机多采用这种方式。如果把指令的执行过程分为取指令、分析（译码）和执
行三个阶段，顺序执行过程如图9.1所示。若取指令、分析和执行指令所用时间相等，用t表示，则顺序执行n条指令所需要的时间T=3×n
×t。如果各部分所用的时间不同，则顺序执行n条指令所用的时间为：图9.2重叠执行方式2）重叠解释方式重叠解释方式是在两条相
邻指令的解释过程中，存在某些时段可以重叠进行，如图9.2所示。其中图9.2（a）是一次重叠方式，执行n条指令所用的时间为T=
(2n+1)t；图9.2（b）是二次重叠方式，执行n条指令所用的时间为T=3t+(n-1)t=(n+2)t。图9.3两段一
次重叠工作方式为了实现重叠解释，需要硬件支持，例如设置多个缓冲寄存器，存放从程序存储器中取出的指令，构成指令队列。设置程序存储器
和数据存储器，使程序与数据分别存储在不同的存储器中，这样在取指令时可读写操作数，支持指令重叠解释执行。由于指令可以提前取出，进入
指令队列等候执行，因此取指令和分析阶段可以合并，这样指令的解释过程可分为两个阶段，重叠解释过程如图9.3所示。如果“分析”和“执行
”的时间相同，那么解释执行n条指令的时间为T=(n+1)t2．先行控制在上述重叠解释方式中，假设“分析”和“执行”时间相等，如
图9.4（a）所示，这样解释执行n条指令的时间为：（9.2）图9.4分析与执行时间不相等和先行控制方式（9.3）如果“分析
”和“执行”时间不能，就会出现如图所示的“空闲”时间。为了解决重叠解释过程中的这种“空闲”，人们采用了先行控制技术，是使“分析”和
“执行”分别连续进行，如图9.4（b）所示。这时，执行n条指令所需要的时间为：为了实现“分析”和“执行”分别连续进行，最简单的办
法是把CPU按功能分为两部分，即总线接口部件和执行部件，并在总线接口部件与执行部件之间设置一个指令队列，例如8086微处理器采用的
就这种方式。这样，可在执行第k条指令时由总线接口部件预取第k+1、k+2甚至k+3条指令。图9.5先行控制逻辑由此可见，先行
控制技术实质上是预取处理技术和缓冲技术的结合，通过对指令流和数据流的先行控制，使指令分析器和执行部件尽量连续地工作。缓冲部件一般采
用先进先出寄存器，其个数称为缓冲深度。先行控制逻辑如图9.5所示，其中缓冲区的深度一般应满足以下关系：D取指栈≥D操作栈≥D读栈
≥D写栈图9.6流水过程示意图9.2标量流水线9.2.1标量流水线工作原理1．什么是标量流水线上述重叠解释执行
过程实际上是最简单的标量流水线。如果把指令的执行过程再细分为5个部分，如图9.6所示，有取指令（IF）、译码（ID）、计算有效地址
或执行（EX）、访问存储器（MEM）和结果写回目标寄存器（WB）。这5个部分分别由相应的硬件来实现，也称为5个子过程或状态，用Si
表示。这样，只要前一条指令完成第一个子过程，就可以读取下一条指令。这样，前面的指令一级一级地往后移动，后面的指令不断地流入，于是构
成标量流水线。图9.7流水线各段组成与时空图如果假设每个子过程所用时间相等，指令一条接着一条流入，经过5个子过程后从输出端流
出。用二维坐标表示，可构成如图9.7所示空间与时间之间的二维关系图，称为时空图。可以看出，在理想情况下，每经一个时钟周期指令向右移
动一格，新的指令从左边进入。4个时钟周期后，5个部件全部工作。其中前4个时钟周期称为填入阶段；以后填满，即正常工作阶段；最后，各条
指令一拍一拍地流出，称为排空阶段。若用m表示部件数或空间段数，整个时间可如图9.7所示分为两个部分。其中，m?t是第一条指令流出
的时间，也就是流出第一个结果的时间；在以后的(n?1)?t中，每一拍执行完一条指令，即流出一个结果。2．流水线的工作特点概括起
来，流水线的工作特点主要有以下4点：（1）一条流水线通常由多个流水段组成；（2）在每一个流水段有专门的功能部件，对指令进行某种
加工处理；（3）流水线的工作一般分为3个阶段，即建立（填入）、填满和排空；（4）在理想情况下，各流水段所需要的时间相等，流水
线填满后每隔时间?t就会有一个结果流出。9.2.2标量流水线分类采用流水线技术可有效地提高计算机的处理速度，因此得到广泛应
用。伴随着硬件和软件的发展，流水线技术已有多种类型。从不同的角度来看，有不同的分类方式。1．按照处理机制分类按照处理机制分类，
流水线可分为操作部件级、指令级和处理机级。操作部件级流水线是把复杂的运算过程分成几个阶段，构成流水线。例如，把浮点加法运算分解成求
阶差、对阶、尾数相加和结果规格化4个子过程，然后按照这4个过程构成流水线。指令级流水线是把一条指令的执行过程分成若干个子过程，按
照子过程构成流水线。例如，前面所说的取指令、译码、执行、访存和写回5个子过程。处理机流水线是一种宏流水过程，其中每一个处理机完成
某一个专门的任务，各处理机产生的结果需要存放到与下一个处理机共享的存储器中，以便传送给下一处理机，如图9.8所示。图9.8处理
机流水线2．按照功能分类按照构成流水线所用部件的功能，可把流水线分成单功能流水线和多功能流水线。单功能流水线是指所有设备或部件
按照一种模式工作，仅实现一种功能，例如，浮点加法流水线只完成浮点加法运算，定点乘法流水线只完成定点乘法运算。多功能流水线是指构成流
水线的部件可进行不同的组合，以实现在不同的时间完成不同的功能。如图9.9所示，是TI-ASC计算机的流水线结构，可构成多种流水线，
实现定点加、浮点加、定点乘和浮点向量点积等功能。图9.9多功能流水线的多种连接3．按照工作方式分类按照工作方式，流水线可分为
静态流水线和动态流水线。所谓静态流水线，是在同一时间内只能以一种方式工作。这种流水线的结构可以是单功能，也可以是多功能。对于多功能
结构，在同一时间内只能进行一种工作。在从一种功能转换到另一种功能时，流水线必须排空。显然，不希望这种流水线的功能频繁切换。动态流水
线允许在工作时将不同的功能段根据需要连接成不同的子流水线集，以完成不同的运算功能。显然，动态流水线必定是多功能流水线；单功能流水
线必定是静态流水线。4．按照连接方式分类按照连接方式，流水线可分为线性流水线和非线性流水线。所谓线性流水线，是从输入到输出各功
能部件只允许经过一次，也就是不存在反馈回路或者分支，一般流水线多属于这一类。非线性流水线是其中的某些功能部件可能被反复经过或者使用
，如图9.10所示。图9.10非线性流水线示意图在非线性流水线中，存在反馈操作与后续操作争用功能部件的现象，因此在控制上有更
高的要求，要处理非线性流水线功能段的使用冲突与调度。9.2.3流水线性能分析流水线技术已经得到广泛的使用，无论单独的微处理
器、大型处理机，还是多处理机系统，无一例外地都在使用流水线技术。因此，有必要对其性能进行分析，主要技术指标有三个，即吞吐率、效率和
加速比。（9.4）1．吞吐率Tp吞吐率是单位时间内处理机所能处理的任务数或者输出的结果数，分为最大吞吐率和实际吞吐率。1）最
大吞吐率若以?ti表示通过流水线各功能段所用的时间，那么在流水线稳定后可获得最大吞吐率：显然，?ti最大的一段将成为流水线的瓶
颈。如果通过各功能段的时间?ti相差不大，属于正常流水线；如果通过各功能段的时间?ti相差很大，则不是性能良好的流水线，需要采取一
定的措施，使各段的?ti趋于一致。2）流水线中的瓶颈如图9.11（a）所示，在这由4个功能段构成的流水线中通过第1、2、4段所
用时间为?t，通过第3段所用时间为3?t，时空图如图9.11（b）所示。显然，最大吞吐率将降为Tpmax=1/(3?t)。3）消
除瓶颈影响的方法为了消除瓶颈，可采取相应的措施，例如，把图9.11（a）中的第3段细分为3段，每段所用时间接近于?t，如图9.1
1（c）所示。这样，通过各子功能段的时间都趋于?t，可使6个任务依次进入流水线，使最大吞吐率保持为Tpmax=1/?t。也可采用空
间重复因素，增设2个第3段，使之并列工作，如图9.11（d）所示。这样，连续的3个任务可以分别通过S3a、S3b和S3c，时空图如
图9.11（e）所示。采取这些措施可在一定程度上减少流水线中因瓶颈而产生的吞吐率下降。图9.11带瓶颈流水线及其消除时空图（9
.5）4）实际吞吐率以上讨论的是流水线连续工作时所达到的最大吞吐率。实际上，如图9.7所示，任何一个流水线都存在填入和排空过
程，因此实际吞吐率总小于最大吞吐率。若设m为流水线中功能段的数量，从图9.7可以看出，完成n个任务所用的时间为：Tk=m?t+(n
?1)?t这样，实际吞吐率为：显然，当n＞＞m时，Tp→Tpmax。2．加速比Sp在流水线中，加速比是执行同一任务时不采用流
水线技术所用的时间与采用流水线技术所用的时间之比。对于n个任务，设有m段流水线，若不采用流水线，即串行执行，所用的时间为To，采用
流水线后使用的时间为Tk，则加速比为：（9.6）（9.7）显然，当n＞＞m时，Sp→m，即最大加速比。为了提高加速比，流水
线的段数m可尽量大一些，也就是增加流水线的深度。3．效率E效率是流水线中各功能段的时间利用率。由于流水线有填入和排空时间，因此
各功能段不能一直处于忙碌状态，故需用效率表示各功能段的时间利用率。它是指各功能段被实际利用的时空区面积与各功能段所提供的总的时空区
面积之比。如图9.7所示，效率：图9.12双功能静态流水线【例9.1】流水线性能分析。设有A、B两个向量，每个向量有4个元素
，要求在如图9.12所示的静态加、乘双功能流水线上计算，并求吞吐率、加速比和效率。解：在流水
线中，功能段S1、S2、S3、S4、S6构成乘法流水线，S1、S5、S6构成加法流水线。设经过每一个功能段的时间均为?t，流水线的
输出可直接返回到输入端或者暂存到缓冲寄存器中，流水线功能切换的时间忽略不计。这样，可让流水线先进行两个向量中4个元素的加法运算：(
a0+b0)、(a1+b1)、(a2+b2)、(a3+b3)，然后切换成乘法功能，按照[(a0+b0)×(a1+b1)]×[(a2
+b2)×(a3+b3)]的顺序进行乘法运算。其时空图如图9.13所示。图9.13流水线时空图举例从图中可以看出，在17?t
时间内输出了7个结果，因此实际吞吐率为：Tp=7/17?t如果顺序操作，需要进行4次加法运算和3次乘法运算。一次加法运算需要3?
t，一次乘法运算需要5?t，总共需要To=4×3?t+3×5?t=27?t这样加速比为：Sp=To/Tk=27?t/17?
t=1.88流水线的效率可用阴影面积除以全部6个状态段的总时空面积而求得：E=(3×4?t+5×3?t)/(6×17?t)=27
/102=26.4%9.2.4流水线中的主要障碍为了充分发挥流水线的作用，人们总是希望流水线畅通无阻，不出现断流。但是实际
上往往有这样或那样的原因使流水线不能畅通。概括起来有3种原因，也称为相关，即资源相关、数据相关和控制相关。下面仍以5个功能段（S1
～S5）流水线为例予以说明，即取指令（IF）、译码（ID）、有效地址计算或指令执行（EX）、访问存储器（MEM），以及结果写回（W
B）。对于不同的指令，在流过流水线时所完成的操作不同，因而对流水线的使用也不相同。下面以ALU类指令、传送类指令（LOAD和ST
ORE）和分支转移类指令（BRANCH）为例予以说明。1）ALU类指令ALU指令在S1取出，在S2译码，在S3执行，在S4不进
行任何操作，在S5结果写回目标寄存器。2）传送类指令LOAD和STORE传送类指令在S1取出，在S2译码及读寄存器，在S3计算
有效地址，在S4访问存储器。若是LOAD指令，在S4读存储器，在S5把读出的数据写回目标寄存器；若是STORE指令，仅在S4把数据
寄存器中的数据写入目标存储器单元中。3）分支转移类指令BRANCH分支转移类指令在S1取出，在S2译码并读寄存器，在S3生成
转移目标地址，并形成条件码，在S4判断条件是否成立。若成立，将转移地址送入程序计数器PC。在S5不进行任何操作。三类指令对各功能段
的占用如表9.1所示。表9.1三类指令对流水线的使用功能段(S)ALU指令LOAD/STOREBRANCHIF(S1)取指取指
取指ID(S2)译码，读寄存器堆译码，读寄存器堆译码，读寄存器堆EX(S3)执行计算有效地址计算转移目标地址，设置条件码MEM(S
4)－访存（读或写）若条件成立，将转移目标地址送PCWB(S5)结果写回寄存器堆读出数据写入寄存器堆－1．资源相关资源相关是当
多条指令进入流水线后，在同一时间争用同一功能部件而发生冲突。因此，也称为资源冲突或者结构冲突。如图9.14所示，有5条指令相继进入
流水线，其中第1条指令是存储器读LOAD。可以看出，在第4拍时第1条指令执行到MEM段，和第i+3条指令的IF段同时访问存储器。若
存储器只有一个输入/输出端口，显然冲突，即资源相关。图9.14两条指令同时访问存储器冲突只要发生资源冲突，流水线就不能正常工
作。最简单的办法是取第i+3条指令时暂停一拍，如图9.15所示。当然，如果能设置两个存储器分别存放数据和程序，这样存储器读与取指令
同时进行，可避免上述资源冲突。这是一种资源重复的解决办法。图9.15用停顿的方法解决存储器冲突2．数据相关1）数据相关数
据相关是由于流水线中各指令重叠执行，使得原来对操作数的访问顺序发生变化而引起的一种数据冲突。主要发生在两条指令执行中后一条指令所需
要的操作数正好是前一条指令执行的结果。例如，以下两条指令，执行过程如图9.16所示。ADDR1，R2，R3；R2+R3→R1
SUBR4，R1，R5；R1-R5→R4图9.16数据相关冲突SUB指令需要在第3拍使用前一条ADD指令的执行结果，而
ADD指令的结果要在第5拍才能写入寄存器R1中。对于流水线来说，两条指令重叠执行，后一条指令需要提前使用前一条指令的结果，即发生了
冲突，读超前于写（RAW）。当然，若顺序执行这两条指令，就不会发生。2）解决办法分析上述两条指令的执行过程，可以看出ADD指令
在第3拍时已经产生了结果。如果能及时把运算结果直接传送给SUB指令，就可以保证流水线正常进行。为此，可采用“定向传送”技术，也称为
旁路技术或相关专用通路技术。图9.17加法运算结果定向传送如图9.17所示，是由5条指令构成的一段程序，其中第一条指令ADD
向寄存器R1存入结果，后续的几条指令都以R1为源操作数。而ADD指令需要在WB段才能把结果写回R1，而后继指令中除了XOR之外都要
在此之前使用R1中的数据。若采用停顿法，将使流水线停顿3拍。而ADD指令在EX段就已经产生了运算结果，因此若能设置专门的通路将结果
直接传送给后续SUB、AND和OR指令的EX段，就会使流水线不发生停顿，如图9.17所示，称为定向传送。定向传送如图9.18（a
）所示，其实现如图9.18（b）所示，增加旁路。在ALU中的结果送往目标寄存器的同时（甚至之前），通过多路转换开关送往需要使用该结
果的ALU的输入端。在有些计算机中把时钟周期分为前后两个部分，即前半周期和后半周期。读操作一般在后半周期进行，写操作一般在前半周期
进行。这样，图9.17中指令OR的定向传送可以取消，如图9.19所示。图9.18旁路定向传送图9.19减少定向传送措施3
）数据相关的类型根据指令对同一寄存器读和写的先后顺序，数据冲突可分为三种类型，即RAW、WAR和WAW。（1）RAW：指令j试
图在指令i写入寄存器之前读取寄存器中的数据，这样指令j读出的就是原来的内容，简称为读超前于写。（2）WAR：指令j试图在指令i读
出寄存器中的数据之前写入寄存器，这样指令i读出的就是寄存器中的新内容，简称为写超前于读。（3）WAW：指令j试图在指令i写入寄存
器之前写入寄存器，这样两条指令的写入过程颠倒，简称为写超前于写。图9.20RISC机中的装入延迟在按序流动的流水线中出现的主
要是RAW相关，解决的办法就是采用上述定向传送技术；而在非按序流动的流水线中，允许后进入流水线的指令先流出流水线，这样三种类型的数
据相关都可能发生。4）装入延迟在RISC计算机中，访问存储器的时间一般长于寄存器的传送时间，因此在执行指令LOAD时常存在一定
的延迟，称为装入延迟。如图9.20所示，指令LOAD在MEM段（S4）才能把数据从存储器中读出，而指令ADD则在EX段就要使用该数
据。由于这种延迟是在访问存储器时产生的，很难在读出时用定向传送的方法来解决，而多采用停顿的方法，如图9.21所示。这一停顿称为流水
线装入延迟或者“空泡”。图9.21装入延迟引起的停顿但是在有些计算机中，没有采用这种硬件连锁的方法来解决，而是采用优化编译技
术，使指令重新排序，来消除这种空泡。3．控制相关1）控制相关控制相关也称为控制转移冲突，主要由转移类指令引起的。统计表明，在
一般程序中，转移指令约占总指令数目的1/4。因此与数据相关相比，它对流水线的影响大得多。图9.22控制相关引起的停顿当转移发
生时，流水线的连续性受到破坏。转移指令把转移目标地址送入程序计数器PC，或者在相对转移中使PC当前值加上一数值。由于一般要在MEM
段的末尾才能使程序计数器PC的值改变，于是常需要停顿3个时钟周期，如图9.22所示。下面举例说明。【例9.2】设在某一计算机中顺
序执行程序时1个时钟周期执行一条指令，设在一个程序中有25%的转移指令，其中2/3转移发生，转移成功时需要4个时钟周期，试计算执行
一条指令的平均时钟周期。解：设执行一条指令的平均时钟周期为Pi，则Pi=1×75%+1×25%×[1×1/3+2/3×(3+1
)]=1.5（周期）显然，使流水线的性能下降33.3%。2）减少控制相关对流水线性能影响的措施控制相关对流水线的影响只能减少
，而不能彻底消除，措施主要有以下几种。（1）尽早判断转移发生并生成转移地址。对于上述流水线，可把原来在MEM段进行的目标地址的计
算提前到ID段进行，并在条件成立时送入程序计数器PC。这样，可使流水线中的停顿时间由3拍减少到1拍。（2）预取转移成功和不成功两
个方向上的目标指令，设置两个指令队列，并将一个方向假设为成功路径，这个路径一般是执行概率高的一条，并且在转移条件码生成之前就取这个
方向上的若干条指令，进行译码和取操作数，但是不执行，或者执行而不送结果。一旦条件成立，表明假设正确，立即执行或送结果。如果假设错误
，上述操作全部作废。在另一个方向上，一般也预取若干条指令，以便假设不正确时使用。图9.23转移预测状态图（3）加快和提前形成
条件码。有一些指令的条件码不必等到指令执行完毕或送结果时才能确定，而是可以提前生成。例如，乘除法运算结果的符号位可根据参加运算的两
数的符号位提前产生。（4）提高转移方向的预测率。条件转移指令一般具有两个方向，如果能够提高转移方向的预测率，即可提高程序执行的速
度。预测方法可用状态图表示，如图9.23所示。使用两位二进制数表示是否转移，11和10表示预测转移发生状态，00和01表示预测转
移不发生状态。状态标志处在11状态，预测转移发生。这时若发生转移，则原状态保持；若不发生转移，则将低位清0，状态标志变为10，仍
是预测转移发生状态。在10状态，若发生转移，则低位置1，状态标志变为11；若不发生转移，则高位清0，状态标志变为00。在00状
态，若不发生转移，则原状态保持；若发生转移，则低位置1，状态标志变为01，仍预测转移不发生。在01状态，若转移发生，则高位置1，
状态标志变为11；若不发生转移，则低位清0，状态标志变为00。统计表明，这种方法的预测准确率达83%。另外，常用的还有采用延
迟转移技术，这里不再详述。9.2.5流水线的实现与控制在上一节讨论了流水线中的主要障碍和一些简单的处理办法。要充分发挥流
水线的效能，还有许多问题有待于深入研究和讨论。比如流水线中的中断处理、非线性流水线中的功能部件竞争使用等。1．流水线中的中断处理
在早期的流水线计算机中，对中断现场不精确保护，即不管在哪一条指令的哪一个流水段上发生了中断请求，都要等已进入流水线的指令处理完后，
再去响应中断请求。显然，此时的现场不再是中断请求时的现场。这对于外部设备的中断请求可能影响不大，而对于自陷一类的内部中断影响就大了
。现在流水线采用精确断点保护法，不管在哪一条指令的哪一个流水段上发生中断请求，都对该指令的现场进行精确保护，而且对于已经进入流水
线的其它指令的现场也进行保护，中断返回时一并恢复。这将使用大量后援寄存器，用于现场保护和恢复。由于中断的概率远小于转移指令的概率
，因此中断处理可以不作为主要问题来讨论。2．非线性流水线中功能段的竞争与调度在线性流水线中每一个功能段对于每一条指令或者任务
只使用一次，因此后续指令或任务可以按照瓶颈段经过的时间一个接一个地进入流水线。但是非线性流水线存在前馈和反馈，因此一条指令或任务可
能多次反复使用某一功能段。这时若不能很好地调度，就会出现两条指令或任务同时争用某一功能段的情况。故，需要相隔适当的时间调度下一条指
令或任务进入流水线。下面介绍借助于预约表来分析下一条指令或任务的调度过程。所谓预约表，是1971年由E.S.Davidson提出
的一种用二维表表述一个任务在非线性流水线中对各功能段使用状况的方法。设有一个非线性单功能流水线P，由K个功能段组成，每一个任务流过
流水线需要的时钟周期数为N（t1,t2,…,tn）。纵向表示功能段，横向表示时钟周期，可画出如图9.24所示预约表。每一行表示
P的一个功能段，每一列表示一个时钟周期，总列数表示任务从流入到流出所经过的总时钟周期数。若某一任务在某一时刻ti使用某一功能段Si
，则在相应的格子中用“√”表示。一行中有多个“√”，表示重复使用该功能段。图9.24预约表这就很容易看出一个任务执行时，各段
所需要的间隔节拍数。例如，第一段间隔数为8，第二段间隔数为1、5、6等。把所有行的间隔节拍数都列出来，可构成一个间隔禁止表F（fo
rbiddenlist），即F={1,5,6,8}，禁止相隔这些拍数调度。为了表示后继任务需要间隔多少节拍调
入流水线，引入一个N-1位的二进制向量C=(Cn?1,Cn?2,…,C2，C1)，称为冲突向量（collisionvecto
r）。其中，第i位的状态表示与当前任务相隔i拍调入下任务时是否发生冲突。0表示不冲突，1表示冲突。冲突向量取N-1位是因为经过N拍
后任务就流出流水线，不会再与后续任务发生冲突；又由于其位数N是最大禁止间隔，因此Cn?1位总是1。根据上述禁止表F，可形成相应的
冲突向量为（10110001），称为原始冲突向量。由于第2，3，4，7位为0，因此需与当前任务相隔2拍、3拍、4拍或7拍调入下一任
务。当下一任务进入流水线之后，将产生新的冲突向量。然后可根据这一新的冲突向量确定第3个任务何时可以调入。这样，一直进行到不再产生新
的冲突向量时为止。如何形成新的冲突向量呢？任何一个任务在流水线中每经过一拍向前推进一段，若设原始冲突向量为（10110001），
相当于原始冲突向量右移一位，左边补0，这样就形成新的冲突向量。例如，选择第2个任务在2拍后调入流水线，原始冲突向量逻辑右移两位，即
（00101100）。为了使第3个任务调入后不与前两个任务发生功能部件使用冲突，新的冲突向量应当是第2个任务的当前冲突向量（001
01100）与第2个任务的初始冲突向量（10110001）按位“或”运算，结果为（10111101）。也就是说，第3个任务必须在第
2个任务进入流水线后再隔2拍或者7拍进入。按照这一方式，选择各种可能的间隔节拍数调入新的任务，又可能产生新的冲突向量，进行同样的“
或”运算，直到不再产生新的冲突向量为止。表9.2各调度方案平均间隔拍数图9.25流水线状态图需要注意的是在产生新的冲突向
量时，每次右移后的位向量应（这里为了简单）与原始冲突向量按位“或”。由此可画出用冲突向量表示的流水线状态转移图，如图9.25所示。
采用图9.25中任何一个闭合回路进行调度，都不会发生冲突。但是，需找到一个最佳的调度策略，以获得最高吞吐率。方法是计算出每一种调
度法的平均间隔节拍数，如表9.2所示，然后找出最小的一个。这里，平均间隔为3.5拍的调度策略有两种，即（3,4）和（4,3）。
一般情况下，先选择第一间隔节拍数小的方案，即先隔3拍，再隔4拍。当然，这是一种不等间隔的调度方案，控制起来会复杂一些，故需综合考虑
。对于多功能流水线，只要把每一种功能预约表重叠起来，按照类似的方法就可以推导出相应的调度方案，这里不再一一叙述。图9.26集
中式动态调度9.2.6流水线的动态调度上述流水线调度是一种静态调度方式。动态调度主要是通过硬件安排指令的执行顺序，减少流水
线中的停顿。与静态调度相比，它能处理在编译时难以发现的相关，有助于简化编译程序，使代码具有可移植性。缺点是硬件电路复杂。目前，动态
调度的方法主要有两种，一种是集中式调度，另一种是分布式调度。1．集中式动态调度集中式动态调度是依赖硬件在程序运行的过程中对可能
出现的相关进行预测，从而保证流水线中的各个功能部件能最大限度地重叠工作，其示意如图9.26所示。主要设置了一个状态寄存器RF和一个
记录控制器（也称为记分牌），用来对各功能部件的工作状态、进入流水线中各条指令的状态、使用源/目寄存器的状况进行集中统一的记录和调度
。在译码阶段，记录控制器根据所记录的状态决定是否将译码后的指令发送到有关的功能部件进行处理。其中主要检查该指令所要使用的功能部件
是否被已进入流水线的指令占用，也就是检查资源相关和数据相关，包括RAW、WAR和WAW。当发现有任何一种冲突可能发生时，将指令挂起
。如果经检查不会发生冲突，则把该指令送到相应的部件执行，同时把执行的状态送入状态寄存器RF中去。就这样，依次在判断的过程中调度任务
，并予以执行。早期的CDC6600计算机采用的就是这一技术，现在的RISC超级标量机有很多也采用与之类似的措施，以提高流水线的
性能。2．分布式动态调度分布式动态调度是指把调度控制分配到各功能部件上。早期的IBM360/91计算机就采用了这一技术。如图
9.27所示，是IBM360/91浮点运算器的组成示意图，主要包括以下部件。图9.27IBM360/91流水线的分布式动态
调度示意图（1）运算器：由相互独立的加法器和乘除法器组成。（2）保存站：在加法器中有3个A1～A3，在乘除法器中有2个M1～M
2，用来存放当前参加运算的数据。当两个数据都到齐，运算器空闲，立即进行运算。每一个保存站都有地址，称为站号。保存站与浮点操作数缓冲
寄存器FLB统一编址，前者为1010～1100、1000和1001，后者为0001～0110。（3）指令处理部件：也称为浮点操作
栈，用来存放取出的指令，经译码产生控制信号，送往相应的部件。（4）浮点数据预取缓冲器FLB：用来暂存由存储器中预取出的浮点操作数
，运算时作为源操作数。（5）浮点数据寄存器FLR：表示为F0～F7，作为另一个源操作数，或者存放运算结果或中间结果。各寄存器有一
个“忙”标志，置1表示该寄存器正被使用。另外，每个寄存器设有“站号标记”，表示数据由何而来。该组寄存器表示为F0～F7。（6）数
据存储缓冲器SDB：用来暂存欲存入存储器的数据。每个缓冲器也设有站号，表示数据由何而来。（7）公用数据总线CDB：用来连接上述各
个部件，传送数据。3．分布式动态调度举例下面针对图9.27所示IBM360/91浮点运算器，通过一段程序来说明流水线分布式动
态调度的思想和解决数据相关的具体过程。1）程序S1：LD F0，FLB1 ；(FLB1)→F0S2：MD F0，FL
B2 ；(F0)×(FLB2)→F0S3：STD F0，A；(F0)→AS4：LD F0，FLB3 ；(FLB3)→F0
S5：ADD F0，FLB4 ；(F0)+(FLB4)→F0通过分析可以看出，按照流水线并行方式工作，程序中存在数据相关。例如
S1时启动第1条指令，把数据从FLB1传送到F0；紧接着的S2启动第2条指令进行乘法运算，并使用F0中的数据，显然F0中的数据应当
是从FLB1中取出的数据，而此时FLB1中的数据尚未传送到F0中。若程序顺序执行，结果正确；若按流水线并行调度，必须插入等待周期。
这里采用分布式动态调度，以解决数据相关。S1：指令LDF0，FLB1译码后，将F0的站号置成0001，表示把浮点数据预取缓冲器
FLB1中的数据送入F0。S2：指令MDF0，FLB2译码后，将F0的“忙”标志置1，表示该指令将使用F0；同时，把M1中的源
1寄存器的站号置成0001，源2寄存器的站号置成0010，即直接接收预取缓冲器FLB1和FLB2中的数据；并且，把F0的站号由刚才
设置的0001改为1000，直接接收乘法运算中存入M1的乘积。一旦乘积结果送入F0，其“忙”标志清0。S3：指令STDF0，A
译码后，将存储缓冲器C1的站号置成1000，直接接收乘除法器保存站M1中得到的乘法运算结果。S4：指令LDF0，FLB3译码后
，将F0的站号改成0011，接收预取缓冲器FLB3中的数据。S5：指令ADDF0，FLB4译码后，将A1源1寄存器的站号置成0
011，源2寄存器的站号置成0100，即直接接收预取缓冲器FLB3和FLB4中的数据；并且把F0的站号由0011改成1010，接收
加法器保存站A1中得到的加法结果。2）调度控制全部调度控制可用图9.28表示。这种调度方法是把数据的传送控制分派到各个单元的站
号的设置，而且随着指令的执行随时进行，即分布式动态调度方式。4．分布式动态调度方式的特点分布式动态调度方式的特点可概括为以下4
点：（1）通过公用数据总线把数据直接传送到所需要的部件，免去了先写入某一寄存器或存储器单元然后再读出的过程，减少了流水线中的停顿
周期。（2）通过修改站号实现分布式动态调度，可消除WAR和WAW数据相关的可能性。（3）通过加法器保存站和乘除法保存站，可减少
资源使用中的冲突机会。（4）通过对FLR寄存器“忙”标志的判断，可检查是否存在RAW数据相关。5．硬件动态预测快速转移法硬件
动态预测转移法借助于硬件动态地预测转移指令的转移方向，即尽早生成转移目标地址。它是把转移指令的地址和转移发生后的目标地址存入一个转
移目标缓冲器中。图9.23转移预测状态图图9.29转移目标缓冲器转移目标缓冲器（Branchtargetbuffer
，BTB）由高速存储器或者寄存器堆组成，按内容访问，如图9.29所示。其中存放转移指令的地址（即PC值）、预测转移地址和2位状态标
志。标志位按照图9.23设置，用于转移预测。在遇到转移指令时，用PC中的值（转移指令地址）与BTB中的内容进行比较。若有相符合的内
容，判断标志位，以确定是否取出转移目标地址。若转移条件成立，根据取出的目标地址执行程序；若转移条件不成立，取消本次操作，并修改状态
标志位。目前，这种方法已经在IntelPentium微处理器中使用。9.3指令级流水线9.3.1指令级流水线概述流水
线可以分为粗粒度和细粒度两种类型，其中细粒度主要指部件级流水线和指令级流水线。若流水线中的处理单元是进程、任务或者作业，则属于粗粒
度，也称为程序级流水线。处理机流水线就是一种粗粒度流水线。这里主要介绍指令级流水线。20世纪80年代发展起来的RISC计算机在指令
级流水线的研发中取得了很大的成就，它的目标是使CPI达到1，即在一个时钟周期内平均执行一条指令。通常，访问存储器的时间需要2个时
钟周期，因此指令平均执行周期CPI总是大于1。而新一代RISC计算机通过挖掘细粒度的并行性，使CPI小于1。指令级流水线的并行性常
用并行度来衡量，是指不存在相关，可同时并行执行的指令的条数。下面举例说明并行度的含义。【例9.3】分析下面两个程序段的并行度。
程序段1程序段2LOADR1，M[R7]ADDR2，R1，1ADD
R3，R3，1SUBR4，R3，R2FPMULF3，F3，F4
STOREM[R4]，R5解：由于在程序段1中，三条指令所使用的数据地址不存在相关，因此可并行执行，并行度为
3。而在程序段2中，ADD指令的目标寄存器是R2，而在SUB指令中R2是源操作数，存在RAW相关。同时，在SUB指令中R4是目标寄
存器，而在STORE指令中R4作为基地址寄存器，这也是一种RAW相关。因此，在程序段2中，三条指令只能顺序执行，并行度为1。目前
，在指令级流水线中，主要使用的方法有超级标量流水线法和超长指令字法。图9.31每拍启动三条指令图9.30理想流水线
9.3.2超级标量流水线1．基本概念在理想的流水线中，每一个时钟周期（即1拍）启动一条指令。若设一条指令的执行过程分为4个
阶段，即取指令、译码、执行和写回，理想流水线如图9.30所示。而在超级标量流水线中，是指在1拍内启动多条指令。图9.31所示为同时
启动了三条指令，并行度为3。图9.32每1/2拍或每1/3拍启动一条或三条指令也可以每1/2拍或者每1/3拍启动一条指令，如
图9.32（a）所示，每1/2拍启动一条指令，并行度为2；还可以每1/2拍或者每1/3拍启动多条指令，如图9.32（b）所示，每1
/3拍启动了三条指令，并行度为9。显然，使用不同的启动方式，或者说不同的并行度，对提高机器速度缩短程序执行时间有不同的效果。图9
.33超级标量机的执行部件2．超级标量机的组成特点在超级标量流水线的计算机中，要实现每一拍完成多个操作任务，就必须有相应的
功能部件予以支持。如图9.33（a）所示，只有一个ALU，因此每一拍只能进行一种操作，也就是只能启动一条指令。若要在1拍中完成多个
操作，就必须有多个功能部件。如图9.33（b）所示，提供了一个ALU和一个浮点运算器FP，这样就可以在1拍中启动两条指令。图中，I
-Cache表示指令高速缓冲存储器，RF表示寄存器堆。图9.34超级标量机典型结构3．超级标量机的典型结构图9.34所示是
一种超级标量机的典型结构。指令执行部件由存储操作部件、ALU部件及转移控制部件组成。存储操作部件执行LOAD/STORE指令，AL
U部件执行整数运算，转移控制部件执行转移指令。程序执行时同时取两条指令，分别送入两个译码器。译码后，根据状态记录部件中记录的功能
部件与寄存器的使用情况，确定哪些指令可以送入执行部件。执行完毕，有关寄存器和执行部件的状态可能发生变化，其状态送状态记录部件，供下
一次判断。也就是说，根据状态记录部件中的相关信息确定多条指令可否同时被调度和执行。自20世纪80年代末，超级标量机陆续问世，例如
Intel公司的i860、IBM公司的RS6000、Motorola公司的88110等。这些机器在一个周期内可启动2～4条指令，常
用IPC（Instructionpercycle）表示，即IPC=2～4。概括起来，超级标量机的主要特点有以下3点：（1）配
置多个性能不同的处理部件，采用多条流水线并行处理。（2）能同时对多条指令进行译码，根据状态记录部件中记录的状态将可执行指令送入相
应的执行部件，以达到在一个时钟周期内启动多条指令的目的。（3）超级标量机是在程序运行期间通过硬件实现多条指令的调度的，是借助于硬
件资源的重复来实现空间上的并行操作。图9.35超长指令字（VLIW）9.3.3超长指令字1．超长指令字超长指令字（V
erylonginstructionword，VLIW）的方法是在20世纪80年代初由美国耶鲁大学的Fisher教授首先提出
来的。它与超级标量法有许多类似之处，也可实现在一个周期内完成多项操作。它的一条指令很长，往往达到上百位，甚至上千位。当初提出的目的
主要是减少访问存储器的次数。它的并发操作如图9.35所示，主要是在流水线的执行阶段，完成3种任务。超长指令字计算机采用单一的控制
器，每个周期启动一条指令。在其内部，一条超长指令字被分成多个控制字段，再由每一个字段独立地控制一个功能部件。图9.36超长指
令字计算机结构示意图2．超长指令字计算机的组成原理具有超长指令字功能的计算机必须有多个功能部件，支持同时进行多种操作。典型结构
如图9.36所示，包含两个存储器读/写部件、一个浮点加法部件和一个浮点乘法部件，由统一的时钟信号控制，从而为多功能操作提供支持。包括存/取1、存/取2、浮点加、浮点乘，可同时进行两路存储器访问、浮点加和浮点乘操作。在这种计算机中，是在编译时处理可能出现的数据相关和资源相关，因此硬件电路比较简单。而且，在编译阶段要完成超长指令字中多个可并行执行的操作的调度。3．超长指令字的生成在超长指令字计算机中，指令的长度与功能部件数直接相关。超长指令字的生成是由编译器在编译时完成的。它将顺序操作序列合并成可以并行执行的指令序列，以实现多个操作的并行性，下面举例说明。设有以下赋值运算：C=A+BK=I+JL=M?KQ=C×K若按照顺序操作，所使用的指令序列如表9.3所示，共需要14个周期。从中找出不存在任何相关的操作同时进行，即可得到表9.4中所示的并/串行操作序列。这样，每一行可构成一个超长字指令，在编译时可以把13条指令压缩成6条，在执行时仅需6个周期即可完成。(a)不分段(b)分段图9.37循环程序分成三段9.3.4软件流水法软件流水法借鉴了硬件流水的思想，使循环程序段在执行时能更多地重叠进行。设有一段程序，如图9.36（a）所示，长度为L，若执行每条指令的平均时间为t，当该段程序循环执行n次时，所需要的时间为：T=n×L×t。图9.37分成三段构成循环图9.38软件流水展开n个体若将该程序段分成相等的三段，即L1、L2和L3，如图9.37（b）所示。对于循环体可以展开，使各程序段的相应部分并行执行，如图9.37所示。这样，程序执行时间可减少为：T=n/3×5×L/3×t=5nLt/9循环次数由原来的n次减少为n/3次。采用软件流水技术就是把循环程序展开n次，类似于硬件流水，也存在装入、循环执行和排空三个阶段。在循环过程中，有三个处在不同程序段中的循环体并行执行，其示意图如图9.38所示。这样，程序执行时间减少为：T=4Lt/3+(n?2)×Lt/3=(n+2)Lt/3软件流水实际上是一种对循环程序进行优化的方法，它在不改变程序语义的前提下，将不同层次循环中的操作重叠执行，从而达到充分利用硬件资源，实现并行操作，缩短程序执行时间的目的。图9.39R4000各流水段功能示意图9.3.6超级流水机举例为了提高标量流水机的性能，必须增大流水线的深度，也就是流水线的段数。目前，超级标量流水机已经有很多，MIPS公司的R4000微处理器就是典型的代表。它把指令的执行过程分为8段，即取指1、取指2、读RF（寄存器）、执行、取数1、取数2、标记检查和写RF（寄存器），如图9.39所示。这样，就可以增加流水线的深度，使更多的指令进入流水线，时空图如图9.40所示。图9.40MIPSR4000超级流水线时空图