计算机系统结构 -第三章:指令集并行-2

 四:动态调度解决控制冒险

1-:动态分支预测技术:

所开发的ILP越多，控制相关的制约就越大，分支预测就要有更高的准确度。

这里的动态分支预测技术是指通过硬件技术，在程序执行时根据每一条转移指令过去的转移历史记录来预测下一次转移的方向。通过提前预测分支方向，减少或消除控制相关导致的流水线停顿。

优点:

根据程序的执行过程动态地改变转移的预测方向，因此有更好的准确度和适应性。

程序每次执行时，可能预测的分支方向与前次相同或不同。

我们需要考虑:准确性,和正确or不正确情况下的开销(流水线的结构,预测的方法,预测错误时的恢复策略等):

如果预测失败,我们会:作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

我们的目的是:希望预测成功,并且尽快的找到目标分支

下面我们去看如何记录历史信息,以及如何根据信息决定未来的预测

3个技术:

BHT分支预测缓冲器:

最简单的动态分支预测方法

通过BHT来记录分支指令的最近若干次的执行情况,并以此来做出预测

(最简单的BHT只需要1位,就可以完成依据最近1次的分支预测)

两位的分支预测:(研究表明两位的预测性能和n位的差不多)

状态机如下:

预测的步骤:
1:分支预测:当分支指令达到了ID,会根据BHT读出的信息进行预测,如果预测成功,继续执行,失败就作废+恢复+重取

2:状态修改

什么时候使用BHT方法?

判断时间小于确定时间:比如如果是5段流水,ID就可以判断分支是否成功了,那么此时预测就没有必要了(所以这个方法不能够给所有的流水线都带来好处)

一般来说.4K的BHT就可以带来82%~99%的准确率了

BHT一般可以单独用一个硬件,也可以放在指令寄存器中

下面看一些例子:

每次都是会有2次出错

只有第一次是3次出错,后面的每次都是1次出错

BTB分支目标缓冲器:

算法的目标,将分支的开销降低为0

将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。这个缓冲区就叫做分支目标缓冲器

融入其他的流水级看一看

所以如果采用了BTB,那么可能的延迟情况如下:

(如果不是BTB中的,而且分支指令预测成功,就会额外花费2个周期写入BTB,如果分支失败就不会写入)
好处:

更快地获得分支目标处的指令；

可以一次提供分支目标处的多条指令，这对于多流出处理器是很有必要的；

使我们可以进行称为分支折叠（branch folding）的优化。(直接将目标送到ID,而不用去计算)

还有一种BTB的形式:

BTB和BHT的结合,同时后续存放的也不是地址了,而是若干的指令

****ROB基于硬件的前瞻执行****:

思想

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

这里明显结合了3个思想:

动态分支预测。用来选择后续执行的指令。

在控制相关的结果尚未出来之前，前瞻地执行后续指令。

用动态调度对基本块的各种组合进行跨基本块的调度。

Tomasulo扩展就可以实现前瞻执行:

把Tomasulo算法的写结果和指令完成加以区分，分成两个不同的段：

写结果段:

把前瞻执行的结果写到ROB中,通过CDB在指令之间传送结果，供需要用到这些结果的指令使用。

指令确认段

    在分支指令的结果出来后，对相应指令的前瞻执行给予确认。

如果前面所做的猜测是对的，把在ROB中的结果写到寄存器或存储器。

如果发现前面对分支结果的猜测是错误的，那就不予以确认，并从那条分支指令的另一条路径开始重新执行。  

前瞻实现的关键部分:允许乱序执行,但是顺序确定

Tomasulo的硬件改造:

->

ROB结构

ROB的每一项都由下面四个字段组成:

指令类型:指出该指令是分支指令、store指令或寄存器操作指令。

目标地址:给出指令执行结果应写入的目标寄存器号（如果是load和ALU指令）或存储器单元的地址（如果是store指令）。

数据值字段:用来保存指令前瞻执行的结果，直到指令得到确认。

就绪字段:指出指令是否已经完成执行并且数据已就绪。

同时需要注意的是:Tomasulo保留站的换名功能是由ROB完成的

流水线****:

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

流出

从浮点指令队列的头部取一条指令。

如果有空闲的保留站（设为r）且有空闲的ROB项（设为b），就流出该指令，并把相应的信息放入保留站r和ROB项b。

如果保留站或ROB全满，便停止流出指令，直到它们都有空闲的项。

执行

如果有操作数尚未就绪，就等待，并不断地监测CDB。(检测RAW冲突)

当两个操作数都已在保留站中就绪后，就可以执行该指令的操作。

写结果

当结果产生后，将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上，经CDB写到ROB以及所有等待该结果的保留站。

释放产生该结果的保留站。

 store指令在本阶段完成，其操作为:

如果要写入存储器的数据已经就绪，就把该数据写入分配给该store指令的ROB项。

否则，就监测CDB，直到那个数据在CDB上播送出来，这时才将之写入分配给该store指令的ROB项。

(后续的写入内存交给了ROB处理)

确认

对分支指令、store指令以及其他指令的处理不同：

其他指令（除分支指令和store指令）

     当该指令到达ROB队列的头部而且其结果已经就绪时，就把该结果写入该指令的目标寄存器，并从ROB中删除该指令。   

store指令

    处理与上面类似，只是它把结果写入存储器。

分支指令

当预测错误的分支指令到达ROB队列的头部时，清空ROB，并从分支指令的另一个分支重新开始执行。（错误的前瞻执行）

当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕。

一定要顺序确认************!!!!!!!!

下面看一个样例

周期1:LD指令流出

周期2

第二个LD流出,第一个LD进入执行

周期三:
MUL流出,

第一个LD指令继续执行

第二个LD进入执行

周期4:

MUL等待第二个LD取出的F2

SUB流出

第一个LD写回

第二个LD继续执行

周期5:

DIV流出

第一个LD确认

第二个LD写回

MUL等待F2

SUB等待F2

周期6:

第二个LD广播了F2,MUL和SU同时进入执行

DIV等待F0

ADD流出

周期8:

sub进入写回

MUL继续执行

ADD等待F8

周期9:
SUB要等待MUL确认才能确认

DIV等待

ADD收到了SUB的广播,进入执行

周期11:
MUL继续执行

ADD写回其他的继续等待

周期16:

MUl写回结果:

周期17:

MUL确认

SUB接收到广播的F0,进入执行

周期18:

SUB确认

周期57:

DIV写回

周期58:

DIV确认

周期59:

ADD确认

总结:

通过ROB实现了指令的顺序完成

我们先将数据存储到ROB中,等待确认才会写回

能够实现精确异常。

很容易地推广到整数寄存器和整数功能单元上。

主要缺点：所需的硬件太复杂。