Branch Predication.ppt

4.3控制相关的动态解决技术本节着重于：
通过硬件技术，动态地进行分支处理，对程序运行时的分支行为进行预测，提前对分支操作做出反应，加快分支处理的速度。
分支的最终延迟取决于流水线的结构、预测的方法和预测错误后恢复所采取的策略。

4.3.1分支预测缓冲分支预测缓冲技术（Branch-PredictionBuffer或者BranchHistoryTable，简写为BTB或者BHT）：目前广泛使用的最简单的动态分支预测技术。使用一片存储区域，记录最近一次或几次分支特征的历史。状态转换图2.分支预测缓冲技术包括两个步骤图4.10分支预测执行不成功和重新执行过程例4.6一个循环共循环10次，它将分支成功9次，1次不成功。假设此分支的预测位始终在缓冲区中。那么分支预测的准确性是多少？
解这种固定的预测将会在第一次和最后一次循环中出现预测错误。
第一次预测错误是源于上次程序的执行，因为上一次程序最后一次分支是不成功的。
最后一次预测错误是不可避免的，因为前面的分支总是成功，共九次。
因此，尽管分支成功的比例率是90%，但分支预测的准确性为80%（两次不正确，8次确）。4.1位预测机制的缺点
只要预测出错，往往是连续两次而不是一次。
5.解决方法采用两个预测位的预测机制。
在两个预测位的分支预测中，更改对分支的预测必须有两次连续预测错误。
两位分支预测的状态转换图
图4.11具有两个分支预测位的分支预测缓冲状态转换机制6.n位分支预测缓冲
采用n位计数器，则计数器的值在0到2n-1之间：
当计数器的值大于或等于最大值的一半（2n-1）时，则预测下一次分支成功；
否则预测下一次分支不成功。
预测位的修改和两位预测时相同：
当分支成功时计数器的值加1，不成功时减1。
研究表明：n位分支预测的性能和两位分支预测差不多，因而大多数处理器都只采用两位分支预测。
7.对于真实的应用程序，两位的分支预测的准确率可达到多少呢？
SPEC89标准程序的测试：
在使用4096个记录项的缓冲区时，分支预测准确率可达到99%到82%。
使用无穷多历史记录项的分支预测缓冲，只有少量程序的分支预测准确率仅仅比4096个记录项提高1%，多数程序的预测精度是相同的。
因此，对于SPEC89应用环境而言，4K的缓冲区是恰当的。
8.上述分支预测机制对于改进后的DLX流水线没有帮助。4.3.2分支目标缓冲1.分支目标缓冲结构和工作过程2.在流水线的各个阶段中，具有分支目标缓冲的工作分配如图4.13。3.采用BTB技术时指令在各种情况下的延迟例4.7按表4.3计算分支转移总的延迟，根据下面的假设，计算分支目标缓冲的性能。（1）对于BTB中的指令，预测准确率90%（2）缓冲区命中率90%（3）不在BTB中分支转移成功的比例为60%BTB命中率预测错误率2
=90%10%2
=0.18（时钟周期）
（3）不在BTB中，实际成功，此时的延迟为：
（1-BTB命中率）不在BTB中分支转移成功率2
=10%60%2
=0.12（时钟周期）
（4）不在BTB中，实际不成功，此时的延迟为0。4.对分支预测机制的一种改进在缓冲区中不仅存入目的地址，而且还存入一个或多个目标指令。有两种潜在的好处：4.3.3基于硬件的前瞻执行（2）在控制相关消除之前指令前瞻执行；
（3）对基本块采用动态调度。
2.基于硬件的前瞻是动态地根据数据相关性来选择指令和指令的执行时间。
实质：数据流驱动运行（data-flowexecution）只要操作数有效，指令就可以执行。
3.指令的确认
前瞻执行的指令产生的结果要一直到指令处于非前瞻执行状态时，才能确定为最终结果，才允许最终写到寄存器或存储器中去。4.实现前瞻的关键思想：允许指令乱序执行，但必须顺序确认。
5.再定序缓冲（reorderbuffer，简记为ROB）保存那些执行完毕但未经确认的指令及其结果。在指令执行完毕和确认之间这段时间里，由
再定序缓冲提供所有其他指令需要的作为操作数的数据。再定序缓冲区还可以取代取（load）缓
冲区。再定序缓冲的每个项包含三个域：
（1）指令的类型指令类型包括是否是分支（尚无结果）、存操作（目的地址为存储器）或寄存器操作
（ALU操作或目的地址是寄存器的取操作）。
（2）目的地址目的地址域给出结果应写入的目的寄存
器号（对于取操作和ALU指令）或存储器的地
址（存操作）。
（3）值域值域用来保存指令前瞻执行的结果，直到指令得到确认。使用再定序缓冲的处理部件的硬件结构例4.8假设浮点功能单元的延迟为加法是2个时钟周期，乘法是10个时钟周期，除法40个时钟周
期。给出下面的代码段当指令MULTD要确认
时的状态。
LD F6,34(R2)
LD F2,45(R3)
MULTD F0,F2,F4
SUBD F8,F