转移预测技术

1、叮叮小文库动态转移预测一、动态转移预测概述1 、动态移预测的概念1 )动态转移预测就是利用硬件来动态地预测转移指令的转移行为，以减少转移指令对流水线性能的影响，也就是减少转移指令的转移开销。2 )动态转移预测相对的是静态转移预测，所谓的静态转移预测，是指在编译阶段由软件技术来实现对转移指令的预测3 )动态转移预测发生在程序编译之后、执行之前2 、态转移预测的思想利用前面一条转移指令的行为去预测后面一条转移指令的行为3 、态转移预测的实现1 )预测是由硬件来实现2 ) 动 态转移预测的实现方案一位转移预测缓冲器二位转移预测缓冲器相关转移预测缓冲器目标转移预测缓冲器3 ) 具 体实现方法设置一个用

2、来预测转移指令转移行为的硬件，这个硬件叫做转移预测缓冲器转移预测缓冲器实际上是一个存储器，存放了转移指令的转移行为if 段取出一条转移指令时，利用转移指令的低位地址去访问转移预测缓冲器， 在读出转移指令的同时也读出了对转移指令转移行为的预测值4 、 动 态转移预测要解决的问题动态转移预测要解决的对问题是由转移指令所引起的控制相关和控制冒险5 、 动 态转移预测的原理在没有采用动态转移预测的流水线中，如果采用第一种实现方式，转移指令在id 流水段判断转移行为，在ex 流水段计算目标地址，在mem 流水段完成转移； 如果采用的是第二种方案，在id 流水段判断转移指令的转移行为、计算转移目 标地址、

3、转移完成。从上述可知，不管是采用哪种实现方案，在没有使用动态转移预测的流水线中，转移指令的转移是否成功要到 id 流水段结束后才能知道。但采用动态转移预测后，在if 流水段取出指令后，利用指令的低位地址去访问 转移预测缓冲器，也就是在读出转移指令的时候，对转移指令转移行为的预测值也被读出，所以在采用动态转移预测的流水线中，转移指令在if 流水段就可以知道其转移行为，也就是提前一个时钟周期知道其转移行为，所以可以减少流水 线停顿。6动态转移预测的性能1）预测的正确率假设一段程序有n条转移指令，在执行的时候其中有m条转移指令的预测是正 确的，那么预测的正确率为m/n2）预测错误的恢复策略、一位转移

4、预测缓冲器0：不转移1：转移1、示意图转移指令 低位地址预测失败取反2、工作原理设置一个只有一位的缓冲器，有两个状态值0和1,其中0值预测转移不成功，1值预测转移是成功的。假设预测器的初始值是 0,也就是对当前转移指令的预测是转移不成功的，当这条转移指令的实际转移行为是转移不成功的，那么预测是正确的，预测器的状态 位不变，对下条转移指令的预测是转移不成功的；当这条转移指令的实际转移行 为是转移成功的，那么预测错误，预测器的状态位变为1,对下一条转移指令的转移预测是转移成功的。假设预测器的初始值是 1,也就是对当前转移指令的转移行为预测是转移成功的，当这条指令的实际转移行为是转移不成功的，那么预

5、测错误，预测器的状态值边变为1,对下一条转移指令转移行为的预测是转移不成功的；当这条转移指令的实际转移行为是成功的，那么预测正确，预测器的状态位不变，对下一条转移指令的预测也是转移成功的3、实现方法设置一个只有一位的预测器，在 if段读出一条转移指令时用指令的低位地址去访问这个预测器，读出这条转移指令的转移行为预测值4、性能一位转移预测缓冲器的性能比较差，当程序的转移行为是间隔变换的，那么对转移指令的转移行为的预测的正确率为 05、改进对一位转移预测缓冲器的改进就是使用二位转移预测缓冲器三、二位转移预测缓冲器1、示意图nt10takenpredict taken2、工作原理设置一个两位的预测缓

6、冲器，有00、01、10、11四个状态值，其中00、01是 预测 转移不成功的，10、11是预测转移成功的。假设预测器的初始值是 00,那么对当前转移指令的转移行为是预测转移不成功的，当当前转移指令的实际转移行为是成功的，那么预测错误，预测器的状态值变为01,对下一条转移指令的转移行为预测是不成功的；当当前转移指令的实际转移行为是不成功的，那么预测正确，预测器的状态位保持00不变，对下一条转移指令的转移行为的预测是不成功的。假设预测器的初始值是 01,那么对当前转移指令的转移行为预测是转移不成功的，当当前转移指令的实际转移行为是成功的，那么预测错误，预测器的状态值变为10,对下一条转移指令的转

7、移行为的预测是转移成功的；当当前转移指令的实际转移行为是不成功的，那么预测正确，预测器的状态值变为00,对下一条转移指令的转移行为的预测是不成功的假设预测器的初始值是10 ,那么对当前转移指令的转移行为预测是转移成功的，当当前转移指令的实际转移行为是不成功的，那么预测错误，预测器的状态值变为01,对下一条转移指令的转移行为的预测是不成功的；当当前转移指令的实际转移行为是转移成功的，那么预测正确，预测器的状态值变为11,对下一条转移指令的转移行为的预测是转移成功的假设预测器的初始值是11,那么对当前转移指令的转移行为的预测是转移成功的，当当前转移指令的实际的转移行为是不成功的，那么预测错误，预测

8、器的状态值变为10,对下一条转移指令的转移行为的预测是转移成功的；当当前转移指令是转移成功的，那么预测正确，预测器的状态值不变，对下一条转移指令的转移行为的预测是转移成功的。3、实现方法1)设置一个专门的cache,在if流水段读出一条转移指令的时候，用转移 指令的 低位地址去访问转移预测器，读出对转移指令的预测值。2)在cache的每一行设置两个附加的标志位，用来标志对转移指令的转移行为,当读出一条转移指令的时候，连同预测值一起读出4、二位转移预测器的性能二位转移预测器的性能比一位转移预测器的性能好5、改进方法1) 增加位数2) 增加容m四、相关转移预测缓冲器1、相关转移指令的概念有两条转移

9、指令，后一条转移指令的转移行为与前面那条转移指令的转移行为相关，那么这两条转移指令叫相关转移指令。2、相关转移指令的例子11)程序if ( aa= 2)aa= 0;if ( bb = 2)bb = 0;if (aa!= bb ) 2)指令序列dsubi r3, r1, #2bnez r3, l1 ; br.bl (aa!=2)dadd r1, r0, r0 ; aa=0l1: dsubi f3, r2, #2bnez r3, l2 ; br.b2 (bb!=2)dadd r2, r0, r0 ; bb=0l2: dsub r3, r1, r2 ; r3=aa-bbbeqz r3, l3 ; b

10、r.b3 (aa=bb)3)相关性分析转移指令b3的转移行为与转移指令 bl和转移指令b2的转移行为是相关的，当转移指令bl和转移指令b2的转移行为是不成功的，那么b3的转移是成功的。3、相关转移指令的例子21) 程序if (d=0)d=1;if (d=1).2) 指令序列bnez r1, l1 ; brbl, (d!=0)daddiu r1, r0, #1 ; d=0, so d=1l1: daddiu r3, r1, # -1 ;bnez r3, l2 ; brb2, (d!=1)l2:3) 相关性分析d pi tnd*0?bl/l: b2以前 的d值d1 ?b20yesnot taken

11、1yesnot taken1notaken1yesnot taken2notaken2notaken结论： 当 bl not taken, b2 肯定 not taken.4、相关转移预测缓冲器相关转移预测缓冲器是对一般转移预测缓冲器进行改造，使改造后的预测缓冲器既能够处理不相关转移指令的预测，也能够处理相关转移指令的预测5、对相关转移预测缓冲器的改进把(1, 1)维的相关转移预测缓冲器改成(m,n)维，其中值m表示具有相关 性的转 移指令的数n表示相关转移预测缓冲器的位数6、相关转移预测缓冲器的性能相关转移预测缓冲器的性能比一般的转移预测缓冲器的性能好五、目标转移预测缓冲器1、目标转移预测缓

12、冲器的定义这个转转移预测缓冲器存放了被调用的指令的下一条要执行的预测指令的地址, 移预测缓冲器叫目标转移预测缓冲器。2、目标转移预测缓冲器的示意图pc of -nslrurt-gfetch ibranch pcpredicted pcyes： instruct ion is branch and , use predicted pc as nert pcno; branenot pre die ted. proceed normally(next pc = pc*4)ertraprediction statebits3、目标转移预测缓冲器的工作原理转移指令的地址存放在 branch pc ,转

13、移指令所对应的转移目标指令地址存放在predicted pc中，当从内存中取出一条转移指令后，用这条指令的pc值，也就是地址值去查找目标转移预测缓冲器的branch pc ,如果在branch pc中找到相等的项，那么接下来到bran ch pc中该项所对应的predicted pc值所指示 的内存中去取下一条指令，如果在branch pc中没有找到，那说明这条指令不是转移指令，或是转移指令而预测转移是不成功的，接下来要到pc+4的内存中去取指令4、目标转移预测缓冲器的特点1）目标转移预测缓冲器在指令的if段就去读转移预测缓冲器，在 if段结束的 时候就知 道该指令是否转移指令和转移指令是否转移成功2）在访问目标转移预测缓冲器的时候，还无法判断是否是转移指令，以及无法 判断转移是否成功，还要进行匹配3）目标转移预测缓冲器的工作原理象cache的工作原理