研究生入学考试计算机系统结构第三章课件

第三章流水线技术提高计算机性能（速度）的两个重要方法：1.缩短执行每条指令所需的平均周期数CPI，如：RISC技术。2.提高处理机在执行指令中的并行度，即同一时刻中处理机内同时运行多条指令。如：采用流水线技术。第三章流水线技术提高计算机性能（速度）的两个重要方法13.1重叠执行和先行控制一.指令的重叠执行

一条指令的执行过程可以粗略地分为：取指令、分析和执行三个阶段，且这个次序是不能改变的。取指令执行分析tTi用Ti表示执行一条指令所需的时间，可以写成：

Ti=t取指令+t分析+t执行3.1重叠执行和先行控制一.指令的重叠执行取指令执行分析t23.1重叠执行和先行控制

如果连续执行一段程序，计算机对前后相邻指令的执行过程可以有两种不同的选择:1.顺序执行方式，即等前一条指令执行完毕，紧接着执行下一条指令.2.让前后连续的指令在处理机内以重叠的方式执行.取指分析执行取指分析执行k+1k3.1重叠执行和先行控制如果连续执行一段程序，计算机33.1重叠执行和先行控制一次重叠执行方式:二次重叠执行方式:取指分析执行取指分析执行取指分析执行第k条指令第k+1条指令第k+2条指令取指分析执行取指分析执行取指分析执行第k条指令第k+1条指令第k+2条指令如果三个阶段所需时间t相等，N条指令顺序执行的时间为：T=3Nt。一次重叠执行的时间：T=(1+2N)t。二次重叠执行的时间为：T=（2+N)t。3.1重叠执行和先行控制一次重叠执行方式:二次重叠执行方43.1重叠执行和先行控制二.先行控制技术1．实现重叠执行存在的问题（1）问题一：

需要独立的取指部件，分析部件，执行部件。解决方案:设置对应存储控制器，指令控制器和运算控制器。3.1重叠执行和先行控制二.先行控制技术53.1重叠执行和先行控制（2）问题二：

主存访问冲突取指令时，处理机必须按指令计数器的指示访问存储器；分析指令时，可能需要从存储器中获取操作数；执行指令时，也可能要求将结果写回到存储器中。

处理机中三个独立的部件可能同时提出对存储器读写的请求，从而发生存储器访问冲突。3.1重叠执行和先行控制（2）问题二： 63.1重叠执行和先行控制解决方案：1）分别设置两个独立的存储器：指令存储器和数据存储器，或一级Cache分为程序Cache和数据Cache，同时工作解决同时读指令和读数据引起的冲突。程序空间和数据空间相互独立并具有独立的指令总线和数据总线的系统结构就称为哈佛结构缺点：结构复杂，需要大量的数据线，对汇编程序员和机器程序员不透明2）多体交叉存储器结构也可减少冲突的发生。3）先行控制技术是最根本的办法。3.1重叠执行和先行控制解决方案：73.1重叠执行和先行控制在复杂的计算机指令系统中，各种指令在分析和执行阶段所需的时间可能有很大的差别。于是，前面对三个阶段所需时间t相等的假设就可能不成立，所得到的节约三分之二时间的结论也被动摇了。下图形象地表示了这种情况所造成的影响。第k条指令分析执行第k+2条指令执行分析第k+1条指令分析执行这种情况可用先行控制技术来缓解。3.1重叠执行和先行控制在复杂的计算机指令系统中，各种指令83.1重叠执行和先行控制2．采用先行控制技术的处理机运算控制器先行指令栈后行写数栈先行读数栈存储控制器去主存储器地址线指令分析器先行操作栈运算器通用寄存器3.1重叠执行和先行控制2．采用先行控制技术的处理机运算控93.1重叠执行和先行控制

缓冲栈实际上是一个以先进先出（FIFO）方式工作的移位寄存器组，上图表示了缓冲栈所处的地位。前置部件的输出不直接送入后置部件，而是通过缓冲栈暂存后才输出。前置部件后置部件缓冲栈①②③3.1重叠执行和先行控制缓冲栈实际上是一个以先10运算控制器先行指令栈后行写数栈先行读数栈存储控制器去主存储器地址线指令分析器先行操作栈运算器通用寄存器3.1重叠执行和先行控制3．先行控制原理通过先行指令计数器PC1预取指令序列通过现行指令计数器PC取出现行指令指令分析器指令分析器:对取自先行指令栈的指令进行预处理.1.对于程序控制类的指令，如转移指令，指今分析器可以直接完成指令的执行.2.对于数据运算型指令，指令分析器要将它们变换成寄存器寄存器型(RR型)指令，即将操作数预先存到寄存器中，使指令能快速执行.立即寻址传数据变址寻址或存储器型指令,传地址RR*指令运算控制器先行指令栈后行写数栈113.1重叠执行和先行控制先行控制技术中采取了两个根本的措施：指令预处理技术和缓冲技术。由于指令和数据的缓冲，保证了指令分析和指令的执行都能全速地运行。第k条指令分析执行第k+2条指令执行分析第k+1条指令分析执行缓冲栈深度应满足以下关系：

D取指栈≥D操作栈≥D读栈≥D写栈第k条指令分析执行第k+2条指令执行分析第k+1条指令分析执行3.1重叠执行和先行控制先行控制技术中采取了两个根本的措施123.2流水线的基本概念一.什么是流水线1.流水线技术（pipelining）把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。

流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。3.2流水线的基本概念一.什么是流水线133.2流水线的基本概念2．流水线结构

重叠执行是流水线结构的思想基础，只要在指令分析器与指令执行部件之后都加上一个锁存器，就成了一个简单的流水线结构。

指令执行部件指令分析器锁存器锁存器分析k+1执行kΔt2Δt1结果出指令入

在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等，它的作用是保存本流水段的执行结果。3.2流水线的基本概念2．流水线结构指令执行部件指令143．时空图时空图可以直观地表现流水线的工作过程

横轴表示时间，即各条指令在处理机中经历各个操作时占用的时间段。如果各级执行所需的时间相等，在横轴上应表现为等距离的时间段。纵轴表示空间，即流水线的各个子操作过程，通常也称为“功能段”。k·Δt(n-1)Δtn-1123………nn-1123………nn-1123………nn-1123………n时间空间S1S2S3S4n-1123………nS5填入填满排空3．时空图横轴表示时间，即各条指令在处理机中经历各个操作时153.2流水线的基本概念4．流水线的工作特点1）一条流水线通常由多个流水段组成，在每一个流水段有专门的功能部件来实现。2）各流水段所需的时间应尽可能相等，否则将引起流水线堵塞、断流。3）流水线每个功能部件后面都有一个缓冲寄存器，称为流水寄存器。4）流水线的工作一般分为3个阶段，即建立（填入）、填满和排空。5）流水线技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。3.2流水线的基本概念4．流水线的工作特点163.2流水线的基本概念二.流水线的种类1、按处理机分类操作部件级

为最低级别的流水线。是把处理机的算术逻辑运算部件分段。如果某一部件的处理过程比较复杂，如浮点运算,需要较长的时间。这时可以将该部件分为若干子部件，分别完成浮点运算中有关的子操作，这种在部件范围内形成的流水线称为操作部件级流水线。3.2流水线的基本概念二.流水线的种类173.2流水线的基本概念一个浮点加法部件的流水线：求阶差对阶尾数加规格化入出部件级流水线通常是流水线处理机中的一部分，这时的处理机由于流水级数较多，又称为超流水线处理机。3.2流水线的基本概念一个浮点加法部件的流水线：求阶差对阶183.2流水线的基本概念处理机级又称为指令流水线，就是将一条指令的解释执行过程分解成若干个子过程，使每个子过程分别在一个部件中完成。处理机间级

处理机间流水线通常是多处理机系统中对任务采取的一种处理策略。3.2流水线的基本概念处理机级193.2流水线的基本概念

上图是处理机间流水线示意图，图中每个处理机是以任务为单位进行处理的，而处理机间的任务传递则是由公用存储器完成的。应当指出，图中给出的是一个处理的“流水”，并没有涉及更多的硬件结构。实际上这个过程更应该看作是一种任务的调度策略。处理机2M处理机nM

输出处理机1M输入

任务1

任务2

任务n3.2流水线的基本概念上图是处理机间流水线示意图，图203.2流水线的基本概念2、

按流水线功能多少分类单功能流水线

指一条流水线只能完成一种单一的任务。多功能流水线

指能够在一个时间段内或不同时间段间改变部件之间的连接，从而达到改变其功能的流水线。3.2流水线的基本概念2、按流水线功能多少分类213.2流水线的基本概念在标量运算中，各种运算是混在一起的。3.2流水线的基本概念在标量运算中，各种运算是混在一起的。223、按照工作方式分类静态流水线当执行某一规定功能的指令全部流出后，才允许改变部件间连接的流水线。（可以是单功能流水线也可以是多功能流水线）3、按照工作方式分类（可以是单功能流水线也可以是多功能流水233.2流水线的基本概念动态流水线没有这种时间上的限制，可以在任何时候根据需要改变其连接。（只能是多功能流水线）3.2流水线的基本概念动态流水线（只能是多功能流水线）243.2流水线的基本概念4、按连接方式分类线性流水线是指在部件上没有反馈连接的流水线。在这种流水线中，指令依次通过各个部件仅一次，完成指令执行的全过程。目前所使用的流水线绝大部分都是这类线性流水线。非线性流水线是指在各部件除了串行的连接外，还通过反馈线使某些部件得以重复使用。指令在通过这种流水线时，可能在反馈部件上重复运行若干次。3.2流水线的基本概念4、按连接方式分类253.2流水线的基本概念反馈回路S1S2S3入出S3××××S1S2时间非线性流水线工作特性示意图3.2流水线的基本概念反馈回路S1S2S3入出S3××××263.2流水线的基本概念5、按流入流出顺序分类顺序流水线其输出的结果与输入的次序相同，早期的流水线又称为顺序流水线。乱序流水线将原始的输入次序打乱，以最有利于处理机执行的方式运行，在输出结果时才恢复原次序。在一些现代处理机中，如Pentium4在流水线运行过程中采用了乱序方式。3.2流水线的基本概念5、按流入流出顺序分类273.2流水线的基本概念

除了上述几种分类方法以外，还可以根据各种不同的观点对流水线进行区分。比如：按照数据表示方式的不同，可以将流水线分为标量流水线和向量流水线两种。在标量处理机中使用的当然是标量流水线。根据流水线在各级之间流动时的控制方法不同，又可以分成同步和异步两种流水线。3.2流水线的基本概念除了上述几种分类方法以外，还可283.2流水线的基本概念处理机内的指令流水线都是同步流水线，即使用统一的时钟控制各级同时开始同时完成动作。而处理机间的流水线通常都是异步流水线，需要在任务传送时进行应答，以确保传输的可靠性。3.2流水线的基本概念处理机内的指令流水线都是同步流水线，293.3流水线的性能指标吞吐率、加速比和效率是表明流水线性能的主要指标。一.吞吐率把流水线在单位时间内完成的任务量定义为吞吐率。kTnTP=其中,n为完成任务的总数，在指令流水线中就是完成的指令总条数；Tk是完成n个任务所用的时间。3.3流水线的性能指标吞吐率、加速比和效率是表明流水线303.3流水线的性能指标各级执行时间相等的流水线

一条k级的流水线执行n条指令的时空图:tnkTkD-+=)1(n-1123………nn-1123………nn-1123………nn-1123………nk·Δt(n-1)Δtn·Δt(k-1)·ΔtTk时间空间S1S2S3S4所需的总时间为：3.3流水线的性能指标各级执行时间相等的流水线tnkTkD313.3流水线的性能指标

当n→∞时，（k–1）可以忽略不计，得到的最大吞吐率为:ttnknTPnD=D-+=¥®1)1(limmax所以，吞吐率为:tnknTPD-+=)1(3.3流水线的性能指标当n→∞时，（k–1）可以323.3流水线的性能指标各级执行时间不等的流水线执行时间不等的流水线时空图n12…3123n…n…321312n…(n-1)Δt2Tk时间空间S4S3S2S13.3流水线的性能指标各级执行时间不等的流水线执行时间不等333.3流水线的性能指标吞吐率的一般表示式为:同样方法可以得到当n→∞时的最大吞吐率为：å=DDD-+D=kikitttntnTP121),,,(max)1(…),,,(max121maxktttTPDDD=…3.3流水线的性能指标吞吐率的一般表示式为:同样方法可以得343.3流水线的性能指标如果流水线中各级的执行时间不相等，其中时间最长者就成了流水线中的“瓶颈”。瓶颈问题对流水线的吞吐率影响是明显的，所以消除“瓶颈”是设计流水线的一个重要原则。“瓶颈”问题的消除

采用的方法主要有两种：1）分割瓶颈部件的工作2）重复设置瓶颈部件3.3流水线的性能指标如果流水线中各级的执行时间不相等，其353.3流水线的性能指标消除“瓶颈”影响的两种方法示意图：S2-1S2-2S2-3S2(3Δt)ΔtΔt(a)(b)S2-3S2-1S2-2Δt2=3Δt3ΔtS1S2S3S4ΔtΔtΔt两种方式在效果上是可以等效的，在输入n条指令的情况下，实际吞吐率都为：tnntnnTPD+=D-+=)5()16(3.3流水线的性能指标消除“瓶颈”影响的两种方法示意图：S363.3流水线的性能指标不消除“瓶颈”时的吞吐率：两种方式在效果上是可以等效的，在输入n条指令的情况下，实际吞吐率都为：tnntnnTPD+=D-+=)5()16(å=DDD-+D=kikitttntnTP121),,,(max)1(…=63D-+Dtntn)1(=3D+t3nn)(3.3流水线的性能指标不消除“瓶颈”时的吞吐率：两种方式在373.3流水线的性能指标二.加速比处理同一批任务，不用流水线与采用流水线时所花费的时间之比，称为流水线的加速比。如果不用流水线所用的时间为T0，用了流水线所用时间为Tk，那么加速比就是：

S=T0/Tk3.3流水线的性能指标二.加速比383.3流水线的性能指标不用流水线时，每条指令执行时必须在时间上顺序地完成各处理步骤，那么n条指令所需时间就为T0=n·kΔt。而一个采用流水线的处理机所需时间为Tk=(k+n–1)Δt。所以加速比就为1)1(0-+=D-+D==nknktnktknTTSk同样办法可以得到最大加速比knknkSn=-+=¥®1limmax3.3流水线的性能指标不用流水线时，每条指令执行时必须在时393.3流水线的性能指标如果考虑各级执行时间不等的情况时，一条指令的执行时间是各级运行时间之和。在没有流水线时，n条指令应是一条指令的n倍。于是，可得到加速比为åå==DDD-+DD=kikikiitttnttnS1211),,,(max)1(…3.3流水线的性能指标如果考虑各级执行时间不等的情况时，一403.3流水线的性能指标三.效率效率被定义为：空区个流水线级占用的总时条指令占用的时空区knE=n-1123………nn-1123………nn-1123………nn-1123………nk·Δt(n-1)Δtn·Δt(k-1)·ΔtTk时间空间S1S2S3S4各级执行时间相等的流水线效率等于：1)1(-+=D-+D=nkntnkktknE3.3流水线的性能指标三.效率空区个流水线级占用的总时条413.3流水线的性能指标显然，n越大，空闲部件占据的比例就小，流水线表现的效率越高。最高效率为：11limmax=-+=¥®nknEn

通过类似的分析方法，我们也可以得到在各级执行时间不等的流水线中的效率计算方法。

åå==DDD-+DD=kikikiitttntktnE1211)],,(max)1([3.3流水线的性能指标显然，n越大，空闲部件占据的比例就小423.3流水线的性能指标同样，效率公式：加速比公式：两者相结合得出：E=S/k或S=k·E1-+=nknkS1-+=nknE效率公式：tnknTPD-+=)1(吞吐率公式：1-+=nknE两者相结合得出：E=TP·Δt或TP=E/Δt。仅限于各级执行时间相等的流水线3.3流水线的性能指标同样，效率公式：加速比公式：两者相结433.3流水线的性能指标例：一个5级的线性流水线，可完成两个数相加运算。现要进行8个操作数连续相加运算，如何实现？性能如何？分析：若按M=A+B+C+D+E+F+G+H进行运算，效率很低。可改为：M=（A+B）+（C+D）+（E+F）+（G+H）12345673.3流水线的性能指标例：一个5级的线性流水线，可完成两个44工作时空图：从时空图中看出，由于输入任务的不连续，全部7个任务（指令），经过18个时钟周期后完成。如每段执行时间均等于Δt，吞吐率TP为：时间空间12345671234567123456712345671234567123184567891011121314151617S5S1S2S3S4M=（A+B）+（C+D）+（E+F）+（G+H）1234567工作时空图：从时空图中看出，由于输入任务的不连续，全部7个任45这时流水线的加速比为:而效率达到：时间空间12345671234567123456712345671234567123184567891011121314151617S5S1S2S3S4效率为何仍然不高？这时流水线的加速比为:而效率达到：时间空间123456712463.3流水线的性能指标整个流水线的效率很低的原因：（1）存在有数据相关，当发生数据相关时，必须等待前一个运算结果产生之后，下一个运算才能开始；（2）流水线有填入与排空部分，当输入到流水线中的任务不多时，填入与排空部分所占的比例比较大。

3.3流水线的性能指标整个流水线的效率很低的原因：47练习：线性多功能静态流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。

用TI－ASC计算机的多功能静态流水线计算两个向量的点积：Z＝AB＋CD＋EF＋GH练习：线性多功能静态流水线，输入任务是不连续的情况，计算流水483.3流水线的性能指标

解：为了尽量减少数据相关性，充分发挥流水线的作用。计算的顺序应该是先做4个乘法：AB、CD、EF和GH，然后做两个加法AB＋CD和EF＋GH，最后求总的结果Z。Z＝{[(AB)＋(CD)]＋[(EF)＋(GH)]}12345763.3流水线的性能指标解：为了尽量减少数据相关性，充分493.3流水线的性能指标

从流水线时空图中看到，用20个时钟周期完成了7个运算。当每一个功能段的延迟时间都为Δt时，3.3流水线的性能指标从流水线时空图中看到，用20个50有：Tk＝20Δt，n＝7。流水线的吞吐率TP为如果采用顺序执行方式，完成一次乘法要用4个Δt

，完成一次加法要用6个Δt

，则完成全部运算要用则流水线的加速比S为：整个流水线共有8段，流水线效率E为：效率更低的原因？有：Tk＝20Δt，n＝7。流水线的吞吐率TP为如果采用51

原因：静态流水线造成加法运算必须在乘法运算所有指令流出流水线后才能进行。

解决：改为动态流水线

课后任务：

采用动态流水线对其性能进行分析原因：静态流水线造成加法运算必须在乘法运算所有指令流出523.3流水线的性能指标四、流水线设计中的若干问题：瓶颈问题当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间。在设计流水线时，要尽可能使各段时间相等。流水线的额外开销流水寄存器延迟时钟偏移开销冲突问题

流水线设计中要解决的重要问题之一。

3.3流水线的性能指标四、流水线设计中的若干问题：533.4流水线的相关与冲突一、一个经典的5段流水线

一条指令的执行过程分为5个周期：取指令周期（IF）、指令译码/读寄存器周期（ID）、执行/有效地址计算周期（EX）、存储器访问／分支完成周期（MEM）、写回周期（WB）。3.4流水线的相关与冲突一、一个经典的5段流水线543.4流水线的相关与冲突三类指令对5级流水线的占用情况:ALU指令LOAD/STOREBRANCHIF(S1)取指取指取指ID(S2)译码,读寄存器堆译码,读寄存器堆译码,读寄存器堆EX(S3)执行计算有效地址计算转移目标地址,设置条件码MEM(S4)--访存(读或写)若条件成立,将转移目标地址送PCWB(S5)结果写回寄存器堆读出数据写入寄存器堆--3.4流水线的相关与冲突三类指令对5级流水线的占用情况:A553.4流水线的相关与冲突5段流水线的两种描述方式第一种描述（类似于时空图）3.4流水线的相关与冲突5段流水线的两种描述方式563.4流水线的相关与冲突第二种描述（按时间错开的数据通路序列）3.4流水线的相关与冲突第二种描述（按时间错开的数据通路序573.4流水线的相关与冲突二、相关相关是指两条指令之间存在某种依赖关系。从对流水线的分析中可以发现，如果流水线始终处于“充满”的状态，实际性能可以达到或接近理论值。如果流入流水线的指令出现断流，将极大地影响流水线的性能。造成断流的原因主要是三大类:

1）名相关2）数据相关3）控制相关3.4流水线的相关与冲突二、相关583.4流水线的相关与冲突1、名相关名：指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。3.4流水线的相关与冲突1、名相关593.4流水线的相关与冲突指令j（在后）与指令i（在前）之间的名相关有两种：反相关：如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关。

指令j写的名＝指令i读的名如：

DIV.D F2，F6，F4ADD.D F6，F0，F123.4流水线的相关与冲突指令j（在后）与指令i（在前）之间603.4流水线的相关与冲突输出相关：如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。

指令j写的名＝指令i写的名名相关的两条指令之间并没有数据的传送。如果一条指令中的名改变了，并不影响另外一条指令的执行。但名相关的两条指令之间的执行顺序必须严格遵守。3.4流水线的相关与冲突输出相关：如果指令j和指令i写相同61解决方法:换名技术：通过改变指令中操作数的名来消除名相关。例如：考虑下述代码：

DIV.D F2，F6，F4ADD.D F6，F0，F12SUB.D F8，F6，F14

DIV.D和ADD.D存在反相关。进行寄存器换名（F6换成S）后，变成：DIV.D F2，F6，F4ADD.D S，F0，F12SUB.D F8，S，F14解决方法:623.4流水线的相关与冲突2、数据相关对于两条指令i（在前）和j（在后），如果下述条件之一成立，则称指令j与指令i数据相关。

指令j使用指令i产生的结果；指令j与指令k数据相关，而指令k又与指令i数据相关。数据相关具有传递性。数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。3.4流水线的相关与冲突2、数据相关63例如：下面这一段代码存在数据相关Loop：L.DF0，0（R1） //F0为数组元素

ADD.DF4，F0，F2 //加上F2中的值

S.D0（R1），F4

//保存结果DADDIUR1，R1，－8//数组指针递减8个字节BNER1，R2，Loop//如果R1≠R2，则分支3.4流水线的相关与冲突例如：下面这一段代码存在数据相关3.4流水线的相关与冲突64当数据的流动是经过寄存器时，相关的检测比较直观和容易。当数据的流动是经过存储器时，检测比较复杂。相同形式的地址其有效地址未必相同。形式不同的地址其有效地址却可能相同。3.4流水线的相关与冲突当数据的流动是经过寄存器时，相关的检测比较直观和容易。3.4653.4流水线的相关与冲突3、控制相关控制相关是指由分支指令引起的相关。典型的程序结构是“if-then”结构。控制相关带来了以下两个限制：与一条分支指令控制相关的指令不能被移到该分支之前，否则这些指令就不受该分支控制了。如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。3.4流水线的相关与冲突3、控制相关663.4流水线的相关与冲突三、流水线冲突流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突有3种类型：结构冲突数据冲突控制冲突3.4流水线的相关与冲突三、流水线冲突673.4流水线的相关与冲突（一）结构冲突

指多条指令进入流水线后，在同一时间争用同一功能部件，从而发生冲突。12345678指令LOADIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3

IFIDEXMEMWB指令i+4IFIDEXMEM访存冲突3.4流水线的相关与冲突（一）结构冲突1683.4流水线的相关与冲突3.4流水线的相关与冲突693.4流水线的相关与冲突解决方法：暂停一拍（也称为流水线气泡，简称气泡）。123456789指令LOADIFIDEXMEMWB指令i+1IFIDEXMEMWB指令i+2IFIDEXMEMWB指令i+3

停顿

IFIDEXMEMWB指令i+4IFIDEXMEM3.4流水线的相关与冲突解决方法：暂停一拍（也703.4流水线的相关与冲突3.4流水线的相关与冲突713.4流水线的相关与冲突（二）数据冲突

1、数据冲突指由于流水线中各指令重叠执行，使得原来对操作数的访问顺序发生变化，从而引起的一种数据冲突。如：DADDR1，R2，R3DSUBR4，R1，R5123456DADDIFIDEXMEM

WBDSUBIFIDEXMEMWB写R1读R13.4流水线的相关与冲突（二）数据冲突1723.4流水线的相关与冲突2、解决办法采用定向传送技术（旁路技术或相关专用通路技术）。IFIDEXMEMWBDSUBIFIDEXMEM

WBDADD123456写R1读R1ALU运算结果目标RALU操作数寄存器旁路传送3.4流水线的相关与冲突2、解决办法733.4流水线的相关与冲突3.4流水线的相关与冲突743.4流水线的相关与冲突3、数据冲突类型根据指令对同一寄存器读和写的先后顺序，数据冲突可分为三种类型：1）RAW（读超前于写）指令入出12345读数写数kjiRi指令:写数j指令:读数解决方法一：按序流动（顺序流动）的流水线中，用定向传送技术。指流水线中流出的结果与流入指令的次序是一致的。3.4流水线的相关与冲突3、数据冲突类型指令入出1234575但是，定向技术并不能解决所有RAW冲突。

如装入延迟：LDR1，0（R2）DADDR4，R1，R5ANDR6，R1，R7XORR8，R1，R9但是，定向技术并不能解决所有RAW冲突。76解决方法二：增加流水线互锁硬件，插入“暂停”。作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。

解决方法二：增加流水线互锁硬件，插入“暂停”。77解决方法三：指令调度（流水线调度）前提：在非按序流动方式（乱步流动）的流水线中。具体实现：通过编译使某些指令的运行结果可能先于j指令流出，情况如下:指允许输出结果的次序与输入指令的次序不同。lkikjil指令入出12345读数写数Ri指令:写数j指令:读数解决方法三：指令调度（流水线调度）指允许输出结果的次序与输入783.4流水线的相关与冲突由于允许非按序执行，使流水线的停顿时间大为减小，有利于提高流水线的吞吐率和效率。但同时还应该注意可能由此引起的另两种冲突:2）WAR（写超前于读）原程序要求对同一单元进行先读后写的操作，可能因为非按序执行成为先写后读，造成出错。3）WAW（写后写）原程序中如果两条指令都要对同一单元进行写数操作，可能因为非按序执行的原因，改变了两条指令写入的次序。

3.4流水线的相关与冲突由于允许非按序执行，使流水线的停顿793.4流水线的相关与冲突（三）控制冲突1、控制冲突流水线遇到分支指令（转移指令）和其他会改变PC值的指令所引起的冲突。分支指令的处理12345678BRANCH(转移)IFIDEXMEM

WB指令i+1

停顿停顿停顿IFIDEXMEM指令i+2停顿停顿停顿IFIDEX指令i+3停顿停顿停顿IFID末尾处更新PC值3.4流水线的相关与冲突（三）控制冲突1803.4流水线的相关与冲突转移指令对流水线的影响

例:设在某一程序中，条件转移指令在程序中所占的比例为25%，其中转移成功的概率为2/3。试计算执行一条指令的平均时钟周期数。解：设执行一条指令的平均时钟周期数为Pi，则Pi=(1-25%)×1+25%×(3+1)=1.753.4流水线的相关与冲突转移指令对流水线的影响813.4流水线的相关与冲突2、有关措施为了减小分支延迟造成的损失，可采用以下措施：1）在流水线中尽早判断出分支转移是否成功。2）尽早计算出分支目标地址。两种措施同时采用，缺一不可。假设该两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。3.4流水线的相关与冲突2、有关措施823.4流水线的相关与冲突为了减小分支延迟造成的损失，还可通过软件（编译器）来减少分支延迟，常见的有以下几种：（1）预测分支失败允许分支指令后的指令继续在流水线中流动，就好象什么都没发生似的。若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动。若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。3.4流水线的相关与冲突为了减小分支延迟造成的833.4流水线的相关与冲突对于上例：设在某一程序中，条件转移指令在程序中所占的比例为25%，其中转移成功的概率为2/3。试计算执行一条指令的平均时钟周期数。

假设采用预测分支失败，则执行一条指令的平均时钟周期数为Pi为：Pi=(1-25%)×1+25%×1/3×1+25%×2/3×(1+1)≈1.173.4流水线的相关与冲突对于上例：843.4流水线的相关与冲突（2）预测分支成功假设分支转移成功，并从分支目标地址处取指令执行。起作用的前题：先知道分支目标地址，后知道分支是否成功。前述5段流水线中，由于判断分支是否成功与分支目标地址计算是在同一流水段完成，这种方法没有任何好处。3.4流水线的相关与冲突（2）预测分支成功853.4流水线的相关与冲突（3）采用延迟转移技术

方法一：从前调度DADDR1，R2，R3IFR2=0THEN延迟槽……IFR2=0THENDADDR1，R2，R3……3.4流水线的相关与冲突（3）采用延迟转移技术DADD86方法三：由失败处调度方法二：从目标处调度DSUBR4,R5,R6

DADDR1,R2,R3IFR1=0THEN延迟槽DSUBR4,R5,R6

DADDR1,R2,R3IFR1=0THENDSUBR4,R5,R6DADDR1,R2,R3IFR1=0THENDSUBR4,R5,R6延迟槽DADDR1,R2,R3IFR1=0THEN……DSUBR4,R5,R6方法三：由失败处调度方法二：从目标处调度DSUBR4,R87补充：非线性流水线的竞争与调度1、非线性流水线中可能发生的冲突前馈反馈输出S4输入S1S2S3（a）带前馈和反馈的非线性流水线连线图（b）一种假定的预约表

1

2

3

4

5

6

7

8

S1

×

×

×

S2

×

×

S3

×

×

×

S4

×

补充：非线性流水线的竞争与调度前馈反馈输出S4输入88非线性流水线中由于有些段需要在时间上复用，就不能像线性流水线那样逐时段连续地输入指令。把前一条指令输入开始到下一条指令输入为止的时间差，称为启动距离。如果所采用的启动距离不合适，可能会在某些部件的使用上发生冲突。前馈反馈输出S4输入S1S2S3（a）带前馈和反馈的非线性流水线连线图非线性流水线中由于有些段需要在时间上复用，就不能像线性流水线89前馈反馈输出S4输入S1S2S3（a）带前馈和反馈的非线性流水线连线图○○○○○○（b）一种假定的预约表

1

2

3

4

5

6

7

8

S1

×

×

×

S2

×

×

S3

×

×

×

S4

×

前馈反馈输出S4输入S1S2S3（a）带前馈和反馈的非90流水线中任何一部件在同一时间段中只能为一条指令服务，出现争用现象是不允许的。为此必须恰当地选择后一条指令输入的时间，既不使发生冲突，又不致使流水线的效率降低太多。那些会引起冲突的启动距离，被称为禁止启动距离。将在任何时间都不会发生冲突的启动距离称为启动循环。流水线中任何一部件在同一时间段中只能为一条指令服务，出现争用912、最优调度方法为了避免冲突，就要对指令输入流水线的时间进行控制，这个任务就是流水线的无冲突调度。1）根据预约表写出禁止向量禁止向量F是一个流水线中所有禁止启动距离的集合。为了找出所有的禁止启动距离，必须考察各段的复用情况。S1在1，4，7三个时段中使用，从第1时段到第4时段的距离为3Δt（4Δt–1Δt=3Δt），显然这是一个禁止启动距离。○○○○○○

1

2

3

4

5

6

7

8

S1

×

×

×

S2

×

×

S3

×

×

×

S4

×

2、最优调度方法○○○○○○1234567892同样理由，可以得到S1的另外两个禁止启动距离：7Δt–4Δt=3Δt；7Δt–1Δt=6Δt。将这种计算所有打“×”时段之间距离的方法施于其他三个部件，可以得到下面的结果:

S2的禁止启动距离：3Δt S3的禁止启动距离：Δt，3Δt，4Δt 禁止向量F=（1,3,4,6）○○○○○○

1

2

3

4

5

6

7

8

S1

×

×

×

S2

×

×

S3

×

×

×

S4

×

同样理由，可以得到S1的另外两个禁止启动距离：7Δt–493向量规定，如果某启动距离为禁止距离，则该位为“1”，反之则为“0”。于是，根据禁止向量，可以得到与之对应的初始冲突向量。如上例中，禁止向量F=（1,3,4,6），则对应的初始冲突向量C=（101101）。由于第2、5位为“0”，因此，可以与当前指令间隔2拍（2Δt）或5拍调入下一个指令。向量规定，如果某启动距离为禁止距离，则该位为“1”，反之则为942）由禁止向量变换成初始冲突向量用以表示非线性流水线工作时各启动距离特性的二进制序列，称为冲突向量。由预约表上第一条指令工作过程所求得的冲突向量称为初始冲突向量。冲突向量用C=（CmCm-1…C2C1）表示，其中m为禁止向量的最大值，如果执行一条指令需要k个时段，那末m≤k–1。于是，冲突向量的各位就可以理解为C1表示启动距离为1Δt时的冲突情况；C2是启动距离为2Δt时的冲突情况；……2）由禁止向量变换成初始冲突向量953）根据初始冲突向量推算出全部冲突向量按照某一个无冲突启动距离输入后续指令后，由于在流水线中存在一条以上指令，使各部件的使用趋于复杂，也必然造成冲突情况发生改变。为了保证后续指令的正常输入，必须找出所有变化了的冲突向量。根据例子，初始冲突向量C0=（101101），由于第2、5位为“0”，因此，可以与当前指令间隔2拍（2Δt）或5拍调入下一个指令。3）根据初始冲突向量推算出全部冲突向量96若选择第2条指令在2拍后调入流水线：

1

2

3

4

5

6

7

8

S1

×

×

×

S2

×

×

S3

×

×

×

S4

×

○○○○○○○○○第一条指令的当前禁止向量：F=（1-2,3-2,4-2,6-2）=（1，2，4）则此时初始冲突向量应该逻辑右移两位，形成第一条指令的当前冲突向量。如（C0=（101101）），即：若选择第2条指令在2拍后调入流水线：12345697为使第3条指令调入后不与前两条指令发生冲突，新的冲突向量应该是第1条指令的当前冲突向量与第2条指令的初始冲突向量按位进行“或”运算。对C1继续推算新的冲突向量，因为其中只有一个0，后续向量也只有一个。在这个例子中，完成了全部推算后，只找到一个新的冲突向量C1。为使第3条指令调入后不与前两条指令发生冲突，新的冲突向量应该984）画出表示冲突向量迁移的有向图101101101111C1C02554）画出表示冲突向量迁移的有向图101101101111C993.5流水线的实现MIPS的一种简单实现一.实现MIPS指令子集的一种简单数据通路。（P87图3.43）该数据通路的操作分成5个时钟周期取指令指令译码/读寄存器执行/有效地址计算存储器访问/分支完成写回只讨论整数指令的实现（包括：load和store，等于0转移，整数ALU指令等。）3.5流水线的实现MIPS的一种简单实现100[研究生入学考试]计算机系统结构第三章课件1013.5流水线的实现二.一条MIPS指令最多需要以下5个时钟周期：1.取指令周期（IF）

IR←Mem[PC]NPC←PC+42.指令译码/读寄存器周期（ID）

A←Regs[rs]B←Regs[rt]Imm←（（IR16）16##IR16..31）

指令的译码操作和读寄存器操作是并行进行的。原因：在MIPS指令格式中，操作码字段以及rs、rt字段都是在固定的位置。这种技术称为固定字段译码技术。3.5流水线的实现二.一条MIPS指令最多需要以下5个时1023.5流水线的实现3.执行/有效地址计算周期（EX）不同指令所进行的操作不同：存储器访问指令

ALUo←A+Imm寄存器－寄存器ALU指令

ALUo←AfuncB寄存器－立即值ALU指令

ALUo←AopImm分支指令

ALUo←NPC+（Imm<<2）；cond←（A=

=0）将有效地址计算周期和执行周期合并为一个时钟周期，这是因为MIPS指令集采用load／store结构，没有任何指令需要同时进行数据有效地址的计算、转移目标地址的计算和对数据进行运算。3.5流水线的实现3.执行/有效地址计算周期（EX）将有1033.5流水线的实现4.存储器访问/分支完成周期（MEM）所有指令都要在该周期对PC进行更新。除了分支指令，其他指令都是做PC←NPC。在该周期内处理的MIPS指令仅仅有load、store和分支三种指令。（1）存储器访问指令

LMD←Mem[ALUo]

或者Mem[ALUo]←B（2）分支指令

if（cond）PC←ALUoelsePC←NPC3.5流水线的实现4.存储器访问/分支完成周期（MEM）1043.5流水线的实现5.写回周期（WB）不同的指令在写回周期完成的工作也不一样。寄存器－寄存器ALU指令

Regs[rd]←ALUo寄存器－立即数ALU指令

Regs[rt]←ALUoload指令

Regs[rt]←LMD3.5流水线的实现5.写回周期（WB）1053.5流水线的实现不采用单周期实现方案的主要原因1.对于大多数CPU来说，单周期实现效率很低，因为不同的指令所需完成的操作差别相当大，因而所需要的时钟周期时间也大不一样。2.单周期实现时，需要重复设置某些功能部件，而在多周期实现方案中，这些部件是可以共享的。3.5流水线的实现不采用单周期实现方案的主要原因106练习：

在一个如下图所示的线性流水线,各级运行所需的时间如下图中所标。

1）画出该流水线工作时空图。2）如果输入的程序没有数据相关和转移指令，在连续执行10条指令后，计算该流水线的吞吐率和效率。3）提出改进吞吐率、加速比和效率的方法，并计算改进后的性能（即改进后的吞吐率、加速比和效率）。取指Dt译码Dt执行2Dt写回2Dt练习：

在一个如下图所示的线性流水线,各级运行所需的时间如下107解：在一个如下图所示的线性流水线,各级运行所需的时间如下图中所标。取指Dt译码Dt执行2Dt写回2Dt1）画出该流水线工作时空图。时间

0t1t2t3t4t5t6t7t8t9t10t11t12

空间S3S21S1S411122223333nnnn……………………解：在一个如下图所示的线性流水线,各级运行所需的时间如下图1082）如果输入的程序没有数据相关和转移指令，在连续执行10条指令后，计算该流水线的吞吐率和效率。å=DDD-+D=kikitttntnTP121),,,(max)1(…=5/（12Dt）åå==DDD-+DD=kikikiitttntktnE1211)],,(max)1([…=0.625时间

0t1t2t3t4t5t6t7t8t9t10t11t12

空间S3S21S1S411122223333nnnn……………………2）如果输入的程序没有数据相关和转移指令，在连续执行10条指1093）提出改进吞吐率、加速比和效率的方法，并计算改进后的性能（即改进后的吞吐率、加速比和效率）。解:执行分为两级,分别为Dt，写回分为两级，分别为Dt。=0.67/DttnknTPD-+=)1(tn6nD-+=)1(E=TP·Δt=10/15=0.67S=k·E

=43）提出改进吞吐率、加速比和效率的方法，并计算改进后的性能（1103.6向量处理机银河-I巨型计算机银河-II巨型计算机3.6向量处理机银河-I巨型计算机银河-I1113.6向量处理机一.标量处理与向量处理一个既有大小又有方向的量称为向量。

如果有下面的一个向量运算，其中A和B都是N×N的矩阵：3.6向量处理机一.标量处理与向量处理1123.6向量处理机要求计算:C=A×B3.6向量处理机要求计算:C=A×B1133.6向量处理机在标量计算机中，我们可以很容易的编出一段循环程序，进行这个矩阵乘法运算，比如一段用FORTRAN语言编的程序段为：

DO100I=1,N DO100J=1,N C(I,J)=0.0 DO100K=1,N C(I,J)=C(I,J)+A(I,K)*B(K,J)100CONTINUE3.6向量处理机在标量计算机中，我们可以很容易的编114如果将这段程序编译成一个假想的汇编程序表示，就成了一个三重循环的汇编程序：

INITIALIZEI=1,J=1,K=1 10 CLR C(I,J)20LOAD A(I,K) LOAD B(K,J) MUL A(I,K),B(K,J) ADD C(I,J),A(I,K)

//C(I,J)←C(I,J)+A(I,K)×B(K,J) INC K //K←K+1 IF K≤NGOTO20 STORE C(I,J) INC J //J←J+1 IF J≤NGOTO10 INC I //I←I+1 IF I≤NGOTO10 HALT对一个操作数进行操作对一对操作数进行操作如果将这段程序编译成一个假想的汇编程序表示，就成了一115上述操作如果由向量计算机来完成，其可能的程序如下所示：

DO100I=1,N C(I,J)=0.0(J=1:N)DO100K=1,NC(I,J)=C(I,J)+A(I,K)*B(K,J)(J=1:N)100CONTINUE

从形式上看，这两段程序差不多，但是在向量计算机上，不管是单元清零，还是做乘法和加法，一条语句处理的都是N个（或N对）数据，而不是一个或一对。上述操作如果由向量计算机来完成，其可能的程序如下所示：1163.6向量处理机要求计算:C=A×B3.6向量处理机要求计算:C=A×B1173.6向量处理机二.向量处理机的概念与特点1．向量处理机把向量数据表示与流水线结合起来，就构成了向量流水处理机，简称为向量流水机或向量处理机。向量处理机的处理对象是向量元素。3.6向量处理机二.向量处理机的概念与特点1183.6向量处理机2．向量流水处理的特点1）在向量机中，一条向量指令往往针对的是一个向量，因此一条向量指令相当于一个标量循环。2）在向量运算中，每一个结果元素仅与参加运算的元素有关，与上一次运算的值无关。3）若向量指令所要访问的向量元素相邻，则可以将其存储到多体交叉存储器中。4）一般向量机中，允许访问存储器与有效地址的计算流水化，在高档向量机中还允许多个向量操作同时进行，即多向量并行操作。3.6向量处理机2．向量流水处理的特点1193.6向量处理机三．向量处理的几种方式向量处理的对象是一些数组，在实际处理时，可以由编译程序选择不同的处理方式。

假定有一个向量运算，其程序表示如下：

DO100i=1,N,1 100 Fi=Ai²＊B+Di＊(Ai²-Ei)按照处理元素的排列次序，可以把处理方式分为三种。

⑴横向处理方式⑵纵向处理方式⑶纵横处理方式3.6向量处理机三．向量处理的几种方式120

DO100i=1,N,1 100 Fi=Ai²＊B+Di＊(Ai²-Ei)⑴横向处理方式

先取i=1的各数组元素,计算出F1的值,再依次算出Fi的值。⑵纵向处理方式Fi=Ai²*B+Di*(Ai²-Ei)求出整个A²的值，作为第一个运算单元第二个运算单元第三个运算单元⑶纵横处理方式将被处理的数组分割为比较小的数组，在这个较小的数组中进行纵向处理，然后在各小数组处理的基础上进行横向处理。 DO100i=1,N,1Fi=Ai²1213.6向量处理机四.向量处理机的结构1.向量处理机的基本结构包括：标量流水部件：标量功能部件、若干标量寄存器向量流水部件：向量功能部件、向量存取部件、向量寄存器、向量控制器等2.向量处理机的类型存储器-存储器型寄存器-寄存器型3.6向量处理机四.向量处理机的结构1223.6向量处理机功能流水线存储系统译码器指令数据A数据B数据C向量处理机基本结构框图存储器-存储器结构3.6向量处理机功能流水线存储系统译码器指令数据A数据B数1233.6向量处理机在数据通道中加入可变长度的延迟电路方案框图存储器系统地址形成器功能选择向量控制指令指令译码延迟选择可变延迟器可变延迟器功能处理流水线C=AΔBAB3.6向量处理机在数据通道中加入可变长度的延迟电路方案框图1243.6向量处理机AM0M1M2M3M4M5M6M7BC=AΔB运算器流水线结构A

B

CA0A1A2A3A4A5A6A7B0B1B2B3B4B5B6B7C0C1C2C3C4C5C6C7由8个存储器模块组成存储系统的向量处理机3.6向量处理机AM0M1M2M3M4M5M6M7BC=125

假定A和B向量都只有8个元素，运算结果C向量也有8个元素。这个向量处理机的工作过程可以用下图表示。存储器-存储器结构向量处理机的一种工作时空图P4P3P2P1M7M6M5M4M3M2M1M0

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

RA7

RA7

RB7

RB7

W7

W7

RA6

RA6

RB6

RB6

W6

W6

RA5

RA5

RB5

RB5

W5

W5

RA4

RA4

RB4

RB4

W4

W4

RA3

RA3

RB3

RB3

W3

W3

RA2

RA2

RB2

RB2

W2

W2

RA1

RA1

RB1

RB1

W1

W1

RA0

RA0

RB0

RB0

W0

W0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

假定A和B向量都只有8个元素，运算结果C向量也有8个元1263.6向量处理机AM0M1M2M3M4M5M6M7BC=AΔB运算器流水线结构由8个存储器模块组成存储系统的向量处理机A

B

CA0A1A2A3A4A5A6A7B6B7B0B1B2B3B4B5C4C5C6C7C0C1C2C33.6向量处理机AM0M1M2M3M4M5M6M7BC=127改变向量存储方法后可以得到如下的时空图：P4P3P2P1M7M6M5M4M3M2M1M0123456789

10

11

1213改变向量存储方法后的处理机时序图

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

RB5

RB5

RA7

RA7

W3

W3

RB4

RB4

RA6

RA6

W2

W2