1、第三章第三章 流水线技术流水线技术 提高计算机性能（速度）的两个重要方法：提高计算机性能（速度）的两个重要方法：1.缩短执行每条指令所需的平均周期数缩短执行每条指令所需的平均周期数CPI，如：如：RISC技术。技术。2.提高处理机在执行指令中的并行度，即同提高处理机在执行指令中的并行度，即同一时刻中处理机内同时运行多条指令。如：一时刻中处理机内同时运行多条指令。如：采用流水线技术。采用流水线技术。3.1 重叠执行和先行控制重叠执行和先行控制一一.指令的重叠执行指令的重叠执行 一条指令的执行过程可以粗略地分为：一条指令的执行过程可以粗略地分为：取指令、分析和执行三个阶段，且这个取指令、分析和执行
2、三个阶段，且这个次序是不能改变的。次序是不能改变的。取指令取指令执行执行分析分析tTi用用Ti表示执行一条指令所需的时间，可以写成：表示执行一条指令所需的时间，可以写成：Ti=t取指令取指令+t分析分析+t执行执行3.1 重叠执行和先行控制重叠执行和先行控制 如果连续执行一段程序，计算机对前后如果连续执行一段程序，计算机对前后相邻指令的执行过程可以有两种不同的相邻指令的执行过程可以有两种不同的选择选择:1.顺序执行方式，即等前一条指令执行完顺序执行方式，即等前一条指令执行完毕，紧接着执行下一条指令毕，紧接着执行下一条指令.2.让前后连续的指令在处理机内以重叠的让前后连续的指令在处理机内以重叠的
3、方式执行方式执行.取指取指分析分析执行执行取指取指分析分析执行执行k+1k3.1 重叠执行和先行控制重叠执行和先行控制一次重叠执行方式一次重叠执行方式:二次重叠执行方式二次重叠执行方式:取指取指分析分析执行执行取指取指分析分析执行执行取指取指分析分析执行执行第第k条指令条指令第第k+1条指令条指令第第k+2条指令条指令取指取指分析分析执行执行取指取指分析分析执行执行取指取指分析分析执行执行第第k条指令条指令第第k+1条指令条指令第第k+2条指令条指令如果三个阶段所需时间如果三个阶段所需时间t相等，相等，N条指令顺序执行条指令顺序执行的时间为的时间为：T=3Nt。一次重叠执行的时间：一次重叠执行
4、的时间：T=(1+2N)t。二次重叠执行的时间为：二次重叠执行的时间为：T=（2+N)t。3.1 重叠执行和先行控制重叠执行和先行控制二二.先行控制技术先行控制技术1实现重叠执行实现重叠执行存在的问题存在的问题（1）问题一：）问题一：需要独立的取指部件，分析部件，执行部件。需要独立的取指部件，分析部件，执行部件。解决方案解决方案:设置对应存储控制器，指令控制器和运算控设置对应存储控制器，指令控制器和运算控制器。制器。3.1 重叠执行和先行控制重叠执行和先行控制（2 2）问题二：）问题二：主存访问冲突主存访问冲突n取指令时取指令时，处理机必须按指令计数器的指示访问，处理机必须按指令计数器的指示访
5、问存储器；存储器；n分析指令时分析指令时，可能需要从存储器中获取操作数；，可能需要从存储器中获取操作数；n执行指令时执行指令时，也可能要求将结果写回到存储器中。，也可能要求将结果写回到存储器中。处理机中三个独立的部件可能同时提出对存储器处理机中三个独立的部件可能同时提出对存储器读写的请求，从而发生存储器访问冲突。读写的请求，从而发生存储器访问冲突。3.1 重叠执行和先行控制重叠执行和先行控制解决方案：解决方案：1）分别设置两个独立的存储器：指令存储器和数）分别设置两个独立的存储器：指令存储器和数据存储器，或一级据存储器，或一级Cache分为程序分为程序Cache和数和数据据Cache，同时工作
6、解决同时读指令和读数据，同时工作解决同时读指令和读数据引起的冲突。引起的冲突。n程序空间和数据空间相互独立并具有独立的指程序空间和数据空间相互独立并具有独立的指令总线和数据总线的系统结构就称为哈佛结构令总线和数据总线的系统结构就称为哈佛结构n缺点：结构复杂，需要大量的数据线，对汇编缺点：结构复杂，需要大量的数据线，对汇编程序员和机器程序员不透明程序员和机器程序员不透明2）多体交叉存储器结构也可减少冲突的发生。）多体交叉存储器结构也可减少冲突的发生。3）先行控制技术是最根本的办法。）先行控制技术是最根本的办法。3.1 重叠执行和先行控制重叠执行和先行控制n在复杂的计算机指令系统中，各种指令在分析
7、在复杂的计算机指令系统中，各种指令在分析和执行阶段所需的时间可能有很大的差别。于和执行阶段所需的时间可能有很大的差别。于是，前面对三个阶段所需时间是，前面对三个阶段所需时间t相等的假设就可相等的假设就可能不成立，所得到的节约三分之二时间的结论能不成立，所得到的节约三分之二时间的结论也被动摇了。下图形象地表示了这种情况所造也被动摇了。下图形象地表示了这种情况所造成的影响。成的影响。第第k条指令条指令分析分析执行执行第第k+2条指令条指令执行执行分析分析第第k+1条指令条指令分析分析执行执行这种情况可用先行控制技术来缓解。这种情况可用先行控制技术来缓解。3.1 重叠执行和先行控制重叠执行和先行控制
8、2采用先行控制技术的处理机采用先行控制技术的处理机运算控制器运算控制器 先先 行行 指指 令令 栈栈 后后 行行 写写 数数 栈栈 先先 行行 读读 数数 栈栈存存 储储 控控 制制 器器去主存储器去主存储器地址线地址线 指指 令令 分分 析析 器器 先行操作栈先行操作栈运运 算算 器器通通 用用 寄寄 存存 器器3.1 重叠执行和先行控制重叠执行和先行控制 缓冲栈实际上是一个以先进先出（缓冲栈实际上是一个以先进先出（FIFO）方）方式工作的移位寄存器组，上图表示了缓冲栈式工作的移位寄存器组，上图表示了缓冲栈所处的地位。前置部件的输出不直接送入后所处的地位。前置部件的输出不直接送入后置部件，而
9、是通过缓冲栈暂存后才输出。置部件，而是通过缓冲栈暂存后才输出。前置部件前置部件后置部件后置部件缓冲栈缓冲栈 运算控制器运算控制器 先先 行行 指指 令令 栈栈 后后 行行 写写 数数 栈栈 先先 行行 读读 数数 栈栈存存 储储 控控 制制 器器去主存储器去主存储器地址线地址线 指指 令令 分分 析析 器器 先行操作栈先行操作栈运运 算算 器器通通 用用 寄寄 存存 器器3.1 重叠执行和先行控制重叠执行和先行控制3先行控制原理先行控制原理通过先行指令计数器通过先行指令计数器PC1预取指令序列预取指令序列通过现行指令计数器通过现行指令计数器PC取取出现行指令出现行指令指令分析器指令分析器指令分
10、析器指令分析器:对取自先行指令栈的指令进行预处对取自先行指令栈的指令进行预处理理.1.对于程序控制类的指令，如转移指令，指今对于程序控制类的指令，如转移指令，指今分析器可以直接完成指令的执行分析器可以直接完成指令的执行.2.对于数据运算型指令，指令分析器要将它们对于数据运算型指令，指令分析器要将它们变换成寄存器寄存器型变换成寄存器寄存器型(RR型型)指令，即将操作指令，即将操作数预先存到寄存器中，使指令能快速执行数预先存到寄存器中，使指令能快速执行.立即寻址立即寻址传数据传数据变址寻址变址寻址或存储器或存储器型指令型指令,传传地址地址RR*指令指令3.1 重叠执行和先行控制重叠执行和先行控制n
11、先行控制技术中采取了两个根本的措施：先行控制技术中采取了两个根本的措施：指令指令预处理技术预处理技术和和缓冲技术缓冲技术。由于指令和数据的缓。由于指令和数据的缓冲，保证了指令分析和指令的执行都能全速地冲，保证了指令分析和指令的执行都能全速地运行。运行。第第k条指令条指令分析分析执行执行第第k+2条指令条指令执行执行分析分析第第k+1条指令条指令分析分析执行执行 缓冲栈深度应满足以下关系：缓冲栈深度应满足以下关系：D取指栈取指栈D操作栈操作栈D读栈读栈D写栈写栈第第k条指令条指令分析分析执行执行第第k+2条指令条指令执行执行分析分析第第k+1条指令条指令分析分析执行执行3.2 流水线的基本概念流
12、水线的基本概念一一.什么是流水线什么是流水线1.流水线技术流水线技术（pipelining）把一个重复的过程分解为若干个子过程，每个把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过能段，这样，每个子过程就可以与其他的子过程并行进行。程并行进行。流水线中的每个子过程及其功能部件称为流水线中的每个子过程及其功能部件称为流水流水线的级或段线的级或段，段与段相互连接形成流水线。流，段与段相互连接形成流水线。流水线的段数称为水线的段数
13、称为流水线的深度。流水线的深度。3.2 流水线的基本概念流水线的基本概念 2流水线结构流水线结构 重叠执行是流水线结构的思想基础，只要在指令重叠执行是流水线结构的思想基础，只要在指令分析器与指令执行部件之后都加上一个锁存器，分析器与指令执行部件之后都加上一个锁存器，就成了一个简单的流水线结构。就成了一个简单的流水线结构。指令执行部件指令执行部件 指令分析器指令分析器锁存器锁存器锁存器锁存器分析分析k+1执行执行k t2 t1 结果出结果出指令入指令入 在流水线的每一个功能部件的后面都要有一个在流水线的每一个功能部件的后面都要有一个缓冲寄存器，或称为锁存器、闸门寄存器等，它缓冲寄存器，或称为锁存
14、器、闸门寄存器等，它的作用是保存本流水段的执行结果。的作用是保存本流水段的执行结果。3时空图时空图时空图可以直观地表现流水线的工作过程时空图可以直观地表现流水线的工作过程 横轴表示时间，即各条指令在处理机中经历各个操作时横轴表示时间，即各条指令在处理机中经历各个操作时占用的时间段。如果各级执行所需的时间相等，在横轴上占用的时间段。如果各级执行所需的时间相等，在横轴上应表现为等距离的时间段。应表现为等距离的时间段。纵轴表示空间，即流水线的各个子操作过程，通常也称纵轴表示空间，即流水线的各个子操作过程，通常也称为为“功能段功能段”。k t (n-1)tn-1n-1 123n nn-1n-1123n
15、 nn-1n-1123n nn-1n-1123n n时间时间空间空间S1S2S3S4n-1n-1123n nS5填入填入填满填满排空排空3.2 流水线的基本概念流水线的基本概念4流水线的工作特点流水线的工作特点1）一条流水线通常由多个流水段组成，在每一）一条流水线通常由多个流水段组成，在每一个流水段有专门的功能部件来实现。个流水段有专门的功能部件来实现。2）各流水段所需的时间应尽可能相等，否则将）各流水段所需的时间应尽可能相等，否则将引起流水线堵塞、断流。引起流水线堵塞、断流。3）流水线每个功能部件后面都有一个缓冲寄存）流水线每个功能部件后面都有一个缓冲寄存器，称为流水寄存器。器，称为流水寄存
16、器。4）流水线的工作一般分为）流水线的工作一般分为3个阶段，即建立（填个阶段，即建立（填入）、填满和排空。入）、填满和排空。5）流水线技术适合于大量重复的时序过程，只）流水线技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流有在输入端不断地提供任务，才能充分发挥流水线的效率。水线的效率。3.2 流水线的基本概念流水线的基本概念二二.流水线的种类流水线的种类1、按处理机分类按处理机分类n操作部件级操作部件级 为最低级别的流水线。是把处理机的算术逻辑为最低级别的流水线。是把处理机的算术逻辑运算部件分段。如果某一部件的处理过程比较运算部件分段。如果某一部件的处理过程比较复杂，如
17、浮点运算复杂，如浮点运算,需要较长的时间。这时可以需要较长的时间。这时可以将该部件分为若干子部件，分别完成浮点运算将该部件分为若干子部件，分别完成浮点运算中有关的子操作，这种在部件范围内形成的流中有关的子操作，这种在部件范围内形成的流水线称为操作部件级流水线。水线称为操作部件级流水线。3.2 流水线的基本概念流水线的基本概念一个浮点加法部件的流水线：一个浮点加法部件的流水线：求阶差求阶差对阶对阶尾数加尾数加规格化规格化入入出出部件级流水线通常是流水线处理机中的一部分，部件级流水线通常是流水线处理机中的一部分，这时的处理机由于流水级数较多，又称为超流水这时的处理机由于流水级数较多，又称为超流水线
18、处理机。线处理机。3.2 流水线的基本概念流水线的基本概念n处理机级处理机级 又称为指令流水线，就是将一条指令的又称为指令流水线，就是将一条指令的解释执行过程分解解释执行过程分解成若干个子过程，使成若干个子过程，使每个子过程分别在一个部件中完成。每个子过程分别在一个部件中完成。n处理机间级处理机间级 处理机间流水线通常是多处理机系统中处理机间流水线通常是多处理机系统中对任务采取的一种处理策略。对任务采取的一种处理策略。3.2 流水线的基本概念流水线的基本概念 上图是处理机间流水线示意图，图中每个处理上图是处理机间流水线示意图，图中每个处理机是以任务为单位进行处理的，而处理机间的机是以任务为单位
19、进行处理的，而处理机间的任务传递则是由公用存储器完成的。应当指出，任务传递则是由公用存储器完成的。应当指出，图中给出的是一个处理的图中给出的是一个处理的“流水流水”，并没有涉，并没有涉及更多的硬件结构。实际上这个过程更应该看及更多的硬件结构。实际上这个过程更应该看作是一种任务的调度策略。作是一种任务的调度策略。处理机处理机2 M 处理机处理机n M 输出输出 处理机处理机1 M输入输入 任务任务1 任务任务2 任务任务n3.2 流水线的基本概念流水线的基本概念2、按流水线功能多少分类按流水线功能多少分类n单功能流水线单功能流水线 指一条流水线只能完成一种单一的任务。指一条流水线只能完成一种单一
20、的任务。n多功能流水线多功能流水线 指能够在一个时间段内或不同时间段间改指能够在一个时间段内或不同时间段间改变部件之间的连接，从而达到改变其功能变部件之间的连接，从而达到改变其功能的流水线。的流水线。3.2 流水线的基本概念流水线的基本概念在标量运算中，各种运算是混在一起的。在标量运算中，各种运算是混在一起的。3、按照工作方式分类按照工作方式分类n静态流水线静态流水线 当执行某一规定功能的指令全部流出后，才允当执行某一规定功能的指令全部流出后，才允许改变部件间连接的流水线。许改变部件间连接的流水线。（可以是单功能流水线也可以是多功能流水线）（可以是单功能流水线也可以是多功能流水线）3.2 流水
21、线的基本概念流水线的基本概念n动态流水线动态流水线 没有这种时间上的限制，可以在任何时候根据没有这种时间上的限制，可以在任何时候根据需要改变其连接。需要改变其连接。（只能是多功能流水线）（只能是多功能流水线）3.2 流水线的基本概念流水线的基本概念4、按连接方式分类按连接方式分类n线性流水线线性流水线 是指在部件上没有反馈连接的流水线。在这种流是指在部件上没有反馈连接的流水线。在这种流水线中，指令依次通过各个部件仅一次，完成指水线中，指令依次通过各个部件仅一次，完成指令执行的全过程。目前所使用的流水线绝大部分令执行的全过程。目前所使用的流水线绝大部分都是这类线性流水线。都是这类线性流水线。n非
22、线性流水线非线性流水线 是指在各部件除了串行的连接外，还通过反馈线是指在各部件除了串行的连接外，还通过反馈线使某些部件得以重复使用。指令在通过这种流水使某些部件得以重复使用。指令在通过这种流水线时，可能在反馈部件上重复运行若干次。线时，可能在反馈部件上重复运行若干次。3.2 流水线的基本概念流水线的基本概念反馈回路反馈回路S1S2S3入入出出S3S3S1S1S2S2时间时间非线性流水线工作特性示意图非线性流水线工作特性示意图3.2 流水线的基本概念流水线的基本概念5、按流入流出顺序分类按流入流出顺序分类n顺序流水线顺序流水线 其输出的结果与输入的次序相同，早期的流水线其输出的结果与输入的次序相
23、同，早期的流水线又称为又称为顺序流水线顺序流水线。n乱序流水线乱序流水线 将原始的输入次序打乱，以最有利于处理机执行将原始的输入次序打乱，以最有利于处理机执行的方式运行，在输出结果时才恢复原次序。的方式运行，在输出结果时才恢复原次序。在一些现代处理机中，如在一些现代处理机中，如Pentium 4在流水线运在流水线运行过程中采用了行过程中采用了乱序方式乱序方式。3.2 流水线的基本概念流水线的基本概念 除了上述几种分类方法以外，还可以根据各种除了上述几种分类方法以外，还可以根据各种不同的观点对流水线进行区分。比如：不同的观点对流水线进行区分。比如：n按照数据表示方式的不同，可以将流水线按照数据表
24、示方式的不同，可以将流水线分为分为标量流水线标量流水线和和向量流水线向量流水线两种。在标两种。在标量处理机中使用的当然是标量流水线。量处理机中使用的当然是标量流水线。n根据流水线在各级之间流动时的控制方法根据流水线在各级之间流动时的控制方法不同，又可以分成不同，又可以分成同步同步和和异步异步两种流水线。两种流水线。3.2 流水线的基本概念流水线的基本概念n处理机内的处理机内的指令流水线指令流水线都是都是同步流水线同步流水线，即使用统一的时钟控制各级同时开始同时即使用统一的时钟控制各级同时开始同时完成动作。完成动作。n而而处理机间的流水线处理机间的流水线通常都是通常都是异步流水线异步流水线，需要
25、在任务传送时进行应答，以确保传输需要在任务传送时进行应答，以确保传输的可靠性。的可靠性。3.3 流水线的性能指标流水线的性能指标 吞吐率、加速比和效率是表明流水线性吞吐率、加速比和效率是表明流水线性能的主要指标。能的主要指标。一一.吞吐率吞吐率 把流水线在单位时间内完成的任务量定把流水线在单位时间内完成的任务量定义为吞吐率。义为吞吐率。kTnTP=其中其中,n为完成任务的总数，在指令流水线中为完成任务的总数，在指令流水线中就是完成的指令总条数；就是完成的指令总条数；Tk是完成是完成n个任务所个任务所用的时间。用的时间。3.3 流水线的性能指标流水线的性能指标n各级执行时间相等的流水线各级执行时
26、间相等的流水线 一条一条k级的流水线执行级的流水线执行n条指令的时空图条指令的时空图:tnkTkD D-+=)1(n-1n-1 123n nn-1n-1123n nn-1n-1123n nn-1n-1123n n k t (n-1)tn t (k-1)tTk时间时间空间空间S1S2S3S4所需的总时间为：所需的总时间为：3.3 流水线的性能指标流水线的性能指标 当当n时，（时，（k 1）可以忽略不计，得到的）可以忽略不计，得到的最大吞吐率为最大吞吐率为:ttnknTPnD D=D D-+=1)1(limmax所以，吞吐率为所以，吞吐率为:tnknTPD D-+=)1(3.3 流水线的性能指标流
27、水线的性能指标n各级执行时间不等的流水线各级执行时间不等的流水线执行时间不等的流水线时空图执行时间不等的流水线时空图n123123nn321312n(n-1)t2Tk时间时间空间空间S4S3S2S1D=kiit13.3 流水线的性能指标流水线的性能指标吞吐率的一般表示式为吞吐率的一般表示式为:同样方法可以得到当同样方法可以得到当n时的最大吞吐率为：时的最大吞吐率为：=D DD DD D-+D D=kikitttntnTP121),(max)1(),(max121maxktttTPD DD DD D=3.3 流水线的性能指标流水线的性能指标n如果流水线中各级的执行时间不相等，如果流水线中各级的执
28、行时间不相等，其中时间最长者就成了流水线中的其中时间最长者就成了流水线中的“瓶颈瓶颈”。瓶颈问题对流水线的吞吐。瓶颈问题对流水线的吞吐率影响是明显的，所以消除率影响是明显的，所以消除“瓶颈瓶颈”是设计流水线的一个重要原则。是设计流水线的一个重要原则。n“瓶颈瓶颈”问题的消除问题的消除 采用的方法主要有两种：采用的方法主要有两种：1）分割瓶颈部件的工作）分割瓶颈部件的工作2）重复设置瓶颈部件）重复设置瓶颈部件3.3 流水线的性能指标流水线的性能指标消除消除“瓶颈瓶颈”影响的两种方法示意图：影响的两种方法示意图：S2-1S2-2S2-3S S2 2(3(3t)tt(a)(b)S2-3S2-1S2-
29、2t2=3t33tS1S2S3S4ttt两种方式在效果上是可以等效的，在输入两种方式在效果上是可以等效的，在输入n条指令的情况条指令的情况下，实际吞吐率都为：下，实际吞吐率都为：tnntnnTPD D+=D D-+=)5()16(3.3 流水线的性能指标流水线的性能指标不消除不消除“瓶颈瓶颈”时的吞吐率：时的吞吐率：两种方式在效果上是可以等效的，在输入两种方式在效果上是可以等效的，在输入n条指令的情况条指令的情况下，实际吞吐率都为：下，实际吞吐率都为：tnntnnTPD D+=D D-+=)5()16(=D DD DD D-+D D=kikitttntnTP121),(max)1(=6 63D
30、3D-+D Dtntn)1(=3 3D D+t3nn)(3.3 流水线的性能指标流水线的性能指标二二.加速比加速比n处理同一批任务，不用流水线与采用流处理同一批任务，不用流水线与采用流水线时所花费的时间之比，称为流水线水线时所花费的时间之比，称为流水线的的加速比加速比。n如果不用流水线所用的时间为如果不用流水线所用的时间为T0，用了，用了流水线所用时间为流水线所用时间为Tk，那么加速比就是：，那么加速比就是：S=T0/Tk3.3 流水线的性能指标流水线的性能指标n不用流水线时，每条指令执行时必须在时间上不用流水线时，每条指令执行时必须在时间上顺序地完成各处理步骤，那么顺序地完成各处理步骤，那么
31、n条指令所需时条指令所需时间就为间就为T0=nkt。而一个采用流水线的处理。而一个采用流水线的处理机所需时间为机所需时间为Tk=(k+n 1)t。n所以加速比就为所以加速比就为1)1(0-+=D D-+D D=nknktnktknTTSk同样办法可以得到最大加速比同样办法可以得到最大加速比knknkSn=-+=1limmax3.3 流水线的性能指标流水线的性能指标n如果考虑各级执行时间不等的情况时，一条指如果考虑各级执行时间不等的情况时，一条指令的执行时间是各级运行时间之和。在没有流令的执行时间是各级运行时间之和。在没有流水线时，水线时，n条指令应是一条指令的条指令应是一条指令的n倍。于是，倍
32、。于是，可得到加速比为可得到加速比为 =D DD DD D-+D DD D=kikikiitttnttnS1211),(max)1(3.3 流水线的性能指标流水线的性能指标三三.效率效率n效率被定义为：效率被定义为：空区空区个流水线级占用的总时个流水线级占用的总时条指令占用的时空区条指令占用的时空区knE=n-1n-1 123n nn-1n-1123n nn-1n-1123n nn-1n-1123n n k t (n-1)tn t (k-1)tTk时间时间空间空间S1S2S3S4各级执行时间相等的流水线效率等于：各级执行时间相等的流水线效率等于：1)1(-+=D D-+D D=nkntnkkt
33、knE3.3 流水线的性能指标流水线的性能指标n显然，显然，n越大，空闲部件占据的比例就小，越大，空闲部件占据的比例就小，流水线表现的效率越高。最高效率为：流水线表现的效率越高。最高效率为：11limmax=-+=nknEnn 通过类似的分析方法，我们也可以得到在各通过类似的分析方法，我们也可以得到在各 级执行时间不等的流水线中的效率计算方法。级执行时间不等的流水线中的效率计算方法。=D DD DD D-+D D D D=kikikiitttntktnE1211),(max)1(3.3 流水线的性能指标流水线的性能指标n同样，同样，效率公式：效率公式：加速比公式：加速比公式：两者相结合得出：两
34、者相结合得出：E=S/k 或或 S=k E1-+=nknkS1-+=nknE效率公式：效率公式：tnknTPD D-+=)1(吞吐率公式：吞吐率公式：1-+=nknE 两者相结合得出：两者相结合得出：E=TP t 或或TP=E/t。仅限于各级执行时仅限于各级执行时间相等的流水线间相等的流水线3.3 流水线的性能指标流水线的性能指标例：一个例：一个5级的线性流水线，可完成两个数相加运级的线性流水线，可完成两个数相加运算。现要进行算。现要进行8个操作数连续相加运算，如何实个操作数连续相加运算，如何实现？性能如何？现？性能如何？分析：分析：若按若按M=A+B+C+D+E+F+G+H进行运算，效率很进
35、行运算，效率很低。低。可改为：可改为：M=（A+B）+（C+D）+（E+F）+（G+H）1234567工作时空图：工作时空图：从时空图中看出，由于输入任务的不连续，全从时空图中看出，由于输入任务的不连续，全部部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
36、=（A+B）+（C+D）+（E+F）+（G+H）123456794.118570=DD=ttTTSk这时流水线的加速比为这时流水线的加速比为:而效率达到：而效率达到：389.0185570=DD=ttTkTEk时间时间空间空间12345671234567123456712345671234567 1 2 3 18 4 5 6 7 8 9 10 11 12 13 14 15 16 17S5S1S2S3S4效率为何仍效率为何仍然不高？然不高？3.3 流水线的性能指标流水线的性能指标整个流水线的效率很低的原因：整个流水线的效率很低的原因：（1）存在有数据相关，当发生数据相关时，必存在有数据相关，当发
37、生数据相关时，必须等待前一个运算结果产生之后，下一个运算须等待前一个运算结果产生之后，下一个运算才能开始；才能开始；（2）流水线有填入与排空部分，当输入到流水流水线有填入与排空部分，当输入到流水线中的任务不多时，填入与排空部分所占的比线中的任务不多时，填入与排空部分所占的比例比较大。例比较大。n练习：线性多功能练习：线性多功能静态流水线静态流水线，输入任务是，输入任务是不连续的情况，计算流水线的吞吐率、加速不连续的情况，计算流水线的吞吐率、加速比和效率。比和效率。用用TIASC计算机的多功能静态流水线计算计算机的多功能静态流水线计算两个向量的点积：两个向量的点积：ZABCDEFGH3.3 流水
38、线的性能指标流水线的性能指标 解：为了尽量减少数据相关性，充分发挥流水解：为了尽量减少数据相关性，充分发挥流水线的作用。计算的顺序应该是先做线的作用。计算的顺序应该是先做4 4个乘法：个乘法：ABAB、CDCD、EFEF和和GHGH，然后做两个加法，然后做两个加法ABABCDCD和和EFEFGHGH，最后求总的结果，最后求总的结果Z Z。Z Z(AB)(AB)(CD)(CD)(EF)(EF)(GH)(GH)1 12 23 34 45 57 76 63.3 流水线的性能指标流水线的性能指标 从流水线时空图中看到，用从流水线时空图中看到，用20个时钟周期完成了个时钟周期完成了7个运算。当每一个功能
39、段的延迟时间都为个运算。当每一个功能段的延迟时间都为t时，时，有：有：Tk20 t，n7。流水线的吞吐率。流水线的吞吐率TP为为如果采用顺序执行方式，完成一次乘法要用如果采用顺序执行方式，完成一次乘法要用4 4个个t，完成一次加法要用，完成一次加法要用6 6个个t，则完成全部，则完成全部运算要用运算要用 则流水线的加速比则流水线的加速比S S为：为：整个流水线共有整个流水线共有8 8段，流水线效率段，流水线效率E E为：为：效率更低的原因？效率更低的原因？原因：原因：静态流水线造成加法运算必须在乘法运算静态流水线造成加法运算必须在乘法运算所有指令流出流水线后才能进行。所有指令流出流水线后才能进
40、行。解决：解决：改为改为动态流水线动态流水线 课后任务：课后任务：采用动态流水线对其性能进行分析采用动态流水线对其性能进行分析3.3 流水线的性能指标流水线的性能指标四、流水线设计中的若干问题：四、流水线设计中的若干问题：n瓶颈问题瓶颈问题 当流水线各段不均匀时，当流水线各段不均匀时，机器的时钟周期取决于瓶颈机器的时钟周期取决于瓶颈段的延迟时间。段的延迟时间。在设计流水线时，要尽可能使各段时间相等。在设计流水线时，要尽可能使各段时间相等。n流水线的额外开销流水线的额外开销p流水寄存器延迟流水寄存器延迟p时钟偏移开销时钟偏移开销n冲突问题冲突问题 流水线设计中要解决的流水线设计中要解决的重要问题
41、之一。重要问题之一。3.4 流水线的相关与冲突流水线的相关与冲突一、一个经典的一、一个经典的5段流水线段流水线 一条指令的执行过程分为一条指令的执行过程分为5个周期：取指令周个周期：取指令周期（期（IF）、指令译码）、指令译码/读寄存器周期（读寄存器周期（ID）、执）、执行行/有效地址计算周期（有效地址计算周期（EX）、存储器访问）、存储器访问分支完成周期（分支完成周期（MEM）、）、写回周期（写回周期（WBWB）。）。3.4 流水线的相关与冲突流水线的相关与冲突n三类指令对三类指令对5 5级流水线的占用情况级流水线的占用情况:ALU指令指令LOAD/STOREBRANCHIF(S1)取指取指
42、取指取指取指取指ID(S2)译码译码,读寄存读寄存器堆器堆译码译码,读寄存器堆读寄存器堆译码译码,读寄存器读寄存器堆堆EX(S3)执行执行计算有效地址计算有效地址计算转移目标地计算转移目标地址址,设置条件码设置条件码MEM(S4)-访存访存(读或写读或写)若条件成立若条件成立,将将转移目标地址送转移目标地址送PCWB(S5)结果写回寄存结果写回寄存器堆器堆读出数据写入寄存器堆读出数据写入寄存器堆-3.4 流水线的相关与冲突流水线的相关与冲突n 5 5段流水线的两种描述方式段流水线的两种描述方式第一种描述第一种描述（类似于时空图）（类似于时空图）3.4 流水线的相关与冲突流水线的相关与冲突第二种
43、描述第二种描述（按时间错开的数据通路序列）（按时间错开的数据通路序列）3.4 流水线的相关与冲突流水线的相关与冲突二、相关二、相关n相关是指两条指令之间存在某种依赖关系。相关是指两条指令之间存在某种依赖关系。n从对流水线的分析中可以发现，如果流水线从对流水线的分析中可以发现，如果流水线始终处于始终处于“充满充满”的状态，实际性能可以达的状态，实际性能可以达到或接近理论值。如果流入流水线的指令出到或接近理论值。如果流入流水线的指令出现断流，将极大地影响流水线的性能。现断流，将极大地影响流水线的性能。n 造成断流的原因主要是三大类造成断流的原因主要是三大类:1）名相关）名相关 2）数据相关）数据相
44、关 3）控制相关）控制相关3.4 流水线的相关与冲突流水线的相关与冲突1、名相关、名相关名：名：指令所访问的寄存器或存储器单元的指令所访问的寄存器或存储器单元的名称。名称。如果两条指令使用相同的名，但是它们之如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在间并没有数据流动，则称这两条指令存在名相关。名相关。3.4 流水线的相关与冲突流水线的相关与冲突指令指令j（在后）与指令（在后）与指令i（在前）之间的名（在前）之间的名相关有两种：相关有两种：反相关：反相关：如果指令如果指令j写的名与指令写的名与指令i读读的名相同，则称指令的名相同，则称指令i和和j发生了反相发生了反相
45、关。关。指令指令j写的名指令写的名指令i读的名读的名如：如：DIV.DDIV.D F2 F2，F6F6，F4F4 ADD.D ADD.D F6F6，F0F0，F12F123.4 流水线的相关与冲突流水线的相关与冲突 输出相关：输出相关：如果指令如果指令j和指令和指令i写相同的名，写相同的名，则称指令则称指令i和和j发生了输出相关。发生了输出相关。指令指令j写的名指令写的名指令i写的名写的名名相关的两条指令之间并没有数据的名相关的两条指令之间并没有数据的传送。传送。如果一条指令中的名改变了，并不影如果一条指令中的名改变了，并不影响另外一条指令的执行。响另外一条指令的执行。但名相关的两条指令之间的
46、执行顺序但名相关的两条指令之间的执行顺序必须严格遵守。必须严格遵守。解决方法解决方法:换名技术：换名技术：通过改变指令中操作数的名来消除通过改变指令中操作数的名来消除名相关。名相关。例如：考虑下述代码：例如：考虑下述代码：DIV.DDIV.DF2F2，F6F6，F4F4 ADD.D ADD.DF6F6，F0F0，F12F12 SUB.D SUB.DF8F8，F6F6，F14F14 DIV.DDIV.D和和ADD.DADD.D存在反相关。存在反相关。进行寄存器换名（进行寄存器换名（F6F6换成换成S S）后，变成：）后，变成：DIV.DDIV.DF2F2，F6F6，F4F4 ADD.D ADD.
47、DS S，F0F0，F12F12 SUB.D SUB.DF8F8，S S，F14 F14 3.4 流水线的相关与冲突流水线的相关与冲突2、数据相关、数据相关对于两条指令对于两条指令i（在前）和（在前）和j（在后），如（在后），如果下述条件之一成立，则称果下述条件之一成立，则称指令指令j与与指令指令i数据相关。数据相关。指令指令j使用指令使用指令i产生的结果；产生的结果；指令指令j与指令与指令k数据相关，而指令数据相关，而指令k又与指又与指令令i数据相关。数据相关。数据相关具有数据相关具有传递性。传递性。数据相关反映了数据的流动关系，即如何数据相关反映了数据的流动关系，即如何从其产生者流动到其消
48、费者。从其产生者流动到其消费者。例如：下面这一段代码存在数据相关例如：下面这一段代码存在数据相关Loop：L.D F0，0（R1）/F0为数组元素为数组元素 ADD.D F4，F0，F2/加上加上F2中的值中的值 S.D 0（R1），），F4/保存结果保存结果 DADDIU R1，R1，8 /数组指针递减数组指针递减8个字节个字节 BNE R1，R2，Loop /如果如果R1R2，则分支，则分支3.4 流水线的相关与冲突流水线的相关与冲突当数据的流动是经过寄存器时，相关的检测比当数据的流动是经过寄存器时，相关的检测比较直观和容易。较直观和容易。当数据的流动是经过存储器时，检测比较复杂。当数据的
49、流动是经过存储器时，检测比较复杂。相同形式的地址其有效地址未必相同。相同形式的地址其有效地址未必相同。形式不同的地址其有效地址却可能相同。形式不同的地址其有效地址却可能相同。3.4 流水线的相关与冲突流水线的相关与冲突3.4 流水线的相关与冲突流水线的相关与冲突3、控制相关、控制相关控制相关控制相关是指由分支指令引起的相关。是指由分支指令引起的相关。典型的程序结构是典型的程序结构是“if-then”if-then”结构结构。控制相关带来了以下控制相关带来了以下两个限制：两个限制：与一条分支指令控制相关的指令不能被与一条分支指令控制相关的指令不能被移到该分支之前，否则这些指令就不受移到该分支之前
50、，否则这些指令就不受该分支控制了。该分支控制了。如果一条指令与某分支指令不存在控制如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。相关，就不能把该指令移到该分支之后。3.4 流水线的相关与冲突流水线的相关与冲突三、流水线冲突三、流水线冲突n流水线冲突流水线冲突是指对于具体的流水线来说，是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。条指令不能在指定的时钟周期执行。n 流水线冲突有流水线冲突有3 3种类型：种类型：结构冲突结构冲突 数据冲突数据冲突 控制冲突控制冲突3.4 流水线的相关与冲突流水线
