95 lines
11 KiB
Markdown
95 lines
11 KiB
Markdown
# 分支预测
|
||
分支预测即根据分支历史，提前预测指令跳转方向及跳转目标。分支预测器种类繁多，例如BTB（Branch Target Buffer）、BHT（Branch History Table）、RAS（Return Address Stack）等，但适用于五级流水的其实并不多。如设计概述中所介绍的，五级流水中，pfs级发出取指请求，fs级取回指令，ds级开始译码，并明确跳转指令的所有信息。也就表示分支预测只有一拍的空间可以利用，且无预译码，可依据的信息只有pc，跳转方向及跳转目标都只能靠猜。适用的实际上仅有BTB。不过对于较为特殊的jirl指令，即寄存器跳转，若直接采用BTB的机制，会使得命中率极低。因此，在BTB的基础上进行改造，由CAM表记录jirl指令的pc，并由RAS机制预测其跳转目标。
|
||
|
||
----
|
||
|
||
接下来介绍分支预测器的具体实现，分为两点：分支预测器的内部实现；分支预测器同流水线的交互。
|
||
## 分支预测器设计
|
||
分支预测器的逻辑可以分为两个部分，由PC进行预测跳转目标及跳转方向的预测部分；根据指令译码结果与分支预测器预测结果的比较，对分支预测器历史信息进行修正的修正部分。
|
||
### 预测部分
|
||
首先来看模块的接口。
|
||
- fetch_pc：取指pc
|
||
- fetch_en：取指使能
|
||
- ret_en：预测结果使能
|
||
- ret_pc：预测跳转目标
|
||
- taken：预测跳转方向
|
||
- ret_index：指示当前预测结果的对应项，用于修正
|
||
|
||
btb表有32项，包含四个内容：
|
||
- btb_pc：30位，用于和取指pc匹配
|
||
- btb_target：30位，存放跳转目标
|
||
- btb_counter：2位，由最高位指示跳转方向
|
||
- btb_valid：1位，当前项是否有效
|
||
|
||
对于jirl指令的预测逻辑由两部分组成，16项的CAM表以及8项的RAS。
|
||
CAM表包含两个内容：
|
||
- ras_pc：30位，用于和取指pc匹配
|
||
- ras_valid：1位，当前项是否有效
|
||
|
||
RAS简单来说就是一个栈。存储30位的跳转目标，由ras_ptr指示栈顶。
|
||
|
||
明确表项内容后，来看预测逻辑。fetch_en以及fetch_pc进入分支预测器时，首先缓存一拍。单看分支预测器，缓存插在什么位置其实都可以，只要有一拍的延迟即可，但考虑到赋值nextpc即fetch_pc的路径非常长，因此将缓存插在靠前的位置。缓存后的信号为fetch_en_r及fetch_pc_r，将其与两个CAM的PC部分，btb_pc和ras_pc进行匹配。该项有效且pc匹配则表示命中。命中项记录在btb_match_rd和ras_match_rd中。
|
||
|
||
两个表中有一项命中，则置起ret_en。若命中在btb CAM表中，ret_pc取对应项的btb_target即可，若命中在ras CAM表中，则取ras栈顶的跳转目标。理论上btb_match_rd和ras_match_rd为one-hot且只会命中在一个表中，因此不必使用优先级逻辑。ret_index同理，而taken在btb_match时，需要看对应项btb_counter最高位，而ras_match时，直接置为1。预测阶段不会对分支预测器的历史信息进行任何修正。
|
||
|
||
### 修正部分
|
||
在ds译码级，汇总分支预测信息以及译码得到的正确分支跳转信息。
|
||
预测信息同上：
|
||
- ds_btb_target
|
||
- ds_btb_index
|
||
- ds_btb_taken
|
||
- ds_btb_en
|
||
|
||
正确的分支跳转信息如下：
|
||
- br_to_btb：表示当前指令是否为分支预测器所覆盖的跳转指令，当前结构的分支预测器覆盖所有跳转指令。
|
||
- br_taken：跳转方向
|
||
- br_target：跳转目标
|
||
|
||
译码级根据以上信息，稍加分析并传递至分支预测器，传递信息包括：
|
||
- operate_en：分支预测器修正操作使能。注意该信号需要在ds_ready_go、es_allowin和ds_valid为1时置起且无例外。只有ds当拍允许流动至下一级时才能发出修正操作。对于ds_ready_go，因为流水线中指令寄存器的依赖有可能导致ds阻塞，阻塞时指令所得到的寄存器值是错误的，即译码得到的分支跳转信息也是错误的。而es_allowin的介入使其操作使能仅维持一拍，避免重复操作。
|
||
- operate_pc：修正操作针对的分支指令的pc
|
||
- operate_index：修正操作针对的CAM表项
|
||
- pop_ras：为jirl指令时置起
|
||
- push_ras：为bl指令时置起
|
||
- add_entry：当前指令为分支指令但预测器未进行预测时置起。这里与上了一个额外条件br_taken，因为当pc在分支预测器中未命中时，顺序指令，也算是预测为untaken。br_taken不为1时，并不需要在预测器中建项
|
||
- delete_entry：当前指令不为分支指令但预测器进行预测时置起。这种情况出现的概率极低，只有在自修改代码中，可以不用考虑
|
||
- pre_error：当前指令为分支指令且预测器进行预测，但跳转目标不一致时置起
|
||
- pre_right：当前指令为分支指令且预测器进行预测，且跳转目标一致时置起
|
||
- target_error：当前指令为分支指令且预测器进行预测，且跳转目标一致，但跳转目标不一致时置起
|
||
- right_orien：正确的跳转方向
|
||
- right_target：正确的跳转目标
|
||
|
||
分支预测器会根据以上信息进行修正，首先由pop_ras即是否为jirl指令区分当前操作的是BTB部分还是RAS部分，针对BTB部分，操作类型包括：
|
||
- 建项：add_entry置起时。使能指定项，并填入operate_pc和right_target，以及初始化btb_counter为2'b10。对于填入项即index的选择，若BTB CAM表中还留有未使能项，则选择其中一项。若所有项都有效则选择btb_counter为2'b00的一项，即大概率不跳转的预测项，因为未在btb中命中的pc即预测为不跳转，两者效果是相同的，只不过该pc若下一次为跳转，则会重新建项，相当于将其btb_counter由2'b00直接转为2'b10，很有可能导致下一次的预测出错。但是这种情况出现的概率肯定比替换掉其他btb_counter的值导致下一次预测错的概率低。若所有项都有效且btb_counter都不为2'b00，则随机选择一项。
|
||
- 修正跳转目标：target_error置起时。重新填入right_target，并初始化btb_counter为2'b10。
|
||
- 修正跳转方向：pre_error或者pre_right置起时。根据right_orien调整btb_counter，若正确的分支方向为taken则累加，若为untaken则递减。
|
||
|
||
针对RAS部分，操作类型包括：
|
||
- 建项：add_entry置起时。使能指定项，填入operate_pc即可。相当于预测pc的分支类型。index的选择同BTB部分。
|
||
- 进栈：当push_ras置起且当前RAS非满时，存入当前pc的下一条指令，并将指针上移。即当前为bl函数跳转指令，其返回地址为bl的下一条指令。RAS指针指向的是空项。
|
||
- 出栈：当pop_ras置起且当前RAS非空时，指针直接下移一项即可。
|
||
|
||
## 分支预测器与流水线交互逻辑
|
||
|
||
首先简单介绍取指逻辑，该部分内容会在后续逐步展开。来看几个关键信号，inst_valid指示当前取指pc是否有效，该信号直接送往icache等待接收。inst_valid主要看fs_allowin信号，即pfs指令允许向后流动时，其取指pc即为有效，能够避免相同pc取指请求的重复发出。nextpc即为取指pc，当前仅关注其最为常规的pc来源seq_pc，顺序取指pc。当inst_valid为1时，并不代表取指请求即刻便能发出，还需要等待icache空闲，由inst_addr_ok表示（取指请求的其他去向tlb、btb不需要等待）。当inst_valid && inst_addr_ok为1，取指请求发出，pfs_ready_go置起，pfs向fs流动。
|
||
fetch_en和fetch_pc发送至分支预测器后，下一拍得到预测结果（btb_en/btb_ret_pc/btb_taken）。当btb_en && btb_taken为1时，fetch_btb_target置起，分支跳转，将nextpc纠正至btb_ret_pc。这段逻辑中有一点需要注意，分支预测器返回的结果仅维持一拍，但pfs并不一定能够向后流动，因此需要缓存分支预测器的返回结果，避免信息丢失。分支预测器的返回结果缓存在btb_lock_buffer中，由btb_lock_en指示缓存是否有效。缓存条件即为分支返回结果且pfs无法向后流动（btb_en && !pfs_ready_go），缓存释放条件为下一次取指重新发起。而nextpc的维护以及fs向ds传递分支预测结果时都将采用btb_ret_pc_t、btb_ret_pc_t、btb_ret_pc_t、btb_ret_pc_t信号，由分支预测器返回信息和缓存的信息相或得到，两者同一时刻仅有一个有效。
|
||
译码级，根据译码和分支预测的结果，能够知道下一条指令取指的方向是否正确。取指级有两个方面的工作需要完成：修正分支预测的历史信息；若预测错误则需纠正取指方向。此处主要讲述第二方面的内容。若译码级检测到分支预测错误，则会置起btb_pre_error_flush信号，由该信号修正取指方向，该工作可继续细分为两个内容
|
||
- 取消掉下一条进入译码级的指令，及错误预测导致错误取指的指令
|
||
两种情况需要考虑：
|
||
- 当该分支指令向后流动的那一拍，即（btb_pre_error_flush && es_allowin）为1时，若下一拍下一条指令紧接着进入译码级，则可直接取消。不过可以用更粗犷的方法，即下一拍的ds_valid直接为0，无需识别是否有指令进入。
|
||
- 同样的条件，若下一拍无指令进入，即当拍fs_to_ds_valid为0，则置起branch_slot_cancel触发器。该触发器为1时，会等待下一条指令进入，当检测fs_to_ds_valid为1时，将其取消，并恢复branch_slot_cancel至0。
|
||
- 纠正nextpc。当译码级发现分支预测错误，会将正确的跳转目标（btb_pre_error_flush_target）和使能信号（btb_pre_error_flush）通过br_bus传递至取指阶段，修正nextpc。
|
||
需要考虑两个问题：
|
||
- 当nextpc修正信息向前传递时，pfs并不一定处于能够取指的状态，例如inst_addr_ok不为1。此时若译码级不阻塞，且pfs不将修正信息存入buffer，会导致信息丢失。
|
||
- 译码级会记录分支预测错误，并取消掉错误预测的分支指令的下一条指令。若pfs在取完预测错误的分支指令后始终处于阻塞状态，之后直接被修正至正确的跳转方向，则会导致正确的指令被取消掉。
|
||
|
||
针对上述两个问题，可在pfs中构建一个状态机解决。br_target_inst_req_state表示状态。当发现预测错误后，根据流水线状态，进入不同的状态。
|
||
- !fs_valid && !inst_addr_ok：预测错误分支指令取出后未进行任何取指，因为fs级为空，inst_addr_ok从未置起。且当前也不处于可取指的状态。进入br_target_inst_req_wait_slot状态。
|
||
- !inst_addr_ok && fs_valid：已有一条错误取指的指令在fs中，但pfs并不处于能够取指的状态。进入br_target_inst_req_wait_br_target状态。
|
||
- inst_addr_ok && !fs_valid：预测错误分支指令取出后未进行任何取指，当前处于可取指的状态，但当前的指令会在译码级取消。进入br_target_inst_req_wait_br_target状态。
|
||
|
||
br_target_inst_req_wait_slot状态会待取指请求发出后切换至br_target_inst_req_wait_br_target状态，该状态便会将nextpc修正至存储btb_pre_error_flush_target的pc buffer（br_target_inst_req_buffer）。当取指请求再次发出后，状态切换至空状态br_target_inst_req_empty。
|
||
|
||
构建状态机后，还需要注意一个问题。也许pfs处于即刻能够发出取指请求的状态。可粗略的判断fs级是否有指令，便改变next_pc同时置起inst_valid，即使当前无法取指(inst_addr_ok为0)也没有关系。
|
||
|