第三讲 流水线的相关

《第三讲 流水线的相关》由会员分享，可在线阅读，更多相关《第三讲 流水线的相关（75页珍藏版）》请在金锄头文库上搜索。

1、第一章 体系结构复习第一节 流水线技术第二节 DLX流水线第三节 流水线中的相关Date第一节 流水线技术1.1 指令的流水执行方式1、顺序执行方式。 执行n条指令所用的时间为：如果每段时间都为t，则执行n条指令所用的时间为：T3 n tDate2、流水执行方式。如果三过程的时间相等，执行n条指令的时间为：T(2n）t在理想情况下，处理机中同时有三条指令在执行处理机的结构要作比较大的改变Date1.2 流水线工作原理 1、简单流水线流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶 段、流水功能段、功能段、流水级、流水节拍等。在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄 存器

2、、流水锁存器、流水闸门寄存器等。会增加指令的执行时 间。为了简化，在一般流水线中不画出流水锁存器。Date取指IF译码ID执行EX访存MEM写回WB 输入输出2、一种指令流水线一般4至12个流水段，等于及大于8个流水段的称为超流水线处理机3、流水线的时空图Date4、流水线的主要特点 一条流水线通常由多个流水段组成，每个流水段有专 门的功能部件对指令进行某种加工。 各流水段的时间应尽量相等。流水线处理机的基本时钟周期等于时间最长的流水段 的时间长度。 在流水线的每一个流水线段中都要设置一个流水锁存 器。 流水线有“建立”、“满载”和“排空”三个阶段。 在理想情况下，当流水线充满后，每隔时间将会

3、流出 一个结果Date1.3 流水线的分类1、线性流水线与非线性流水线流水线的各个流水段之间是否有反馈信号 线性流水线（Linear Pipelining）：每一个流水段都流过一次，而且仅流过一次。S1 S2 S3输入输出Date 非线性流水线（Nonlinear Pipelining）：在流水线的某些流水段之间有反馈回路或前馈回路。线性流水线能够用流水线连接图唯一表示非线性流水线必须用流水线连接图和流水线预约表等 共同表示Date2、按照流水线的级别来分 指令级流水线（Instruction Pipelining）。一条指令的解释过程分成多个子过程 部件级流水线（操作流水线），如浮点加法器流

4、水线。 处理机级流水称为宏流水线（Macro Pipelining）。每个处理机对同一个数据流的不同部分分别进行处理。Date3、单功能流水线与多功能流水线 单功能流水线：只能完成一种固定功能的流水线。Cray-1计算机种有12条YH-1计算机有18条Pentium有一条5段的定点和一条8段的浮点流水线。Pentium有三条指令流水线，其中两条定点指令流水线，一条浮点指令流水线。 多功能流水线：流水线的各段通过不同的连接实现不同的功能。Texas公司的ASC计算机中的8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法，逻辑运算、移位操作、数据转换、向量运算等。DateDate4、静

5、态流水线与动态流水线 静态流水线：同一段时间内，多功能流水线中的各个功能段只能按 照一种固定的方式连接，实现一种固定的功能。 从一种功能切换为另一种功能时，必须排空流水线只有连续出现同一种运算时，流水线的效率才能得到充分的发挥。Date 动态流水线：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。Date1.4 线性流水线的性能分析衡量流水线性能的主要指标有：吞吐率、加速比和效率 1、吞吐率（Though Put）：单位时间内流水线所完成的 任务数量。 计算流水线吞吐率的最基本公式：其中：n为任务数，m为完成n个任务所用的时间 各段执行时间相等，输入连续任务情况下

6、：完成n个连续任务需要的总时间为：Tm（mn1）t其中：m 为流水线的段数，t为时钟周期Date吞吐率为：最大吞吐率为： 各段执行时间不相等，输入连续任务情况下：最大吞吐率为： 流水线各段执行时间不相等的解决办法一是将流水线的“瓶颈”部分再细分（如果可分的话）。 二是“瓶颈“流水段重复设置：Date一是将流水线的“瓶颈”部分再细分（如果可分的话）。DateDate2、加速比（Speedup）:完成同样一批任务，不使用流水线所用的时 间与使用流水线所用的时间之比。 计算流水线加速比的基本公式： 各段执行时间相等，输入连续任务情况下：加速比为：n m时，SpmDateDateDate4、流水线性能

7、分析举例对于单功能线性流水线，输入连续任务的情况，通 过上面给出的公式很容易计算出流水线的吞吐率、加速 比和效率。例1：用一条4段浮点加法器流水线求8个浮点数的 和：ZABCDEFGH解：Z（AB）（CD）（EF）（GH ）DateDate1.5 非线性流水线的调度技术非线性流水线调度的任务是要找出一 个最小的循环周期，按照这周期向流水线 输入新任务，流水线的各个功能段都不会 发生冲突，而且流水线的吞吐率和效率最 高。Date1、线性流水线与非线性流水线流水线的各个流水段之间是否有反馈信 号 线性流水线（Linear Pipelining）：每一个流水段都流过一次，而且仅流过 一次。S1S2

8、S3 输入输出S4Date 非线性流水线（Nonlinear Pipelining）在流水线的某些流水段之间有反馈回路或前馈回路。线性流水线能够用流水线连接图唯一表示非线性流水线必须用流水线连接图和流水线预约表等 共同表示DateDate 一张预约表可能与多个流水线连接图相对应Date 一个流水线连接图对应与多张预约表Date2.非线性流水线的冲突问题：向非线性流水线仍每隔一拍送入一个新任务，会发 生什么现象？ 启动距离：连续输入两个任务之间的时间间隔 流水线冲突：几个任务争用同一个流水段2018/8/123.无冲突调度方法 由E.S.Davidson及其学生于1971年提出 禁止向量：预约表

9、中每一行任意两个“” 之间距离的集合。上例中为（3，4，6） 冲突向量：C（CmCm-1C2C1）其中：m是禁止向量中的最大值。如果i在禁止向量中，则Ci1，否则Ci0。上例中C(101100)Date例2：一条4功能段的非线性流水线，每个功能段 的延迟时间都相等，它的预约表如下：(1)写出流水线的禁止向量和初始冲突向量。(2)画出调度流水线的状态图。(3)求最小启动循环和最小平均启动距离。(4)求平均启动距离最小的恒定循环。Date解： (1)禁止向量为：(2，4，6)初始冲突向量：S = 101010 (2)构造状态图S逻辑右移2、4、6位时，不作任何处理，逻辑右移1、3、5和大于等于7时

10、：S右移1位之后：010101101010111111 ，S右移3位之后：000101101010101111 ，S右移5位之后：000001101010101011 ，S右移7位或大于7位后：还原到它本身。Date101111右移5位之后：000001101010 101011， 101011右移3位之后：000101101010 101111， 101011右移5位之后：000001101010 101011。Date 简单循环：状态图中各种冲突向量只经过一 次的启动循环。 (3)最小的启动循环为（1，7）和（3，5）,平均启动距离为 4。 (4)启动距离最小的恒定循环为（5）DateDa

11、teDate4.优化调度方法 L.E.Shar于1972年提出流水线最小平均启动 距离的限制范围：(1)最小平均启动距离的下限是预约表中任意 一行里“”的最多个数。(2)最小平均启动距离小于等于状态图中任意 一个简单循环的平均启动距离。(3)最小平均启动距离的上限是冲突向量中1 的个数再加上1。 1992年，L.E.Shar又证明了上述限制范围。 最有用的是第1条。预约表中“”最多的行 一定是瓶颈流水段 Date 对于例2的预约表，在同一行中“”最多的为2 个，因此，最小平均距离可以达到2。 最小启动循环可以是(2)、(1,3)、(1,1,4)、 (1,2,3)、。现取恒定循环(2)。 每一行

12、中与第1个“”的距离为2的倍数的 位置都要预留出来。S3行的第2个“”从周期5延迟到周期6。为此 ，S2行的第2个“”从周期6延迟到周期7；S1行的第2个“”从周期7延迟到周期8。 实际上，只要在流水段S4的输出端到流水段 S3的输入端中间插入一个非计算延迟D1。DateDateDate 在非线性流水线中，“”最多的流水段一定是 “瓶颈“流水段。 实现最优调度的目标是使“瓶颈”流水段处于 忙碌状态，没有空闲周期。 最优调度方法能够使非线性流水线的吞吐率 、加速比和效率达到最优。 Date作业 非线性流水线调度问题的研究Date第二节 DLX流水线一. DLX指令集结构RISC机主要特点1.选取

13、使用频率最高的指令；2.每条指令的功能应尽可能简单；3.以寄存器寄存器方式工作，即指令系统 中除load/store指令可访存外，其余指令都只 与寄存器打交道；4.所有指令长度均相同；5.采用优化编译技术，减少相关；6.平均CPI接近1Date1. DLX中的寄存器32个通用寄存器，命名为R0，R1，R31 32个浮点寄存器，命名为F0，F1，F31 2. DLX的数据类型8位、16位和32位整型数据；32位单精度数据和64位双精度数据 3. DLX的寻址方式四种寻址方式 4. DLX的指令格式DLX指令的字长均是32位，用六位表示操作码Date5. DLX中的操作 （1）Load 和 Sto

14、re操作对所有的通用寄存器和浮点寄存器进行Load 和 Store操作，指令系统中除load/store指令可访存外， 其余指令都只与寄存器打交道。LW R1，30（R2） （2）ALU操作寄存器寄存器型指令ADD R3，R2，R1 （3）Branch分支和跳转操作BEQZ R4，name （4）浮点操作ADDD F1,F2,F3Date二.基本的DLX流水线取指IF译码ID执行EX访存MEM写回WB 输入输出Date第三节 流水线中的相关 相关（correlation）：是指在一段程序的 相近指令之间有某种关系，这种关系可能影 响指令的重叠执行。3.1 资源相关3.2 数据相关3.3 控制相

15、关Date3.1 资源相关(结构相关)资源相关:多条指令进入流水线后在同一机器 周期内争用同一功能部件所发生的冲突.Date解决方法:1.停顿一拍流水线2.指令、数据分别存放在不同存储 器中Date3.2 数据相关数据相关：由于流水线中各条指 令的重叠操作使得原来对操作数的 访问顺序发生了变化而导致了数据 相关的冲突。DateADD R1,R2,R3; (R2)+(R3) R1SUB R4,R1,R5; (R1)-(R5) R4Date解决数据相关的方法有两种： 推后分析 设置专用路径。DateDate定向传送R1值到SUB、AND、OR指令进一步改进Date与LOAD指令发生数据相关：Dat

16、e解决方法:1.由硬件自动插入空操作，直到LOAD操作 完成 2.软件方法 Date3.3 控制相关控制相关：由条件转移指令引起的相关。Date条件分支对流水线的影响 由条件分支或程序中断引起的相关被称为全局相关。 处理好条件转移和中断的关键问题有两个：一是要确保流水线能够正常工作，二是减少因“断流”引起的吞吐率和效率的下降。 条件分支的处理方法条件转移指令对流水线的影响很大，必须采取措施来减 少这种影响。可能采取的措施有如下几种：(1) 静态分支预测技术(2) 动态分支预测技术静态分支技术 静态分支预测：在程序执行过程中转移预测方向不能改变 1.尽早生成转移目标地址:由MEM段提前到ID段2.加快和提前形成条件码 必要性：对减少流水线吞吐率