转移预测关键技术.docx

动态转移预测
一、动态转移预测概述
1、  动态移预测概念
  1）  动态转移预测就是运用硬件来动态地预测转移指令转移行为，以减少转移指令对流水线性能影响，也就是减少转移指令转移开销。
  2）  动态转移预测相对是静态转移预测，所谓静态转移预测，是指在编译阶段由软件技术来实现对转移指令预测
  3）  动态转移预测发生在程序编译之后、执行之前

2、  态转移预测思想
  运用前面一条转移指令行为去预测背面一条转移指令行为
3、  态转移预测实现
 1）  预测是由硬件来实现
 2）动态转移预测实现方案
    一位转移预测缓冲器
    二位转移预测缓冲器
    有关转移预测缓冲器
    目的转移预测缓冲器
 3）详细实现办法
 设立一种用来预测转移指令转移行为硬件，这个硬件叫做转移预测缓冲器
 转移预测缓冲器事实上是一种存储器，存储了转移指令转移行为
 IF段取出一条转移指令时，运用转移指令低位地址去访问转移预测缓冲器，在读出转移指令同步也读 出了对转移指令转移行为预测值

4、动态转移预测要解决问题
动态转移预测要解决对问题是由转移指令所引起控制有关和控制冒险

5、动态转移预测原理
在没有采用动态转移预测流水线中，如果采用第一种实现方式，转移指令在ID流水段判断转移行为，在EX流水段计算目的地址，在MEM流水段完毕转移；如果采用是第二种方案，在ID流水段判断转移指令转移行为、计算转移目的地址、转移完毕。从上述可知，不论是采用哪种实现方案，在没有使用动态转移预测流水线中，转移指令转移与否成功要到ID流水段结束后才干懂得。但采用动态转移预测后，在IF流水段取出指令后，运用指令低位地址去访问转移预测缓冲器，也就是在读出转移指令时候，对转移指令转移行为预测值也被读出，因此在采用动态转移预测流水线中，转移指令在IF流水段就可以懂得其转移行为，也就是提前一种时钟周期懂得其转移行为，因此可以减少流水线停顿。

6、动态转移预测性能
1）预测对的率
 假设一段程序有n条转移指令，在执行时候其中有m条转移指令预测是对的，那么预测对的率为m/n
2）预测错误恢复方略

二、一位转移预测缓冲器
1、示意图

2、工作原理
 设立一种只有一位缓冲器，有两个状态值0和1，其中0值预测转移不成功，1值预测转移是成功。
假设预测器初始值是0，也就是对当前转移指令预测是转移不成功，当这条转移指令实际转移行为是转移不成功，那么预测是对的，预测器状态位不变，对下条转移指令预测是转移不成功；当这条转移指令实际转移行为是转移成功，那么预测错误，预测器状态位变为1，对下一条转移指令转移预测是转移成功。
假设预测器初始值是1，也就是对当前转移指令转移行为预测是转移成功，当这条指令实际转移行为是转移不成功，那么预测错误，预测器状态值边变为1，对下一条转移指令转移行为预测是转移不成功；当这条转移指令实际转移行为是成功，那么预测对的，预测器状态位不变，对下一条转移指令预测也是转移成功

3、实现办法
  设立一种只有一位预测器，在IF段读出一条转移指令时用指令低位地址去访问这个预测器，读出这条转移指令转移行为预测值

  4、性能
   一位转移预测缓冲器性能比较差，当程序转移行为是间隔变换，那么对转移指令转移行为预测对的率为0

5、改进
  对一位转移预测缓冲器改进就是使用二位转移预测缓冲器

三、二位转移预测缓冲器
  1、示意图

   2、工作原理
   设立一种两位预测缓冲器，有00、01、10、11四个状态值，其中00、01是预测转移不成功，10、11是预测转移成功。
   假设预测器初始值是00，那么对当前转移指令转移行为是预测转移不成功，当当前转移指令实际转移行为是成功，那么预测错误，预测器状态值变为01，对下一条转移指令转移行为预测是不成功；当当前转移指令实际转移行为是不成功，那么预测对的，预测器状态位保持00不变，对下一条转移指令转移行为预测是不成功。
   假设预测器初始值是01，那么对当前转移指令转移行为预测是转移不成功，当当前转移指令实际转移行为是成功，那么预测错误，预测器状态值变为10，对下一条转移指令转移行为预测是转移成功；当当前转移指令实际转移行为是不成功，那么预测对的，预测器状态值变为00，对下一条转移指令转移行为预测是不成功
   假设预测器初始值是10，那么对当前转移指令转移行为预测是转移成功，
   当当前转移指令实际转移行为是不成功，那么预测错误，预测器状态值变为01，对下一条转移指令转移行为预测是不成功；当当前转移指令实际转移行为是转移成功，那么预测对的，预测器状态值变为11，对下一条转移指令转移行为预测是转移成功
   假设预测器初始值是11，那么对当前转移指令转移行为预测是转移成功，当当前转移指令实际转移行为是不成功，那么预测错误，预测器状态值变为10，对下一条转移指令转移行为预测是转移成功；当当前转移指令是转移成功，那么预测对的，预测器状态值不变，对下一条转移指令转移行为预测是转移成功。

3、实现办法
   1）  设立一种专门CACHE，在IF流水段读出一条转移指令时候，用转移指令低位地址去访问转移预测器，读出对转移指令预测值。
   2）  在CACHE每一行设立两个附加标志位，用来标志对转移指令转移行为，当读出一条转移指令时候，连同预测值一起读出

4、二位转移预测器性能
   二位转移预测器性能比一位转移预测器性能好

5、改进办法
 1）  增长位数
 2）  增长容量

四、有关转移预测缓冲器

1、有关转移指令概念
有两条转移指令，后一条转移指令转移行为与前面那条转移指令转移行为有关，那么这两条转移指令叫有关转移指令。

2、有关转移指令例子1
1）  程序
IF ( aa== 2)
aa= 0;
IF ( bb == 2)
bb = 0;
IF (aa!== bb ) {
……
}
2）  指令序列
DSUBI R3，R1，#2
BNEZ R3，L1 ；br.b1 (aa!=2)
DADD R1，R0，R0 ；aa==0
L1：DSUBI F3，R2，#2
BNEZ R3，L2 ；br.b2 (bb!=2)
DADD R2，R0，R0 ；bb==0
L2：DSUB R3，R1，R2 ；R3=aa-bb
BEQZ R3，L3 ；br.b3 (aa==bb)
3）  有关性分析
转移指令b3转移行为与转移指令b1和转移指令b2转移行为是有关，当转移指令b1和转移指令b2转移行为是不成功，那么b3转移是成功。

  3、有关转移指令例子2
1）  程序
If (d==0)
d=1;
if (d==1)
{…...}
2） 指令序列
BNEZ R1，L1 ；brb1，(d!=0)
DADDIU R1，R0，#1 ；d==0，so d=1
L1：DADDIU R3，R1，# -1 ;
BNEZ R3，L2 ；brb2，(d!=1)……
L2:
3） 有关性分析

4、有关转移预测缓冲器
    有关转移预测缓冲器是对普通转移预测缓冲器进行改造，使改造后预测缓冲器既可以解决不有关转移指令预测，也可以解决有关转移指令预测

5、对有关转移预测缓冲器改进
   把（1，1）维有关转移预测缓冲器改成（m,n）维，其中值m表达具备有关性转移指令数量，n表达有关转移预测缓冲器位数

 6、有关转移预测缓冲器性能
   有关转移预测缓冲器性能比普通转移预测缓冲器性能好

五、目的转移预测缓冲器

 1、目的转移预测缓冲器定义
转移预测缓冲器存储了被调用指令下一条要执行预测指令地址，这个转移预测缓冲器叫目的转移预测缓冲器。

2、目的转移预测缓冲器示意图

3、目的转移预测缓冲器工作原理
    转移指令地址存储在Branch PC，转移指令所相应转移目的指令地址存储在 Predicted PC中，当从内存中取出一条转移指令后，用这条指令PC值，也就是地址值去查找目的转移预测缓冲器 Branch PC，如果在Branch PC中找到相等项，那么接下来到Branch PC中该项所相应Predicted PC值所批示内存中去取下一条指令，如果在Branch PC中没有找到，那阐明这条指令不是转移指令，或是转移指令而预测转移是不成功，接下来要到PC+4内存中去取指令

4、目的转移预测缓冲器特点
1）  目的转移预测缓冲器在指令IF段就去读转移预测缓冲器，在IF段结束时候就懂得该指令与否转移指令和转移指令与否转移成功
2）  在访问目的转移预测缓冲器时候，还无法判断与否是转移指令，以及无法判断转移与否成功，还要进行匹配
3）  目的转移预测缓冲器工作原理象CACHE工作原理同样
4）  目的转移预测缓冲器只存储预测转移是成功指令地址，不存储非转移指令和预测转移不成功转移指令

5、目的转移预测缓冲器性能
  目的转移预测缓冲器性能比其她前面简介转移预测缓冲器性能都好

 6、使用目的转移预测缓冲器指令执行过程

7、目的转移预测缓冲器改进
1）  在目的转移预测缓冲器中放入转移目的指令地址
2）  在目的转移预测缓冲器中存储转移目的指令
3）  在目的转移预测缓冲器中存储转移目的指令地址和转移目的指令