控制相关的动态解决技术 ■控制相关:由条件转移或程序中断引起的相关,也称全 局相关。控制相关对流水线的吞吐率和效率影响相对于 数据相关要大得多 条件指令在一般程序中所占的比例相当大 中断虽然在程序中所占的比例不大,但中断发生在程序中的哪一条指令 ,发生在一条指令执行过程中的哪一个功能段都是不确定的 ■处理好条件转移和中断引起的控制相关是很重要的。 关键问题: 要确保流水线能够正常工作 减少因断流引起的吞吐率和效率的下降 计算机体系结构 Chapter4 3.6
计算机体系结构 Chapter4_3.6 控制相关的动态解决技术 ▪ 控制相关：由条件转移或程序中断引起的相关，也称全 局相关。控制相关对流水线的吞吐率和效率影响相对于 数据相关要大得多 • 条件指令在一般程序中所占的比例相当大 • 中断虽然在程序中所占的比例不大，但中断发生在程序中的哪一条指令 ，发生在一条指令执行过程中的哪一个功能段都是不确定的 ▪ 处理好条件转移和中断引起的控制相关是很重要的。 ▪ 关键问题： • 要确保流水线能够正常工作 • 减少因断流引起的吞吐率和效率的下降
分支对性能的影响 假设在一条有K段的流水线中,在最后一段才能确定目标地 址 i+1 i+2 i+k-3 i+k-2 Output 2 p+k-3p+k-2+Output 当分支方向预测错误时,不仅流水线中有多个功能段要浪 费,更严重的是可能造成程序执行结果发生错误,因此当 程序沿着错误方向运行后,作废这些程序时,一定不能破 坏通用寄存器和主存储器的内容。 计算机体系结构 Chapter4 3.7
计算机体系结构 Chapter4_3.7 分支对性能的影响 ▪ 假设在一条有K段的流水线中，在最后一段才能确定目标地 址 i-1 i i+1 i+2 i+k-3 p+1 p+2 p+k-3 i+k-2 p+k-2 Output Output •当分支方向预测错误时，不仅流水线中有多个功能段要浪 费，更严重的是可能造成程序执行结果发生错误，因此当 程序沿着错误方向运行后，作废这些程序时，一定不能破 坏通用寄存器和主存储器的内容
条件转移指令对流水线性能的影响 假设对于一条有K段的流水线,由于条件分支的影响,在最 坏情况下,每次条件转移将造成κ-1个时钟周期的断流。假 设条件分支在一般程序中所占的比例为p,条件成功的概率 为q。试分析分支对流水线的影响 结论:条件转移指令对流水线的影响很大,必须采取相关 措施来减少这种影响。 预测可以是静态预测“ Static"( (at compile time)或动态预氵 “ Dynamic"( at runtime) ·动态分支预测ws.静态分支预测,哪个好? 计算机体系结构 Chapter4 3.8
计算机体系结构 Chapter4_3.8 条件转移指令对流水线性能的影响 ▪ 假设对于一条有K段的流水线，由于条件分支的影响，在最 坏情况下，每次条件转移将造成k-1个时钟周期的断流。假 设条件分支在一般程序中所占的比例为p, 条件成功的概率 为q。试分析分支对流水线的影响。 ▪ 结论：条件转移指令对流水线的影响很大，必须采取相关 措施来减少这种影响。 ▪ 预测可以是静态预测“Static” (at compile time) 或动态预测 “Dynamic” (at runtime) • 动态分支预测 vs. 静态分支预测，哪个好？
Dynamic Branch Prediction 动态分支预测:预测分支的方向在程序运行时刻动态确定 需解决的关键问题是 ·如何记录转移历史信息 如何根据所记录的转移历史信息,预测转移的方向 主要方法 基于BPB( Branch Prediction Buffer)或BHT( Branch History Table)的方法 1- oit bht和2- bit bht Correlating Branch Predictors Tournament Predictors: Adaptively Combining Local and Global Predictors High Performance Instruction Delivery BTB Integrated Instruction Fetch Units Return Address Predictors Performance= f(accuracy, cost of misprediction) Misprediction Flush Reorder Buffer 计算机体系结构 Chapter4 3.9
计算机体系结构 Chapter4_3.9 Dynamic Branch Prediction ▪ 动态分支预测：预测分支的方向在程序运行时刻动态确定 ▪ 需解决的关键问题是： • 如何记录转移历史信息 • 如何根据所记录的转移历史信息，预测转移的方向 ▪ 主要方法 • 基于BPB(Branch Prediction Buffer)或BHT(Branch History Table)的方法 - 1-bit BHT和2-bit BHT - Correlating Branch Predictors - Tournament Predictors: Adaptively Combining Local and Global Predictors • High Performance Instruction Delivery - BTB - Integrated Instruction Fetch Units - Return Address Predictors ▪ Performance = ƒ(accuracy, cost of misprediction) • Misprediction Flush Reorder Buffer
1-bit Bht Branch History Table:分支指令的PC的低位索引1- bit bht 该表记录上一次转移是否成功 不做地址检查 ■例题:一个循环供循环10次,它将分支成功9次,1次不成 功,假设此分支的预测位始终在缓冲区中,那么分支预测 的准确性是多少? ·静态预测s.动态预测 问题:在一个循环中,1- bit bht将导致2次分支预测错误 (avg is 9 iterations before exit) 最后一次循环,前面都是预测成功,而这次需要退出循环 第一次循环,由于前面预测为失败,而这次实际上为成功 计算机体系结构 Chapter4 3.10
计算机体系结构 Chapter4_3.10 1-bit BHT ▪ Branch History Table: 分支指令的PC的低位索引1-bit BHT • 该表记录上一次转移是否成功 • 不做地址检查 ▪ 例题：一个循环供循环10次，它将分支成功9次，1次不成 功，假设此分支的预测位始终在缓冲区中，那么分支预测 的准确性是多少？ • 静态预测 vs. 动态预测 ▪ 问题: 在一个循环中, 1-bit BHT 将导致2次分支预测错误 (avg is 9 iteratios before exit): • 最后一次循环, 前面都是预测成功，而这次需要退出循环 • 第一次循环，由于前面预测为失败，而这次实际上为成功