流水线中相关.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中，任何流水寄存器到任何功能单元的 输入

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

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

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

8、言，由于Load指令之后的半数指令需要暂停，所以这些被暂停指令的CPI是2。又知Load指令占全部指令的20，所以真实流水线的实际CPI为：(0.91+0.12)=1.1，这表示理想流水线的指令执行速度是其执行速度的1.1倍。,3.3 流水线中的相关,5对数据相关的编译调度方法,(1) 流水线中常常会遇到许多种类型的暂停 例如，按通常的代码生成模式，表达式 ABC的代码会导致暂停,3.3 流水线中的相关,ABC的代码会导致暂停,(3) 举例： 例3.6 请为下列表达式生成没有暂停的DLX 指令序列： abc ； def ； 假设载入延迟为1个时钟周期。 题解,(2) 编译器可以通过重新排列代码

9、的顺序来消 除这种暂停，这种技术称为流水线调度或 指令调度。,3.3 流水线中的相关,(1) 指令发射(issue)：指令从译码段(ID)进入 执行段(EX)。 相应的指令称为已发射的指令。 (2) DLX整数流水线中，可以在ID段检测所有的 数据相关； 若数据相关，则在指令流出前，让其暂停。 (3) 可以在ID段确定需要什么样的定向，并设置 相应的控制； 这样能减少硬件复杂度(因为不必挂起已 改变了机器状态的指令）。,6. 对DLX流水线控制的实现,3.3 流水线中的相关,(4) 也可以在需要用到操作数的那个时钟周期检测 相关或定向； (5) 举例说明： 由Load指令引起的RAW相关的互锁

10、(简称Load 互锁)可以通过ID段的检测来实现； 到ALU输入的定向可以在EX段实现。 Load互锁 流水线相关硬件可以检测到的各种相关情况 可以看出，仅需把Load指令的目的寄存 器地址与Load指令后的两条指令的源寄存器 地址进行比较。,3.3 流水线中的相关, 在ID段检测是否需要启动Load互锁需要进行 三种比较, 当检测到相关后，控制部件必须在流水线中 插入暂停周期，并使IF和ID段中的指令停止 前进。,将ID/EX中的控制部分清“O”。 IF/ID内容回送到其自身入口。,定向逻辑 有更多的情况要考虑 关键思路：流水线寄存器不仅包含数据，而且 包含源寄存器和目的寄存器地址（字段）,

11、3.3 流水线中的相关, 所有的定向发生在： ALU或DM输出 ALU输入，DM输入， “O”检测部件 (图示),3.3.3 流水线的控制相关,1. 分支指令的执行结果,一、分支引起的暂停及减少分支开销的方法, 转移失败：PC值加4 转移成功：将PC值改变为转移目标地址 到MEM段的末尾才改变,一旦检测到分支指令(在ID段)，就暂停 执行其后的指令，直到分支指令到达MEM段， 确定出新的PC值为止。,2. 处理分支指令最简单的方法,3.3 流水线中的相关,在DLX流水线中，分支转移成功导致暂停3个 时钟周期。 若分支指令的频度为30，理想CPI1， 则 实际CPI13032,3. 减少分支开销

12、的两种途径, 在流水线中尽早判断分支转移是否成功； 转移成功时，尽早计算出转移目标地址。 两者应同时采用，缺一不可。 对于DLX作如下改进: (1) 把“0？”测试移至ID段；,3.3 流水线中的相关,(2) 在ID段增设一个加法器，这样可以把分支 开销减少一拍。 改进后流水线的分支操作 （表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.IR610; ID/EX.B RegsIF/ID.

13、IR1115; ID/EX.NPC IF/ID.NPC + (IR16)16#IR1631; ID/EX.IR IF/ID.IR; ID/EX.cond (RegsIF/ID.IR610 op 0; ID/EX.Imm (IR16)16#IR1631;,MEM,WB,表 3.5 改进后流水线的分支操作,(动画演示),(动画演示),二、程序中分支的行为特点,1. 各种能改变PC值的指令的执行频度 （SPEC基准程序，DLX上执行） 条件分支 整数程序：1415 浮点程序：312 向前分支与向后分支的比： 31 无条件分支 绝大多数：4,3.3 流水线中的相关,2条件分支转移成功的概率, 平均值

14、整数程序 向前：13 无条件：4 向后：3 浮点程序 向前：7 无条件：1 向右：3,所有条件分支：67 向前：60 向后：85 （向后分支一般形成循环）,3.3 流水线中的相关,3.3 流水线中的相关,三、减少流水线分支损失的方法,（种简单的静态方法，编译时预测）,1. “冻结”或“排空”流水线 在流水线中停住或删除分支后的指令， 直到知道转移目标地址。 优点：简单。,2预测分支失败 流水线继续照常流动，就像没发生什么似的。,3.3 流水线中的相关, 在知道分支结果之前，分支指令后的指令不 能改变机器状态，或者改变了之后能够回退。 若分支失败，则照常执行；否则，从转移目 标处开始取指令执行。

15、 DLX流水线的处理过程,3.3 流水线中的相关,3. 预测分支成功 假设分支转移成功，并开始从分支目标地址 处取指令执行。 起作用的前题：先知道分支目标地址，后知 道分支是否成功。 对DLX流水线没有任何好处。,3.3 流水线中的相关,4. 延迟分支 (delayed branch) (1) 基本概念 把分支开销为n 的分支指令看成是延迟长 度为n 的分支指令，其后紧跟有n 个延迟槽。 流水线遇到分支指令时，按正常方式处理，顺 带执行延迟槽中的指令，从而减少分支开销。 延迟分支以及指令的执行顺序,3.3 流水线中的相关,(2) 具有一个分支延迟槽的DLX流水线的执行过程 分支延迟槽中的指令“

16、掩盖”了流水线原来 必需插入的暂停周期。,3.3 流水线中的相关,(3) 分支延迟指令的调度（编译器） 任务：在延迟槽中放入有用的指令 三种调度方法,从前调度 （最好） 从目标处调度 从失败处调度,调 度 策 略,对调度的要求,什么情况下起作用？,从 前 调 度,从目标处调度,从失败处调度,必须保证在分支失败时执行被调度 的指令不会导致错误。有可能需要 复制指令。,被调度的指令必须与分支无关,必须保证在分支成功时执行被调度 的指令不会导致错误。,任何情况,分支成功时 (但由于复制指令，有 可能会增大程序空间),分支失败时, 三种方法的要求及效果,对放入延迟槽的指令有限制 编译器预测分支是否成功

17、的能力, 延迟分支调度受到的限制, 进一步改进：引入“取消分支” 若预测方向正确，正常执行延迟槽中的指令； 否则，将之变为no-op指令。,3.3 流水线中的相关,3.3 流水线中的相关,预测成功-取消”分支的执行过程,四、各种分支处理方法的性能,1. 假设：,理想CPI1 则流水线的加速比为： SD(1C）D(1fp分支) D 流水线的深度,C 分支引起的流水线暂停时钟周期数 (每条指令的平均值) 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 流水线中的相关,