计算机体系结构 第5章 指令级并行及其开发—硬件方法（2）_分支历史表bht

第5章 指令级并行及其开发—硬件方法

5.4 动态分支预测技术

5.4.1 采用分支历史表 BHT

分支历史表BHT（Branch History Table）

• 最简单的动态分支预测方法。
• 用BHT来记录分支指令最近一次或几次的执行情况（成功还是失败 ），并据此进行预测。

只有1个预测位的分支预测

• 记录分支指令最近一次的历史，BHT中只需要1位二进制位。（效果差）

采用2位二进制位来记录历史

• 提高预测的准确度

• 研究结果表明：两位分支预测的性能与n位（n>2）分支预测的性能差不多。

• 两位分支预测的状态转换如下所示：

  

两位分支预测中的操作的两个步骤：

• 分支预测；
  • 当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测 。
  • 若预测正确，就继续处理后续的指令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。
• 状态修改。

BHT方法有效的场景：

• 判定分支是否成功所需的时间大于确定分支目标地址所需的时间。
• 因此，对于之前的5段经典流水线：由于判定分支是否成功和计算分支目标地址都是在ID段完成，所以BHT方法不会给该流水线带来好处。

BHT的实现（2两种方法）：

• 和分支指令一起存放在指令Cache中，在取址阶段，把历史位读出来
• 用一块专门的硬件来实现，在取指令的同时，用指令地址的低位去访问BHT，读出历史位

5.4.2 采用分支目标缓冲器BTB

目标：将分支的开销降为 0（在IF段获取分支目标地址，顺序下一条指令地址，以及预测的结果）

方法：分支目标缓冲

• 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。
• 这个缓冲区就是分支目标缓冲器（Branch-Target Buffer，简记为BTB）。

BTB的结构

• 将其看成是用专门的硬件实现的一张表格。
• 表格中的每一项至少有两个字段：
  • 执行过的成功分支指令的地址；（作为该表的匹配标识 ）
  • 预测的分支目标地址。

采用BTB后，在流水线各个阶段所进行的相关操作：

采用BTB后，各种可能情况下的延迟 ：

（可以根据采用BTB后，在流水线各个阶段所进行的相关操作得出延迟的时间）

• 如果预测错误或者在BTB中没有匹配的项，会有至少2个时钟周期的延迟
  • 此时需要更新BTB中的项，需要花费一个时钟周期
  • 且一般对BTB的项进行修改时，需要停止取指令，所以取新的指令又要花费一个时钟周期

BTB的另一种形式

• 在分支目标缓冲器中增设一个至少是两位的**“分支历史表BHT”**字段

• 更进一步，在表中对于每条分支指令都存放若干条分支目标处的指令，就形成了分支目标指令缓冲器。
• 也就形成了前瞻或预取指令。

5.4.3 基于硬件的前瞻执行

之所以采取这种方法，是为了确保没有进行不可恢复的写操作，以便在预测错误时能够恢复原来的现场

前瞻执行（speculation）的基本思想：

• 对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果取、流出和执行后续的指令。
• 执行指令的结果不是写回到寄存器或存储器，而是写入一个称为再定序缓冲器ROB（ReOrder Buffer）中 。
• 等到相应的指令得到“确认”（commit）（即确实是应该执行的）之后，才将结果写入寄存器或存储器。

基于硬件的前瞻执行结合了3种思想：

• 动态分支预测。用来选择后续执行的指令。
• 在控制相关的结果尚未出来之前，前瞻地执行后续指令。
• 用动态调度对基本块的各种组合进行跨基本块的调度。

对Tomasulo算法加以扩充，就可以支持前瞻执行。

• 把Tomasulo算法的写结果和指令完成加以区分，分成两个不同的段：写结果，指令确认

• 写结果段

  • 把前瞻执行的结果写到ROB中；
  • 通过CDB在指令之间传送结果，供需要用到这些结果的指令使用。

• 指令确认段

  • 在分支指令的结果出来后，对相应指令的前瞻执行给予确认。
  • 如果前面所做的猜测是对的，把在ROB中的结果写到寄存器或存储器。
  • 如果发现前面对分支结果的猜测是错误的，那就不予以确认，并从那条分支指令的另一条路径开始重新执行。

实现前瞻的关键思想：

• 允许指令乱序执行，但必须顺序确认。
• 在指令被确认之前，不允许它进行不可恢复的操作。

支持前瞻执行的浮点部件的结构

ROB中项的组成：

• 指令类型
  • 指出该指令是分支指令、store指令或寄存器操作指令。
• 目标地址
  • 给出指令执行结果应写入的目标寄存器号（如果是load和ALU指令）
  • 存储器单元的地址（如果是store指令）。
• 数据值字段
  • 用来保存指令前瞻执行的结果，直到指令得到确认。
• 就绪字段
  • 指出指令是否已经完成执行并且数据已就绪。

寄存器的换名

• Tomasulo算法中保留站的换名功能是由ROB来完成的。

采用前瞻执行机制后，指令的执行步骤（在Tomasulo算法的基础上改造的 ）：

• 流出

  • 从浮点指令队列的头部取一条指令。
  • 如果有空闲的保留站（设为r）且有空闲的ROB项（设为b），就流出该指令，并把相应的信息放入保留站r和ROB项b。
  • 如果保留站或ROB全满，便停止流出指令，直到它们都有空闲的项。

• 执行

  • 如果有操作数尚未就绪，就等待，并不断地监测CDB。(检测RAW冲突)
  • 当两个操作数都已在保留站中就绪后，就可以执行该指令的操作。

• 写结果

  • 当结果产生后，将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上，经CDB写到ROB以及所有等待该结果的保留站。
  • 释放产生该结果的保留站。
  • store指令在本阶段完成，其操作为:
    • 如果要写入存储器的数据已经就绪，就把该数据写入分配给该store指令的ROB项。
    • 否则，就监测CDB，直到那个数据在CDB上播送出来，才将之写入分配给该store指令的ROB项。

• 确认

  • 对分支指令、store指令以及其它指令的处理不同：
  • 其它指令（除分支指令和store指令）
    • 当该指令到达ROB队列的头部而且其结果已经就绪时，就把该结果写入该指令的目的寄存器，并从
      ROB中删除该指令。
  • store指令
    • 处理与上面的类似，只是它把结果写入存储器。
  • 分支指令
    • 当预测错误的分支指令到达ROB队列的头部时，清空ROB，并从分支指令的另一个分支重新开始执行。（错误的前瞻执行）
    • 当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕。

前瞻执行的特点

• 通过ROB实现了指令的顺序完成。
• 能够实现精确异常。
• 很容易地推广到整数寄存器和整数功能单元上。
• 主要缺点：所需的硬件太复杂。

例题：

假设浮点功能部件的延迟时间为：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。对于下面的代码段，给出当指令MUL.D即将确认时的状态表内容。

L.D     F6,34（R2）
L.D	    F2,45（R3）
MUL.D	F0,F2,F4
SUB.D	F8,F6,F2
DIV.D	F10,F0,F6
ADD.D	F6,F8,F2
1
2
3
4
5
6

前瞻执行中MUL.D确认前，保留站的状态如下图：

ROB的状态如下图：