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

1、第三章第三章 流水线技术流水线技术 主要内容n3.1 重叠执行和先行控制n3.2 流水线的基本概念n3.3 流水线的性能指标n3.4 流水线的相关与冲突 n3.5 流水线的实现u引入引入 提高计算机性能（速度）的两个重要方法： 1. 缩短执行每条指令所需的平均周期数CPI。 如：RISC技术 2. 提高处理机在执行指令中的并行度，即同一时刻中处理机内同时运行多条指令。 如：采用流水线技术第三章第三章 流水线技术流水线技术n3.1 重叠执行和先行控制3.1 3.1 重叠执行和先行控制重叠执行和先行控制一一. .指令的重叠执行指令的重叠执行 一条指令的执行过程可以粗略地分为：取指令、分析和执行三个

2、阶段，且这个次序是不能改变的。取指令取指令执行执行分析分析tTi用Ti表示执行一条指令所需的时间，可以写成： Ti = t取指令取指令 + t分析分析 + t执行执行3.1 3.1 重叠执行和先行控制重叠执行和先行控制 如果连续执行多条指令（一段程序），计算机对前后相邻指令的执行过程可以有两种不同的方式:1. 顺序执行方式，即等前一条指令执行完毕，紧接着执行下一条指令。取指取指分析分析执行执行取指取指分析分析执行执行k+ 1k如果取指令、指令分析和指令执行的时间相等，都是t，则n条指令顺序执行的时间为 ：T=3nt 优：控制简单。优：控制简单。缺：速度慢；缺：速度慢； 功能部件利用率低。功能部

3、件利用率低。3.1 3.1 重叠执行和先行控制重叠执行和先行控制l一次重叠执行方式：取指取指分析分析执行执行取指取指分析分析执行执行取指取指分析分析执行执行第第k条指令条指令第第k + 1条指令条指令第第k + 2条指令条指令如果三个阶段所需时间t相等，n条指令顺序执行的时间为 ：T=(1+2n)t2. 让前后连续的指令在处理机内以重叠的方式执行.优：总执行时间减少近优：总执行时间减少近 1/3； 功能部件利用率提高。功能部件利用率提高。缺：需增加硬件；缺：需增加硬件； 控制过程更复杂。控制过程更复杂。 二次重叠执行方式：取指取指k分析分析k执行执行k取指取指k+1分析分析k+1执行执行k+1

4、取指取指k+2分析分析k+2执行执行k+2第第k条指令条指令第第k + 1条指令条指令第第k + 2条指令条指令如果三个阶段所需时间t相等，n条指令顺序执行的时间为 ：T=（2+n)t优：总执行时间减少近优：总执行时间减少近 2/3； 功能部件利用率进功能部件利用率进 一步提高。一步提高。缺：增加硬件；缺：增加硬件； 主存冲突。主存冲突。3.1 3.1 重叠执行和先行控制重叠执行和先行控制3.1 3.1 重叠执行和先行控制重叠执行和先行控制二二. .先行控制技术先行控制技术1实现重叠执行存在的问题（1）问题一：）问题一： 需要独立的取指部件，分析部件，执行部件。 解决方案: 分别设置对应存储控

5、制器，指令控制器和运算控制器。3.1 3.1 重叠执行和先行控制重叠执行和先行控制（2 2）问题二：）问题二： 主存访问冲突n取指令，处理机按指令计数器PC的指示访问存储器；n分析指令，可能需要从存储器中获取操作数；n执行指令，可能要求将结果写回到存储器中。 处理机中三个独立的部件可能同时提出对存储器读写的请求，从而发生存储器访问冲突。3.1 3.1 重叠执行和先行控制重叠执行和先行控制解决方案：解决方案：1）分别设置两个独立的存储器：指令存储器和数据存储器，或一级Cache分为程序Cache和数据Cache ，同时工作解决同时读指令和读数据引起的冲突。 n程序空间和数据空间相互独立并具有独立

6、的指令总线和数据总线的系统结构就称为哈佛结构哈佛结构n缺点：缺点：结构复杂，需要大量的数据线；对汇编程序员和机器程序员不透明2）多体交叉存储器结构也可减少冲突的发生。3）先行控制先行控制技术是最根本的办法n在主存和指令分析部件之间增设指令缓冲站指令缓冲站（先行指令指先行指令指令缓冲站令缓冲站）n先行指令传冲站组成和工作原理先行指令传冲站组成和工作原理 先行程序计数器先行程序计数器 PC1 现行程序计数器现行程序计数器 PC 指令分析部件指令分析部件 指令寄存器指令寄存器 IR 控制逻辑控制逻辑 主存控制器主存控制器 指令缓冲指令缓冲 存存 储储 区区 PC1PC1：用于从主存预取：用于从主存预

7、取指令指令p 每分析完一条指令，就自动向指每分析完一条指令，就自动向指令缓冲站发出取下令缓冲站发出取下 一条指令的请求。一条指令的请求。指令取出之后就把指令缓冲站中的指令取出之后就把指令缓冲站中的该指令作废。该指令作废。p 指令缓冲站中存放的指令的条数指令缓冲站中存放的指令的条数是动态变化的。是动态变化的。p 按队列方式工作。按队列方式工作。p 只要指令缓冲站不满，它只要指令缓冲站不满，它就自动地向主存控制器发取就自动地向主存控制器发取指令请求，不断地预取指令。指令请求，不断地预取指令。PC: 用来记录当前正用来记录当前正在分析的指令的地址在分析的指令的地址3.1 3.1 重叠执行和先行控制重

8、叠执行和先行控制3.1 3.1 重叠执行和先行控制重叠执行和先行控制n问题：问题：在复杂的计算机指令系统中，各种指令在分析和执行阶段所需的时间可能有很大的差别。于是，前面对三个阶段所需时间t相等的假设就可能不成立，所得到的节约三分之二时间的结论也被动摇了。下图形象地表示了这种情况所造成的影响。第第k条指令条指令分析分析k执行执行k第第k+2条指令条指令执行执行k+2分析分析k+2第第k+1条指令条指令分析分析k+1执行执行k+1 这种情况可用先行控制先行控制技术来缓解。3.1 3.1 重叠执行和先行控制重叠执行和先行控制2采用先行控制技术的处理机运算控制器运算控制器 先先 行行 指指 令令 栈

9、栈 后后 行行 写写 数数 栈栈 先先 行行 读读 数数 栈栈存存 储储 控控 制制 器器去主存储器去主存储器地址线地址线 指指 令令 分分 析析 器器 先行操作栈先行操作栈运运 算算 器器通通 用用 寄寄 存存 器器3.1 3.1 重叠执行和先行控制重叠执行和先行控制n 缓冲站实际上是一个以先进先出（FIFO）方式工作的移位寄存器组，上图表示了缓冲栈所处的地位。前置部件的输出不直接送入后置部件，而是通过缓冲栈暂存后才输出。前置部件前置部件后置部件后置部件缓冲站缓冲站 运算控制器运算控制器 先先 行行 指指 令令 栈栈 后后 行行 写写 数数 栈栈 先先 行行 读读 数数 栈栈存存 储储 控控

10、 制制 器器去主存储器去主存储器地址线地址线 指指 令令 分分 析析 器器 先行操作栈先行操作栈运运 算算 器器通通 用用 寄寄 存存 器器3.1 3.1 重叠执行和先行控制重叠执行和先行控制3先行控制原理通过先行指令计数器通过先行指令计数器PC1预取指令序列预取指令序列通过现行指令计数器通过现行指令计数器PC取取出现行指令出现行指令指令分析器指令分析器指令分析器指令分析器:对取自先行指令栈的指令进行预处理对取自先行指令栈的指令进行预处理.1.对于程序控制类的指令，如转移指令，指今分析对于程序控制类的指令，如转移指令，指今分析器可以直接完成指令的执行器可以直接完成指令的执行.2.对于数据运算型

11、指令，指令分析器要将它们变换对于数据运算型指令，指令分析器要将它们变换成寄存器成寄存器-寄存器（寄存器（RR型）指令，即将操作数预先型）指令，即将操作数预先存到寄存器中，使指令能快速执行存到寄存器中，使指令能快速执行.立即寻址立即寻址传数据传数据变址寻址变址寻址或存储器或存储器型指令型指令,传传地址地址RR*指令指令3.1 3.1 重叠执行和先行控制重叠执行和先行控制n先行控制技术中采取了两个根本的措施：指令预处理指令预处理技术技术和缓冲技术缓冲技术。由于指令和数据的缓冲，保证了指令分析和指令的执行都能全速地运行。第第k条指令条指令分析分析k执行执行k第第k+2条指令条指令执行执行k+2分析分

12、析k+2第第k+1条指令条指令分析分析k+1执行执行k+1第第k条指令条指令分析分析k执行执行k第第k+2条指令条指令执行执行k+2分析分析k+2第第k+1条指令条指令分析分析k+1执行执行k+1改进前改进前改进后改进后n3.2 流水线的基本概念3.2 3.2 流水线的基本概念流水线的基本概念一一. .什么是流水线什么是流水线1. 流水线技术（pipelining）把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。流水线流水线中的每个子过程及其功能部件称为中的每个子过程及其功能部件称

13、为流水线的流水线的级或段级或段，段与段相互连接形成流水线。流水线的段数称，段与段相互连接形成流水线。流水线的段数称为为流水线的深度流水线的深度(Pipeline Depth)。3.2 3.2 流水线的基本概念流水线的基本概念 2流水线结构重叠执行是流水线结构的思想基础，只要在指令分析器与指令执行部件之后都加上一个锁存器，就成了一个简单的流水线结构。 指令执行部件指令执行部件 指令分析器指令分析器锁存器锁存器锁存器锁存器分析分析k+1执行执行k t2 t1 结果出结果出指令入指令入在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等，它的作用是保存本流水段的执行结果。3

14、时空图：可以直观地表现流水线的工作过程 横轴表示时间，即各条指令在处理机中经历各个操作时占用的时间段。横轴表示时间，即各条指令在处理机中经历各个操作时占用的时间段。 纵轴表示空间，即流水线的各个子操作过程，通常也称为纵轴表示空间，即流水线的各个子操作过程，通常也称为“功能段功能段”。 k t (n-1)tn-1n-1 123n nn-1n-1123n nn-1n-1123n nn-1n-1123n n时间时间空间空间S1S2S3S4n-1n-1123n nS5填入填入填满填满排空排空通过时间排空时间3.2 3.2 流水线的基本概念流水线的基本概念4流水线的工作特点1）一条流水线通常由多个流水段

15、多个流水段组成，在每一个流水段有专门的功能部件专门的功能部件来实现。2）各流水段所需的时间应尽可能相等，否则将引起流水线堵塞、断流。时间较长的段将成为流水线瓶颈流水线瓶颈。3）流水线每个功能部件后面都有一个缓冲寄存器，称为流水寄存器。4）流水线的工作一般分为3个阶段，即填入填入( (建立建立) )、填满和填满和排空排空。5）流水线技术适合于大量重复大量重复的时序过程时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。3.2 3.2 流水线的基本概念流水线的基本概念二二. . 流水线的种类流水线的种类1.按处理机分类（1）操作部件级为最低级别的流水线。是把处理机的算术逻辑运算部件分段

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

17、结果入入出出3.2 3.2 流水线的基本概念流水线的基本概念 （3）处理机间级处理机间流水线通常是多处理机系统中对任务采取的一种处理策略。 上图是处理机间流水线示意图，图中每个处理机是以任务为单位进行处理的，而处理机间的任务传递则是由公用存储器完成的。应当指出，图中给出的是一个处理的“流水”，并没有涉及更多的硬件结构。实际上这个过程更应该看作是一种任务的调度策略。 处理机处理机2 M 处理机处理机n M 输出输出 处理机处理机1 M输入输入 任务任务1 任务任务2 任务任务n3.2 3.2 流水线的基本概念流水线的基本概念2.按流水线功能多少分类（1）单功能流水线指一条流水线只能完成一种单一的

18、任务。（2）多功能流水线指能够在一个时间段内或不同时间段间改变部件之间的连接，从而达到改变其功能的流水线。n在标量运算中，各种运算是混在一起的。n例如：ASC处理机，运算流水线（浮点加减法运算+定点乘法运算）ASC处理机的多功能流水线 求求 阶阶 差差 对对 阶阶 相相 加加 规格化规格化 相相 乘乘 累累 加加 输输 出出 1 2 3 4 6 5 7 8 输输 入入 输输 入入 相相 加加 规格化规格化 输输 出出 输输 出出 累累 加加 相相 乘乘 输输 入入 求求 阶阶 差差 对对 阶阶 2 3 4 5 6 7 8 6 7 8 （b）浮点连接）浮点连接 （a）分段）分段 （c）定乘连接）

19、定乘连接 1 1 2 3 4 5 3、 按照工作方式分类（1）静态流水线当执行某一规定功能的指令全部流出后，才允许改变部件间连接的流水线。3.2 流水线的基本概念流水线的基本概念（可以是单功能流水线也可以是多功能流水线）（可以是单功能流水线也可以是多功能流水线）3.2 3.2 流水线的基本概念流水线的基本概念（2）动态流水线没有这种时间上的限制，可以在任何时候根据需要改变其连接。（只能是多功能流水线）（只能是多功能流水线）3.2 3.2 流水线的基本概念流水线的基本概念4.按连接方式分类（1）线性流水线是指在部件上没有反馈连接的流水线。在这种流水线中，指令依次通过各个部件仅一次，完成指令执行的

20、全过程。目前所使用的流水线绝大部分都是这类线性流水线。（2）非线性流水线是指在各部件除了串行的连接外，还通过反馈线使某些部件得以重复使用。指令在通过这种流水线时，可能在反馈部件上重复运行若干次。3.2 3.2 流水线的基本概念流水线的基本概念反馈回路反馈回路S1S2S3入入出出S3S3S1S1S2S2时间时间非线性流水线工作特性示意图非线性流水线工作特性示意图3.2 3.2 流水线的基本概念流水线的基本概念5.按流入流出顺序分类（1）顺序流水线其输出的结果与输入的次序相同，早期的流水线又称为顺序流水线。（2）乱序流水线将原始的输入次序打乱，以最有利于处理机执行的方式运行，在输出结果时才恢复原次

21、序。在一些现代处理机中，如Pentium 4在流水线运行过程中采用了乱序方式。3.2 3.2 流水线的基本概念流水线的基本概念除了上述几种分类方法以外，还可以根据各种不同的观点对流水线进行区分。比如：n按照数据表示方式的不同，可以将流水线分为标量流水线和向量流水线两种。在标量处理机中使用的当然是标量流水线。n根据流水线在各级之间流动时的控制方法不同，又可以分成同步和异步两种流水线。n处理机内的指令流水线都是同步流水线，即使用统一的时钟控制各级同时开始同时完成动作。n而处理机间的流水线通常都是异步流水线，需要在任务传送时进行应答，以确保传输的可靠性。课后练习课后练习 (下面的练习可以巩固你的知识

22、！下面的练习可以巩固你的知识！)1. 如果一条指令的执行需要取指、译码和执行三个过程，每一级分别需要Dt， 2Dt和3Dt。画出按顺序执行、一次重叠、二次重叠及先行控制四种方式工作时的时空图。n3.3 流水线的性能指标3.3 3.3 流水线的性能指标流水线的性能指标 吞吐率、加速比和效率是表明流水线性能的主要指标。一一. .吞吐率吞吐率 定义：在单位时间内流水线所完成的任务数量。kTnTP =n：任务总数Tk：处理完成n个任务所用的时间3.3 流水线的性能指标流水线的性能指标n1. 各段执行时间相等的流水线 一条k段的流水线完成n个任务的时空图: S1 S2 S3 S4 空间空间 时间时间 1

23、 （单位：单位：t） 1 1 1 2 2 2 2 3 3 3 3 n-1 n-1 n-1 n-1 n n n n kt (n-1)t Tk 所需总时间为：tnkTkD=) 1(最大吞吐率为:ttnknTPnD=D=1) 1(limmax实际吞吐率为:tnknTPD=) 1(3.3 流水线的性能指标流水线的性能指标 分母Tk ：当n时,（k 1）可以忽略不计，Tkntq 只有当nk时，才有TPTPmax。 n2. 各级执行时间不等的流水线执行时间不等的流水线时空图3.3 流水线的性能指标流水线的性能指标n123123nn321312n(n-1)t2Tk时间空间S4S3S2S1 D=kiit1各段

24、时间不等的吞吐率吞吐率:同样，当n时的最大吞吐率为：=DDDD=kikitttntnTP121),(max)1(),(max121maxktttTPDDD=3.3 流水线的性能指标流水线的性能指标n3. 流水线瓶颈问题 如果流水线中各级的执行时间不相等，其中时间最长的段就成了流水线中的“瓶颈”。瓶颈问题对流水线的吞吐率影响是明显的，所以消除“瓶颈”是设计流水线的一个重要原则。n“瓶颈”问题的消除 采用的方法主要有两种：1）分割瓶颈部件的工作）分割瓶颈部件的工作2）重复设置瓶颈部件）重复设置瓶颈部件3.3 流水线的性能指标流水线的性能指标3.3 流水线的性能指标流水线的性能指标消除消除“瓶颈瓶颈

25、”影响的两种方法示意图：影响的两种方法示意图：tS1S2S3S4t3tt S1 S2 入入 出出 S4 t t t t t t S3a S3c S3b S1 S3a S2 S3b 入入 出出 S3c S4 t t t 3t 细分瓶颈段 ：重复瓶颈段 ：3.3 流水线的性能指标流水线的性能指标 段段 S3b S3a S2 S3c S4 时间时间 S1 1 6 2 3 4 5 7 1 2 3 4 5 6 7 8 9 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 重复设置瓶颈段后的时空图缺点：控制逻辑比较复杂，所需的硬件增加了。不消除“瓶颈”时的吞吐率：两种方式在效

26、果上是可以等效的，在输入n条指令的情况下，实际吞吐率都为：tnntnnTPD=D=)5() 16(=DDDD=kikitttntnTP121),(max)1(=63DDtntn)1(=3Dt3nn)(3.3 流水线的性能指标流水线的性能指标3.3 流水线的性能指标流水线的性能指标二二. .加速比加速比n处理同一批任务，不用流水线(顺序执行)与采用流水线所花费的时间之比，称为流水线的加速比流水线的加速比。n设不使用流水线所用的时间为T Ts s，使用流水线所用时间为T Tk k，那么加速比就是：ksTTS =n1. 流水线各段时间均相等流水线各段时间均相等（都是t）n一条k段流水线完成n个连续任

27、务n顺序执行n个任务的时间：Ts = nktn采用流水线所需时间为： Tk = ( k + n 1 )tn加速比为：1)1(s=DD=nknktnktknTTSkn 当nk, 最大加速比：knknkSn=1limmax3.3 流水线的性能指标流水线的性能指标n2. 流水线的各段时间不完全相等流水线的各段时间不完全相等（ti表示第i段的执行时间）n一条k k段流水线完成n n个连续任务，一条指令的执行时间是各级运行时间之和ti。n顺序执行n个任务的时间：Ts = ntin采用流水线所需时间为： Tk =ti+(n-1)max (t1, t2, tk, )n加速比为：=DDDDD=kikikiit

28、ttnttnS1211),(max)1(3.3 流水线的性能指标流水线的性能指标3.3 流水线的性能指标流水线的性能指标三三. . 效率效率n定义：流水线中的设备实际使用时间与整个运行时间的比值，即流水线设备的利用率。n1. 假设各级执行时间相等假设各级执行时间相等 S1 S2 S3 S4 空间空间 时间时间 1 （单位：单位：t） 1 1 1 2 2 2 2 3 3 3 3 n-1 n-1 n-1 n-1 n n n n kt (n-1)t Tk n显然，n越大，空闲部件占据的比例就小，流水线表现的效率越高。最高效率为：11limmax=nknEn3.3 流水线的性能指标流水线的性能指标流水

29、线效率等于：kkTtknED=1=nkn注：上式仅适用于各段时间相等流水线。3.3 流水线的性能指标流水线的性能指标2.从时空图上看，效率就是n个任务占用的时空面积和k个段总的时空面积之比。n流水线效率的一般公式一般公式：（直观，通用）空区个流水线级占用的总时条指令占用的时空区knE =n 例如：各级执行时间不等的流水线中的效率 =DDDDD=kikikiitttntktnE1211),(max) 1( S1 S2 S3 S4 空间空间 时间时间 1 （单位：单位：t） 1 1 1 2 2 2 2 3 3 3 3 n-1 n-1 n-1 n-1 n n n n kt (n-1)t Tk n同样

30、，效率公式：加速比公式：两者相结合得出：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+

31、H）12345673.3 流水线的性能指标流水线的性能指标工作时空图：从时空图中看出，由于输入任务的不连续，全部7个任务（加法指令），总共需要18个时钟周期后完成。如每段执行时间均等于t，吞吐率TP为：时间空间12345671234567123456712345671234567 1 2 3 18 4 5 6 7 8 9 10 11 12 13 14 15 16 17S5S1S2S3S4ttTnTPkD=D=1389. 0187M=（A+B）+（C+D）+（E+F）+（G+H）123456794. 11857=DD=ttTTSks这时流水线的加速比为:而效率达到：389. 018557=DD=

32、ttknE段总的时空区区个任务实际占用的时空时间空间12345671234567123456712345671234567 1 2 3 18 4 5 6 7 8 9 10 11 12 13 14 15 16 17S5S1S2S3S4效率为何仍然不高？整个流水线的效率很低的原因：整个流水线的效率很低的原因：（1） 存在有数据相关，当发生数据相关时，必须等待前一个运算结果产生之后，下一个运算才能开始；（2） 流水线有填入与排空部分，当输入到流水线中的任务不多时，填入与排空部分所占的比例比较大。 3.3 流水线的性能指标流水线的性能指标n练习：（线性多功能练习：（线性多功能静态流水线静态流水线，输入任务是不连续的情况，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。）计算流水线的吞吐率、加速比和效率。）n用用TIASC计算机的多功能静态流水线，计算两个向量的点积：计算机的多功