分支预测器BPU
- 0 Intro
- 0.1 CPU执行过程
- 0.2 分支预测
- 0.2.1 TAGE预测器
- 0.2.2 跳转地址
分支预测器BPU是深入研究一个高性能处理器的一个很好的开始项目;
0 Intro
条件分支是指后续具有两路可执行的分支。可以分为跳转分支(taken branch)和不跳转分支(not-taken branch)。不跳转分支,指接下来会顺序执行紧挨着JMP的指令。跳转分支,通过JMP跳转到另外一块内存去执行那里的指令。
分支预测器的主要功能是:预测执行过程中的分支指令(Eg: if-else、循环语句等)的跳转方向,进行提前取指并执行正确的指令流;
常见的分支预测器:
1.静态预测器:不依赖于程序执行历史,总是预测跳转或者不跳转;
2.动态预测器:一般使用一个计数器来记录分支跳转和不跳转的次数,如果跳转次数多于不跳转次数,则预测分支会跳转;
3.两级自适应预测器:使用一个全局历史寄存器来记录最近的分支执行情况,并依据这些信息来预测分支的跳转方向;
4.局部历史表:该预测器策略为每个分支维护一个局部历史表,记录该分支最近的执行情况,并依据这些信息来预测分支的跳转方向;
5.相关预测器:该预测器不仅考虑分支的历史执行情况,还考虑其他相关分支的执行情况,以提高预测的准确性;
依据上面的预测器原理可以设计成不同的预测器组件;
0.1 CPU执行过程
典型CPU执行五级流水线:取指、译码、执行、访存和写回;
取指:根据程序计数器(pc)的记录,依次取出指令传递给译码单元并更新pc;
译码:根据不同的指令集架构进行指令行为区分,识别出指令的操作及操作数等;
执行:得到指令的对应的操作类型及操作数后,进行执行操作;
访存:从memory中读取或写入memory中;
写回:将指令执行的结果写回到寄存器中,用于后续指令;
为了提高CPU的性能,减少时钟浪费,一般措施是引入:引入分支预测及乱序执行技术;
乱序执行:可以提高指令执行的效率,当前条指令处于等待状态而后续的指令不依赖于前条指令时,可以优先执行后续指令,通过引入乱序执行,有效缩短指令执行时间。
分支预测:可以避免流水线的空闲等待,在指令流水型执行时,不必等待执行结果,提前进行指令预测并取指令进行后续动作,可以大大减少指令等待时间,接下来对分支预测技术进行详细介绍。
0.2 分支预测
分支预测主要用来预测下一条指令,当没有分支预测机制时,需要等待指令操作数计算出跳转地址后才能确定下一条执行指令,并由取指令单元取指令,这个过程会导致流水线处于等待状态。对于现代处理器来说,若预测结果错误,需要冲刷流水线。
预测任务主要分为两个部分:1.预测是否跳转;2.预测跳转的地址;
静态与动态预测器的区别:就是会不会参考程序的执行历史;
最典型的动态预测器:2-bit饱和计数器;----状态机表示的逻辑还是很清楚的;
最最理想的情况:可以为每一个分支都分配一个2bit饱和计数器,但是这样的做法会带来巨大的开销,因此一般情况下使用pc的一部分去寻址pattern history table(PHT),查询表中饱和计数器的数值,做出预测,但会导致不同分支寻址到相同的表项而做出错误的预测(aliasing),我们会在下面提到一些解决方法:
0.2.1 TAGE预测器
利用饱和计数器作为预测表项–TAGE预测器;
TAGE预测器核心思想:使用多个不同长度的历史寄存器来捕捉分支指令的历史行为。
TAGE的预测机制:Base Predicitor使用PC部分位来索引,3bit饱和计数器用于计算预测结果,2bit的userful counter及partial tage作为表项,构成标记预测器;
四个标记预测器采用不同长度的全局历史寄存器(GHR),四个标记预测表大小一致,因此需要先将GHR压缩为相同位宽后与PC部分位进行哈希作为索引查询表项(利用哈希解决aliasing问题),查询到tag命中(tag的哈希计算方法不同于索引的哈希计算方法),则取出该标记预测器的预测结果,预测结果由3bit的饱和计数器计算得出。
Tage最终的预测结果取GHR最长的标记预测器的预测结果。
上述表格:predictor(3bit饱和计数器)+ tag(1bit 是否命中) + u(userful counter用来记录是否需要更新)。
0.2.2 跳转地址
上面是解决的分支指令跳不跳的问题–即taken or not taken的问题;
当做出对跳转的预测时,需要查询跳转的地址,这一部分一般由BTB实现。BTB是类似于cache的结构,主要用来记录目标的跳转地址。BTB表用(partial)pc作为索引,当一个分支指令第一次执行时,记录该分支指令的目标地址并分配一个表项,当前面提到的预测器得到taken/not taken的预测结果后,在BTB中查询跳转地址。
未完待续…
[Ref]
https://www.birentech.com/Research_nstitute_details/1.html