动态调度(Cnt),推断执行 和IP 计算机体系结构 Chapter4_3.1
计算机体系结构Chapter4_3.1 动态调度 (Cont), 推断执行 和ILP
Review Tomasulo 引入动态调度的动机 动态硬件方案可以用硬 在没有专用编译器的情况下,提高 件进行循环展开 系统性能 解决编译时无法判定的部分相关问 如何处理分支? 题 我们可以用硬件做循环展 · Scoreboard和 Tomasula 开必须可以解决分支指令 Tomasula主要贡献 题 Dynamic scheduling 如何处理精确中断? · Register renaming-消除了WWAW, Out-of-order execution WAR相关 out-of-order completion Load/store disambiguation 算法的主要缺陷 复杂 要求高速CDB 性能受限于 Common data bus 计算机体系结构 Chapter4 3.2
计算机体系结构 Chapter4_3.2 Review Tomasulo ▪ 引入动态调度的动机 • 在没有专用编译器的情况下，提高 系统性能 • 解决编译时无法判定的部分相关问 题 • Scoreboard 和Tomasula ▪ Tomasula 主要贡献 • Dynamic scheduling • Register renaming---消除了WAW， WAR相关 • Load/store disambiguation ▪ 算法的主要缺陷 • 复杂 • 要求高速CDB • 性能受限于Common Data Bus ▪ 动态硬件方案可以用硬 件进行循环展开 ▪ 如何处理分支? • 我们可以用硬件做循环展 开必须可以解决分支指令 问题 ▪ 如何处理精确中断? • Out-of-order execution out-of-order completion!
为什么顺序发射? 顺序发射使我们可以进行程序的数据流分析 我们可以知道某条指令的结果会流向哪些指令 如果我们乱序发射,可能会混淆RAW和WAR相关 每一周期发射多条指令也使用该原则将会正确地工作 需要多端口的“ rename table”,以便同时对一组指令所用 的寄存器重命名 需要在单周期内发射到多个RS中 ·寄存器文件需要有2X个读端口和x个写端口 计算机体系结构 Chapter4 3.3
计算机体系结构 Chapter4_3.3 为什么顺序发射? ▪ 顺序发射使我们可以进行程序的数据流分析 • 我们可以知道某条指令的结果会流向哪些指令 • 如果我们乱序发射，可能会混淆RAW和WAR相关 ▪ 每一周期发射多条指令也使用该原则将会正确地工作: • 需要多端口的 “rename table” ,以便同时对一组指令所用 的寄存器重命名 • 需要在单周期内发射到多个RS中. • 寄存器文件需要有2x 个读端口和x个写端口
关于异常处理??? 乱序完成加大了实现精确中断的难度 在前面指令还没有完成时,寄存器文件中可能会有后面指令的 运行结果 如果这些前面的指令执行时有中断产生,怎么办? 例如: DIVD F10FO F2 SUBD F4.F6F8 ADDD F12F14.F16 需要“ rollback"寄存器文件到原来的状态 精确中断的含义是其返回地址为: 该地址之前的所有指令都已完成 其后的指令还都没有完成 实现精确中断的技术:顺序完成(或提交) 即提交指令完成的顺序必须与指令发射的顺序相同 计算机体系结构 Chapter4 3.4
计算机体系结构 Chapter4_3.4 关于异常处理??? ▪ 乱序完成加大了实现精确中断的难度 • 在前面指令还没有完成时，寄存器文件中可能会有后面指令的 运行结果. • 如果这些前面的指令执行时有中断产生，怎么办？ • 例如： DIVD F10, F0, F2 SUBD F4, F6, F8 ADDD F12, F14, F16 ▪ 需要“rollback” 寄存器文件到原来的状态: • 精确中断的含义是其返回地址为： - 该地址之前的所有指令都已完成 - 其后的指令还都没有完成 ▪ 实现精确中断的技术：顺序完成（或提交） • 即提交指令完成的顺序必须与指令发射的顺序相同
进行循环重叠执行需要尽快解决分支问题! ■在循环展开的例子中,我们假设整数部件可以快速解决分 支问题,以便进行循环重叠执行! Loop LD F00 R1 MULTD F4 F0 F2 SD F40 R1 sUB工 R1R1#8 BAEZ R1 Loop 如果分支依赖于mutd,怎么办?? 需要能预测分支方向 ·如果分支成功,我们就可以重叠执行循环 对于 superscalar机器这一问题更加突出 计算机体系结构 Chapter4 3.5
计算机体系结构 Chapter4_3.5 进行循环重叠执行需要尽快解决分支问题! ▪ 在循环展开的例子中，我们假设整数部件可以快速解决分 支问题，以便进行循环重叠执行! Loop: LD F0 0 R1 MULTD F4 F0 F2 SD F4 0 R1 SUBI R1 R1 #8 BNEZ R1 Loop ▪ 如果分支依赖于multd,怎么办?? • 需要能预测分支方向 • 如果分支成功，我们就可以重叠执行循环 ▪ 对于superscalar机器这一问题更加突出
控制相关的动态解决技术 ■控制相关:由条件转移或程序中断引起的相关,也称全 局相关。控制相关对流水线的吞吐率和效率影响相对于 数据相关要大得多 条件指令在一般程序中所占的比例相当大 中断虽然在程序中所占的比例不大,但中断发生在程序中的哪一条指令 ,发生在一条指令执行过程中的哪一个功能段都是不确定的 ■处理好条件转移和中断引起的控制相关是很重要的。 关键问题: 要确保流水线能够正常工作 减少因断流引起的吞吐率和效率的下降 计算机体系结构 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): • 最后一次循环, 前面都是预测成功，而这次需要退出循环 • 第一次循环，由于前面预测为失败，而这次实际上为成功