Skip to content

Latest commit

 

History

History
executable file
·
59 lines (35 loc) · 5.88 KB

riscv_btb.md

File metadata and controls

executable file
·
59 lines (35 loc) · 5.88 KB

RISC-V 分支预测

1 分支指令类型

  • 无条件间接跳转 jalr
  • 带条件跳转

2 分支预测

分支预测的必要性:条件跳转/分支指令一定会发生跳转无需进行判断;对于带条件跳转/分支指令而言,流水线在取指令阶段无法得知该指令的条件是否成立,因此无法确定是跳还是不跳,理论上只有在执行阶段完成之后,才能解析出最终的跳转结果。假设处理器将取指暂停,一直等到执行阶段完成后才继续取指,则会造成大量的流水线空泡期,进而影响其性能。

分支预测的过程中要解决两个问题:预测方向;预测跳转的地址。

对于预测方向可以分为静态预测和动态预测。

2.1 静态预测

静态分支预测仅依靠这条分支指令本身的信息进行预测,与任何曾经执行过的指令信息和历史信息无关。常见的静态预测方法BTFN(back taken,forward not taken),即对于向后的指令跳转预测为跳,向前的跳转则预测为不跳。向后跳转指跳转的目标地址(PC值)比当前分支指令的PC值要小。

2.2 动态预测

动态预测是指依赖已经执行过的指令的历史信息和分支指令本身的信息综合进行“方向”预测。

  • 一比特饱和计数器: 每次分支指令执行之后,便使用此计数器记录上次的“方向”。预测机制是:下一次分支指令永远采用上次记录的“方向”作为本次的预测。结构简单,但是预测精度不如两比特饱和计数器。
  • 两比特饱和计数器: 每次分支指令执行之后,对应的状态机会发生转换。预测机制,当目前状态为“强不需要跳转(strongly not taken)”或者“弱不需要跳转(weakly not taken)”时,预测该指令的方向为”不需要跳转(not taken)“;当目前状态为”弱需要跳转(weakly taken)”或者”强需要跳转(strongly taken)“时,预测该指令的方向为“需要跳转(taken)”。每次预测错误便会向相反的方向更改状态机状态,总共对应有上述4个状态。对应的动态分支算法有一级预测器、两级预测器。

2.2.1 一级预测器

将有限个“两比特饱和计数器”组织成一堆的表格,称为预测器表格(predictor table),并直接使用PC值的一部分进行索引。“一级”是指其索引仅仅采用指令本身的PC值。虽然简单易行,但是其索引机制过于简单,很多不同的分支指令都会指向同样的表项(比如不同的PC之间某些位相同),并且由于没有考虑到分支指令的上下文执行历史,分支预测的精度不如两级预测器。

2.2.2 两级预测器

两级预测器也称为相关预测器,对于每条分支指令而言,将有限个“两比特饱和计数器”组织成PHT(Pattern History Table)。使用该分支跳转的历史(Branch History)作为PHT的索引。分支历史又可以分为局部历史和全局历史。局部分支预测器会使用分立的局部历史缓存来保存不同指令的分支历史,每个局部历史缓存有自己对应的PHT。全局分支预测器则仅使用分支指令共享的全局历史缓存,它的弊端是无法区分单独每个分支指令的历史,不同的指令会互相冲击,优势是比较节省资源。

3 预测地址

  1. BTB(Branch Target Buffer)分支目标缓存,是指使用容量有限的缓存保存最近执行过的分支指令PC值,以及它们的跳转目标地址。对于后续需要取指的每条PC值,将其与BTB中存储的的各个PC值进行比较,如果出现匹配,则预测这是一条分支指令,并使用其对应存储的跳转目标地址作为预测的跳转地址。它的一个缺点是对于间接跳转/分支指令的预测效果并不理想。这主要是由于间接跳转/分支的目标地址是使用寄存器索引的操作数计算所得,而寄存器中的值随着程序执行可能每次都不一样,因此BTB中存储的上次跳转的目标地址并不一定等于本次跳转的目标值。

  2. RAS(Return Address Stack)返回地址堆栈,是指使用容量有限的硬件堆栈来存储函数调用的返回地址。间接跳转/分支可以用于函数的调用和返回。而函数的调用和返回在程序中往往是成对出现的,因此可以在函数调用时将当前PC值加4(或者2) 。即将其顺序执行的下一条指令的PC值压入RAS堆栈中,等到函数返回(使用分支跳转指令)时将RAS中的值弹出,这样就可以快速地为该函数返回的分支跳转指令预测目标地址。

  3. 间接BTB是指专门为间接跳转/分支指令而设计的BTB,与普通BTB类似,存储较多的历史目标地址,但是通过高级的索引方法进行匹配(而不是简单的PC值比较),结合了BTB和动态两级预测器的技术,能够提供较高跳转目标地址预测成功率。缺点是硬件开销大,只有在高级的处理器中才会使用。

3.1 RAS 依据

RAS用于函数返回地址的预测,但是RAS需要能够明确判定什么指令属于“函数调用”类型的分支跳转指令从而进行压栈,什么指令属于“函数返回”类型的分支跳转指令从而进行出栈。

RISC-V架构规定,如果使用jal指令且目标寄存器索引值rd等于x1x5rat0),则属于需要进行RAS压栈。

如果使用jalr指令(jalr rd, rs1, imm),则按照使用的寄存器值(rs1rd,link位于rs1时,判断为函数返回;link位于rd时,判断为函数调用)的不同,明确规定相应的RAS压栈或者出栈行为。(图中的link表示x1x5

rd rs1 rs1=rd RAS action
!link !link - none
!link link - pop
link !link - push
link link 0 push and pop
link link 1 push