流水线原理及其在CPU设计中的应用

第6章流水线原理及其在CPU设计中的应用国家级规划教材张代远计算机组成原理教程（第二版）第6章流水线原理及其在CPU设计中的应用流水线技术是重要的加快处理器运算速度的基本技术之一。本章介绍了流水线的基本概念、原理。线性流水线原理、性能分析非线性流水线原理、性能分析通过模型机给出了CPU指令级流水线的具体实施方案。相关概念及相关处理结构相关数据相关控制相关26.1概述来看一个例子假设有4个工人要到医院去体检，每个人都要按照顺序检查内科、外科、五官科。怎样做？见图示。36.1概述流水线：流水线是一种并行工作方式，它有以下特点：有一批可以重复运行的任务；每一个任务能被分解成多个子任务；使用多个功能部件；不同的功能部件完成不同的子任务；多个功能部件并行运行。46.1概述计算机中怎样引入流水线技术？计算机级流水；处理器级流水；指令级流水。本章研究的是指令级流水线56.2指令流水线概念及指令的重叠运行方式为了能够实现指令级流水工作，必须将指令的整个运行阶段划分成几个子功能段。一种粗略的划分方式为：取指令阶段、译码阶段、执行阶段（见图6.1）。重叠概念：将每一条指令的整个运行阶段分解为更小的功能段，使得多条指令在时间上并行运行，称为时间重叠，简称为重叠。61.顺序运行方式顺序运行方式：设总共有n条指令需要运行。若第i条指令与第i+1条指令的各功能段之间都没有时间上的重叠。当第i条指令与第i+1条指令之间没有等待时间时（见图6.2），这样的串行运行方式称为顺序运行方式。顺序运行方式运行n条指令所用的时间为（见图6.2）6.2指令流水线概念及指令的重叠运行方式(6.1)76.2指令流水线概念及指令的重叠运行方式2.一次重叠运行方式指令的一次重叠：第i条指令与第i+1条指令有一个功能段在时间上重叠，称为指令的一次重叠（见图6.3）。86.2指令流水线概念及指令的重叠运行方式设重叠部分的工作时间相等，则完成n条指令时间为（见图6.3）比较（6.1）式与（6.2）式，当n>1时有(6.2)（6.3）96.2指令流水线概念及指令的重叠运行方式3.二次重叠运行方式指令的二次重叠：第i条指令与第i+1条指令有两个功能段在时间上重叠，称为指令的二次重叠（见图6.4）。106.2指令流水线概念及指令的重叠运行方式如果重叠部分时间相等，则运行n条指令所用的时间为（见图6.4）。显然有（6.4）116.2指令流水线概念及指令的重叠运行方式于是，当n>1时有因此，指令的二次重叠运行速度要高于一次重叠的运行速度；指令的一次重叠运行速度要高于顺序运行的速度。可见，相邻指令重叠段数越多，指令的运行速度就越快。（6.5）126.2指令流水线概念及指令的重叠运行方式指令级流水线指令以流水线方式工作的前提在硬件上能将整个指令的运行阶段分解为一些更小的子功能段；指令也能划分成对应于硬件子功能段的子任务；为了能够完成指令的运行，子功能段的输出数据要能被其他子功能段所使用。因此，需要在各个子功能段之间加上状态部件（见图6.5）。请观察模型机的指令级流水线136.2指令流水线概念及指令的重叠运行方式流水线的瓶颈若各个子功能段的工作时间不相等，则工作时间长的子功能段成为流水线的“瓶颈功能段”。图6.6给出了具有瓶颈功能段的流水线的例子。站在输出端看，整个流水线的速度取决于速度最慢的子功能段，快速子功能段不能充分发挥能力。146.2指令流水线概念及指令的重叠运行方式两个基本概念：指令周期：指令从开始到运行完毕所使用的最短时间，即采用非流水线运行方式下完整运行一条指令的最短时间。流水周期：设流水线方式下，若每一个功能段所需最短时间相等，则该最短时间称为流水周期。若功能段所需时间不等，则选择瓶颈段经历时间作为流水周期。156.3时空图常采用时空图来描述流水线的工作过程。见图6.7。时空图反映了流水线的时间-空间关系。在时空图中，横坐标是流水线的运行时间；纵坐标是流水线的空间，即各子功能段。假设一个浮点流水线加法器可以分解为求阶差、对阶、尾数加、规格化四个子功能段，就可以画出流水线的时空图（见图6.8）。16线性流水线和非线性流水线线性流水线：各个功能段串连，数据从一个功能段输出，流入另一个功能段，每一个功能段流过一次，仅流过一次。见图6.9。非线性流水线：除了串行连接外，还有反馈回路。见图6.10。6.4流水线的分类176.4流水线的分类单功能流水线与多功能流水线单功能流水线：各功能段之间只能进行固定的连接，只完成一种功能。多功能流水线：各功能段之间可以进行不同的连接，实现不同功能。图6.11给出了一个实例18（6.6）吞吐率：指在单位时间内完成任务数量或输出结果数量式中n为任务数；Tk

为k段流水线处理完n个任务所有时间。TP也称为流水线的实际吞吐率。6.5流水线的性能指标与线性流水线性能分析吞吐率的一般定义式19

6.5流水线的性能指标与线性流水线性能分析加速比：顺序工作方式所用时间与流水方式所用时间的比值。式中Tk表示k段流水线按照流水线方式处理完n个任务所需要的时间，Ts为按照顺序运行方式处理完这n个任务所需要的时间。（6.7）加速比的一般定义式206.5流水线的性能指标与线性流水线性能分析效率：流水线的各个功能段的利用率。η的分子是流水线功能段“忙”区占用的面积，分母是“忙”区和“空闲”区的面积之和。图6.12可以帮助理解该公式。（6.8）216.5.1线性流水线的性能分析线性流水线的吞吐率假设线性流水线的各段工作时间相等，记为Δt

，输入的n个任务连续，则一条k段线性流水线的吞吐率TP可以由下面公式计算：（6.10）226.5.1线性流水线的性能分析线性流水线吞吐率的上确界（工程上称为最大吞吐率）因为TP是n的一元函数，而k>1，求导得说明TP(n)是n的严格单调增函数，所以上确界（最大吞吐率）为236.5.1线性流水线的性能分析一般而言，假设某一线性流水线有k个功能段，每个功能段的工作时间分别是Δti（i=1,2,…,k），则其吞吐率为(6.15)246.5.1线性流水线的性能分析具有瓶颈段的线性流水线的吞吐率的上确界是（6.16）256.5.1线性流水线的性能分析事实上，线性流水线的吞吐率要低于最大吞吐率，主要原因：线性流水线存在“装入”和“排空”时间；输入的任务往往是不连续的；程序本身存在数据相关。266.5.1线性流水线的性能分析线性流水线的加速比式中Tk为k段流水线按照流水线的运行方式处理完n个任务所用时间，TS为按照顺序运行方式完这n个任务所用的时间。(6.17)276.5.1线性流水线的性能分析由于k>1，所以

故S(n)是n的严格单调增函数，所以加速比的上确界Smax为(6.18)(6.19)286.5.1线性流水线的性能分析结论：当n>>k时，线性流水线各段工作时间相等的情况下，线性流水线的最大加速比近似等于该线性流水线的段数。根据加速比公式可以画出图6.17的曲线。可以看出n较大时加速比接近于它的渐近线。k越多，它能够获得的加速比理论值越大，但是n实际不可能很大，原因是：296.5.1线性流水线的性能分析实际应用的影响一般程序存在数据相关、转移、中断等情况，使连续输入的n受到限制。物理实现实现成本；寄存器数量；布线长度。306.5.1线性流水线的性能分析一般而言，每个功能段的工作时间为，

则k段线性流水线完成n个连续任务的实际加速比为(6.20)316.5.1线性流水线的性能分析流水线的效率效率反映资源利用率。并行系统效率的一般概念，涉及到可扩展性，等效率函数等概念。326.5.1线性流水线的性能分析各功能段的工作时间相等的线性流水线的效率为上面的效率表达式也是n的严格单调增函数，故其上确界为(6.22)(6.21)336.5.1线性流水线的性能分析各功能段的工作时间不相等的效率(6.23)346.5.1线性流水线的性能分析每一个功能加权后，得到：(6.24)356.5.2线性流水线的特点流水线中处理的必须是连续任务。每一个任务分解为几个有联系的子任务，每一个子任务由一个专门的功能部件实现。每一个功能部件后面都要有一个缓冲寄存器，用于保存本段的运行结果。流水线中各段的时间应尽量相等，否则，产生瓶颈问题。366.6非线性流水线6.6.1引言 非线性流水线中存在回路，不能像线性流水线那样每隔一个流水周期输入一个任务，否则，会出现流水线（或功能部件）冲突问题。非线性流水线的调度就是要提供一个方案，按照该方案所确定的流水周期向流水线中输入新任务，各功能部件都不发生冲突，而且流水线的性能指标达到最高。376.6.2预约表几个名词：流线连接：相邻功能段之间的前向直接连接线。见图6.18的S1到S2和S2到S3之间的连接线。前馈连接：不相邻功能段之间的前向直接连接线。见图6.18的S1到S3之间的连接线。反馈连接：功能段之间的反向连接线见图6.18的S3到S2之间的连接线，S3到S1之间的连接线。386.6.2预约表预约表：图6.19和图6.20画出了图6.18给出的非线性流水线的X功能和Y功能的各个功能段被使用的情况，这两个图中的表就是预约表，描述了一个功能在运行过程中数据流通过流水线的时间与空间（各功能段）之间的关系。396.6.2预约表预约表的行数表示功能段数，列数表示给定功能的运行时间。横坐标表示流水线的工作时间，单位为流水周期。纵坐标表示流水线的功能段。X和Y表示该功能段在这一流水周期处于的工作状态。每一张预约表对应一个特定功能的运行过程。一条非线性流水线一般需要一个结构图和预约图来共同表示。406.6.3启动距离分析启动距离：向一条非线性流水线的输入端输入两个相邻任务之间的流水周期数。禁止启动距离：引起冲突的启动距离。一些启动距离会产生冲突，另一些不会产生冲突。会产生冲突的启动距离实例见例6.1，该例中启动距离为2、5均可产生冲突，预约表分别见图6.21、图6.22。416.6.3启动距离分析禁止向量：将预约表中的每一行中任意两个标记之间的距离都算出，去掉重复的，求得一个10进制数列，将该数列按照递减方式排列成一个向量，称为禁止向量，记为Vf。求出图6.19的禁止向量Vf＝(7,5,4,2)。允许启动距离：不会引起冲突的启动距离。允许启动序列：由允许启动距离构成的数列。426.6.3启动距离分析允许启动循环：当一个启动序列是一个循环数列时，这样的循环数列称为允许启动循环。启动循环的平均允许启动距离：其中dav为启动循环的平均启动距离，C

为启动循环阶，di(i=1,2,...,C)为启动循环的启动距离。恒定循环：一阶启动循环又称为恒定循环。436.6.4迭加原理与无冲突调度方法非线性流水线无冲突调度的目标是找出平均允许启动距离最小的启动循环。根据该原理导出状态图的画法规则。零输入调度向量：某时刻旧任务对后继任务影响综合效果，记为：446.6.4迭加原理与无冲突调度方法零状态调度向量：假设在某一时刻已经进入但还没有流出流水线的任务总是，并假设为空，即只考虑新任务对后继任务调度的影响时，用二进制向量表示，称为零状态调度向量。456.6.4迭加原理与无冲突调度方法

迭加原理：假设在某一时刻已经进入但还没有流出流水线的任务总数是，同时考虑新、旧任务对后继任务调度的影响时，综合效果用二进制向量表示，它是零输入调度向量与零状态调度向量按位求逻辑或的运算结果（证明见教材)466.6.4迭加原理与无冲突调度方法由(6.30)得到递推公式为了保证流水线不冲突，后继任务的调度应该是允许距离，得到：（6.32）（6.31）476.6.4迭加原理与无冲突调度方法将（6.32）式代入（6.31）式得到迭加原理数学表达的递推公式：（6.34）486.6.4迭加原理与无冲突调度方法将（6.32）式代入（6.31）式得到迭加原理数学表达的另一种递推公式：（6.34）式反映了两个相邻任务的调度向量之间的关系，而（6.35）式反映了两个相邻任务的零输入调度向量之间的关系。（6.35）496.6.4迭加原理与无冲突调度方法零状态调度向量的求解方法：先根据预约表求得禁止向量。将零状态调度向量表示成一个维的二进制向量，如果是禁止启动距离，则规定；如果是允许启动距离，则规定，显然总有，对应于最大禁止启动距离（中最大的那个）。506.6.4迭加原理与无冲突调度方法引入记号表示初始调度向量，得到一般无冲突调度方法：(1)将初始调度向量送入一个m+1位具有逻辑右移功能的移位寄存器；(2)当从移位寄存器移出的位为0时，用移位寄存器中的值与零状态调度向量作“按位或”运算，得到一个新的调度向量；516.6.4迭加原理与无冲突调度方法(3)若移位寄存器移出的位为1，不作任何处理；(4)对于(2)和(3)重复m+1次；(5)对于中间形成的每一个新的调度向量，按(2)和(3)的方法做。526.6.4迭加原理与无冲突调度方法无冲突调度方法特殊情况－零状态调度向量是常数根据前面的讨论知道，仅仅考虑作用，即任务刚刚进入流水线时(时刻)，流水线中没有任何其他旧任务（即在时刻流水线为空）时后继任务的调度向量。应该指出的是，如果在流水线的整个工作过程中，预约表没有改变，则与任务无关，即536.6.4迭加原理与无冲突调度方法于是可以将看成常向量，并记为Z。因此有此时(6.34)可以写成：(6.37)546.6.4迭加原理与无冲突调度方法如果假设在第一个X1输入流水线之前，流水线是空的，在这种情况下，满足如下初始条件：此时按照（6.37）式有：(6.38)556.6.4迭加原理与无冲突调度方法根据（6.37）式、（6.38）式得到特殊情况下无冲突调度方法：将零状态调度向量Z送入一个m+1位具有逻辑右移功能的移位寄存器；当从移位寄存器移出的位为0时，用移位寄存器中的值与零状态调度向量做“按位或”运算，得到一个新的调度向量；若移位寄存器移出的位为1，不作任何处理；566.6.4迭加原理与无冲突调度方法对于2和3重复m+1次；对于中间形成的每一个新的调度向量，按2和3的方法做。关于允许启动距离d的讨论576.6.4迭加原理与无冲突调度方法允许启动距离的最大值是：将最大禁止启动距离的范围代入上式有：于是，允许启动距离的取值范围为：(6.39)(6.40)(6.41)586.6.4迭加原理与无冲突调度方法以图6.19为例示例运用迭加原理寻找状态图调度方法：假设一批任务X1,X2,…,Xn要无冲突地输入流水线，并假设在第一个任务X1输入流水线之前，流水线是空的，将第一个任务X1进入时刻作为初始时刻，即T(X1+0)。则零状态调度向量Z=(01011010)就反映了X1刚刚输入流水线后，准备向流水线输入任务X2

的允许和禁止流水周期数。由于Z=(01011010)的1、3、6、8位是0，表示经过1、3、6、8个流水周期后可以无冲突地向流水线输入新任务X2。596.6.4迭加原理与无冲突调度方法于是新任务X2流入流水线地时刻为，这时，流水线中已经存在有两个任务X2和X3，后面的新任务再流入流水线时，在流水线中的冲突情况与任务X2有关，还与已经迁移了d个流水周期的任务X1有关。对于X3的后继任务X4、X4的后继任务X5等等，情况相同。根据迭加原理推出的无冲突调度方法，得到以下几个无冲突调度方案。在下面的例子中，假设算子“→”的优先级高于“∨”的优先级。606.6.4迭加原理与无冲突调度方法启动循环（1,8）启动循环（3）启动循环（6）把上面的工作画在一张图上，可以直观的看出流水线的调度方案。这张图称为状态图。见图6.27。状态图说明了流水线持续输入任务的情况下流水线的允许启动距离状态的变迁。616.7非线性流水线的性能分析6.7.1引言时空图在分析非线性流水线时并不方便，而且不能反映各参数之间的内在联系。本书作者给出了计算非线性流水线参数公式，并给出了各参数之间关系的数学表达式。626.7非线性流水线的性能分析6.7.2非线性流水线的Tk的求法假设任务总数为n。启动循环为(d1+d2+…+dC)，启动距离的个数为C，非线性流水线的功能段数为K，预约表中的标记总数为K1，预约表中的列数为N，每个功能段的运行时间是Δt，Tk表示对某一K段非线性流水线，输入N

个任务时从输入到流出该非线性流水线所经历的时间。636.7非线性流水线的性能分析设某时刻Tstart=t，向流水线输入初始任务，则向流水线输入的第一个新任务的起始时刻是t+d1，向流水线输入的第2个新任务的时刻为t+d1+d2，如此推下去，输入C

个新任务的起始时刻是t+d1+d2+…+dC

，输入C+1个新任务的起始时刻是t+(d1+d2+…+dC)+d1，向流水线输入的第n+1个新任务的起始时刻是646.7非线性流水线的性能分析设总任务为n，分别是X0,X1,…,Xn-1，并设

根据(6.42)式有：其中表示最后一个任务流出流水线的结束时刻，N表示最后一个任务的排空流水周期数由（6.43）式可以得到：(6.43)(6.44)656.7.3非线性流水线的吞吐率、效率、加速比及其关系非线性流水线的吞吐率有以下公式当各段同权时，效率公式为非线性流水线的加速比公式:（6.45）（6.46）（6.47）666.7.3非线性流水线的吞吐率、效率、加速比及其关系由上面几个公式得到非线性流水线的吞吐率、效率、加速比之间的关系:（6.48）（6.49）676.7.3非线性流水线的吞吐率、效率、加速比及其关系通过上面两个公式可以得到线性流水线的对应关系，对于线性有，所以（6.51）（6.50）686.7.3非线性流水线的吞吐率、效率、加速比及其关系定义：输入任务时的非性流水线的吞吐率、效率、加速比分别记为。利用（6.45）式~（6.47）式可以求得：（6.52）696.7.3非线性流水线的吞吐率、效率、加速比及其关系类似的可以求得：（6.53）（6.54）706.7.3非线性流水线的吞吐率、效率、加速比及其关系根据以上公式可以求出这三个参数TPmax、ηmax、Smax

之间的关系。对于给定的流水线，Δt是常数。对于特定的任务，K1、K、N也是常数，因此从(6.52)~(6.54)可以看出三个性能参数取决于平均启动距离dav，并且与dav成反比。不同的调度方案dav是不同的，为了获得TPmax、ηmax、Smax的最大值，应当选择dav最小的方案。716.7.3非线性流水线的吞吐率、效率、加速比及其关系从(6.52)式~(6.54)式可以直接求得线性流水线的相应参数。（6.55）（6.56）（6.57）726.8模型机的指令级流水线模型机流水线的数据路径模型机流水线的控制相关及处理结构相关数据相关控制相关流水线的基本性能问题736.8.1模型机流水线的数据路径在模型机中load指令划分为5个流水周期，它们是IF、ID、EX、MEM、WB周期。图6.30是第4章的一个单周期的数据路径，包括5个阶段：（1）IF：取指令子功能段。（2）ID：指令译码/读寄存器堆子功能段。（3）EX：执行或计算地址子功能阶段。（4）MEM：存储器访问子功能段。（5）WB：写回子功能段。746.8.1模型机流水线的数据路径在图6.30中所示的单周期数据路径中，指令的每一步在图中由左至右映射到数据路径上。写回过程与PC的更新过程是例外，第一种导致数据相关、第二种导致控制相关。根据前面的讨论，为了使得流水线能正常工作，在每一个子功能段的后面应当有一个寄存器，保存该子功能段的输出结果。图6.31画出了这样的寄存器，称为流水线寄存器。需要注意的是写回阶段后面没有流水线寄存器。756.8.1模型机流水线的数据路径为了处理数据相关，需要将指令的源寄存器号和目的寄存器号沿着流水线寄存器向前传递，如图6.32。为了讨论方便，也采用另一种表示流水线数据的路径的方法，这种方法假定每一条指令有它独立的数据路径，然后把这些数据路径放在同一时间轴上表示它们之间的关系。如图6.33所示。766.8.1模型机流水线的数据路径图6.33是一种简化的流水线图形表示。IM表示取指阶段的指令存储器和程序计数器PC等。Reg表示指令译码/读寄存器堆阶段的寄存器堆和符号扩展。ALU表示算术逻辑单元ALU和计算转移地址的加法器Add等。DM表示存储器访问，这一阶段也将转移地址写入PC（如果转移成功）。776.8.2模型机流水线的控制本节介绍如何在流水线的数据路径中加入控制：首先，标识已有的数据路径上的控制信号线。这里采用与第4章中单周期数据路径相同的标识方式（见图4.20和表4.12），如表6.2所示。为了详细说明流水线的控制过程，根据流水线将控制线分成五组：取指令、指令译码/读寄存器、指令执行/地址计算、存储器访问、写回。786.8.2模型机流水线的控制情况分别如下：取指令、指令译码/读寄存器无需设置流水线控制器。指令执行/地址计算：设置信号有RegDst、ALUOp和ALUSrc。存储器访问：设置信号有Branch、MemRead、和MemWrite。写回：设置信号有MemtoReg和RegWrite。796.9相关及其处理

6.9.1相关概念在流水线的体系结构中，关键的性能屏障是存在流水线断流。当一组新的输入不能注入流水线时，就发生断流。这是由于相关引起的。相关是流水线的主要障碍，它使得指令流中下一条指令无法在紧接着的流水周期内运行，相关将会降低流水线可能获得的理想性能。806.9.1相关概念相关有以下几种情况：结构相关 数据相关控制相关816.9.2结构相关结构相关产生原因：一种特定体系结构的实现没有足够的资源支持某些种类的指令在时间上重叠。实例：存储器资源有限，不支持访问存储器指令和取指令的重叠。见图6.36。结果：指令串行化，降低处理器效率。解决方案：断流法（让流水线中的一部分指令正常运行而另一部分指令被延迟运行），见图6.37。826.9.2结构相关常见的结构（资源）相关：资源没有充分重复设置，不足以让流水线中的若干条指令同时运行。如一个流水周期写两次寄存器。部分功能部件没有充分流水运行，一系列使用该部件的指令不能按照每个流水周期前进一拍的速率流水运行。如瓶颈段流水线。836.9.3数据相关数据相关产生原因：流水线中的流水指令改变了操作数的读写顺序，使得顺序与逻辑指令序列不同。将以流水方式运行的指令序列称为流水指令序列，简称流水指令。逻辑指令序列也就是通常意义下的指令序列。846.9.3数据相关实例（PGM6.1）：addR1,R2,R3 //add指令写寄存器R1subR4,R1,R5 //第一个操作数依赖于add指令的运算结果andR6,R7,R1 //第二个操作数依赖于add指令的运算结果orR8,R1,R9 //第一个操作数依赖于add指令的运算结果xorR10,R1,R11 //第一个操作数依赖于add指令的运算结果add指令后的所有指令都用到了add结果，如图6.40所示。856.9.3数据相关数据相关解决方案采用编译技术解决数据相关采用前传技术需要断流的数据相关866.9.3数据相关1.采用编译技术解决数据相关通过编译器禁止像PGM6.1中具有相关性的五条指令，避免数据相关。例如在add和sub之间插入两条没有相关性的指令消除数据相关。若没有这种指令则插入一定数量的nop指令。参看图6.40。

addR1,R2,R3

nop

nop subR4,R1,R5 andR6,R1,R7 orR8,R1,R9

xorR10,R1,R11876.9.3数据相关2.采用前传技术前传技术是将某一指令的操作结果尽快传递给它的后继指令，而不必等到该指令完全运行完毕的一种技术。一般来说，指令只在流水线中的特定功能段和特定的时刻产生操作结果或接受前传。图6.41是一条6段流水线。886.9.3数据相关前传技术是流水线中广泛采用的一种技术，它将流水线中某一个功能段的输出结果超越它的直接前驱功能段，而前向传递给需要该功能段输出数据的其他功能段。图6.47是前传技术的示意图。896.9.3数据相关前传技术在模型机中不仅在R型指令中使用，在其他指令中也使用，例如：PGM6.2

addR1,R2,R3 loadR8,0(R1) storeR8,58(R1)图6.48画出了该序列的所有可能的前传，这些前传可以使得指令序列PGM6.2在流水线中正常流动，而不会断流。906.9.3数据相关3.需要断流的数据相关前传虽然可以解决一些数据相关问题，但并非所有的数据相关都可以采用前传的方法来解决。例如：PGM6.3 loadR1,0(R2) addR3,R1,R4 subR5,R1,R6 orR7,R1,R8就不能通过前传解决。其带前传的流水线数据路径采用简化的图6.50表示。916.9.3数据相关在这种情况下，需要断流流水线，让需要结果的操作一直等到该结果产生为止。图6.51画出了load指令与add指令之间通过断流解决数据相关的简化流水线图。这里，除了需要一个前传单元以外，还需要一个相关检测单元。图6.52给出了相关检测单元和前传单元的流水线连接。926.9.4控制相关控制相关产生原因：流水线中的转移指令（分支指令）或其他改写PC（除PC正常增量以外）的指令造成的相关。控制相关解决方案：转移断流法：一旦发现有转移指令就对该指令之后的直接后继指令进行重新取指令的操作。见图6.53。936.9.4控制相关猜测法：在条件转移指令后，选择一个分支方向，让后继指令进入流水线运行。实现方法是直接取下一条指令，好像转移指令只是一条普通的指令那样，流水线看起来也没有特殊之处。但是只要转移条件满足（即转移成功）时，就需要用空操作代替取来的指令，并到目标地址重新取指令。946.9.4控制相关借助于编译技术：转移延迟技术：在流水线中，转移指令后面加上延迟槽，并在延迟槽中填入适当的指令，以提高流水线吞吐率的一种技术。见图6.58、图6.59。延迟槽深度为1的5段模型机流水线的工作流程如图6.60、图6.61所示。分支取消技术：转移指令带有对分支能否被选中（即转移是否成功）的预测。当预测准确时，延迟槽中的指令像通常那样流水运行，否则就把延迟槽中的指令变成空操作指令。见图6.62、图6.63。延迟槽深度为1的5段模型机流水线的工作流程如图6.64、图6.65。956.10流水线的基本性能问题需要解决的问题流水线增大了CPU的指令吞吐率，但没有减少每一条指令各自的运行时间。限制了流水线的深度。除了流水线延迟引起的限制，流水线的不平衡和流水线的附加开销也引入了某些限制。前者因为时钟不能快于最慢的流水线功能段，后者是因为流水线的延迟和时钟偏移。966.11超标量流水线概念一般的流水线处理器只有一条指令级流水线，流水线除了有装入和排空时间外，还有数据相关、转移等的影响，因此，一般流水线标量处理器每个流水周期平均完成的指令的条数小于1，即它的指令级并行度ILP<l。为了提高指令及并行度，可以采用超标量处理器，使用超标量流水线（superscalarpipelining）。通常把一个流水周期内能够同时发射多条指令的处理器称为超标量处理器。976.12本章小结本章介绍了流水线的基本概念、原理及其在CPU设计中的应用，包括：指令流水线概念及指令的重叠运行方式时空图流水线的分类流水线的性能指标与线性流水线性能分析非线性流水线非线性流水线的性能分析模型机的指令级流水线相关及其处理结构相关数据相关控制相关流水线的基本性能问题超标量流水线概念9899串行工作方式图示内科外科五官科考察一下4个工人在医院体检的两种不同方式100串行工作方式图示W1内科外科五官科101串行工作方式图示W1内科外科五官科102串行工作方式图示W1内科外科五官科103串行工作方式图示W2内科外科五官科104串行工作方式图示W2内科外科五官科105串行工作方式图示W2内科外科五官科106串行工作方式图示W3内科外科五官科107串行工作方式图示W3内科外科五官科108串行工作方式图示W3内科外科五官科109串行工作方式图示W4内科外科五官科110串行工作方式图示W4内科外科五官科111串行工作方式图示W4内科外科五官科112串行工作方式图示内科外科五官科这种工作方式的缺点是什么？答案：效率低113流水工作方式图示内科外科五官科114流水工作方式图示W1内科外科五官科115流水工作方式图示W2W1内科外科五官科116流水工作方式图示W3W2W1内科外科五官科117流水工作方式图示W4W3W2内科外科五官科118流水工作方式图示W4W3内科外科五官科119流水工作方式图示W4内科外科五官科120流水工作方式图示内科外科五官科返回主调处121时间t取指令译码执行图6.1将一条指令分解为取指令阶段、译码阶段、执行阶段122取指令i译码i执行i取指i+1译码i+1执行i+1时间ti：i+1：指令流图6.2指令的顺序运行123取指i译码i执行i取指i+1译码i+1执行i+1取指i+2译码i+2执行i+2时间ti：i+1：i+2：指令流图6.3指令的一次重叠运行方式124取指令i译码i执行i取指令i+1译码i+1执行i+1取指令i+2译码i+2执行i+2指令i：指令i+1：指令i+2：时间t图6.4指令的二次重叠运行方式125取指令IF指令译码ID指令执行EX输入输出IF/IDID/EXEX/OUT图6.5用于流水线的指令的各个子功能段之间应当加寄存器126快速S1快速S2快速S3快速S1慢速S2快速S3慢速S1慢速S2慢速S3输入输入输入快速输出慢速输出慢速输出abc图6.6有“瓶颈”段的流水线127取指令k取指令k+1取指令k+2取指令k+3译码k译码k+1译码k+2译码k+3执行k执行k+1执行k+2执行k+3空间S执行译码取指令时间t时空图的横坐标t表示流水线的执行时间；纵坐标S表示空间，其含义是流水线的各个子功能段，对应于流水线执行指令的各个子过程。在时空图中，流水线的一个子功能段通常也简称为功能段

图6.7时空图：流水线的时间-空间关系图128将浮点流水线加法器分解为求阶差、对阶、尾数加、规格化4个子功能段。图中画出了该流水线的时空图，并假设求阶差、对阶、尾数加、规格化4个子功能段所需要的时间相等求阶差1求阶差2求阶差3求阶差4求阶差5对阶1对阶2对阶3对阶4对阶5尾数加1尾数加2尾数加3尾数加4尾数加5规格化1规格化2规格化3规格化4规格化5求阶差对阶尾数加规格化空间功能块0t1t2t3t4t5

t6t7t8时间t图6.8一条浮点流水线加法器的时空图129

S1、S2、S3分别表示流水线的3个子功能段。输入数据从S1功能段输入，完成操作后由S1功能段输出，并作为S2功能段的输入信号，在S2功能段完成相应的操作后，从S2的另一端输出，再作为S3功能段的输入信号，在S3功能段完成相应的操作后，从S3的输出端输出。从而完成了全部操作，数据流出了流水线。数据在流水线中的各个功能段流过时，每一个功能段都流过1次，而且仅仅流过1次S1S2S3输入输出图6.9一种3个功能段构成的线性流水线130

S1、S2、S3分别表示流水线的3个子功能段。非线性流水线指的是在流水线的各个功能段之间除了有串行的连接之外，还有反馈回路。由于反馈回路的存在，会使得非线性流水线的分析变得复杂。但有时系统中会出现反馈回路，因此，对反馈回路的分析是有着实际应用价值的S1S2S3输入输出图6.10一种3个功能段构成的非线性流水线131a.定点乘法输入求阶差对阶尾数加规格化尾数乘累加输出输入求阶差对阶尾数加规格化尾数乘累加输出b.浮点加法ABAB图6.11多功能流水线132111122223333……………………n-1nn-1n-1n-1nnn空间S1S4S3S2功能段“空闲”区功能段“忙”区功能段“空闲”区Tk图6.12流水线的效率分析133S1输入输出S2S4S3Δt1=ΔtΔt2=3ΔtΔt3=ΔtΔt4=Δt这是一个具有4个功能段的线性流水线。该流水线的各个功能段的工作时间不相等。S1、S3、S4功能段的工作时间为Δt1=Δt3=Δt4=Δt，S2功能段的工作时间为Δt2=3Δt。当线性流水线中各段的工作时间不完全相等时，线性流水线中就存在“瓶颈”段。图中的S2功能段就是这条流水线的“瓶颈段”图6.13一条具有瓶颈段的4个功能段的线性流水线134图6.14具有瓶颈段的线性流水线的时空图图中T1表示第一个任务从进入到流出流水线的时间，即T1=Δt1+Δt2+Δt3+Δt4，Δti

表示功能段Si（i=1,…,4）需要使用的时间S1S2S3S4123…n123…n123…n123…n空间(n-1)maxΔti

T1时间135将线性流水线的“瓶颈”部分再细分，如图所示。即把第二个功能段再分成三个串联起来的子功能段，分别记为S2-1、S2-2、S2-3，这样，每一个功能段及子功能段的延迟时间均为Δt。根据线性流水线的吞吐率的表达式可以知道，这样做可以提高线性流水线的吞吐率S2-1S1S2-2S3S2-3S4S2(3Δt)输出输入图6.15将线性流水线的“瓶颈”段再细分成若干子功能段136S2-1S2-2S2-3S1S3S4Δt1=ΔtΔt3=ΔtΔt4=ΔtΔt2=3Δt输入输出如果“瓶颈”功能段不能再细分时，则采用若干个相同的“瓶颈”功能段并联重复设置的方法来提高线性流水线的吞吐率。其控制逻辑比较复杂，需要设置一个数据分配器和一个数据收集器图6.16“瓶颈”功能段并联重复设置13711248163264128n246810加速比Sk=6k=10图中画出了k=6和k=10两条线性流水线的加速比曲线。可以看出，当n较大时，加速比曲线接近于它的渐进线。线性流水线的段数k越大，其加速比的上确界也越大图6.17线性流水线的加速比曲线138S1输入S2S3X输出Y输出这时一条由三个功能段组成的非线性流水线。有一个输入端，两个输出端。两个输出端分别是X输出端和Y输出端。由于非线性流水线存在反馈连接，因此输出端的位置较为灵活，不必在一定要位于S3功能段的右边图6.18一条三段非线性流水线结构图139时间（流水周期Δt）12345678S3S2S1功能段XXXXXXXX预约表中的X表示在对应的流水周期，相应的功能段处于忙碌状态；而表中的空格则表示在对应的流水周期，相应的功能段处于空闲状态图6.19图6.18的非线性流水线功能X的预约表140时间（流水周期Δt）123456S3S2S1功能段YYYYYY表中的Y表示在对应的流水周期，相应的功能段处于忙碌状态，而表中的空格则表示在对应的流水周期，相应的功能段处于空闲状态图6.20图6.18的非线性流水线功能Y的预约表141S3S2S1时间（流水周期Δt）12345678X1X2X3X1X1X1X2X1X2X2X3X1X2X3X1X4X1X2X3X4X2X3X4X2X3X491011………图中Xi（i=1,2,…）表示按照X功能的预约表，以启动距离2输入的第i个任务。可以看出，在第4个流水周期任务X1和X2同时争用S2功能段，从而产生冲突。这种情况还发生在其它的一些功能段图6.21对图6.19的非线性流水线功能X，2是禁止启动距离142S3S2S112345678X1X1X1X1X1X191011………X1X2X2X1X2X2X2时间（流水周期Δt）图中Xi（i=1,2,…）表示按照X功能的预约表，以启动距离5输入的第i个任务。可以看出，在第6个流水周期任务X1和X2同时争用S1功能段，从而产生冲突。这种情况还发生在其它的一些功能段图6.22启动距离为5时流水线的冲突情况143S3S2S112345678X1X1X1X1X1X191011………X1X2X512131415161718192021X2X2X2X3X2X1X3X4X4X5X3X4X4X5X3X4X4X7重复周期…X2X3X3X4X2X3X5X6X5X5X6X6X7X2X3X4X5X6X5X6重复周期重复周期重复周期对图6.19给出的非线性流水线的功能X，启动序列(3,3,…)构成了一个启动循环图6.23图6.19给出的非线性流水线的功能X的启动循环(3)144图6.24图6.19给出的非线性流水线的功能X的启动循环(6)S3S2S112345678X1X1X1X1X1X191011………X1X312131415161718192021X2X1X2X2X3X2X4X4重复周期…X2X2X2X3X3X3X4X2X2X3重复周期X3对图6.19给出的非线性流水线的功能X，启动序列(6,6,…)构成了一个启动循环145S3S2S112345678X1X1X1X1X1X191011………X3X4X1X2X512131415161718192021X2X2X2X2X2X2X2X1X3X4X3X4X3X4X3X4X3X4X3X4X3X4X5X6X2和X1的启动距离为1X3和X2的启动距离为8X4和X3的启动距离为1，如此等等。X1流出时刻X2流出时刻重复周期…对图6.19给出的非线性流水线的功能X，启动序列(1,8,1,8…)构成了一个启动循环图6.25图6.19给出的非线性流水线的功能X的启动循环(1,8)1461234S3S2S1功能段XXXS4X时间（流水周期Δt）对于允许启动距离p=1的一阶启动循环，其预约表呈对角线形状

图6.26对角线形状的预约表147图6.27图6.19预约表的状态图图中画出了流水线从零状态调度向量到各个调度向量之间的状态迁移。最重要的是启动距离，因为它们给出了流水线的无冲突调度方案。虽然启动距离为8的那些数据可以改成大于8的任何正整数，但是这样做会降低流水线的工作速度，因此图中只保留了数据8。这里m=738010110100101101101111111183686零状态调度向量Z调度向量调度向量148图6.28一个非线性流水线的计算实例t1t2t3t4t5t6S1XXS2XS3XXX149中画出了流水线从零状态调度向量到各个调度向量之间的状态迁移。最重要的是启动距离，因为它们给出了流水线的无冲突调度方案。虽然启动距离为5的那些数据可以改成大于5的任何正整数，但是这样做会降低流水线的工作速度，因此图中只保留了数据5。这里m=4350101001011011111535零状态调度向量Z调度向量调度向量图6.29例6.4预约表的状态图150图6.30单周期数据路径的功能段划分40Mux01PC0Mux11MuxAddress指令存储器ReadReg1ReadReg2WrigeRegWriteDataReadData1ReadData2寄存器堆AddressReadDataWriteData数据存储器符号扩展左移两位AddALUZeroAdd1632

IF功能段 ID功能段 EX功能段 MEM功能段 WB功能段151图6.31单周期CPU的各个功能段之间带有流水线寄存器40Mux01PC0Mux11MuxAddress指令存储器ReadReg1ReadReg2WrigeRegWriteDataReadData1ReadData2寄存器堆AddressReadDataWriteData数据存储器符号扩展左移两位AddIF/ID ID/EX EX/MEM MEM/WBALUZeroAdd1632152图6.32寄存器堆的WriteReg端的写编号来自流水线寄存器MEM/WB，而它是由流水线寄存器ID/EX传递过来的40Mux01PC0Mux11MuxAddress指令存储器ReadReg1ReadReg2WrigeRegWriteDataReadData1ReadData2寄存器堆AddressReadDataWriteData数据存储器符号扩展左移两位AddIF/ID ID/EX EX/MEM MEM/WBALUZeroAdd1632153图6.33流水线数据路径的简化图形表示154图6.34当指令在流水线中传递时控制信号的使用155图6.35在流水线寄存器中带有控制信号的流水线数据路径156图6.36结构相关引起的访问存储器资源冲突157图6.37将指令3推迟（断流）1个流水周期进入流水线，可以解决存储器结构相关问题IFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIF断流ID断流EX断流MEM断流WB断流load指令1指令2指令3断流一个流水周期CC1CC2CC3CC4CC5时间（流水周期数）单端口存储器的load指令引起结构相关时的流水线断流。在流水周期4没有指令进入流水线（正常情况下应该是指令3进人流水线）。当一条指令被断流后，流水线中所有该指令之后的指令都会被断流。流水线中该指令之前的指令还是正常运行。因为读入的指令被断流，断流周期将流过流水线158图6.38将存储器分成指令存储器IM和数据存储器DM以避免访问存储器资源冲突159图6.39将存储器分成指令存储器IM和数据存储器DM来解决存储器资源相关IFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBIFIDEXMEMWBload指令1指令2指令4指令3CC1CC2CC3CC4CC5时间（流水周期数）由于将存储器分成了指令存储器IM和数据存储器DM，存储器访问load指令不会引起结构相关。在流水周期4指令3正常进入了流水线，因此没有产生流水线断流。这种采用资源重复设置的方法是一种解决流水线断流的方案，但是增加了硬件成本160图6.40数据相关的简化流水线图形表示161S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6时间（流水周期）123456S1S2S3S4S5S6S1S2S3S4S5S6指令i指令i+1指令i+2指令i与指令i+1在功能段S3是单周期数据相关，指令i与指令i+2在功能段S3是2周期数据相关图6.41单周期与2周期数据相关发生在S3功能段162图6.42单周期与2周期前传S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6S3功能段单周期前传S1S2S3S4S5S6S3功能段2周期前传S1/S2S2/S3S3/S4S4/S5S5/S6时间（流水周期）123456163S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6时间（流水周期）123456S1S2S3S4S5S6S1S2S3S4S5S6指令i指令i+1指令i+2指令i与指令i+1在功能段3、功能段5是单周期数据相关，指令i、

i+1与指令i+2没有数据相关图6.43单数据相关发生在S3、S5功能段164图6.44单周期与2周期数据相关发生在S3功能段，单周期数据相关还发生在S5功能段S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6时间（流水周期）123456S1S2S3S4S5S6S1S2S3S4S5S6指令i指令i+1指令i+2指令i与指令i+1在功能段3、功能段5是单周期相关，指令i与指令i+2在功能段3是2周期相关165图6.45在流水线的不同功能段出现的单周期与多周期前传S1S2S3S4S5S6S1/S2S2/S3S3/S4S4/S5S5/S6时间（流水周期）123456S3功能段单周期前传S1S2S3S4S5S6S3功能段单周期前传、2周期前传S1/S2S2/S3S3/S4S4/S5S5/S6S5功能段单周期前传S5功能段单周期前传166图6.46模型机EX功能段的1CC前传和2CC前传简图167图6.47前传的流水线简化图形表示168图6.48指令序列PGM5.2的前传数据路径简化图169图6.49含有R型指令前传单元的数据路径PCMuxMuxALUEXMWBMWBWBID/EXEX/MEMMEM/WBMuxIF/IDInstructionMuxRdRtRtRs指令存储器寄存器堆前传单元数据存储器主控制单元R.IF/ID.rsR.IF/ID.rtI.IF/ID.rtR.IF/ID.rdR.EX/MEM.rdR.MEM/WB.rd170图6.50load指令引起的数据相关171图6.51load指令与add指令之间通过断流解决数据相关1726.52带有数据相关检测单元的数据路径

PCMuxMuxMuxALUEXMWBMWBWBID/EXEX/MEMMEM/WBMux0MuxIF/IDInstructionID/EX.MemReadIF/IDWritePCWriteRtRsRdRt.数据存储器R.IF/ID.rsR.IF/ID.rtI.IF/ID.rtR.IF/ID.rdR.EX/MEM.rdR.MEM/WB.rd寄存器堆指令存储器前传单元主控制单元相关检测单元173图6.53转移指令的最简单处理方法的简化流水线图形描述本图是对转移指令最简单处理方法的简化流水线图形描述。当在ID段发现有转移指令后就忽略转移指令的直接后继指令，并计算地址，按新地址重新取指令。这种转移指令的处理方式使得不管转移是否成功，在模型机的5段流水线中都将产生1个流水周期的断流IFIDEXMEMWBIF清空清空清空清空IFIDEXMEMIFIDEXMEMWB转移指令i忽略直接后继转移指令的目标或直接后继转移指令的目标或直接后继+1时间（流水周期数）123456789WBIFIDEXMEMWB转移指令的目标或直接后继+2174图6.54转移的影响原始指令流…ib+k-1…ib+2ib+1ib转移成功………it+2it+1it转移目标新指令流长为k-1的延迟槽ib=转移成功it=转移目标

k=流水线的段数△t=流水周期b=延迟槽的大小ib+k-1ib+k-2…ib+2ib+1ib指令流△t流水周期175图6.55在猜测转移不成功分支策略情况下的流水线工作情况转移指令+1是流水指令序列中转移指令的直接后继指令，也是对应的逻辑指令序列中的转移不成功分支的第一条指令。当在ID段发现转移不成功时，流水线中已经读取到了正确的指令，只需继续运行，流水线不断流IFIDEXMEMWBIFIDEXMEMIFIDEXMEMWB转移不成功转移指令+1转移指令+2转移指令+3时间（流水周期数）12