计算机体系结构期末复习1：分支预测
目录
一、为什么需要分支预测
1.存在分支的指令
2.控制相关的处理方式一：stall(阻塞）流水线
二、分支预测方法
1.预测正确与预测错误的性能损失
2.减少预测错误的惩罚
3.提高分支预测的准确度
1）编译时（静态方法）
2）运行时（动态方法）
三、动态预测方法
1.Last Time Predictor
2.Last Time Predictor改进：2 bits 饱和计数器
3.Two Level Predictior(两层预测器）
1）局部相关性：
2）全局相关性：
3）全局历史寄存器（GHR）：
5）模式历史表（PHT）：
6）提高全局预测器准确性的方法
一、为什么需要分支预测
CPU流水线上的指令存在控制相关，即PC值可能不再顺序执行，可能会跳转到另一地址。
1.存在分支的指令
1）条件跳转：比如beq $rs, $rt, offset，在X（执行）阶段确定是否跳转
2）无条件跳转：比如j target,在D(译码)阶段确定是否跳转
3）函数调用：比如jal target,在D(译码)阶段确定是否跳转
4）跳转寄存器：比如JR $ra，在D(译码)阶段确定是否跳转
2.控制相关的处理方式一：stall(阻塞）流水线
这种思路是，既然我在decode阶段（甚至exe阶段）才知道分支的跳转情况（也就是下一条取什么指令），那么流水线阻塞一个周期，等到该条指令运行完decode阶段，再读入下一条指令。
正常五级流水线如下图：
用stall方法来处理五级流水线如下图：
显然，stall的方式十分低效。与其等待分支结果运算出来，不如尝试分支预测。
二、分支预测方法
1.预测正确与预测错误的性能损失
1）预测正确：假如预测正确，那么我们下一条取的指令就是我们期望中的，不会带来任何延迟。
2）预测错误：假如预测错误，我们需要刷新取进来的错误指令，重新取一条新的指令。
3)性能损失分析：
假设不预测，插入bubble,会阻塞两个周期。
假如预测成功，正常执行就好。
假如预测失败，需要刷新掉decode和exe阶段正在执行的指令（即错误执行的指令）。也会像不预测那样损失掉两个周期的时间。
我们来定量计算一下： 假如五级流水线中，无数据危害引起的stalls，20% 的分支指令，其中70%预测错误，那么：
CPI=（1+0.2x0.7x2）=(1+0.14x2)=1.28
其中0.14是预测错误的概率，2是预测错误引来的额外阻塞时间。要想降低CPI，我们从这两点入手。
2.减少预测错误的惩罚
1）如果能在decode阶段获取分支跳转结果，那么不预测或者预测错误只需要阻塞一个周期。惩罚从2变成1.
2）如果能在fetch阶段就获取分支结果，那么一定能取进正确的指令，也不会引进额外的阻塞。
3.提高分支预测的准确度
1）编译时（静态方法）
- 一直预测为跳转
- 一直预测为不跳转
- 预测后向为跳转，前向为不跳转
- 基于提前分析（略）
- 基于程序分析（略）
2）运行时（动态方法）
- Last time prediction (single-bit)
- Two-bit counter based prediction
- Two-level prediction (global vs. local)
- Hybrid
- Advanced algorithms (e.g., using perceptrons）
三、动态预测方法
1.Last Time Predictor
1）思路：每个分支语句采用1bit记录预测结果（T表示跳转，N表示不跳转）。上一条分支语句跳转，这一条分支语句就预测跳转；上一条分支语句不跳转，这一条分支语句就预测不跳转。
2）缺陷：遇到双层循环时，会连续两次预测错误。（跳出内存循环时预测错误一次，跳进外层循环时错误一次）。预测分析器的转换太快。
2.Last Time Predictor改进：2 bits 饱和计数器
3.Two Level Predictior(两层预测器）
1）局部相关性：
一条分支语句的结果可能与过去多次的预测结果有关，而不仅仅与最后一次有关。两层预测器将关注过去两次的分支跳转结果。
2）全局相关性：
一条分支语句的结果可能与其他分支语句的结果相关。比如某种pattern会循环多次。（比如for(int i=0;i<4;i++)作为内层循环，TTTTNT可能会循环多次）
3）全局历史寄存器（GHR）：
记录过去所有分支的跳转历史。比如0100代表第二条发生了跳转，第一、三、四条没有跳转。
5）模式历史表（PHT）：
记录跳转历史。
- 使用GHR的内容进行索引
- 每个表项是个2bits饱和计数器，用于预测当出现该表项的pattern时，下一条分支该如何跳转
- 当需要预测分支跳转时，根据历史分支跳转情况查找PHT
6）提高全局预测器准确性的方法
A. 思路：由于不同的分支语句碰到一样的历史pattern时跳转趋势可能不同，因此增加上下文信息让预测器知道当前预测是哪个分支语句。
方法：GHR和分支语句的PC进行哈希，再去索引PHT。
B.思路： 为不同分支维护单独的PHT。即由PC的低位决定访问哪个PHT，再由GHR索引PHT的表项。
