流水线中的相关.ppt

《流水线中的相关.ppt》由会员分享，可在线阅读，更多相关《流水线中的相关.ppt（63页珍藏版）》请在三一办公上搜索。

1、3.3流水线中的相关,1相关的概念,流水线中的相关是指相邻或相近的两条指令因存在某种关联，后一条指令不能在原指定的时钟周期开始执行。,结构相关 当硬件资源满足不了同时重叠执行的指 令的要求，而发生资源冲突时，就发生了结 构相关。,2相关的分类,第三章 流水线技术,数据相关 当一条指令需要用到前面某条指令的结 果，从而不能重叠执行时，就发生了数据相 关。控制相关 当流水线遇到分支指令和其他能够改变 PC值的指令时，就会发生控制相关。,3几个问题,相关有可能会使流水线停顿。,3.3 流水线中的相关,在本章中，我们约定：,当一条指令被暂停时，暂停在其后发射（流出）的指令，但继续执行在其前发射的 指令

2、。,消除相关的基本方法：让流水线中的某些指令暂停，而让其它 指令继续执行。,3.3 流水线中的相关,3.3.1 流水线中的结构相关,2.如果某种指令组合因资源冲突而不能顺利重 叠执行，则称该机器具有结构相关。,1.在流水线机器中，为了使各种指令组合能顺 利地重叠执行，需要把功能部件流水化，并 把资源重复设置。,3.常见的导致结构相关的原因：功能部件不是全流水 重复设置的资源的份数不够,3.3 流水线中的相关,4.结构相关举例：访存冲突,当数据和指令存在同一存储器中时，访存指令会导致访存冲突。解决办法：插入暂停周期（“流水线气泡”或“气泡”）,3.3 流水线中的相关,引入暂停后的时空图,3.3

3、流水线中的相关,5.避免结构相关：,6.有些设计方案允许有结构相关,所有功能单元完全流水化 设置足够的硬件资源硬件代价很大。,降低成本 减少部件的延迟,解决方法：设置相互独立的指令存储器和 数据存储器或设置相互独立的 指令Cache和数据Cache。,3.3 流水线中的相关,3.3.2 流水线的数据相关,1.数据相关简介 当指令在流水线中重叠执行时，流水线有 可能改变指令读/写操作数的顺序，使之不同 于它们在非流水实现时的顺序，这将导致数据 相关。数据相关举例,3.3 流水线中的相关,2.利用定向技术减少数据相关引起的暂停(1)定向技术的主要思路：在发生上述 数据相关时，后面的指令并不是马 上

4、就要用到前一条指令的计算结果。如果能够将计算结果从其产生的地 方直接送到需要它的地方，就可以 避免暂停。(2)采用定向技术消除上例中的相关 工作过程演示,3.3 流水线中的相关,(3)当定向硬件检测到前面某条指令的结果寄存 器就是当前指令的源寄存器时，控制逻辑会 将前面那条指令的结果直接从其产生的地方 定向到当前指令所需的位置。(4)一个功能单元的输出不仅可以定向到其自身 的输入，而且还可以定向到其它单元的输入。举例,3.3 流水线中的相关,3.3 流水线中的相关,(5)在DLX中，任何流水寄存器到任何功能单元的 输入都可能需要定向路径。,(6)当两条指令对存储器同一单元进行读写时，也可能发生

5、数据相关。但本章仅讨论有关寄 存器的数据相关。,3.数据相关的分类,按照指令对寄存器的读写顺序，可以将数据相关分为以下三种类型：（考虑两条指令i和j，假设i 先进入流水线）,3.3 流水线中的相关,(2)写后写相关(WAW)在 i 写入之前，j 先写。最后写入的结果是 i 的，错误！,(1)写后读相关(RAW)(命名规则)在 i 写入之前，j 先去读。j 读出的内容是错误的。这是最常见的相关。,这种相关仅出现在这样的流水线中：,流水线中有多个段可以进行写操作 当某条指令在流水线中暂停时，允许其后 的指令继续向前流动。,3.3 流水线中的相关,DLX整数流水线中不会发生这种相关（仅在WB段进行写

6、操作）,若对DLX作以下修改，则会发生WAW相关：把ALU操作指令的“写回”移到MEM段 假设访问数据存储器需占用两拍 举例,(3)读后写相关(WAR),在 i 读之前，j 先写。i 读出的内容是错误的！,这种相关仅出现在这样的流水线中：有些指令是在流水线的后部读源操作数，而有些指令则是在流水线的前部写结果。,DLX流水线中不会发生这种相关；（读在先(ID),写在后(WB)）,这种相关很少发生；（因为流水线一般是先读操作数，后写结果）,复杂指令可能导致这种相关。,3.3 流水线中的相关,(1)并非所有的数据相关都可以用定向技术解决 举例,4.需要暂停的数据相关,3.3 流水线中的相关,(2)增

7、加流水线互锁硬件，插入“暂停”。当互锁硬件发现这种相关时，就 暂停流水线，直到相关消失。举例：演示A 演示B,3.3 流水线中的相关,3.3 流水线中的相关,例3.5 假设某指令序列中20的指令是Load指令，并且紧跟在Load指令之后的半数指令需要使用到载入的结果，如果这种数据相关将产生一个时钟周期的延迟。理想流水线（没有任何延迟，CPI为1）的指令执行速度要比这种真实流水线的快多少？解：我们可以利用CPI作为衡量标准。对于真实的流水线而言，由于Load指令之后的半数指令需要暂停，所以这些被暂停指令的CPI是2。又知Load指令占全部指令的20，所以真实流水线的实际CPI为：(0.91+0.

8、12)=1.1，这表示理想流水线的指令执行速度是其执行速度的1.1倍。,3.3 流水线中的相关,5对数据相关的编译调度方法,(1)流水线中常常会遇到许多种类型的暂停 例如，按通常的代码生成模式，表达式 ABC的代码会导致暂停,3.3 流水线中的相关,ABC的代码会导致暂停,(3)举例：例3.6 请为下列表达式生成没有暂停的DLX 指令序列：abc；def；假设载入延迟为1个时钟周期。题解,(2)编译器可以通过重新排列代码的顺序来消除这种暂停，这种技术称为流水线调度或 指令调度。,3.3 流水线中的相关,(1)指令发射(issue)：指令从译码段(ID)进入 执行段(EX)。相应的指令称为已发射

9、的指令。(2)DLX整数流水线中，可以在ID段检测所有的 数据相关；若数据相关，则在指令流出前，让其暂停。(3)可以在ID段确定需要什么样的定向，并设置 相应的控制；这样能减少硬件复杂度(因为不必挂起已 改变了机器状态的指令）。,6.对DLX流水线控制的实现,3.3 流水线中的相关,(4)也可以在需要用到操作数的那个时钟周期检测 相关或定向；(5)举例说明：由Load指令引起的RAW相关的互锁(简称Load 互锁)可以通过ID段的检测来实现；到ALU输入的定向可以在EX段实现。Load互锁 流水线相关硬件可以检测到的各种相关情况 可以看出，仅需把Load指令的目的寄存 器地址与Load指令后的

10、两条指令的源寄存器 地址进行比较。,3.3 流水线中的相关,在ID段检测是否需要启动Load互锁需要进行 三种比较,当检测到相关后，控制部件必须在流水线中 插入暂停周期，并使IF和ID段中的指令停止 前进。,将ID/EX中的控制部分清“O”。IF/ID内容回送到其自身入口。,定向逻辑 有更多的情况要考虑 关键思路：流水线寄存器不仅包含数据，而且 包含源寄存器和目的寄存器地址（字段）,3.3 流水线中的相关,所有的定向发生在：ALU或DM输出 ALU输入，DM输入，“O”检测部件(图示),流水线的控制相关,1.分支指令的执行结果,一、分支引起的暂停及减少分支开销的方法,转移失败：PC值加4 转移

11、成功：将PC值改变为转移目标地址 到MEM段的末尾才改变,一旦检测到分支指令(在ID段)，就暂停执行其后的指令，直到分支指令到达MEM段，确定出新的PC值为止。,2.处理分支指令最简单的方法,3.3 流水线中的相关,在DLX流水线中，分支转移成功导致暂停3个时钟周期。若分支指令的频度为30，理想CPI1，则 实际CPI13032,3.减少分支开销的两种途径,在流水线中尽早判断分支转移是否成功；转移成功时，尽早计算出转移目标地址。两者应同时采用，缺一不可。对于DLX作如下改进:(1)把“0？”测试移至ID段；,3.3 流水线中的相关,(2)在ID段增设一个加法器，这样可以把分支 开销减少一拍。改

12、进后流水线的分支操作（表3.5）,3.3 流水线中的相关,流 水 段,分 支 指 令 操 作,IF,ID,EX,IF/ID.IR MemPC;IF/ID.NPC,PC(if ID/EX.cond ID/EX.NPC else PC+4);,ID/EX.A RegsIF/ID.IR6.10;ID/EX.B RegsIF/ID.IR11.15;ID/EX.NPC IF/ID.NPC+(IR16)16#IR16.31;ID/EX.IR IF/ID.IR;ID/EX.cond(RegsIF/ID.IR6.10 op 0;ID/EX.Imm(IR16)16#IR16.31;,MEM,WB,表 3.5 改

13、进后流水线的分支操作,(动画演示),(动画演示),二、程序中分支的行为特点,1.各种能改变PC值的指令的执行频度（SPEC基准程序，DLX上执行）条件分支 整数程序：1415 浮点程序：312 向前分支与向后分支的比：31 无条件分支 绝大多数：4,3.3 流水线中的相关,2条件分支转移成功的概率,平均值 整数程序 向前：13无条件：4 向后：3 浮点程序 向前：7 无条件：1 向右：3,所有条件分支：67向前：60向后：85（向后分支一般形成循环）,3.3 流水线中的相关,3.3 流水线中的相关,三、减少流水线分支损失的方法,（种简单的静态方法，编译时预测）,1.“冻结”或“排空”流水线 在

14、流水线中停住或删除分支后的指令，直到知道转移目标地址。优点：简单。,2预测分支失败 流水线继续照常流动，就像没发生什么似的。,3.3 流水线中的相关,在知道分支结果之前，分支指令后的指令不 能改变机器状态，或者改变了之后能够回退。若分支失败，则照常执行；否则，从转移目 标处开始取指令执行。DLX流水线的处理过程,3.3 流水线中的相关,3.预测分支成功 假设分支转移成功，并开始从分支目标地址 处取指令执行。起作用的前题：先知道分支目标地址，后知 道分支是否成功。对DLX流水线没有任何好处。,3.3 流水线中的相关,4.延迟分支(delayed branch)(1)基本概念 把分支开销为n 的分

15、支指令看成是延迟长 度为n 的分支指令，其后紧跟有n 个延迟槽。流水线遇到分支指令时，按正常方式处理，顺 带执行延迟槽中的指令，从而减少分支开销。延迟分支以及指令的执行顺序,3.3 流水线中的相关,(2)具有一个分支延迟槽的DLX流水线的执行过程分支延迟槽中的指令“掩盖”了流水线原来 必需插入的暂停周期。,3.3 流水线中的相关,(3)分支延迟指令的调度（编译器）任务：在延迟槽中放入有用的指令 三种调度方法,从前调度（最好）从目标处调度 从失败处调度,调 度 策 略,对调度的要求,什么情况下起作用？,从 前 调 度,从目标处调度,从失败处调度,必须保证在分支失败时执行被调度的指令不会导致错误。

16、有可能需要复制指令。,被调度的指令必须与分支无关,必须保证在分支成功时执行被调度的指令不会导致错误。,任何情况,分支成功时(但由于复制指令，有可能会增大程序空间),分支失败时,三种方法的要求及效果,对放入延迟槽的指令有限制 编译器预测分支是否成功的能力,延迟分支调度受到的限制,进一步改进：引入“取消分支”若预测方向正确，正常执行延迟槽中的指令；否则，将之变为no-op指令。,3.3 流水线中的相关,3.3 流水线中的相关,预测成功-取消”分支的执行过程,四、各种分支处理方法的性能,1.假设：,理想CPI1 则流水线的加速比为：SD(1C）D(1fp分支)D 流水线的深度,C 分支引起的流水线暂

17、停时钟周期数(每条指令的平均值)f 分支的出现频度p分支 分支开销,2DLX流水线中各种分支处理方法的开销(表3.7),3.3 流水线中的相关,表 3.7 各种减少分支损失方法的效果,调度方法,每条分支指令的平均分支损失,暂停流水线,预测分支成功,预测分支失败,1.00,每条条件分支指 令的分支损失,延迟分支,每条无条件分支指令的损失,具有分支暂停 的实际 CPI,整型平均,浮点平均,整型平均,整型平均,浮点平均,浮点平均,1.00,1.00,0.62,0.25,1.00,1.00,1.00,1.00,1.00,0.69,0.21,1.00,1.17,1.15,1.00,1.17,1.15,0.74,1.12,1.11,0.70,1.00,0.35,0.00,0.30,1.04,1.04,3.3 流水线中的相关,