流水线技术--流水线中的相关

1、1633.3流水线中的相关1相关的概念 流水线中的相关流水线中的相关是指相邻或相近的两条指是指相邻或相近的两条指令因存在某种关联，后一条指令不能在原指定令因存在某种关联，后一条指令不能在原指定的时钟周期开始执行的时钟周期开始执行。 结构相关结构相关 当硬件资源满足不了同时重叠执行的指当硬件资源满足不了同时重叠执行的指 令的要求，而发生资源冲突时，就发生令的要求，而发生资源冲突时，就发生了结了结 构相关。构相关。2相关的分类第三章 流水线技术虚拟存储器的特点263 数据相关数据相关 当一条指令需要用到前面某条指令的结当一条指令需要用到前面某条指令的结 果，从而不能重叠执行时，就发生了果，从而不能

2、重叠执行时，就发生了数据相数据相 关关。 控制相关控制相关 当流水线遇到分支指令和其他能够改变当流水线遇到分支指令和其他能够改变 PCPC值的指令时，就会发生值的指令时，就会发生控制相关控制相关。3几个问题 相关有可能会使流水线停顿。相关有可能会使流水线停顿。3.3 流水线中的相关虚拟存储器的特点363在本章中，我们在本章中，我们约定：约定： 当一条指令被暂停时，暂停在其后发射（流出）的指令，但继续执行在其前发射的 指令。 消除相关的消除相关的基本方法：基本方法： 让流水线中的某些指令暂停，而让其它让流水线中的某些指令暂停，而让其它 指令继续执行。指令继续执行。3.3 流水线中的相关虚拟存储器

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

4、或“气泡气泡”）3.3 流水线中的相关虚拟存储器的特点虚拟存储器的特点虚拟存储器的特点863引入暂停后的时空图引入暂停后的时空图3.3 流水线中的相关虚拟存储器的特点9635. 避免结构相关：6. 有些设计方案允许有结构相关 所有功能单元完全流水化所有功能单元完全流水化 设置足够的硬件资源设置足够的硬件资源硬件代价很大。硬件代价很大。 降低成本降低成本 减少部件的延迟减少部件的延迟解决方法解决方法： 设置相互独立的指令存储器和设置相互独立的指令存储器和 数据存储器或设置相互独立的数据存储器或设置相互独立的 指令指令CacheCache和数据和数据CacheCache。3.3 流水线中的相关虚拟

5、存储器的特点10633.3.2 流水线的数据相关1. 数据相关简介 当指令在流水线中重叠执行时，流水线有当指令在流水线中重叠执行时，流水线有 可能改变指令读可能改变指令读/ /写操作数的顺序，使之不同写操作数的顺序，使之不同 于它们在非流水实现时的顺序，这将导致数据于它们在非流水实现时的顺序，这将导致数据 相关。相关。 数据相关举例数据相关举例3.3 流水线中的相关虚拟存储器的特点虚拟存储器的特点12632. 利用定向技术减少数据相关引起的暂停 (1)(1) 定向技术的定向技术的主要思路：主要思路：在发生上述在发生上述 数据相关时，后面的指令并不是马数据相关时，后面的指令并不是马 上就要用到前

6、一条指令的计算结果。上就要用到前一条指令的计算结果。 如果能够将计算结果从其产生的地如果能够将计算结果从其产生的地 方直接送到需要它的地方，就可以方直接送到需要它的地方，就可以 避免暂停。避免暂停。 (2) (2) 采用定向技术消除上例中的相关采用定向技术消除上例中的相关 工作过程演示工作过程演示3.3 流水线中的相关虚拟存储器的特点虚拟存储器的特点虚拟存储器的特点1563(3) (3) 当定向硬件检测到前面某条指令的结果寄存当定向硬件检测到前面某条指令的结果寄存 器就是当前指令的源寄存器时，控制逻辑会器就是当前指令的源寄存器时，控制逻辑会 将前面那条指令的结果直接从其产生的地方将前面那条指令

7、的结果直接从其产生的地方 定向到当前指令所需的位置。定向到当前指令所需的位置。(4) (4) 一个功能单元的输出不仅可以定向到其自身一个功能单元的输出不仅可以定向到其自身 的输入，而且还可以定向到其它单元的输入。的输入，而且还可以定向到其它单元的输入。 举例举例3.3 流水线中的相关虚拟存储器的特点16633.3 流水线中的相关虚拟存储器的特点1763(5) (5) 在在DLXDLX中，任何流水寄存器到任何功能单元的中，任何流水寄存器到任何功能单元的 输入都可能需要定向路径。输入都可能需要定向路径。(6) (6) 当两条指令对存储器同一单元进行读写时，当两条指令对存储器同一单元进行读写时， 也

8、可能发生数据相关。但本章仅讨论有关寄也可能发生数据相关。但本章仅讨论有关寄 存器的数据相关。存器的数据相关。3. 数据相关的分类 按照指令对寄存器的读写顺序，可以将数据按照指令对寄存器的读写顺序，可以将数据相关分为以下三种类型：相关分为以下三种类型：（考虑（考虑两条指令两条指令i i和和j j ， 假设假设i i 先进入流水线）先进入流水线）3.3 流水线中的相关虚拟存储器的特点虚拟存储器的特点1963(2) (2) 写后写相关写后写相关 (WAW)(WAW) 在在 i i 写入之前，写入之前，j j 先写。先写。 最后写入的结果是最后写入的结果是 i i 的，错误！的，错误！(1) (1)

9、写后读相关写后读相关 (RAW) (RAW) ( (命名规则命名规则) ) 在在 i i 写入之前，写入之前，j j 先去读。先去读。 j j 读出的内容是错误的。读出的内容是错误的。 这是最常见的相关。这是最常见的相关。 这种相关仅出现在这样的流水线中这种相关仅出现在这样的流水线中： 流水线中有多个段可以进行写操作流水线中有多个段可以进行写操作 当某条指令在流水线中暂停时，允许其后当某条指令在流水线中暂停时，允许其后 的指令继续向前流动。的指令继续向前流动。3.3 流水线中的相关虚拟存储器的特点 DLX DLX整数流水线中不会发生这种相关整数流水线中不会发生这种相关 （仅在（仅在WBWB段进

10、行写操作）段进行写操作） 若对若对DLXDLX作以下修改，则会发生作以下修改，则会发生WAWWAW相关相关： 把把ALUALU操作指令的操作指令的“写回写回”移到移到MEMMEM段段 假设访问数据存储器需占用两拍假设访问数据存储器需占用两拍 举例举例虚拟存储器的特点2163(3) (3) 读后写相关读后写相关 (WAR)(WAR)在在 i i 读之前，读之前，j j 先写。先写。i i 读出的内容是错误的！读出的内容是错误的！ 这种相关仅出现在这样的流水线中：这种相关仅出现在这样的流水线中： 有些指令是在流水线的后部读源操作数，有些指令是在流水线的后部读源操作数， 而有些指令则是在流水线的前部

11、写结果。而有些指令则是在流水线的前部写结果。 DLX DLX流水线中不会发生这种相关；流水线中不会发生这种相关； （读在先（读在先(ID),(ID),写在后写在后(WB)(WB)） 这种相关很少发生；这种相关很少发生； （因为流水线一般是先读操作数，后写结果）（因为流水线一般是先读操作数，后写结果） 复杂指令可能导致这种相关。复杂指令可能导致这种相关。3.3 流水线中的相关虚拟存储器的特点2263(1) (1) 并非所有的数据相关都可以用定向技术解决并非所有的数据相关都可以用定向技术解决 举例举例4. 需要暂停的数据相关3.3 流水线中的相关2463(2) (2) 增加流水线互锁硬件，插入增加

12、流水线互锁硬件，插入“暂停暂停”。 当互锁硬件发现这种相关时，就当互锁硬件发现这种相关时，就 暂停流水线暂停流水线，直到相关消失。直到相关消失。 举例：举例：演示演示A A 演示演示B B 3.3 流水线中的相关26633.3 流水线中的相关2763例例3.53.5 假设某指令序列中假设某指令序列中2020的指令是的指令是LoadLoad指令，指令，并且紧跟在并且紧跟在LoadLoad指令之后的半数指令需要使用到载指令之后的半数指令需要使用到载入的结果，如果这种数据相关将产生一个时钟周期入的结果，如果这种数据相关将产生一个时钟周期的延迟。理想流水线（没有任何延迟，的延迟。理想流水线（没有任何延

13、迟，CPICPI为为1 1）的）的指令执行速度要比这种真实流水线的快多少？指令执行速度要比这种真实流水线的快多少？解解：我们可以利用我们可以利用CPICPI作为衡量标准。对于真实的流作为衡量标准。对于真实的流水线而言，由于水线而言，由于LoadLoad指令之后的半数指令需要暂停，指令之后的半数指令需要暂停，所以这些被暂停指令的所以这些被暂停指令的CPICPI是是2 2。又知。又知LoadLoad指令占全指令占全部指令的部指令的2020，所以真实流水线的实际，所以真实流水线的实际CPICPI为：为：(0.9(0.91+0.11+0.12)=1.12)=1.1，这表示理想流水线的指令执，这表示理想

14、流水线的指令执行速度是其执行速度的行速度是其执行速度的1.11.1倍倍。 3.3 流水线中的相关28635对数据相关的编译调度方法 (1) (1) 流水线中常常会遇到许多种类型的暂停流水线中常常会遇到许多种类型的暂停 例如，按通常的代码生成模式，表达式例如，按通常的代码生成模式，表达式 A AB BC C的代码会导致暂停的代码会导致暂停3.3 流水线中的相关A AB BC C的代码会导致暂停的代码会导致暂停3063(3) (3) 举例：举例： 例例3.63.6 请为下列表达式生成没有暂停的请为下列表达式生成没有暂停的DLXDLX 指令序列：指令序列： a ab bc c ； d de ef f

15、 ； 假设载入延迟为假设载入延迟为1 1个时钟周期。个时钟周期。 题解题解(2) (2) 编译器可以通过重新排列代码的顺序来消编译器可以通过重新排列代码的顺序来消除这种暂停，这种技术称为除这种暂停，这种技术称为流水线调度或流水线调度或 指令调度。指令调度。3.3 流水线中的相关3263(1) (1) 指令发射指令发射(issue)(issue)：指令从译码段：指令从译码段(ID)(ID)进入进入 执行段执行段(EX)(EX)。 相应的指令称为相应的指令称为已发射的指令已发射的指令。 (2) DLX(2) DLX整数流水线中，可以在整数流水线中，可以在IDID段检测所有的段检测所有的 数据相关；

16、数据相关； 若数据相关，则在指令流出前，让其暂停。若数据相关，则在指令流出前，让其暂停。 (3) (3) 可以在可以在IDID段确定需要什么样的定向，并设置段确定需要什么样的定向，并设置 相应的控制；相应的控制； 这样能减少硬件复杂度这样能减少硬件复杂度( (因为不必挂起已因为不必挂起已 改变了机器状态的指令）。改变了机器状态的指令）。6. 对DLX流水线控制的实现3.3 流水线中的相关3363(4) (4) 也可以在需要用到操作数的那个时钟周期检测也可以在需要用到操作数的那个时钟周期检测 相关或定向；相关或定向；(5) (5) 举例说明：举例说明： 由由LoadLoad指令引起的指令引起的R

17、AWRAW相关的互锁相关的互锁( (简称简称Load Load 互锁互锁) )可以通过可以通过IDID段的检测来实现；段的检测来实现； 到到ALUALU输入的定向可以在输入的定向可以在EXEX段实现。段实现。LoadLoad互锁互锁 流水线相关硬件可以检测到的各种相关情况流水线相关硬件可以检测到的各种相关情况 可以看出，仅需把可以看出，仅需把LoadLoad指令的目的寄存指令的目的寄存 器地址与器地址与LoadLoad指令后的两条指令的源寄存器指令后的两条指令的源寄存器 地址进行比较。地址进行比较。3.3 流水线中的相关 在在IDID段检测是否需要启动段检测是否需要启动LoadLoad互锁需要

18、进行互锁需要进行 三种比较三种比较3663 当检测到相关后，控制部件必须在流水线中当检测到相关后，控制部件必须在流水线中 插入暂停周期，并使插入暂停周期，并使IFIF和和IDID段中的指令停止段中的指令停止 前进。前进。l 将将ID/EXID/EX中的控制部分清中的控制部分清“O”O”。l IF/IDIF/ID内容回送到其自身入口。内容回送到其自身入口。定向逻辑定向逻辑 有更多的情况要考虑有更多的情况要考虑 关键思路：关键思路：流水线寄存器不仅包含数据，而且流水线寄存器不仅包含数据，而且 包含源寄存器和目的寄存器地址（字段）包含源寄存器和目的寄存器地址（字段）3.3 流水线中的相关3763 所

19、有的定向发生在：所有的定向发生在： ALUALU或或DMDM输出输出 ALU ALU输入，输入，DMDM输入，输入， “O”O”检测部件检测部件 ( (图示图示) )386339633.3.3 流水线的控制相关1. 分支指令的执行结果一、分支引起的暂停及减少分支开销的方法 转移失败：转移失败：PCPC值加值加4 4 转移成功：转移成功：将将PCPC值改变为转移目标地址值改变为转移目标地址 到到MEMMEM段的末尾才改变段的末尾才改变 一旦检测到分支指令一旦检测到分支指令( (在在IDID段段) )，就暂停，就暂停执行其后的指令，直到分支指令到达执行其后的指令，直到分支指令到达MEMMEM段，段

20、，确定出新的确定出新的PCPC值为止。值为止。2. 处理分支指令最简单的方法3.3 流水线中的相关 在在DLXDLX流水线中，分支转移成功导致流水线中，分支转移成功导致暂停暂停3 3个个时钟周期时钟周期。 若分支指令的频度为若分支指令的频度为3030，理想理想CPICPI1 1， 则则 实际实际CPICPI1 13030323241633. 减少分支开销的两种途径 在流水线中尽早判断分支转移是否成功；在流水线中尽早判断分支转移是否成功； 转移成功时，尽早计算出转移目标地址。转移成功时，尽早计算出转移目标地址。两者应同时采用，缺一不可。两者应同时采用，缺一不可。对于对于DLXDLX作如下改进作如

21、下改进: :(1) (1) 把把“0 0？”测试移至测试移至IDID段；段；3.3 流水线中的相关4363(2) (2) 在在IDID段增设一个加法器，这样可以把分支段增设一个加法器，这样可以把分支 开销减少一拍。开销减少一拍。 改进后流水线的分支操作改进后流水线的分支操作 （表（表3.53.5）3.3 流水线中的相关流流 水水 段段分分 支支 指指 令令 操操 作作IFIFIDIDEXEXIF/ID.IR IF/ID.IR MemPC; IF/ID.NPC,PC MemPC; IF/ID.NPC,PC (if ID/EX.cond ID/EX.NPC else PC+4); (if ID/E

22、X.cond ID/EX.NPC else PC+4);ID/EX.A ID/EX.A RegsIF/ID.IR RegsIF/ID.IR6.106.10; ID/EX.B ; ID/EX.B RegsIF/ID.IR RegsIF/ID.IR11.1511.15;ID/EX.NPC ID/EX.NPC IF/ID.NPC + (IR IF/ID.NPC + (IR1616) )1616#IR#IR16.3116.31; ;ID/EX.IR ID/EX.IR IF/ID.IR; ID/EX.cond IF/ID.IR; ID/EX.cond (RegsIF/ID.IR (RegsIF/ID.I

23、R6.106.10 op 0; op 0;ID/EX.Imm ID/EX.Imm (IR (IR1616) )1616#IR#IR16.3116.31; ;MEMMEMWBWB表 3.5 改进后流水线的分支操作( (动画演示动画演示) )( (动画演示动画演示) )4563二、程序中分支的行为特点1. 各种能改变各种能改变PCPC值的指令的执行频度值的指令的执行频度 （SPECSPEC基准程序，基准程序，DLXDLX上执行）上执行） 条件分支条件分支 整数程序：整数程序：14141515 浮点程序：浮点程序：3 31212 向前分支与向后分支的比：向前分支与向后分支的比： 3131 无条件分支

24、无条件分支 绝大多数：绝大多数：443.3 流水线中的相关47632条件分支转移成功的概率条件分支转移成功的概率 平均值平均值 整数程序整数程序 向前：向前：1313无条件：无条件：4 4 向后：向后：3 3 浮点程序浮点程序 向前：向前：7 7 无条件：无条件：1 1 向右：向右：3 3所有条件分支：所有条件分支：6767向前：向前：6060向后：向后：8585（向后分支一般形成循环）（向后分支一般形成循环）3.3 流水线中的相关48633.3 流水线中的相关4963三、减少流水线分支损失的方法（种简单的静态方法，编译时预测）（种简单的静态方法，编译时预测）1. “冻结”或“排空”流水线 在

25、流水线中停住或删除分支后的指令，在流水线中停住或删除分支后的指令，直到知道转移目标地址。直到知道转移目标地址。 优点：优点：简单。简单。2预测分支失败 流水线继续照常流动，就像没发生什么似的。流水线继续照常流动，就像没发生什么似的。3.3 流水线中的相关5063 在知道分支结果之前，分支指令后的指令不在知道分支结果之前，分支指令后的指令不 能改变机器状态，或者改变了之后能够回退。能改变机器状态，或者改变了之后能够回退。 若分支失败，则照常执行；否则，从转移目若分支失败，则照常执行；否则，从转移目 标处开始取指令执行。标处开始取指令执行。 DLXDLX流水线的处理过程流水线的处理过程 3.3 流

26、水线中的相关52633. 3. 预测分支成功预测分支成功 假设分支转移成功，并开始从分支目标地址假设分支转移成功，并开始从分支目标地址 处取指令执行。处取指令执行。 起作用的前题：先知道分支目标地址，后知起作用的前题：先知道分支目标地址，后知 道分支是否成功。道分支是否成功。 对对DLXDLX流水线没有任何好处。流水线没有任何好处。3.3 流水线中的相关53634. 延迟分支 (delayed branch)(delayed branch) (1)(1) 基本概念基本概念 把分支开销为把分支开销为n n 的分支指令看成是延迟长的分支指令看成是延迟长 度为度为n n 的分支指令，其后紧跟有的分支

27、指令，其后紧跟有n n 个延迟槽。个延迟槽。 流水线遇到分支指令时，按正常方式处理，顺流水线遇到分支指令时，按正常方式处理，顺 带执行延迟槽中的指令，从而减少分支开销。带执行延迟槽中的指令，从而减少分支开销。 延迟分支以及指令的执行顺序延迟分支以及指令的执行顺序 3.3 流水线中的相关5563(2)(2) 具有一个分支延迟槽的具有一个分支延迟槽的DLXDLX流水线的流水线的执行过程执行过程分支延迟槽中的指令分支延迟槽中的指令“掩盖掩盖”了流水线原来了流水线原来 必需插入的暂停周期。必需插入的暂停周期。3.3 流水线中的相关5663(3) (3) 分支延迟指令的调度（编译器）分支延迟指令的调度（

28、编译器）任务：任务：在延迟槽中放入有用的指令在延迟槽中放入有用的指令 三种调度方法三种调度方法l 从前调度从前调度 （最好）（最好）l 从目标处调度从目标处调度l 从失败处调度从失败处调度5863调 度 策 略对调度的要求什么情况下起作用？从从 前前 调调 度度从目标处调度从目标处调度从失败处调度从失败处调度必须保证在分支失败时执行被调度必须保证在分支失败时执行被调度的指令不会导致错误。有可能需要的指令不会导致错误。有可能需要复制指令。复制指令。被调度的指令必须与分支无关被调度的指令必须与分支无关必须保证在分支成功时执行被调度必须保证在分支成功时执行被调度的指令不会导致错误。的指令不会导致错误。任何情况任何情况 分支成功时分支成功时( (但由于复制指令，有但由于复制指令，有可能会增大程序空间可能会增大程序空间) )分支失败时分支失败时 三种方法的要求及效果三种方法的要求及效果5963l 对放入延迟槽的指令有限制对放入延