上一节介绍分支预测的作用和相关指令分类。本节主要介绍常用的分支预测算法
(一)预测算法分类:
当CPU碰到跳转指令时,可以选择以下三种方法:
不预测,将流水线停滞,等到方向确定了再取接下来的指令;
固定往左或者往右,如果走错了,则返回岔路口; 简称静态预测
将岔路口信息记下来,以后就可以预测它大概率往哪儿走;简称动态预测
这三种方法都是CPU常用的一些手段,在流水线和超标量CPU诞生前,通常采用方法1将流水线停滞;在一些微控制器领域,通常为了节省功耗,采用方法2静态预测方式;在高性能CPU领域,通常以动态预测为主,并结合静态预测,以达到较高的准确度,提升cpu性能。接下来部分主要介绍动态预测算法。
(二)动态预测方法
上一节讲述到,预测的核心问题有两个:跳不跳?跳到哪里?下面介绍2-bit饱和计数器和Gshare,tage来解决跳不跳问题,btb来解决跳到哪里的问题。
2- bit 饱和计数器:
所谓2-bit计数器,即每条指令PC,通过一个2-bit的计数器,记录历史跳转情况:
(1)2-bit所能记录的数字包含00/01/10/11。
(2)分支实际跳转一次,计数器+1,不跳转,则-1。
(3)2-bit计数器当前状态为10或者11,则预测本次跳转,如果为00或者01,则预测本次不跳转。
实际研究表明,2-bit计数器相较于1-bit精度较高,如果再提高到3-bit,精度提升不明显。因此业界大多使用2-bit计数器。
Gshare 两级预测器:
何谓两级预测器?两级指的是自己的历史+别人的历史。为什么需要参考别人的历史跳转,可参考如下代码。
以上Gshare两级预测器,使用的是GR(global history register,包含所有分支的历史信息),再异或PC值,作为2-bit饱和计数器的索引值。
TAGE :
tage是一种处理器广泛使用的现代预测器,其解决的本质问题是,采用多个表支持不同长度的历史信息。
h表示的是全局历史信息,该历史信息可以是2bit(T1),也可以是4Bit(T2)…。本质上仍然是通过自己的历史+别人的历史来进行预测。只是别人的历史,长度可选。Tage详细的预测算法后面会再详细介绍。
BTB :
以上2-bit饱和计数器和两级预测器能预测是否进行跳转,但是无法预测跳到哪里?跳转地址通常通过BTB(branch target buffer)进行预测,以下为简单BTB的结构,即通过PC索引历史跳转地址。
Return stack :
上面跳转指令分类中,有一条较为特殊的指令–ret。当公共函数被调用时,ret后下一条指令可能是无法预测到。因此常用returnstack来进行指令保存:1)函数调用时,将函数函数调用的下一条指令入栈 2)当子函数ret时,将栈里的指令弹出。