计算机体系结构第三章-1

第三章流水线技术

主要内容3.1重叠执行和先行控制3.2流水线的基本概念3.3流水线的性能指标3.4流水线的相关与冲突

3.5流水线的实现引入提高计算机性能（速度）的两个重要方法：

1.缩短执行每条指令所需的平均周期数CPI。如：RISC技术

2.提高处理机在执行指令中的并行度，即同一时刻中处理机内同时运行多条指令。如：采用流水线技术第三章流水线技术3.1重叠执行和先行控制3.1重叠执行和先行控制一.指令的重叠执行一条指令的执行过程可以粗略地分为：取指令、分析和执行三个阶段，且这个次序是不能改变的。取指令执行分析tTi用Ti表示执行一条指令所需的时间，可以写成：

Ti=t取指令

+t分析

+t执行3.1重叠执行和先行控制

如果连续执行多条指令（一段程序），计算机对前后相邻指令的执行过程可以有两种不同的方式:1.顺序执行方式，即等前一条指令执行完毕，紧接着执行下一条指令。取指分析执行取指分析执行k+1k如果取指令、指令分析和指令执行的时间相等，都是t，则n条指令顺序执行的时间为：T=3nt

优：控制简单。缺：速度慢；功能部件利用率低。3.1重叠执行和先行控制一次重叠执行方式：取指分析执行取指分析执行取指分析执行第k条指令第k+1条指令第k+2条指令如果三个阶段所需时间t相等，n条指令顺序执行的时间为：T=(1+2n)t2.让前后连续的指令在处理机内以重叠的方式执行.优：总执行时间减少近

1/3；功能部件利用率提高。缺：需增加硬件；控制过程更复杂。

二次重叠执行方式：取指k分析k执行k取指k+1分析k+1执行k+1取指k+2分析k+2执行k+2第k条指令第k+1条指令第k+2条指令如果三个阶段所需时间t相等，n条指令顺序执行的时间为：T=（2+n)t优：总执行时间减少近

2/3；功能部件利用率进一步提高。缺：增加硬件；主存冲突。3.1重叠执行和先行控制3.1重叠执行和先行控制二.先行控制技术1．实现重叠执行存在的问题（1）问题一： 需要独立的取指部件，分析部件，执行部件。解决方案:

分别设置对应存储控制器，指令控制器和运算控制器。3.1重叠执行和先行控制（2）问题二：

主存访问冲突取指令，处理机按指令计数器PC的指示访问存储器；分析指令，可能需要从存储器中获取操作数；执行指令，可能要求将结果写回到存储器中。处理机中三个独立的部件可能同时提出对存储器读写的请求，从而发生存储器访问冲突。3.1重叠执行和先行控制解决方案：1）分别设置两个独立的存储器：指令存储器和数据存储器，或一级Cache分为程序Cache和数据Cache，同时工作解决同时读指令和读数据引起的冲突。程序空间和数据空间相互独立并具有独立的指令总线和数据总线的系统结构就称为哈佛结构缺点：结构复杂，需要大量的数据线；对汇编程序员和机器程序员不透明2）多体交叉存储器结构也可减少冲突的发生。3）先行控制技术是最根本的办法在主存和指令分析部件之间增设指令缓冲站（先行指令指令缓冲站）先行指令传冲站组成和工作原理PC1：用于从主存预取指令

每分析完一条指令，就自动向指令缓冲站发出取下一条指令的请求。指令取出之后就把指令缓冲站中的该指令作废。指令缓冲站中存放的指令的条数是动态变化的。

按队列方式工作。只要指令缓冲站不满，它就自动地向主存控制器发取指令请求，不断地预取指令。PC:用来记录当前正在分析的指令的地址3.1重叠执行和先行控制3.1重叠执行和先行控制问题：在复杂的计算机指令系统中，各种指令在分析和执行阶段所需的时间可能有很大的差别。于是，前面对三个阶段所需时间t相等的假设就可能不成立，所得到的节约三分之二时间的结论也被动摇了。下图形象地表示了这种情况所造成的影响。第k条指令分析k执行k第k+2条指令执行k+2分析k+2第k+1条指令分析k+1执行k+1

这种情况可用先行控制技术来缓解。3.1重叠执行和先行控制2．采用先行控制技术的处理机运算控制器

先行指令栈

后行写数栈

先行读数栈存储控制器去主存储器地址线

指令分析器

先行操作栈运算器通用寄存器3.1重叠执行和先行控制

缓冲站实际上是一个以先进先出（FIFO）方式工作的移位寄存器组，上图表示了缓冲栈所处的地位。前置部件的输出不直接送入后置部件，而是通过缓冲栈暂存后才输出。前置部件后置部件缓冲站①②③运算控制器

先行指令栈

后行写数栈

先行读数栈存储控制器去主存储器地址线

指令分析器

先行操作栈运算器通用寄存器3.1重叠执行和先行控制3．先行控制原理通过先行指令计数器PC1预取指令序列通过现行指令计数器PC取出现行指令指令分析器指令分析器:对取自先行指令栈的指令进行预处理.1.对于程序控制类的指令，如转移指令，指今分析器可以直接完成指令的执行.2.对于数据运算型指令，指令分析器要将它们变换成寄存器-寄存器（RR型）指令，即将操作数预先存到寄存器中，使指令能快速执行.立即寻址传数据变址寻址或存储器型指令,传地址RR*指令3.1重叠执行和先行控制先行控制技术中采取了两个根本的措施：指令预处理技术和缓冲技术。由于指令和数据的缓冲，保证了指令分析和指令的执行都能全速地运行。第k条指令分析k执行k第k+2条指令执行k+2分析k+2第k+1条指令分析k+1执行k+1第k条指令分析k执行k第k+2条指令执行k+2分析k+2第k+1条指令分析k+1执行k+1改进前改进后3.2流水线的基本概念3.2流水线的基本概念一.什么是流水线1.流水线技术（pipelining）把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度(PipelineDepth)。3.2流水线的基本概念2．流水线结构重叠执行是流水线结构的思想基础，只要在指令分析器与指令执行部件之后都加上一个锁存器，就成了一个简单的流水线结构。

指令执行部件

指令分析器锁存器锁存器分析k+1执行kΔt2Δt1

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

横轴表示时间，即各条指令在处理机中经历各个操作时占用的时间段。

纵轴表示空间，即流水线的各个子操作过程，通常也称为“功能段”。k·Δt(n-1)Δtn-1123………nn-1123………nn-1123………nn-1123………n时间空间S1S2S3S4n-1123………nS5填入填满排空通过时间排空时间3.2流水线的基本概念4．流水线的工作特点1）一条流水线通常由多个流水段组成，在每一个流水段有专门的功能部件来实现。2）各流水段所需的时间应尽可能相等，否则将引起流水线堵塞、断流。时间较长的段将成为流水线瓶颈。3）流水线每个功能部件后面都有一个缓冲寄存器，称为流水寄存器。4）流水线的工作一般分为3个阶段，即填入(建立)、填满和排空。5）流水线技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。3.2流水线的基本概念二.流水线的种类1.按处理机分类（1）操作部件级为最低级别的流水线。是把处理机的算术逻辑运算部件分段。如果某一部件的处理过程比较复杂，如浮点运算,需要较长的时间。这时可以将该部件分为若干子部件，分别完成浮点运算中有关的子操作，这种在部件范围内形成的流水线称为操作部件级流水线。3.2流水线的基本概念例如：一个浮点加法部件的流水线：求阶差对阶尾数加规格化入出部件级流水线通常是流水线处理机中的一部分，这时的处理机由于流水级数较多，又称为超流水线处理机。3.2流水线的基本概念（2）处理机级又称为指令流水线，就是将一条指令的解释执行过程分解成若干个子过程，使每个子过程分别在一个部件中完成。取指令译码执行存结果入出3.2流水线的基本概念

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

处理机2M

处理机nM

输出

处理机1M输入

任务1

任务2

任务n3.2流水线的基本概念2.按流水线功能多少分类（1）单功能流水线指一条流水线只能完成一种单一的任务。（2）多功能流水线指能够在一个时间段内或不同时间段间改变部件之间的连接，从而达到改变其功能的流水线。在标量运算中，各种运算是混在一起的。例如：ASC处理机，运算流水线（浮点加减法运算+定点乘法运算）ASC处理机的多功能流水线3、按照工作方式分类（1）静态流水线当执行某一规定功能的指令全部流出后，才允许改变部件间连接的流水线。3.2流水线的基本概念（可以是单功能流水线也可以是多功能流水线）3.2流水线的基本概念（2）动态流水线没有这种时间上的限制，可以在任何时候根据需要改变其连接。（只能是多功能流水线）3.2流水线的基本概念4.按连接方式分类（1）线性流水线是指在部件上没有反馈连接的流水线。在这种流水线中，指令依次通过各个部件仅一次，完成指令执行的全过程。目前所使用的流水线绝大部分都是这类线性流水线。（2）非线性流水线是指在各部件除了串行的连接外，还通过反馈线使某些部件得以重复使用。指令在通过这种流水线时，可能在反馈部件上重复运行若干次。3.2流水线的基本概念反馈回路S1S2S3入出S3××××S1S2时间非线性流水线工作特性示意图3.2流水线的基本概念5.按流入流出顺序分类（1）顺序流水线其输出的结果与输入的次序相同，早期的流水线又称为顺序流水线。（2）乱序流水线将原始的输入次序打乱，以最有利于处理机执行的方式运行，在输出结果时才恢复原次序。在一些现代处理机中，如Pentium4在流水线运行过程中采用了乱序方式。3.2流水线的基本概念除了上述几种分类方法以外，还可以根据各种不同的观点对流水线进行区分。比如：按照数据表示方式的不同，可以将流水线分为标量流水线和向量流水线两种。在标量处理机中使用的当然是标量流水线。根据流水线在各级之间流动时的控制方法不同，又可以分成同步和异步两种流水线。处理机内的指令流水线都是同步流水线，即使用统一的时钟控制各级同时开始同时完成动作。而处理机间的流水线通常都是异步流水线，需要在任务传送时进行应答，以确保传输的可靠性。课后练习(下面的练习可以巩固你的知识！)1.如果一条指令的执行需要取指、译码和执行三个过程，每一级分别需要Dt，2Dt和3Dt。画出按顺序执行、一次重叠、二次重叠及先行控制四种方式工作时的时空图。3.3流水线的性能指标3.3流水线的性能指标

吞吐率、加速比和效率是表明流水线性能的主要指标。一.吞吐率定义：在单位时间内流水线所完成的任务数量。kTnTP=n：任务总数Tk：处理完成n个任务所用的时间3.3流水线的性能指标1.各段执行时间相等的流水线一条k段的流水线完成n个任务的时空图:所需总时间为：最大吞吐率为:ttnknTPnD=D-+=¥®1)1(limmax实际吞吐率为:tnknTPD-+=)1(3.3流水线的性能指标

分母Tk

：当n→∞时,（k–1）可以忽略不计，Tk→n·△t

只有当n>>k时，才有TP≈TPmax。

2.各级执行时间不等的流水线执行时间不等的流水线时空图3.3流水线的性能指标n12…3123n…n…321312n…(n-1)Δt2Tk时间空间S4S3S2S1各段时间不等的吞吐率:同样，当n→∞时的最大吞吐率为：å=DDD-+D=kikitttntnTP121),,,(max)1(…),,,(max121maxktttTPDDD=…3.3流水线的性能指标3.流水线瓶颈问题如果流水线中各级的执行时间不相等，其中时间最长的段就成了流水线中的“瓶颈”。瓶颈问题对流水线的吞吐率影响是明显的，所以消除“瓶颈”是设计流水线的一个重要原则。“瓶颈”问题的消除采用的方法主要有两种：1）分割瓶颈部件的工作2）重复设置瓶颈部件3.3流水线的性能指标3.3流水线的性能指标消除“瓶颈”影响的两种方法示意图：ΔtS1S2S3S4Δt3ΔtΔt细分瓶颈段：重复瓶颈段：3.3流水线的性能指标重复设置瓶颈段后的时空图缺点：控制逻辑比较复杂，所需的硬件增加了。不消除“瓶颈”时的吞吐率：两种方式在效果上是可以等效的，在输入n条指令的情况下，实际吞吐率都为：tnntnnTPD+=D-+=)5()16(å=DDD-+D=kikitttntnTP121),,,(max)1(…=63D-+Dtntn)1(=3D+t3nn)(3.3流水线的性能指标3.3流水线的性能指标二.加速比处理同一批任务，不用流水线(顺序执行)与采用流水线所花费的时间之比，称为流水线的加速比。设不使用流水线所用的时间为Ts，使用流水线所用时间为Tk，那么加速比就是：1.流水线各段时间均相等（都是△t）一条k段流水线完成n个连续任务顺序执行n个任务的时间：Ts=n·kΔt采用流水线所需时间为：Tk=(k+n–

1)Δt加速比为：1)1(s-+=D-+D==nknktnktknTTSk

当n>>k,最大加速比：knknkSn=-+=¥®1limmax3.3流水线的性能指标2.流水线的各段时间不完全相等（△ti表示第i段的执行时间）一条k段流水线完成n个连续任务，一条指令的执行时间是各级运行时间之和∑Δti。顺序执行n个任务的时间：Ts=n·∑Δti采用流水线所需时间为：Tk=∑Δti+(n-1)max(Δt1,Δt2,…Δtk,)加速比为：åå==DDD-+DD=kikikiitttnttnS1211),,,(max)1(…3.3流水线的性能指标3.3流水线的性能指标三.效率定义：流水线中的设备实际使用时间与整个运行时间的比值，即流水线设备的利用率。1.假设各级执行时间相等显然，n越大，空闲部件占据的比例就小，流水线表现的效率越高。最高效率为：11limmax=-+=¥®nknEn3.3流水线的性能指标流水线效率等于：注：上式仅适用于各段时间相等流水线。3.3流水线的性能指标2.从时空图上看，效率就是n个任务占用的时空面积和k个段总的时空面积之比。流水线效率的一般公式：（直观，通用）空区个流水线级占用的总时条指令占用的时空区knE=

例如：各级执行时间不等的流水线中的效率åå==DDD-+DD=kikikiitttntktnE1211)],…,(max)1([同样，效率公式：加速比公式：两者相结合得出：E=S/k或S=k·E1-+=nknkS1-+=nknE效率公式：tnknTPD-+=)1(吞吐率公式：1-+=nknE

两者相结合得出：E=TP·Δt或TP=E/Δt3.3流水线的性能指标3.效率与吞吐率、加速比的关系（各级时间相等的流水线）例：一个5级的线性流水线，可完成两个数相加运算。若要进行8个操作数连续相加运算，如何实现？性能如何？分析：

假设M=A+B+C+D+E+F+G+H

首先，选择一种效率较高的运算方法。若按从左至右顺序相加进行运算，效率很低。可采用两两相加：

M=（A+B）+（C+D）+（E+F）+（G+H）12345673.3流水线的性能指标工作时空图：从时空图中看出，由于输入任务的不连续，全部7个任务（加法指令），总共需要18个时钟周期后完成。如每段执行时间均等于Δt，吞吐率TP为：时间空间12345671234567123456712345671234567123184567891011121314151617S5S1S2S3S4M=（A+B）+（C+D）+（E+F）+（G+H）1234567这时流水线的加速比为:而效率达到：时间空间12345671234567123456712345671234567123184567891011121314151617S5S1S2S3S4效率为何仍然不高？整个流水线的效率很低的原因：（1）存在有数据相关，当发生数据相关时，必须等待前一个运算结果产生之后，下一个运算才能开始；（2）流水线有填入与排空部分，当输入到流水线中的任务不多时，填入与排空部分所占的比例比较大。

3.3流水线