计算机体系结构（第二版）课件第二章流水线技术

第二节处理机实现流水线的基本结构一、重叠执行方式的基本结构

1.重叠执行方式的基本结构

采用二次重叠执行方式，同时有三条指令分别在取指令、分析和执行。要使它们能够重叠执行，处理机在结构上必须有独立的取指令部件、指令分析部件和指令执行部件。它们有各自的控制线路，实现各自的功能，这样才能取指令、分析和执行的同时进行。为此，要把顺序执行方式中的一个集中的指令控制器分解成三个相结独立的控制器，分别是：存储控制器，简称存控；指令控制器，简称指控；运算控制器，简称运控。重叠执行方式的基本结构如图所示。一、多条指令的执行方式

二、什么是流水线

三、流水线的表示方法四、流水线的分类五、流水线的特点

第一节流水线的基本概念

第一节流水线的基本概念

一、多条指令的执行方式

一条指令的执行过程可以分为多个阶段，通常分为取指令、分析指令、执行指令三个阶段。假设三个阶段所需要的时间均为t。（1）顺序方式。顺序执行方式是指在任何时刻，处理机中只有一条指令在执行。执行n条指令所需要的时间为T=3nt。控制简单，节省设备。执行指令速度慢，功能部件利用率低。（2）一次重叠方式。一次重叠执行方式是指在任何时刻，处理机中至多只有二条指令在同时执行。执行n条指令所需要的时间为T=(2n+1)t。时间缩短近一半，功能部件利用率高。需要增加一些硬件，控制过程也复杂一些。（3）二次重叠方式。二次重叠执行方式是指在任何时刻，处理机中至多可以有三条指令在同时执行。执行n条指令所需要的时间为T=(n+2)t。时间缩短了近2/3，提高指令的执行速度。付出更高的代价。取指k分析k执行k取指k+1分析k+1执行k+1取指k分析k执行k取指k+1分析k+1执行k+1取指k+2分析k+2执行k+2取指k分析k执行k取指k+1分析k+1执行k+1取指k+2分析k+2执行k+2顺序执行方式

一次重叠执行方式

二次重叠执行方式

第一节流水线的基本概念二、什么是流水线

计算机中的流水线与工厂中的生产流水线十分相似，它是指把一个重复的过程分解为若干个子过程，一个过程的子过程可以与其它过程的不同的子过程并行进行，实现不同过程在时间上重叠进行的工作方式。实现流水线的技术方法称为流水线技术。从本质上讲，流水线技术是一种时间并行技术，是通过时间重叠的技术途径实现并行处理（时间并发性）。根据子过程划分，相应的流水线也要划分出相应的段，每一个段称为流水节拍、流水步、流水步骤、流水阶段、流水段、功能段等。一个流水阶段与另外一个流水阶段相连接形成流水线。过程从流水线的一端进入，经过流水线的处理，从流水线的另一端进出。流水线技术是一种非常经济而又有效的技术，已成为计算机中普遍使用的一种并行处理技术。采用流水线技术只需要增加少量的硬件，就能够把处理机的运算速度提高几倍。

第一节流水线的基本概念

第一节流水线的基本概念

流水线的表示方法有三种：连接图、时空图和预约表，其中时空图用于表示线性流水线，预约表用于表示非线性流水线，而连接图则均可表示。

1.连接图

四个流水段的指令流水线的连接图如图所示，其实质是将带执行时间的各流水段按照流水线的执行顺序从左到右排列，并用带箭头的直线把它们连接起来。

2.时空图

时空图是一种最常用、能直观描述线性流水线工作过程的表示方法，四个流水段的指令流水的时空图如图所示。其实质是利用平面直角坐标系的第一象限。横坐标表示时间，即是输入到流水线的各个任务在流水线中所经过的时间。纵坐标表示空间，即流水线的每一个流水段。三、流水线的表示方法线性指令流水线的连接图

非线性指令流水线的连接图

取指令译码执行保存结果取指令译码执行保存结果12345123451234512345四功能段指令流水线时空图

第一节流水线的基本概念

第一节流水线的基本概念3.预约表

预约表是一种最常用、能直观描述某过程非线性流水线工作状态的表示方法，四个流水段的指令流水线的预约表如图3.4所示。其实质是利用一张表，行表示时间即非线性流水线的段数，列表示空间既任务通过非线性流水线的时间，表中用“×”表示行对应流水段在列对应时间段要被使用。一行中可以有多个“×”，表明同一个任务在不同时间重复使用了同一个流水段；一列中有多个“×”则表明任务在同一时间使用了多个流水段。×××××

四功能段非线性指令流水线预约表

第一节流水线的基本概念

四、流水线的分类

从不同的角度，可以把流水线分成多种不同类型，以反映流水线在某一方面的结构、特点或性能。

1.按流水线的功能多寡分类

（1）单功能流水线（UnifunctionPipelining）单功能流水线是指只能完成一种固定功能的流水线。（2）多功能流水线（MultifunctionPipelining）多功能流水线是指流水线的各段可以实现不同的连接，在不同的时间内，或在同一时间内，通过不同的连接方式实现不同的处理功能。

输入示阶差对阶规格化尾数加输出

第一节流水线的基本概念输入对阶尾数加规格化尾数乘输出累加求阶差定点乘法

浮点加法

浮点点积

TI-ASC计算机的多功能流水线

输入尾数乘累加输出输入求阶差对阶尾数加规格化输出

第一节流水线的基本概念2.按多功能流水线在同一时间内各段连接方式分类

在多功能流水线中，按照在同一时间内是否可以实现多种连接，来同时执行多种功能的要求，把多功能流水线分为静态流水线和动态流水线。（1）静态流水线（StaticPipelining）静态流水线是指在同一段时间内，多功能流水线只能按一种方式连接，实现一种功能。只有当按照这种连接流入的所有处理的对象都流出流水线之后，多功能流水线才能重新进行连接以实现其他功能。如图3.6所示中的8段多功能流水线如果按照图3.7所示的时空图工作，那么就是一种静态流水线。（2）动态流水线（DynamicPipelining）动态流水线是指在同一段时间内，多功能流水线中的各段可以实现多种连接，同时执行多种功能。当然，任何一个功能段只能参加到一种连接中。

第一节流水线的基本概念空间浮点加定点乘输出1 2n-1n 1累加12n-1n12数乘123规格化123n-1n尾数加123n-1n对阶123n-1n 求阶差

123n-1n输入123n-1n123n-1n时间静态流水线的时空图

空间浮点加定点乘输出12…n-1n123…累加1234…尾数乘12345…规格化12…n-1n尾数加12…n-1n对阶12…n-1n求阶差12…n-1n输入12…n-1n123456…

时间动态流水线的时空图

第一节流水线的基本概念

第一节流水线的基本概念

3.按流水线的级别分类

按照流水线的级别，可以把流水线分为功能部件级、处理机级和处理机间级。（1）指令流水线（InstructionPipelining）指令流水线又称为处理机级流水线，它是把一条指令的执行过程分解为多个子过程，每个子过程在一个独立的功能部件中完成。（2）运算操作流水线（ArthmeticPipelining）运算操作流水线又称为功能部件级流水线，它是把处理机的算术逻辑部件分段，使运算过程能进行流水操作。（3）宏流水线（MacroPipelining）宏流水线又称为处理机间流水线，它是由两个或两个以上的处理机通过存储器串行连接起来，每个处理机对同一数据流的不同部分分别进行处理，前一个处理机的输出结果存入存储器中，作为后一个处理机的输入，每个处理机完成整个任务中的一部分。

第一节流水线的基本概念处理机1存储器处理机2处理机n存储器存储器…处理机1存储器处理机2处理机n存储器存储器…一种宏流水线

第一节流水线的基本概念

4.按流水线的各功能段之间是否有反馈回路分类按照流水线的各功能段之间是否有反馈回路，可以把流水线分为线性流水线和非线性流水线。（1）线性流水线（linearPipelining）线性流水线是指流水线各段串行连接，数据顺序流经流水线各段水线各段一次且仅流过一次。（2）非线性流水线（nonlinearpipelining）非线性流水线是指在流水线各段之间除有串行连接之外，还有反馈回路，数据流经有反馈回路的功能段的次数可以有多次。

第一节流水线的基本概念五、流水线的特点

（1）流水线是由多个独立的从一个大的处理功能部件分解而来的小功能部件组成，依靠小功能部件并行工作来提高处理速度。把一个重复的处理过程分解为若干个子过程，每个子过程需要设置一个对应的功能部件来实现，这是流水线本质。（2）流水线中各功能段的时间应尽量相等，否则将引起“堵塞”、“断流”等。在流水线设计中，当遇到“瓶颈”时，必须采取办法解决。（3）流水线需要有“装入时间”和“排空时间”。“装入时间”是指第一个任务进入流水线到输出流水线的时间。“排空时间”是指第n个（最后一个）任务进入流水线到输出流水线的时间。

（4）只有连续不断地提供同种任务才能充分发挥流水线的效率。因此，在采用流水线方式工作的处理机中，特别是当流水线的级数较多时，要在软件和硬件设计等多方面尽量为流水线提供连续的任务，以提高流水线的效率。（5）在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等。它的作用是保存本流水段的执行结果，如图所示。

第一节流水线的基本概念取指令译码执行存结果锁存器锁存器锁存器锁存器流水线中锁存器

第二节处理机实现流水线的基本结构二、先行控制方式的基本结构五、流水线结构设计中的若干问题

三、先行控制的指令流水线四、运算操作流水线和宏流水线的基本结构一、重叠执行方式的基本结构重叠执行方式的基本结构

取指部件读数写数主存储器分析部件运算部件寄存器组运算控制器存储控制器取指修改PC

第二节处理机实现流水线的基本结构

第二节处理机实现流水线的基本结构

2.访问冲突及其解决方法

采用了重叠执行方式的基本结构后，可实现取指令、分析和执行的并发进行，但存在访问主存的冲突问题（即资源冲突、结构相关）。例如，取指令要访存，分析指令时可能要访存取操作数，执行指令时可能要向主存写运算结果。在一般机器中，指令和数据是混合存放在一个主存中，而且在一个存储周期只能访问一个存储单元。因此，一般的存储器体系结构无法实现指令的重叠执行。解决这个问题的方法一般有以下三种。（1）设置两个独立编址的主存储器。（2）主存储器采用多体交叉编址的并行存储器。（3）采用先行控制技术是解决访存冲突的根本办法。

第二节处理机实现流水线的基本结构二、先行控制方式的基本结构

1.先行控制方式的基本原理

在二次重叠执行方式执行指令中，假设取指令、分析指令和执行指令的时间相等，则流水线连续流畅，否则功能段会相互等待。但实际上往往是不相等的，若取指令、分析指令和执行指令分别为△t1、△t2、△t3，且△t2＞△t3＞△t1，多条指令的执行过程如图2-13所示。从图2-13可以看出，取指段在取完第k+1条指令后，由于分析段还没有分析完第k条指令，第k+1条指令不能进入分析段而产生了堵塞，导致取指段空闲；执行段执行完第k条指令后，由于分析段还没有分析完第k+1条指令，执行段得不到第k+1条指令而产生了断流，又导致执行段空闲。另外，当指令之间存在数据相关等相关时，重叠也会被打断。例如，如果第k条指令是转移指令，则顺序取来的第k+1条指令可能无效,从而产生了停顿。

第二节处理机实现流水线的基本结构取指k分析k执行k分析k+1取指k+1执行k+1取指k+2分析k+2执行k+2各功能段延迟时间不相等的二次重叠执行方式

第二节处理机实现流水线的基本结构

先行控制方式的基本思想是：当流水线中某功能段的延迟时间较长时，该功能段前面的功能段对后继任务进行预处理，预处理好的后继任务置于缓冲器中。而该功能段后面的功能段则对以前置于缓冲器的任务进行后行处理。这样，所有的功能段都处于忙碌状态。某任务的流程中，各功能段之间有等待的时间间隔，但各自的流程是连续的。当然，如果前面功能段的缓冲器已满，或者后面功能段没有后行处理任务，流水线仍是不流畅的。采用先行控制方式工作，不仅可解决延迟时间不相等和不能在较长时间内提供同种任务而造流水线不流畅，解决了访问冲突。当有多个功能段要访问存储器时，根据具体情况，让某功能段访存，其前面的功能段则对后继任务进行预处理，而后面的功能段则进行后行处理。

第二节处理机实现流水线的基本结构2．什么是先行控制

先行控制是通过对任务的预处理和缓冲，以平滑功能部件工作速度上的差异，使功能部件能独立地工作，并始终处于忙碌状态，提高任务执行的速度。它实质是缓冲技术和预处理技术相结合的结果。缓冲技术和预处理技术是先行控制的关键。缓冲技术是在工作速度不固定的两个功能段之间设置缓冲栈，用以平滑它们的工作速度的差异。预处理技术是把要进入某功能段的任务进行外围处理，减少该功能段的执行时间。例如，把进入运算器的指令都处理成寄存器——寄存器型（RR型）指令，它与缓冲技术相结合，为进入运算器指令准备好所需的全部操作数。

第二节处理机实现流水线的基本结构

3.先行控制方式的基本结构

先行控制方式的基本结构如图所示。它一般要设置4个先行缓冲栈，这四个缓冲栈的作用如下。（1）先行指令缓冲栈（2）先行操作栈（3）先行读数栈（4）后行写数栈通常把先行指令缓冲栈、先行读数栈、先行操作栈和后行写数栈统称为先行控制器。先行控制器与指令分析器一起构成先行控制方式中的指令控制部件。而原来的运算器及运算控制器一起组成指令执行部件。

第二节处理机实现流水线的基本结构主存储器存储控制器先行指令缓冲栈指令分析器寄存器组运算器运算控制器先行读数栈后行写数栈先行操作栈先行控制的基本结构

第二节处理机实现流水线的基本结构

先行指令缓冲栈的组成结构如图所示。只要指令缓冲栈未满，存储控制器就根据先行程序计数器PC1进行取指令，指令分析器在分析完一条指令后，则根据现行程序计数器PC2自动从指令缓冲栈取另外一条指令来进行分析，先行程序计数器PC1与现行程序计数器PC2的顺序一致，一维持正确的执行顺序。

主存储器存储控制器先行程序计数器PC1指令寄存器IR指令缓冲寄存器堆控制逻辑现行程序计数器PC2指令分析器先行指令缓冲栈的组成

第二节处理机实现流水线的基本结构4.缓冲深度的选择

先行控制器四个缓冲栈中的缓冲寄存器的个数即是缓冲深度。缓冲深度多少合适呢？缓冲深度小，缓冲作用不大；缓冲深度大，会浪费寄存器，控制也复杂。对于缓冲深度的选择，一般是在采用静态分析的基础上，通过系统模拟的方法来确定各个缓冲栈的缓冲深度。静态分析方法可从两个极端情况来考察。一是假设先行指令缓冲栈缓冲深度深度为Di，且已完全充满。此时在先行指令缓冲栈的输出端，给指令分析器的提供指令较简单，流出的速度快；而在输入端，由于要访存取指令，指令注入速度慢。设平均每条指令分析的时间为t1,平均取一条指令的时间为t2。在先行指令缓冲栈从完全充满到全部被取空的过程中，若指令分析器一共分析了L1条，所花时间为L1t1，同时从主存中读取了L1－Di条指令，所花时间二者应相等，即L1t1=（L1－Di）t2。故得：

Di=「L1（t2–t1）/t2」

第二节处理机实现流水线的基本结构

当取值大于L1条时，该先行指令缓冲器将被取空，指令分析器被迫处于等待状态。二是假定先行指令缓冲栈为空，且取指速度快，平均时间为t2ˊ；而分析指令由于指令复杂、速度较慢，平均时间为t1ˊ。从先行指令缓冲栈完全为空到完全充满指令的过程中，若从主存取到先行指令缓冲中的指令条数为L2条，而指令分析器分析的指令条数为Di，所花时间二者应相等，即L2t2ˊ=（L2－Di）t2ˊ。故得：

Di=「L2（t1ˊ–t2ˊ）/t1ˊ」当取值大于L2条时，该先行指令缓冲器将被充满，也就失去了缓冲作用。

第二节处理机实现流水线的基本结构

若让t1与t2非常接近，即提高主存速度，如采用并行主存储器，或增大Cache容量或级数，对减少缓冲深度很有效。由于在一般程序中，执行时间短的指令要远远多于执行时间长的指令，指令分析器分析指令的速度要大于运算器执行指令的速度。因此常用前一种方法来计算缓冲深度。另外在确定缓冲深度时，还要选择一些典型程序，通过模拟方法选取合理的缓冲深度。各个缓冲栈的缓冲深度有如下关系：

D先行指令≥D先行操作≥D先行读数≥D后行写数

第二节处理机实现流水线的基本结构三、先行控制的指令流水线

在采用先行控制方式的处理机中，先行控制结构中的各个部件也构成了一条流水线，如图所示。它把指令的执行分解为五个子过程，即取指令、指令译码、取操作数、执行运算、写结果。由于各种指令在同一个功能部件中执行的时间可能相差很大，因此，在各个功能段之间都设置多个缓冲寄存器，以平滑流水线中各功能部件的操作。先行指令缓冲栈先行指令分析器先行读数数栈

先行操作栈指令执行部件后行写数栈功能：取指令组计算操作数地址形成RR*型指令运算保存结果输入输出先行控制方式中的指令流水线

第二节处理机实现流水线的基本结构四、运算操作流水线和宏流水线的基本结构

1.运算操作流水线的基本结构

把运算操作过程分成多个子过程，每一个子过程的延迟时间虽然不可能绝对相等，但偏移不大。因此，采用集中控制方式，使所有的流水段与一个统一的时钟同步。而时钟周期的大小则要根据流水段的划分来确定。由于实际执行的误差，可能引起段间的干扰。为避免干扰，保证段间时间宽度匹配，在各段之间增设门（Latch）寄存器，如图所示。门寄存器则是各段之间的标志。

2.宏流水线的基本结构

宏流水线是每个处理机对同一数据流的不同作业分别进行处理，其结构则是异构型的多处理机系统。多处理机系统对任务处理的效率，不仅与系统结构有关，而且与算法、语言、软件等有关。

第二节处理机实现流水线的基本结构段S1门寄存器段S2段Sn门寄存器门寄存器门寄存器运算操作流水线的基本结构

第二节处理机实现流水线的基本结构五、流水线结构设计中的若干问题

1.瓶颈问题

当流水线的各段时间相等时，其任务是每一个节拍同步地往前流动一段，该节拍往往就是机器的时钟周期。当流水线各段时间不相等时，时间最大的那个段就成了瓶颈，机器的时钟周期取决于该瓶颈段的延迟时间。

2.额外开销问题

流水线的额外开销由两部分构成：流水线寄存器延迟和时钟偏移开销。采用流水技术后，虽然可以提高指令执行的吞吐率，从而提高程序的执行速度，但流水线并不能真正减少单条指令的执行时间。实际上，由于这些开销的存在，反而会使每条指令的执行时间有所增加。3.相关问题

在运算操作流水线中，如果后面的计算要用到前面计算的结果，则流水线的性能和效果会受到比较大的影响。对于指令流水线来说，也是如此。如果流水线中的指令之间存在关联，则它们可能要相互等待，引起流水线的停顿。如何处理好相关问题，是流水线设计中要解决的重要问题之一。

第三节线性流水线的性能及其分析一、吞吐率（TP,Thoughputrate）二、加速比（S，Speedupratio）

三、效率(E，Efficiency)

四、吞吐率、加速比和效率之间的关系

六、流水线最佳段数的选择

五、流水线“瓶颈”问题的解决方法

第三节线性流水线的性能及其分析一、吞吐率（TP,Thoughputrate）

1.吞吐率的定义

流水线的吞吐率是指在单位时间内流水线所完成的任务数量或输出的结果数量。即：

TP=n/Tk式中：n为任务数，Tk是处理完成n个任务所用的时间，式是计算流水线吞吐率最基本公式。

第三节线性流水线的性能及其分析

2.流水线各段的执行时间相等的吞吐率若有一条k段的线性流水线，各段的执行时间相等，均为△t。当n个任务是连续的理想情况下输入到流水线，流水线的时空图如图所示。时间空间S4S3S2S1123…n-1n123…n-1n123…n-1n123…n-1n

k·△t(n-1)△t

n·△t(k-1)△tTk各段执行时间均相等的流水线时空图

第三节线性流水线的性能及其分析

流水线完成n个任务所需要的总时间可从两方面来分析。一是从流水线的输出端看，用k个△t输出第一任务，即k·△t为“装入时间”，其余n-1个任务，每个△t输出一个任务，即用n-1个时期周期输出n-1个任务。二是从流水线的输入端看，用n个△t向流水线输入n个任务，另外还要用k-1个△t作为流水线的“排空时间”。因此，流水线完成n个任务需要的总时间为：

Tk=（n+k-1）·△t连续输入n个任务的一条k段线性流水线的实际吞吐率为：相应的最大吞吐率为最大吞吐率与实际吞吐率的关系是

第三节线性流水线的性能及其分析

123…n

123…n

123…n

123…nS4S3S2S1时间

当流水线中各流水段的执行时间不相等时，流水线的最大吞吐率与实际吞吐率主要是由流水线中执行时间最长的那个流水段来决定。这时除“瓶颈”流水段一直忙碌外，其余流水段都有空闲时间，图中“”的部分表示该段流水线在这一段时间内是空闲的，这实际上是一种资源的浪费。

(n-1)△t2Tk

第三节线性流水线的性能及其分析线性流水线的实际吞吐率为相应流水线的最大吞吐率为：

第三节线性流水线的性能及其分析二、加速比（S，Speedupratio）1.加速比的定义流水线的加速比是指完成同样一批任务，不使用流水线即顺序执行所用的时间与使用流水线所用的时间之比。如果不使用流水线所用的时间为T0，使用流水线的执行时间为Tk，则流水线的加速比为：

S=T0/Tk是计算流水线加速比的基本公式。

2.流水线各段的执行时间相等的加速比若有一条k段的线性流水线，各段的执行时间相等，均为△t。当n个任务是连续的理想情况下输入到流水线，该流水线完成n个连续任务所需要的时间见（2-4）式。如果不使用流水线执行这n个任务，所需要的时间为：。因此，流水线的实际加速比为：

第三节线性流水线的性能及其分析相应的最大加速比为:3.流水线各段的执行时间不相等的加速比

第三节线性流水线的性能及其分析三、效率(E，Efficiency)1.效率的定义流水线的效率是指流水线的设备利用率。在时空图上，流水线的效率定义为n个任务占用的时空区与k个流水段占用的总时空区之比。即：

E=n个任务占用的时空区/k个流水段占用的总时空区式是计算流水线效率的基本公式，其分母是n个任务所用的时间与k个流水段所围成的时空总面积，分子是n个任务实际上占用的有效时空面积。因此，流水线的效率包含时间和空间两方面的因素，通过时空图来计算流水线的效率非常方便。

第三节线性流水线的性能及其分析

2.流水线各段的执行时间相等的效率各段的执行时间相等，均为△t的k段的线性流水线，完成n个连续任务所需要的时间见（2-4）式，每个功能段在这段时间内都被占用，则时空图的总面积为k(k+n-1)△t。一个任务占用的时空区为k.△t，n个任务实际占用的有效面积为n.k.△t。各段的执行时间相等的流水线效率为：

从式中可以看出，当n＞＞k时，流水线的效率达到最大值1。这时，流水线的各段均处于忙碌状态。从时空图中看，每一块都是有效的。相应的流水线的最大效率为：

3.流水线各段的执行时间不相等的效率

第三节线性流水线的性能及其分析

第三节线性流水线的性能及其分析四、吞吐率、加速比和效率之间的关系说明流水线的效率是流水线实际加速比S与它的最大加速比Smax=k之比。只有当流水线的效率达到其最大值，即E=1时，才能使实际加速比达到最大，即S=k。当n＞＞k时，有：Emax=1Smax=kTPmax=1/△t

各段的执行时间不相等时，即流水线中存在“瓶颈”流水段，除了瓶颈流水段一直处于忙碌状态之外，其他各个流水段都有空闲时间，这些流水段的效率没有得到充分发挥。因此，整个流水线的吞吐率、加速比和效率也比较低。采用提高流水线吞吐率的方法，由于能够使流水线中的各个流水段始终处于忙碌状态，没有空闲时间。因此，流水线的吞吐率、加速比和效率也就显著提高了。

第三节线性流水线的性能及其分析五、流水线“瓶颈”问题的两种解决方法

1.分离“瓶颈”流水段

分离“瓶颈”流水段将流水线的“瓶颈”功能段部分再细分，分解成几个独立的子功能段，消除执行时间不相等而带来的“瓶颈”段。例如，把图2.19所示的第二个流水段再细分为三个子流水段，分别为S2-1、S2-2和S2-3，如图所示。这样，每个流水段及子流水段的延迟时间均为△t。

2.重复设置“瓶颈”流水段

如果由于结构等方面的原因，瓶颈流水段难以再细分，则可以通过重复设置瓶颈流水段，让多个瓶颈流水段并行工作，消除执行时间不相等而带来的“瓶颈”段。例如，把图所示的第二个流水段重复设置，流水线连接图如图所示。但是，采用瓶颈流水段重复设置的方法，其控制逻辑比较复杂。S1S2-2S2-3S3S4S2-1S2-1S2-2S2-3S4S3S1“瓶颈”流水段再次细分流水线

“瓶颈”流水段重复设置流水线

第三节线性流水线的性能及其分析

第三节线性流水线的性能及其分析123456789…n-2n-1n123456789…n-2n-1n147…n-2258…n-1369…n123456789…n-2n-1nS4S3S2-3S2-2S2-1S1空间时间

第三节线性流水线的性能及其分析六、流水线最佳段数的选择假设在非流水线的机器上采用顺序执行方式完成一个任务所需要的时间为t，那么，在同等速度的有k段流水线的机器上执行一个任务需要的时间为：t/k+d，其中d为锁存器的延迟时间。流水线的最大吞吐率为：TP=1/(t/k+d)。又粗略地估计流水线的总价格为：C=a+bk。其中，a为所有流水段的总价格，b为每个锁存器的价格。流水线的性能价格比PCR定义为：K0=

目前,一般处理机中的流水线段数在2段至10段之间,极少有超过15段的流水线,一般把8段或超过8段的流水线称为超流水线。

第三节线性流水线的性能及其分析

例2.1一个四段线性流水线，各段执行时间不等，如图3-19所示。①当n=4时，画出它的时空图，求TP、TPmax、S和E的值。②当n=12时，画出分离“瓶颈”流水段的流水线连接图和时空图，求TP、TPmax、S和E的值。③当n=12时，画出重复设置“瓶颈”流水段的流水线连接图和时空图，求TP、TPmax、S和E的值。解：（1）流水线的时空图如图3-20所示，由时空图可以看出，n=4时，k=4。所以TP=n/Tn=n/[6△t+(n-1)3△t]=4/15△tTPmax=TP=1/3△t T0=n×k△t=4×(1+3+1+1)△t=24△t S=T0/Tn=24△t/15△t=1.6

因为有效面积=3×(△t×4)+1×(3△t×4)=24△t

实际面积=4×Tn=60△t

所以E=24△t/60△t=0.4

第三节线性流水线的性能及其分析（2）线性流水线中的段2为“瓶颈”流水段，分离该流水段后的流水线连接图如图3-21所示，时空图类似于图3-18。且n=12时，k=6。所以TP=n/Tn=n/[6△t+(n-1)△t]=12/17△t TPmax=TP=1/△tS=n·k/(k+n-1)=12×6/(6+12-1)=4.24E=S/k=0.7（3）线性流水线中的段2为“瓶颈”流水段，重复设置该流水段后的流水线连接图如图3-22所示，时空图如图3-23所示。且n=12时，k=6。所以TP=n/Tn=n/[6△t+(n-1)△t]=12/17△t TPmax=TP=1/△tS=n·k/(k+n-1)=12×6/(6+12-1)=4.24E=S/k=0.7

第三节线性流水线的性能及其分析

例2.2如图2-25所示的静态加、乘双功能流水线中，由段S1、S2、S3、S4、S6组成乘法流水线，由段S1、S5、S6组成加法流水线。设向量a=（a1，a2，a3，a4），向量b=（b1，b2，b3，b4），计算П(ai+bi)。画出该流水线时空图，求TP、S和E的值。S1S2S3S4S6S5乘流水线XYZ加流水线

第三节线性流水线的性能及其分析

解：由于该流水线为静态双功能流水线，计算要求先加后乘，因此应先置加法功能，连续计算（a1+b1）、（a2+b2）、（a3+b3）、（a4+b4）四个加法后；再设置乘法功能，而且按[(a1+b1)×(a2+b2)]×[(a3+b3)×(a4+b4)]顺序做3个乘法。因此可画出该流水线的时空图如图2-26所示，图中A=a1+b1，B=a2+b2，C=a3+b3，D=a4+b4。空间S6S5S4S3S2S11234三12341234一二一二一二一二一二三三三三ABCDA·BC·D(A·B)×(C·D)

t6t12t17a1b1a2b2a3b3a4b4ABCDA·BC·D时间

第三节线性流水线的性能及其分析

由时空图可以看出，在总共17个△t的时间内输出7个结果，所以有：

TP=n/Tn=7/17△t

而当用串行方法完成操作时，需要四次加法和三次乘法，完成一次加法需要3△t，完成一次乘法需要5△t，完成该运算总共需要时间为：

T0=4×3△t+3×5△t=27△t

所以S=T0/Tn=1.88E=有效时空区面积/全部时空区面积

=(3×4△t+5×3△t)/(6×17△t)=0.264

第三节线性流水线的性能及其分析

例2.3有一条动态多功能流水线由5段组成，如图2.27所示。加法用1、3、4、5段，乘法用1、2、5段，第4段的时间为2△t，其余各段时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算试计算其吞吐率、加速比和效率。

S1S2S3S4S5乘流水线加流水线

第三节线性流水线的性能及其分析

解：首先应选择适合于流水线工作的算法。对于本题，应先计算A=A1×B1、B=A2×B2、C=A3×B3和D=A4×B4，再计算A×B和C×D；然后求总的累加结果。其次，画出完成计算的时空图，如图2.28所示，图中阴影部分表示相应段在工作。412312341234空间S5S4S3S2S1ABCDA＋BC＋D(A＋B)＋(C＋D)

t6t16ABCDA＋BC＋DA1A2A3A4B1B2B3B4一一一一二二二二三三三三时间

第三节线性流水线的性能及其分析

由图2.28可见，它在16个△t时间中，给出了7个结果。所以吞吐量为：

TP=7/16△t

如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需要（4×3＋3×5）△t=27△t，所以加速比为：

S=27△t/16△t≈1.69

该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得：

E=（4×3＋3×5）△t/5×16△t≈0.338

第四节流水线中的相关及其处理

一、流水线中相关的基本概念二、资源相关三、操作数相关四、指令相关五、变址相关六、条件转移相关及其对流水线效率的影响七、条件转移相关的处理技术八、无条件转移相关九、中断转移相关

第四节流水线中的相关及其处理一、流水线中相关的基本概念

1.什么是顺序流动与异步流动

流水线中任务是从输入端流入，于输出端流出。一般来说，先流入流水线的任务，则先于输出端流出。但是，由于要处理的任务有简单、有复杂，执行时间有多少，即可能发生超越现象，还有任务在流水线中，由于某种原因有一段时间没有流动。因此，有可能发生任务流入流水线的顺序与任务流出流水线的顺序不一样。顺序流动是指任务从流水线流出的次序同它们流入流水线的次序一样。异步流动是指任务从流水线流出的次序同它们流入流水线的次序不一样，也称为乱序流动或错序流动。

第四节流水线中的相关及其处理2.流水线中的相关及其分类

相关是指程序中指令之间存在的相互依赖关系，是程序固有的一种属性。而某一次相关是否导致实际冲突的发生以及该冲突所带来的流水线停顿时间，则是流水线的属性。流水线中的相关是指程序中指令之间存在的可能影响指令流水线连续流动执行的某种关系，这种相关一般有三大类，即资源（结构）相关、数据相关和控制相关。数据相关与资源相关由于它对程序执行过程影响较小，仅涉及相应指令的前后一条或几条指令的执行，所以又称为局部相关；控制相关由于它对程序执行过程影响较大，可能改变程序的执行方向，所以又称为全局相关。

第四节流水线中的相关及其处理控制相关数据相关指令相关变址相关操作数相关：先写后读、先读后写、写—写流水线的相关资源相关：主存相关、操作部件相关转移相关：无条件、一般条件、复合条件、循环中断相关

第四节流水线中的相关及其处理3.数据相关及其类型分析

数据相关是指在流水线的机器中，程序中相近的两条指令要对同一存储单元进行操作时，应有一定的先后次序，否则会导致数据供求关系上的冲突，引发程序执行错误。从存储单元的操作次序来看，数据相关有“先写后读”相关、“先读后写”相关和“写—写”相关三种。存储单元存储的内容一般有指令、操作数和地址（一般是地址信息的一部分，可称之为变址），因此，从存储单元存储的内容来看，数据相关有指令相关、操作数相关和变址相关三种。指令相关一定是前面一条指令要修改或产生在其后的指令，变址相关一定是前面一条指令要产生在其后指令的部分地址信息（如基址或变址），因此，指令相关和变址相关从操作次序上属于“先写后读”相关。操作数相关从操作次序上来讲可以任意，因此操作数相关则有“先写后读”相关、“先读后写”相关和“写后写”相关三种。

第四节流水线中的相关及其处理4.控制相关及其分类

控制相关是指在流水线的机器中，由于转移指令或中断引起程序执行方向的改变，使得转移指令或中断引起的断点指令与后续指令不能同时在流水线中执行。它包括转移相关和中断相关两种。转移指令一般可分为无条件转移指令、一般条件转移指令、复合条件转移指令和循环转移指令，因此，从转移指令的条件来看，转移相关有无条件转移相关、一般条件转移相关、复合条件转移相关和循环转移相关四种。5.相关处理及其基本思想

由于程序中相关的存在，就限制了流水线并行执行指令，如何克服相关对并行执行指令的限制则是相关处理。相关处理的充分条件是保证程序顺序，所谓程序顺序是指由原来程序确定的完全串行方式下指令的执行顺序。但并不是存在相关的指令一定要保证程序顺序，只有可能导致错误时，才必须保证程序顺序，即相关处理的必要条件是保证语义顺序。这就为消除相关、提高并行执行指令的程度提供了基础。相关处理的基本思想有两种，一是避免发生冲突，即相关仍然存在；二是消除相关，即相关不存在了。流水线处理机的实际CPI等于理想流水线CPI加上各类停顿的时钟周期数。即：

CPI实际=CPI理想＋停顿资源冲突＋停顿数据冲突＋停顿控制冲突其中理想流水线的CPI是流水线性能指标的最大值。那么，流水线中的相关处理实质是减少停顿的时钟周期数。第四节流水线中的相关及其处理第四节流水线中的相关及其处理二、资源相关

1.资源相关及其形成

资源相关是指相近的多条指令进入流水线后，同一时间争用同一功能部件从而发生的冲突或争用现象。在指令流水线中，指令在执行（操作）部件的延迟时间一般比其它功能部件要长且不相同，存储部件在指令执行过程中可能多次要被访问，争用现象一般发生在操作部件和存储部件上。因此，资源相关一般可分为主存相关和操作部件相关。

假设指令执行过程为取指令、译码、执行和写结果，执行部件一般是由定点算术逻辑部件（ALU，延迟时间为2个时钟周期）、浮点数加法部件（FADD，延迟时间为3个时钟周期）、浮点乘除法部件（FMDU，延迟时间为4个时钟周期）、图形处理部件（GPU，延迟时间为4个时钟周期）和存取数部件（LSU，延迟时间为1个时钟周期）组成的多功能操作部件，其他功能部件的延迟时间为1个时钟周期。现需要执行以下程序指令：

kFADDRO，R1；RO←（RO）＋（R1）

k+1FMULR2，R3；R2←（R2）×（R3）

k+2FADDR4，R5；R4←（R4）＋（R5）

k+3FMULR6，R7；R6←（R7）×（R8）第四节流水线中的相关及其处理0123456789101213K空间写结果浮点乘浮点加译码取指时间KK+1KK+1KK+1K+1K+2K+2K+2K+3K+2K+3K+3K+3K+2K+3第四节流水线中的相关及其处理

由于k和k+2两条指令都要使用浮点加功能部件，那么在第五个△t时，就会出现浮点加法部件争用的现象。由于k+1和k+3两条指令都要使用浮点乘除功能部件，那么在第六个△t时，就会出现浮点乘除法部件争用的现象。

若现需要执行以下程序指令：

kFADDMEM1，R0，R1；MEM1←（RO）＋（R1）

k+1ADDMEM2，R2，R3；MEM2←（R2）＋（R3）

k+2……k+3……k+4……k+5……

第四节流水线中的相关及其处理01234567K空间写结果定点加浮点加译码取指时间KK+1KK+1K+1K+2K+2K+3K+3K+5KK+4K+4K+1

由于k和k+1指令在第六个△t时都要向存储器写数，k+5指令在第六个△t时要向存储器取指令，从而出现了存储部件争用的现象。第四节流水线中的相关及其处理2.资源相关的处理

对于给定的流水线，当存在资源相关时，为了使流水线正常流动，可以采用延迟执行方法处理。例如，对于图2-30中的操作部件相关，可延迟k+2、k+3条指令进入指令流水线，当k+2条指令在第四个△t、k+3条指令在第六个△t进入指令流水线，则避免了浮点数加法部件和浮点乘除法部件的冲突。当然流水线的吞吐率和效率均下降了。要使流水线效率不下降，就必须对流水线或主存进行改造，以消除资源相关。对于操作部件相关，实际上操作部件是瓶井，流水线瓶井段的解决方法有细分瓶井段或重复设置瓶井段。对于主存相关，实际上是主存访问的冲突，存储访问冲突的解决方法有指令与数据Cache分离、采用多体交叉并行存储器和指令存储预取技术。第四节流水线中的相关及其处理三、操作数相关

1.什么是操作数相关

操作数相关是指在流水线的机器中，程序中相近的两条指令的操作数在同一存储单元而要进行操作时，应有一定的先后次序，否则会导致数据供求关系上的冲突，引发程序执行错误。操作数相关包括“先写后读”相关、“先读后写”相关和“写后写”相关三种。第四节流水线中的相关及其处理三、操作数相关

第四节流水线中的相关及其处理

2.操作数相关的形成假设有一串指令在由8个功能段组成的指令流水线中执行，这一串指令流入的次序是g、h、i、j、k、……。由于在指令流水线中，读操作数段在前，写操作数段在后，因此，“先写后读”相关不仅在流水线异步流动过程中会出现，即使顺序流动也容易形成。“先读后写”与“写—写”相关只有在流水线异步流动过程中才可能形成，顺序流动不会出现。三、操作数相关

第四节流水线中的相关及其处理

2.操作数相关的形成

如果指令h写入结果的目的地址同指令i读取操作数的源地址是同一个存储单元或寄存器，即这两条指令有“先写后读”的要求。如果当指令i到达读段时，指令h还没有到达写段完成写操作数，那么指令i读出的数据就是错误的。

存储单元pOinmlkj（i先写k后写相关）

p（i）Onml kj h（i先读j后写相关）指令：j（i）hg （h先写i后读相关）输入输出12读34567写8第四节流水线中的相关及其处理三、操作数相关

第四节流水线中的相关及其处理

2.操作数相关的形成如果顺序指令i的读操作数和指令j的写操作数是同一个存储单元或寄存器，即这两条指令有“先读后写”的要求。当指令i与其前面的指令h或g存在其它相关，则可采用异步流动方式，即如果指令i以后的指令与进入流水线的全部指令之间都没有相关，那么完全可以仅使相关的指令i暂停流动，而其后的指令依次越过指令i继续向前流动。但是可能出现指令j的写操作数先于指令i的读操作数，那么指令i读取的数据就可能是错误的。显然，“先读后写”相关只有在流水线异步流动过程中才可能形成，顺序流动不会出现。存储单元pOinmlkj（i先写k后写相关）

p（i）Onml kj h（i先读j后写相关）指令：j（i）hg （h先写i后读相关）输入输出12读34567写8第四节流水线中的相关及其处理三、操作数相关

第四节流水线中的相关及其处理

2.操作数相关的形成如果顺序指令i的写操作和指令k写操作是同一个存储单元或寄存器，即这两条指令有“写后写”的要求。若由于其他的相关，采用了异步流动方式，则可能出现指令k先于指令i到达写段，那么该存储单元或寄存器的内容最后是由指令i写入的，而不是按指令流序列的顺序要求由指令k写入的，那么，该存储单元的数据就是错误的。显然，“写—写”相关也是只有在异步流动中才可能形成。存储单元pOinmlkj（i先写k后写相关）

p（i）Onml kj h（i先读j后写相关）指令：j（i）hg （h先写i后读相关）输入输出12读34567写8第四节流水线中的相关及其处理

3.操作数相关的处理

延迟的方法(二种)

一是后读或后写指令及其后的指令停止流动，即使指令j及其后的指令停止在流水线中流动，当指令h流过相应操作段后，指令j及其后的指令才继续流动。这种方法保证了顺序流动，且控制实现比较简单，也不需要对流水线作任何改进，但是降低了流水线的吞吐率和效率。

第四节流水线中的相关及其处理三、操作数相关

3.操作数相关的处理

延迟的方法(二种)

另一是为保持流水线连续流动，则仅使后读或后写一条指令停止流动，即当指令j以后的指令与已进入流水线的全部指令之间都没有相关时，完全可以仅使相关的指令j暂停流动，而其后的指令依次越过指令j继续向前流动，即采用异步流动。采用异步流动方式能提高流水线吞吐率和效率，但是容易出现两种新的相关问题——“写后写”相关和“先读后写”相关，还要解决超越和新出现的两种相关，使控制变得复杂。第四节流水线中的相关及其处理三、操作数相关

设置相关专用通路的方法在一般程序中，“先写后读”相关出现的概率很大。建立相关专用通路的方法是在流水线的读段与写段之间增加一条专用的数据通路，以减少停止流动指令的等待时间，如图所示。输入输出12读34567写8存储单元

专用通路指令：k（j）ih g （h先写j后读相关）第四节流水线中的相关及其处理

设置相关专用通路两种方式：一是设置运算器输出到输入端的专用数据通路，使上一指令的输出结果直接送到运算器的一个输入锁存器，如图所示。另一是利用D型触发器建立通用寄存器到运算器的直接通路，D型触发器可在一个脉冲触发下将输入端状态传递给输出端，这样可实现同一个脉冲触发下运算器的结果立即送到相关的寄存器。

锁存器

锁存器通用寄存器运算器专用通路第四节流水线中的相关及其处理数据重定向的方法（1）对于“先写后读”操作数相关。若先A→B，后B→C，可等效于A→B和A→C，即新增加一条A到C的专用路径，取消原来B到C的路径。这样就可以避免写读相关，或缩短发生写读相关的时间，但没有消除“先写后读”相关。（2）对于“写后写”操作数相关。若先A→B，后C→B，经过数据重定向，改为C→B′。引用变量B则改为引用变量B′。这样就消除了“写后写”相关，即“写后写”不存在先后次序的限制了。（3）对于“先读后写”操作数相关。若先B→A，后C→B，经过数据重定向，让B′存B的内容，则改为B′→A和C→B。这样就消除了“先读后写”相关，即“先读后写”不存在先后次序的限制了。第四节流水线中的相关及其处理例如要执行下列程序指令：

k：LOADF1，Ak+1：FADDF1，F2k+2：FMULF1，F3k+3：STOREB，F1

其中：F1、F2、F3为浮点通用寄存器，A、B是主存储器单元。程序指令执行过程中的数据流程如图2-35（a）所示，图中箭线表示数据传输路径。为了处理“先读后写”数据相关，专门设置了A→FADD、FADD→FMUL、FMUL→B三条通路，撤消了F1→FADD和F1→FMUL二条通路。另外，为了处理“写后写”数据相关，撤消了A→F1和FADD→F1二条通路，数据流程如图2-35（b）所示。第四节流水线中的相关及其处理k+3k+2k+2k+1k+1k+1kFADDABF1FMULF2k+2F3原始数据流程k+1k+2k+3k+2k+1k、k+1FADDABF1FMULF2k+2F3数据重定向后的数据流程

第四节流水线中的相关及其处理四、指令相关

例如以下程序指令：k：storek+1，R0；[k+1]←R0k+1：……

显然，第k+1条指令内容由第k条指令决定。指令相关是指相近的两条指令，后面的指令由前面指令的执行结果来决定（修改或产生后面的指令），使得这两条指令不能同时在流水线上流动，否则后面的指令是无效的。要判断是否产生了指令相关，需要对多条指令地址与多条指令的运算结果地址比较，是极其复杂的。如果发现指令相关，还要让已取到指令缓冲区的相关指令作废，重新取指令，不仅要化费一定的硬件代价，时间损失也很大。所以指令相关的处理方法是在程序中不允许修改指令。第四节流水线中的相关及其处理五、变址相关

例如以下程序指令：k：opB，R0；B←BOPR0k+1：storeR1，B（X＋d）；R1←[（B）＋（X）＋d]k+2：storeR2，B（X）；R2←[（B）＋（X）]其中：R0、R1、R2为通用寄存器，B为基址寄存器，X为变址寄存器。变址相关是