动态分支预测技术

动态分支预测:在程序运行时,根据分支指令过去的表现来预测其将来的行为

分支预测的有效性取决于:

  • 预测的准确性
  • 预测正确和不正确两种情况下的分支开销
    • 决定开销的因素:流水线结构;预测的方法;预测错误时的恢复策略等

采用动态分支预测的目的:

  • 预测分支是否成功
  • 尽快找到分支目标地址,避免控制相关造成流水线停顿

采用分支历史表BHT

  • 最简单的动态分支预测方法
  • 用BHT来记录分支指令最近一次或几次的执行情况(成功还是失败 ),并据此进行预测

采用两位二进制位来记录历史,且性能与n位(n>2)差不多,状态转换图如下:

图片1.png

例如当前状态为10,将预测分支成功,若分支成功则进入状态11,继续处理后续指令;若分支失败则进入状态00,作废已经预取和分析的指令,恢复现场并从另一分支重新取指令。

采用分支目标缓冲器BTB

目标:将分支开销降为0

方法:分支目标缓冲

  • 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来,缓冲区以分支指令的地址作为标识,这个缓冲区就是BTB

图片2.png

采用BTB后在流水线各个阶段所进行的操作:

图片3.png

另一种形式:在分支目标缓冲器中增设一个至少两位的分支历史表字段;进一步地,在表中对于每条分支指令都存放若干条分支目标处的指令,形成分支目标指令缓冲器。就形成了前瞻或预取指令。

基于硬件的前瞻执行

思想:

对分支指令的结果进行猜测,并假设这个猜测总是对的,然后按这个猜测结果继续取、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器,而是写入一个称为再定序缓冲器ROB(ReOrder Buffer)中 。等到相应的指令得到“确认”(即确实是应该执行的)之后,才将结果写入寄存器或存储器。

对Tomasulo算法的写结果和指令完成分成两个不同的段:

  • 写结果
    • 把前瞻执行的结果写到ROB中
    • 通过CDB在指令之间传送结果,供需要用到这些结果的指令使用
  • 指令确认段
    • 如果前面所做的猜测是对的,把在ROB中的结果写到寄存器或存储器
    • 如果发现前面对分支结果的猜测是错误的,那就不予以确认,并从那条分支指令的另一条路径开始重新执行

实现前瞻的关键思想:允许指令乱序执行,但必须顺序确认;在指令被确认之前,不允许它进行不可恢复的操作。

支持前瞻执行的浮点部件的结构:

图片4.png

ROB中的项

  • 指令类型:指出该指令是分支指令、store指令或寄存器操作指令
  • 目标地址:给出指令执行结果应写入的目标寄存器号(如果是load和ALU指令)或存储器单元的地址(如果是store指令)
  • 数据值字段:用来保存指令前瞻执行的结果,直到指令得到确认
  • 就绪字段:指出指令是否已经完成执行并且数据已就绪

保留站换名通过ROB实现。

采用前瞻执行机制后,指令的执行步骤:

  • 流出
    • 从浮点指令队列的头部取一条指令
    • 如果有空闲的保留站(设为r)且有空闲的ROB项(设为b),就流出该指令,并把相应的信息放入保留站r和ROB项b
    • 如果保留站或ROB全满,便停止流出指令,直到它们都有空闲的项
  • 执行
    • 如果有操作数尚未就绪,就等待,并不断地监测CDB(检测RAW冲突)
    • 当两个操作数都已在保留站中就绪后,就可以执行该指令的操作
  • 写结果
    • 当结果产生后,将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上,经CDB写到ROB以及所有等待该结果的保留站
    • 释放产生该结果的保留站
    • store指令在本阶段完成,其操作为
      • 如果要写入存储器的数据已经就绪,就把该数据写入分配给该store指令的ROB项
      • 否则,就监测CDB,直到那个数据在CDB上播送出来,才将之写入分配给该store指令的ROB项
  • 确认
    • 其他指令(除分支和store)
      • 当该指令到达ROB队列的头部而且其结果已经就绪时,就把该结果写入该指令的目的寄存器,并从ROB中删除该指令
    • store指令
      • 当该指令到达ROB队列的头部而且其结果已经就绪时,就把该结果写入存储器,并从ROB中删除该指令
    • 分支指令
      • 当预测错误的分支指令到达ROB队列的头部时,清空ROB,并从分支指令的另一个分支重新开始执行
      • 当预测正确的分支指令到达ROB队列的头部时,该指令执行完毕

例子

  1. L.D F6,34(R2)
  2. L.D F2,45(R3)
  3. MUL.D F0,F2,F4
  4. SUB.D F8,F2,F6
  5. DIV.D F10,F0,F6
  6. ADD.D F6,F8,F2

加法2周期,乘法10周期,除法40周期。当指令MUL.D即将确认时:

图片5.png

前瞻执行:

  • 通过ROB实现了指令的顺序完成
  • 能够实现精确异常
  • 很容易地推广到整数寄存器和整数功能单元上
  • 主要缺点:所需的硬件太复杂

多指令流出技术

在每个时钟周期内流出多条指令,CPI<1

图片6.png

多流出处理机的两种基本风格

超标量(Superscalar)

  • 在每个时钟周期流出的指令条数不固定,依代码的具体情况而定。(有个上限)
  • 设这个上限为n,就称该处理机为n-流出
  • 可以通过编译器进行静态调度,也可以基于Tomasulo算法进行动态调度

超长指令字VLIW(Very Long Instruction Word)

  • 在每个时钟周期流出的指令条数是固定的,这些指令构成一条长指令或者一个指令包
  • 指令包中,指令之间的并行性是通过指令显式地表示出来的
  • 指令调度是由编译器静态完成的

超标量处理机与VLIW处理的相比的优点:

  • 超标量结构对程序员是透明的,处理机能自己检测下一条指令能否流出,不需要由编译器或专门的变换程序对程序中的指令进行重新排列
  • 即使是没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行,当然运行的效果不会很好

基于静态调度的多流出技术

静态调度:在典型的超标量处理器中,每个时钟周期可流出1到8条指令。指令按序流出,在流出时进行冲突检测

MIPS处理机实现超标量

假设每个时钟周期流出两条指令:1整数型指令+1浮点操作指令

load、store、分支归为整数型指令

对指令的处理:

  • 从Cache中取两条指令
  • 确定那几条指令可以流出(0~2条指令)
  • 把它们发送到相应的功能部件

假设浮点指令是加法指令,执行时间为两个时钟周期

图片7.png

限制超标量流水线性能发挥的障碍

  • load指令:load后续三条指令不能使用其结果,否则会引起停顿
  • 分支延迟
    • 如果分支指令是流出包中的第一条指令,则其延迟是3个时钟周期
    • 否则就是流出包中的第二条指令,其延迟就是两个时钟周期

基于动态调度的多流出技术

扩展Tomasulo算法:支持双流出超标量流水线

如何实现多流出

  • 在半个时钟周期里完成流出步骤,这样一个时钟周期就能处理两条指令
  • 设置一次能同时处理两条指令的逻辑电路

超长指令字技术

  • 把能并行执行的多条指令组装成一条很长的指令
  • 设置多个功能部件
  • 指令字被分割成一些字段,每个字段称为一个操作槽,直接独立地控制一个功能部件
  • 在VLIW处理机中,在指令流出时不需要进行复杂的冲突检测,而是依靠编译器全部安排好了

存在的问题:

  • 程序代码长度增加了
    • 提高并行性而进行的大量的循环展开
    • 指令字中的操作槽并非总能填满
    • 解决:采用指令共享立即数字段的方法,或者采用指令压缩存储—调入Cache或译码时展开的方法
  • 采用了锁步机制
    • 任何一个操作部件出现停顿时,整个处理机都要停顿。因为所有部件都是同步的。在最新的VLIW处理器,各个功能部件尽可能多的独立,通过硬件检测机制允许指令非同步执行
  • 机器代码不兼容性,程序移植困难

多流出处理器收到的限制

  • 程序固有的指令级并行性
  • 硬件上实现困难
  • 超标量和超长指令字处理器固有的技术限制

现存的多数超量处理器,它们将编译器的静态调度和硬件的动态度机结合起来,共同决定可同时并行流出的指令数

超流水线处理机

将每个流水段进一步细分,这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机

典型的超流水线处理器:SGI公司的MIPS系列R4000,指令流水线有8级

图片8.png

  • IF:取指令的前半步,根据PC值去启动对指令Cache的访问
  • IS:取指令的后半步,在这一级完成对指令Cache的访问
  • RF:指令译码,访问寄存器组读取操作数,冲突检测,并判断指令Cache是否命中
  • EX:指令执行。包括:有效地址计算,ALU操作,分支目标地址计算,条件码测试
  • DF:取数据的前半步,启动对数据Cache的访问
  • DS:取数据的后半步,在这一级完成对数据Cache的访问
  • TC:标识比较,判断对数据Cache的访问是否命中
  • WB:load指令或运算型指令把结果写回寄存器组