指令级并行之动态分支预测技术
当要提高ILP（指令级并行）时，控制相关就是会成为主要限定因素之一。所开发的ILP越多，控制相关的制约性就越大，分支预测就要求有更高的准确度。对于每个时钟周期流出多条指令（若为n条，就称为n流出）的处理机来说是非常重要的。这是因为：①在n流出的处理机中，遇到分支指令的可能性增加了n倍。要给处理机连续提供指令，就需要预测分支的结果；②Amdahl定律告诉我们，机器的CPI越小，控制停顿的相对影响就越大。
前面介绍的集中静态处理分支指令的方法，如预测成功和延迟分支。在这些方法中，所进行的操作是预先定义好的，与分支的实际执行情况无关。下面讨论动态的进行分支处理的方法。这些方法是在程序运行的时候，根据分支指令过去的表现来预测其将来的行为。如果分支行为发生了变化，预测结果也随之改变。因此有较好的预测准确度和适应性。
分支预测的有效性不仅取决于其准确性，而且还与预测正确和不正确两种情况下的分支开销有密切关系。这些分支开销是由流水线的结构、预测的方法和预测错误时的恢复策略等诸因素决定的。
采用这些动态分支预测技术的目的有两个：预测分支是否成功和尽快找到分支目标地址（或指令），从而避免控制相关造成流水线停顿。
在这些方法中，需要解决以下关键问题：①如何记录分支的历史信息；②如何根据这些信息来预测分支的去向（甚至取到指令）。
预测错误时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径上重新取指令，为了能恢复现场，需要在执行预测的目标指令之前将现场保持起来。
采用分支历史表
分支历史表（Branch History Table，BHT）有时也称为分支预测缓冲器（Branch Prediciton Buffer）。这种方法是最简单的动态分支预测法。它用BHT来记录分支指令最近一次或几次的执行情况（成功或不成功），并据此进行预测。如果只执行分支指令最近一次的历史，BHT中只需要1位二进制位，是最简单的了。为了提高预测的准确度，常采取两位二进制位来记录历史。有研究结果表明，两位分支预测的性能与n位（n>2）分支预测的性能差不多。因而大多数处理机是采用分支预测。下面介绍这种方法。
两位分支预测的状态转换如下图。其中，在00和01状态下，预测分支不成功；在10和11状态下，预测分支成功。连线边上注明了分支指令的实际执行情况。只有连续两次预测错误，才会改变对分支去向的预测。在11状态下连续两次错误预测错误，状态将变为00（预测分支不成功）。
两位分支预测的操作有两个步骤：①分支预测；②状态修改。当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测，如果是“预测成功”，那么就从分支目标地址取后续的指令。等分支指令的实际执行结果出来后，如果发现预测正确，就继续处理后续的指令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径中重新取指令。不管是哪种情况，都要按照上图状态进行修改。
在BHT方法中，只对分支是否成功进行预测，对分支目标地址没有提供支持。所以它只有在以下情况中有用：判定分支是否成功所需的时间大于确定分支目标地址所需的时间。在前述5段经典流水线中，由于判定分支是否成功和计算分支目标地址都是在ID段完成，所以BHT方法不会给该流水线带来好处。
一般来说，采用4K的BHT就可以了，如果要进一步提高预测准确率，需要采用更复杂的预测方法。
BHT可以跟分支指令一起存放在指令Cache中，也可以用一个专门的硬件来实现。如果是前者，在取指阶段，就把历史位一起读出来。如果是后者，就在取指令的同时，用指令地址的低位（例如低12位）去访问BHT，读出历史位。
采用分支目标缓冲器
在高性能流水线中，特别是在多流出的处理机中，只准确的预测分支还不够，还要能够提供足够的指令流。许多现代的处理器都要要求每个时钟周期能提供4~8条指令。这需要尽早知道分支是否成功，尽早知道分支目标得治，尽早获取分支目标指令。
对于前述5段流水线，BHT方法是在ID段对BHT进行访问，所以在ID段的末尾，能够获得分支目标地址（在ID段计算出）、顺序下一条指令地址（在IF段计算出）以及预测的结果，如果能再提前一拍（即在IF段）就知道这些信息，那么分支开销就可以减少为0。分支目标缓冲器（Branch Target Buffer，BTB）能够实现这一点。BTB有时也称为分支目标Cache。
如上图，可以把它看成是用专门硬件实现的一张表格。表格的每一项至少有两个字段：①执行过的成功分支指令的地址；②预测的分支目标地址。第一个字段作为该表的匹配标识。在每次取指令的同时，我们把该指令的地址与BTB中的所有项目的第一个字段进行比较。如果能匹配，就可确定该指令时分支指令且上一次执行时分支成功，据此可以预测这次执行也将分支成功，其分支目标地址由匹配项的第二个字段给出。如果没有匹配的，就把当前指令当作普通的指令（即不是分支指令）来执行。
当采用BTB后，在流水线各个阶段进行的相关操作如上图所示。
BTB的另一种形式是在分支目标缓冲器中存储一条或者多条分支目标处的指令。有的实现方案还保留了分支目标地址，有的则降之去掉了。这种方案的3个潜在好处是：①更快地获得分支目标处的指令；②可以一次提供分支目标处的多条指令，这对于多流出处理器是很有必要的；③便于进行分支折叠优化。
↶ 返回首页