25-Hazard-handle

冲突的种类

• 什么是流水线中的“冲突”？
  • 在流水线中经常有一些被称为“冲突”的情况发生，它使得指令序列中下一条指令无法按照设计的时钟周期执行，这些“冲突”可能会降低流水线可以获得的理想性能。
• 流水线中的冲突种类
  • 第一种是结构冲突，是指令在重叠执行的过程中，硬件资源满足不了指令重叠执行的要求，发生硬件资源冲突而产生的冲突。
  • 第二种是数据冲突，是指在同时重叠执行的几条指令中，一条指令依赖于前面指令执行结果数据，但是又得不到时发生的冲突。
  • 第三种是控制冲突，它是指流水线中的分支指令或者其他需要改写 PC 的指令造成的冲突。
• 解决流水线中“冲突”问题的重要性
  • 流水线冲突问题是流水线执行过程中的主要障碍，会给流水线中指令序列的顺利执行带来许多不利的影响。
  • 如果不能较好的处理流水线冲突问题，就可能影响流水线的性能，甚至使程序运行产生错误的结果。

结构冲突

• 同一个时间段内，同一个部件的同一功能端口被不同的指令同时使用——硬件资源不足
• 解决策略：
  1. 通过合理的功能划分，要求一个部件每条指令只能使用一次，且只能在特定周期使用，避免一部分结构冲突
  2. 设置多个独立部件来避免结构冲突，本质是增加硬件资源的数量：
     • 如区分寄存器的写端口和读端口，分别用使用下降沿和上升沿触发
     • 如区分存储器的指令部分和数据部分（哈佛架构），从而使指令和数据的访问各自独立；
  3. 引入暂停周期，后果是降低流水线的性能

• IM 和 DM 是指令存储器和数据存储器；
• 现代 L1 cache 天然区分 i-cache 和 d-cache，由此可以避免结构冲突
• Reg 分前半周期和后半周期进行访问，实现写端口和读端口独立地访问；

数据冲突

• 后发指令需要前面指令的结果时，却还没有产生、或正在产生但没有写入到寄存器中；
• 上图的所有数据冲突都是由于前面的指令在写结果之前，后面的指令就要读取，这称为写后读 Read After Write 数据冲突
• 事实上，在非“乱序”执行的流水线中，所有数据冲突都是 RAW 冲突；

[! note] 写后写冲突 Wirte After Write 假设指令 i 在 j 之前进入流水线，指令 j 和指令 i 的目的操作数相同，但是当它们在流水线中重叠执行时，指令 j 可能在指令 i 将其计算结果写入之前就先行对保存该计算结果的寄存器进行了写操作，这样就导致了寄存器写入顺序的错误，此时，目的寄存器的内容是指令 i 写入的值，而不是指令 j 写入的值。

MIPS 指令流水不会发生 WAW 冲突

• 如果在流水线中不只一个流水段可以进行写操作，或者当流水线暂停某条指令的执行时，允许该指令之后的其他指令继续执行，就可能发生这种数据冲突。
• 但是 MIPS 流水线中的指令不会发生这种数据冲突，因为流水中只有 WB 段才会写寄存器。
• 如果对流水线进行改变，将 ALU 结果的写回操作移到 MEM 段进行，因为这时计算结果已经有效，同时再假定访问数据存储器需要两个流水段，那么流水线中执行的指令就可能发生 WAW 冲突。

[! note] 读后写冲突 Write After Read 指令 j 可能在指令 i 读取某个源寄存器的内容之前就对该寄存器进行了写操作，结果就是导致了指令 i 后来读取的值是错误的。

MIPS 指令流水中不会发生 WAR 冲突

• 因为 MIPS 流水线在 ID 段完成所有的读操作，而在 WB 段完成所有的写操作。

解决策略：

插入空操作

• 编译器采取措施，插入空操作指令 nop，其作用仅仅是 PC+4
• 优点：硬件控制简单
• 缺点：指令空间需要预备一条 nop 指令，并且浪费了指令的执行时间（上图中浪费了 5 条指令的空间和时间）

插入气泡

• 硬件上采取措施，阻塞 (stall) 相关指令、使其延迟执行
• 实现起来比较复杂，需要修改数据通路，检测哪两条指令发生了数据相关，以确定是否需要阻塞；
• 阻塞时，可以将控制信号清零来阻止结果的写入；也可以将指令清零使后续指令执行空操作；或让 PC 写使能信号清零，PC 值不变，使当前指令重复执行；
• 优缺点：不占用指令条数，但是有额外的时间开销；

转发技术

• add 指令中 r1 的结果在 Exe 段就已经计算完毕，这个结果存放在 Ex/Mem 段间寄存器中，因此可以直接从该流水线寄存器中取出数据送到 ALU 的输入端，这样 sub 指令执行时，所需的 r1 寄存器的数据就是新值，是正确的
• 同样 and 指令所需的 r1 的数据，也可以在 Mem/Wr 流水段寄存器中读取；
• 对于 or 指令，则可以化用解决结构冲突的办法，前半周期写回寄存器 Reg1 中，后半周期从中读取，从而不会浪费时间；
• 转发技术必须在硬件上作相应改动：

• ALU 的两个输入端都从原来只有 ID/Ex 寄存器传递来的数据，扩展了其它转发来的可能的输入；
• 这样转发能够解决：
  • 相邻的两条 ALU 运算类指令之间
  • 相隔一条的 ALU 运算类指令之间
  • 相隔一条的 Load 和 ALU 运算类指令之间， 这三种数据冒险
• R 型指令后直接跟 sw 指令的相关性想要解决解决，则不能使用从寄存器中读出的数据，而是从 R 型指令 Exe 段运算的结果直接输入到 sw 指令的 ALU 中

Load-use 冒险

• lw 指令只有在 Mem 段结束才能获得 DM 中的结果，这时已不能通过转发来将新值写入 ALU 中
• 解决办法：
  1. 插入一条 nop 空操作
  2. 编译优化，使直接需要 lw 写入寄存器的指令向后推迟一周期
  3. 如果要硬件解决，则必需要增加 Load-use 冒险检测部件，并在检测到发生 Load-use 冒险时，进行流水线阻塞处理；
     • Load-use 冒险发生的条件是，load 指令之后紧跟的指令需要装入的操作数
     • load-use 检测的时间越早越好，但不能早 ID 阶段（总要知道指令的功能是什么），因此检测点安排在 ID 阶段，设置一个 MemRead 信号，如果有 Load 指令读取 Mem，则信号置 1，否则取 0，这个信号至多持续 2 周期（只要下一条指令能够确定，紧邻的上一条指令不是 Load 即可）
     • 一旦检测到 MemRead=1，且本身信号需要读取 reg，则插入一个气泡，具体的操作有三步：
       1. 将 ID/Ex 流水段寄存器中的所有控制信号清零（相当于插入一个气泡）
       2. 保持 IF/ID 流水段寄存器的值不变，使 Load 后紧跟的指令继续保存在 IF/ID 流水段寄存器中，在下一个周期再重新执行译码/取数操作
       3. 保持 PC 值不变，使 Load 后的第二条指令在下一个时钟周期重新执行取指令操作；

控制冲突

• 由于发生了指令执行顺序改变而引起的流水线阻塞称为控制冒险，主要有两种改变指令执行顺序的方法：
  1. 转移指令：分支指令 B-type 和无条件跳转指令 J-type
  2. 异常和中断：Exception Control Flow

转移指令引起的控制冒险

• beq 指令的转移目标地址计算操作在 Exe 段，并在 Mem 段由控制信号 Branch 来进行转移，根据 Exe 的比较结果来更新 PC 的值
• 因此，上图中 beq 指令执行到 DM 阶段开始处，才能确定需要进行转移，此时 and、or、sub 指令执行的结果都要被舍弃——损失的时间片 C=3
• 由分支指令引起的控制冒险，特称分支冒险，可以通过硬件气泡、软件 nop 的方式解决——损失多少个时间片，就需要锁少个 nop 指令、或多少个气泡

除了被动地插入气泡或空操作（这毕竟阻塞了流水线，影响了效率），还可以进行分支预测的方式降低由于分支冒险带来的时间损失：

1. 静态预测：简单地预测分支指令的条件总是满足或不满足

   • 对于预测不满足的情况，即预测分支失败，则流水线按照顺序执行后面的指令，当数据通路中 beq 指令执行到 Exe 段最终判断分支确实失败，那么没有任何影响；如果判断分支成功，则这之间执行的指令要舍弃、其造成的影响也要舍弃——清零控制信号，实际上只需清空 RegWr 和 MemWr 两个信号就足够；

2. 动态预测：根据分支指令发生转移的历史情况进行预测，并根据实际执行情况动态地调整预测位

   • 转移发生的历史情况记录在分支历史记录表中，(Branch History Table, Branch Prediction Buffer, Branch Target Buffer 只是不同的名字)
   • 
   • 每个表项由分支指令的地址作索引，在分支指令的 IF 段即可取得预测位；
     1. 首先根据当前分支指令的地址低位查找 BHT 中的对应表项，
     2. 若未命中，说明该分支是第一次执行，则由控制逻辑加入一个新的表项，将该分支指令的地址低位、转移目标地址和初始预测位填入表项中；
     3. 若命中，则控制逻辑根据预测位决定转移还是顺序
   • 预测位的宽度对准确率的影响很大：
     1. 1-bit 预测位：总是根据上次实际发生的情况来预测下次分支的情况，若预测错，则预测位取反，否则预测位不变
        • 
        • 缺点是：分支情况连续两次发生改变时，预测错误。对于循环，第一次进循环和最后一次出循环都会发生错误
     2. 2-bit 预测位：预测发生有两种状态，强转移 11 和弱转移 10，实际不发生时从 11 转移到 10；预测不发生时同理、镜像：
        • 
        • 双重循环条件下，1-bit 预测位的内循环与外循环预测正确率差距较大，2-bit 的预测正确率差距很小；

[! warning] 分支预测错误时的保护 采用分支预测方式时，流水线控制逻辑必须确保错误预测指令的执行结果，不能影响到后续指令的正确执行，而且要能从正确的分支地址处重新启动流水线工作。

3. 延迟分支
   • 采用编译优化来调整指令顺序，把分支指令前与分支指令无关的指令调到分支指令后面执行，以填充延迟损失的时间片，不够时用 nop 指令填充
   • 分支指令后面被填的指令称为分支延迟槽 (branch delay slot)，需要填入的指令条数等于延迟损失的时间片
   • 延迟分支技术通过编译器重排指令顺序来实现，属于静态调度技术
   • 分支延迟损失的时间片是影响流水线执行效率的重要因素，分支延迟损失时间片越小，插入的气泡或 nop 指令越少，在预测错误时后退的指令条数越少，在分支延迟的方式下，调度到分支延迟槽的无关指令条数越少。
   • 减少分支延迟损失时间片的关键是尽量提早进行分支条件的预测。

ECF 引起的控制冒险

异常执行流会改变程序的执行流程，使得流水线执行发生阻塞。例如，ALU 运算类指令发现“溢出”时，已经完成 Exe 阶段，此时已有两条新的指令进入了流水线。

通过在数据通路的不同流水段中加入相应的检测逻辑，即可检测出哪条指令发生了异常：

• 溢出可在 Exe 段检出
• 无效指令可在 ID 段检出
• 除数为零可在 ID 段检出
• 无效指令地址可在 IF 段检出
• 无效数据地址可在 Load/Store 的 Exe 段检出

外部中断的检测可以放在第一个流水段 IF 或最后一个流水段 Wr 中进行：

• 之所以放在 IF 中检测，是因为可以在取指令前进行，若有中断请求发生，则能确保在该时钟周期就开始执行中断服务程序，并让已经在流水线中的指令继续执行完，不需要进行指令冲刷 (flush)
• 若放在 Wr 中检测，则需要将刚执行完的指令的后面紧跟的几条指令，从流水线中清除掉

对于五段流水线处理器，任何一个时钟周期都由 5条活动的指令，因而很可能在一个时钟周期内同时有多条指令发生异常或中断，不同流水段发生不同类型的异常。

• 对于同时发生多个异常和中断的情况，关键问题是确定哪条指令的异常应最先被响应和处理
• 优先级确定的原则是，在同一个时钟周期内的指令序列中，最先执行的指令锁产生的异常最先被响应，外部中断请求最后响应：Wr>Mem>Ex>ID>IF

处理器硬件对异常和中断引起的冒险的处理的大致做法如下：

• 当检测到有异常或中断后，首先清除发生异常的指令以及其后在流水线中的所有指令，
• 然后保存断点，并将异常处理程序的首地址送至 PC 的输入端
• 指令清除的方式与分支错误时指令清除的方式类似，通过相应的冲刷 (flush)信号将指令或指令的控制信号清零（主要是 RegWr 和 MemWr 信号）

处理器应当能够确定异常和中断发生的精确位置，即保存的断点是精确的返回地址。

流水线方式执行指令时，异常可能发生在不同指令的不同阶段，因而会产生一些潜在的危险：

• 如五段流水线处理器中，假定正在执行的指令序列为 lw、add、ori，而且 lw 指令将在 Mem 段发生缺页异常，add 指令将在 Exe 段发生溢出异常，ori 将在 IF 段发生指令地址越界异常

• 这时，正确的处理顺序应当是先处理 lw 的异常，但 ori 指令处于 IF 段时，lw 指令才处于 Exe 段，add 才处于 ID 段，即 ori 异常发生了，lw 和 add 的异常还没有发生，而如果立即处理 ori 的异常，那么就会导致 lw 和 add 的异常被忽略，从而程序的结果错误；

• 正确的做法是：每个时钟周期内，在多个流水段发生的异常的原因和断点只是被记录到特定的寄存器中，并将发生异常的标记同时记录到流水段寄存器，发生异常的指令继续在流水线中执行，直到执行到最后一个阶段，由最后阶段内的硬件检测本指令是否发生过异常或此时是否有外部中断产生，若有，则清除流水线中后面所有阶段正在执行的指令，然后转到相应的异常处理程序执行。

• 多周期 CPU 的异常处理：

  • 

• 流水线的异常处理：

  •