4.3 动态分支预测技术,4.3 动态分支预测技术,动态分支预测 在程序运行时，根据分支指令过去的表现来预测其将来的行为 如果分支行为发生了变化，预测结果也跟着改变 有更好的预测准确度和适应性 需要解决的关键问题 如何记录分支的历史信息； 如何根据这些信息来预测分支的去向（甚至取到指令）4.3 动态分支预测技术,一.采用分支历史表 BHT（Branch History Table） 又称为分支预测缓冲器（Branch Prediciton Buffer） 最简单的动态分支预测方法 用BHT来记录分支指令最近一次或几次的执行情况（成功或不成功），并据此进行预测 1. 只有1个预测位的分支预测缓冲 记录分支指令最近一次的历史，BHT中只需要1位二进制位最简单）,2.采用两位二进制位来记录历史 提高预测的准确度 研究结果表明：两位分支预测的性能与n位（n2）分支预测的性能差不多 1）两位分支预测的状态转换如下所示：,4.3 动态分支预测技术,2）操作步骤：（2步） 分支预测 当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测 若预测正确，就继续处理后续的指令，流水线没有断流。
否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令 状态修改,4.3 动态分支预测技术,3. BHT方法只在以下情况下才有用： 适用情况：判定分支是否成功所需的时间大于确定分支目标地址所需的时间 前述5段经典流水线：由于判定分支是否成功和计算分支目标地址都是在ID段完成，所以BHT方法不会给该流水线带来好处 4. 研究结果表明：对于SPEC89测试程序来说，具有大小为4K的BHT的预测准确率为82%～99% 一般来说，采用4K的BHT就可以了 5. BHT可以跟分支指令一起存放在指令Cache中，也可以用一个专门的硬件来实现4.3 动态分支预测技术,二.采用分支目标缓冲器BTB (Branch Target Buffer) 目的：将分支的开销减少为 0 方法：分支目标缓冲器 BTB 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识 这个缓冲区就是分支目标缓冲器（Branch-Target Buffer，简记为BTB，或者Branch-Target Cache）4.3 动态分支预测技术,1.BTB的结构,,4.3 动态分支预测技术,BTB是用专门的硬件实现的一张表格。
表格中的每一项至少有两个字段： ①执行过的成功分支指令的地址；（作为该表的匹配标识 ） ②预测的分支目标地址2.采用BTB后，在流水线各个阶段所进行的相关操作：,,,预测分支成功,实际分支不成功,BTB的建立,延迟2个时钟周期,,,之前不成功的分支 未执行过的分支 普通指令,三.基于硬件的前瞻执行 1. 前瞻执行（Speculation）的基本思想 对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取、流出和执行后续的指令只是执行指令的结果不是写回到寄存器或存储器，而是放到一个称为ROB（ReOrder Buffer）的缓冲器中等到相应的指令得到“确认” （commit）（即确实是应该执行的）之后，才将结果写入寄存器或存储器4.3 动态分支预测技术,2.基于硬件的前瞻执行结合了三种思想： 1）动态分支预测用来选择后续执行的指令 2）在控制相关的结果尚未出来之前，前瞻地执行后续指令 3）用动态调度对基本块的各种组合进行跨基本块的调度 3.对Tomasulo算法加以扩充，就可以支持前瞻执行 把Tomasulo算法的写结果和指令完成加以区分，分成两个不同的段： 写结果 指令确认,4.3 动态分支预测技术,写结果段 把前瞻执行的结果写到ROB中； 通过CDB在指令之间传送结果，供需要用到这些结果的指令使用。
指令确认段 在分支指令的结果出来后，对相应指令的前瞻执行给予确认 如果前面所做的猜测是对的，把在ROB中的结果写到寄存器或存储器 如果发现前面对分支结果的猜测是错误的，那就不予以确认，并从那条分支指令的另一条路径开始重新执行4.3 动态分支预测技术,,支持前瞻执行的浮点部件的结构,,介于保留站和寄存器组之间,,支持前瞻执行的浮点部件的结构,换名功能是由ROB来完成的 实现前瞻的关键思想： 允许指令乱序执行，但必须顺序确认4.3 动态分支预测技术,采用前瞻执行机制后，指令的执行步骤： 书P132 （在Tomasulo算法的基础上改造的 ） 1. 流出 从浮点指令队列的头部取一条指令 如果有空闲的保留站（设为r）且有空闲的ROB项（设为b），就流出该指令，并把相应的信息放入保留站r和ROB项b 如果保留站或ROB全满，便停止流出指令，直到它们都有空闲的项4.3 动态分支预测技术,2. 执行 如果有操作数尚未就绪，就等待，并不断地监测CDB (检测RAW冲突) 当两个操作数都已在保留站中就绪后，就可以执行该指令的操作 3. 写结果 当结果产生后，将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上，经CDB写到ROB以及所有等待该结果的保留站。
释放产生该结果的保留站 store指令在本阶段完成，其操作为:,4.3 动态分支预测技术,如果要写入存储器的数据已经就绪，就把该数据写入分配给该store指令的ROB项 否则，就监测CDB，直到那个数据在CDB上播送出来，这时才将之写入分配给该store指令的ROB项 4. 确认 对分支指令、store指令以及其他指令的处理不同： 其他指令（除分支指令和store指令） 当该指令到达ROB队列的头部而且其结果已经 就绪时，就把该结果写入该指令的目标寄存器，并从 ROB中删除该指令4.3 动态分支预测技术,store指令 处理与上面类似，只是它把结果写入存储器 分支指令 当预测错误的分支指令到达ROB队列的头部时，清空ROB，并从分支指令的另一个分支重新开始执行 （错误的前瞻执行） 当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕4.4 多指令流出技术,4.4 多指令流出技术,一.单流出（单发射）处理机和多流出（多发射）处理机 1. 单流出处理机——每个周期只取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果理想的CPI=1） 设计目标：每个时钟周期平均执行一条指令，即指令并行度ILP期望值为1.,4.4 多指令流出技术,2. 多流出处理机(多发射) 每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果。
需要多套（m）指令部件（取指部件和译码部件）和多个写结果部件设置多个指令执行部件，有些指令部件采用流水线结构 设计目标：一个时钟周期内流出多条指令， 指令并行度ILP1（CPI＜1）同时发射两条指令的多发射处理机流水线：,4.4 多指令流出技术,二. 多流出处理机有两种基本结构 1. 超标量处理机（空间并行）： 一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机 最基本的要求是有两套或两套以上完整的指令执行部件 为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线4.4 多指令流出技术,目前的指令调度技术，每个周期发射2-4条指令比较合理 例如：Intel公司的i860、i960、Pentium，IBM公司的Power 6000每个周期发射2条指令；Pentium Ⅲ每个周期发射3条指令 超标量处理机在每个时钟周期流出的指令条数不固定，依代码的具体情况而定有上限，设这个上限为m，就称该处理机为m-流出（发射m条指令） 实际指令级并行度1＜ILP＜m 可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度4.4 多指令流出技术,2. 超长指令字VLIW（Very Long Instruction Word） 基本思路：由编译器在编译时找出指令间潜在的并行性，进行适当调度安排，把多个能并行执行的操作组合在一起，成为一条具有多个操作段的超长指令（100多位到几百位），并设置多个功能部件。
超长指令字被分割成一些操作段，每个字段称为一个操作槽，直接独立地控制一个功能部件 VLIW处理机是一种单指令多操作码多数据的系统结构4.4 多指令流出技术,每拍启动一条长指令，执行3个操作，相当于3条指令并行在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个混合指令包 指令包中，指令之间的并行性是通过指令显式地表示出来的 指令调度是由编译器静态完成的4.4 多指令流出技术,三. 多流出流水线的调度问题 顺序发射与乱序发射：指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射(in-order issue)，否则，称为乱序发射(out-order issue) 顺序完成与乱序完成：指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成否则，称为乱序完成 多流水的调度主要有三种方法： 顺序发射顺序完成 顺序发射乱序完成 乱序发射乱序完成,4.4 多指令流出技术,,以如下指令为例，说明三种调度方法：,同时发射两条指令的多发射处理机流水线：,真数据相关,真数据相关 输出相关,反相关,流水线1 流水线2,,,,功能 部件 冲突,,,（1）顺序发射顺序完成,6条指令共用了10个时钟周期才完成。
有8个空闲的时钟周期指令流水线时空图(假设采用“定向技术”)：,,,,插入5个空闲的时钟周期，为了维持顺序完成2）顺序发射乱序完成,共需9个周期仅有3个空闲周期 总执行时间缩短了； 功能部件利用率提高了FA3,顺序发射乱序完成的指令完成次序：,指令流水线时空图：,,（3）乱序发射乱序完成,先行指令窗口： 能够从指令Cache中预取多条指令多数超标量处理机的指令窗口大小为2-8条指令 能够通过硬件对窗口内的指令进行数据相关性分析和功能部件冲突的检测可以把没有功能部件冲突、没有数据相关和控制相关的指令超越它前面的指令先发射到操作部件中去3）乱序发射乱序完成,共需8个周期无空闲周期 总执行时间最短； 功能部件利用率最高指令在流水线中的发射次序：,指令在流水线中的完成次序：,指令流水线时空图：,,4.4 多指令流出技术,四、超流水线处理机 两种定义： 在一个时钟周期内能够分时发射多条指令的处理机称为超流水线处理机 指令流水线的段数大于等于8的流水线处理机 提高处理机性能的两种方法： 通过增加硬件资源来提高处理机性能----超标量处理机 通过各部分硬件的重叠工作来提高处理机性能----超流水线处理机。
对于一台每个时钟周期能流出n条指令的超流水线来说，这n条指令不是同时流出的，而是每隔1/n个时钟周期流出一条指令 即处理机的流水线周期为1/n个时钟周期每个时钟周期分时发射2条指令的超流水线处理机的指令执行时空图,4.4 多指令流出技术,1．典型结构 MIPS R4000采用8级超流水线结构 每个时钟周期包含两个流水段； 是一种很标准的超流水线处理机结构； 指令流水线有8个流水段； 指令Cache和数据Cache的容量各8KB； 每个时钟周期可以访问Cache两次； 在一个时钟周期内可以从指令Cache中读出两条指令，从数据Cache中读出或写入两个数据 主要运算部件有整数部件和浮点部件4.4 多指令流出技术,MIPS R4000的8级流水线结构图,,,一个时钟周期,,,一个时钟周期,4.4 多指令流出技术,4.4 多指令流出技术,每个时钟周期分时发射2条指令的超流水线处理机的指令执行时空图如下：,2、与超标量机提高处理机性能的途径不同 超标量处理机通过重复设置多个“取指令”部件，多个“译码”、“执行”和“写回结果”部件，使其同时工作来提高指令的执行速度，以增加硬件资源为代价来换取处理机性能。