5.2.5 动态分支预测技术

　　动态分支预测技术能够根据近期转移是否成功的历史记录来预测下一次转移的方向，它能够随程序的执行过程动态地改变转移的预测方向。
　　动态转移预测技术的关键是要解决好两个问题，一是如何记录转移历史信息，另一个是如何根据所记录的转移历史信息预测转移的方向。
　　记录转移历史信息的方法通常有三种。第一种是把最近一次或几次转移是否成功的信息记录在转移指令表中；第二种是用一个小容量的高速缓冲栈保存条件转移指令的转移目标地址，第三种是用Cache保存转移目标地址之后的n条指令。下面，根据三种不同的记录转移历史信息的方法介绍三类动态转移预测技术。

　　方法一：在指令Cache中记录转移历史信息
　　在指令Cache中专门设置一个字段，称为"转移历史表"。在执行转移指令时，把转移成功或不成功的信息记录在这个"转移历史表"中。可以只用一个二进制位来记录最近一次转移是否成功的信息，也可以用多个二进制位来记录最近几次转移是否成功的信息。当下次再执行到这条指令时，转移预测逻辑根据"转移历史表"中记录的信息预测转移成功或不成功。
　　当采用只记录最近一次转移是否成功的历史信息时，每一条指令的"转移历史表"只需要一个二进制位，它的状态转换图如图5.35(a)所示。每个圆圈表示一种状态，圆圈中的"T"或"N"表示最近一次执行这条转移指令时，实际转移成功或不成功的信息，这个信息也就是"转移历史表"中所记录的内容。在执行条件转移指令时，如果"转移历史表"中记录的内容是"T"，则转移预测逻辑预测转移成功，并按照转移成功的方向取指令并分析指令；如果记录的是"N"，则按照转移不成功的方向继续取下一条指令并分析指令。在转移条件实际形成之后，如果与预测的转移方向相同，则预测正确，流水线没有任"断流"损失；如果与预测的转移方向不同，则要作废已经预取和分析的指令，并从另一个方向取指令和分析指令。
　　无论预测的转移方向与指令实际执行结果的转移方向是否相同，都要用本条转移指令实际转移是否成功的信息来修改"转移历史表"。修改的方法可以按照图5.35(a)所示状态转换图进行，图中带有箭头的线表示状态转换的方向，线旁边的T表示指令实际执行结果为转移成功，而N表示指令实际执行结果为转移不成功。当采用只记录最近一次转移是否成功的历史信息时，"转移历史表"的修改方法很简单。如果"转移历史表"中原来记录的是"T"，本次转移成功，T"转移历史表"中的内容继续保持"T"；如果原来记录的是"T"，本次转移不成功，则"转移历史表"中的内容要修改为"N"。同样，如果"转移历史表"中原来记录的是"N"，本次转移不成功，则"转移历史表"中的内容继续保持"N"；如果原来记录的是"N"，本次转移成功，则"转移历史表"中的内容要修改为"T"。
　　为了取得更好的转移预测效果，通常需要记录最近多次转移是否成功的历史信息，这时，"转移历史表"也需要有多个二进制位。如果转移历史信息记录得愈多，状态转换关系也就愈复杂。记录最近两次转移是否成功的历史信息的状态转换关系如图5.35(b)所示。与图5.35(a)类似，每个圆圈表示一种状态，圆圈中的上面一行表示最近两次执行这条转移指令时，实际转移成功或不成功的信息，这个信息也是"转移历史表"中所记录的内容。圆圈中的下面一行表示在当前这种状态下，本次执行这条转移指令时预测的转移方向。

　　在图5.35(b)中，对于左上角的状态，圆圈中的"TT"表示历史上最近两次执行这条转移指令时转移都成功，本次又执行这条转移指令，预测转移成功。如果实际执行结果转移又成功，则"转移历史表"中所记录的内容仍保持"TT"；如果实际执行结果转移不成功，则要转向右上角的状态"TN"，把"转移历史表"中记录的内容修改为"TN"。同样，对于右上角的状态，圆圈中的"TN"表示历史上最近一次执行这条转移指令时转移不成功，而再上一次执行这条指令时转移是成功的，本次又执行这条转移指令，预测转移成功。如果实际执行结果转移成功，则转向左下角的状态"NT"，把"转移历史表"中记录的内容修改为"NT"；如果实际执行结果转移不成功，则转向右下角的状态"NN"，把"转移历史表"中记录的内容修改为"NN"。对于另外两种状态，可以结合图5.35(b)自己进行分析。
　　实际上，在图5.35(b)中，修改"转移历史表"的规则是采用了一种向左移位的方法，右边新移入的就是本次执行这条转移指令时转移是否成功的信息；而转移预测是偏向于转移成功的，只有历史上最近两次执行这条转移指令时转移都没有成功，本次才预测转移不成功，对于另外三种情况都预测转移成功。
　　"转移历史表"的修改规则和转移预测规则可以有多种多样，"转移历史表"除了记录转移是否成功的历史信息之外，也可以记录转移预测是否成功的信息。同样，预测本次转移方向时，也可以用最近预测是否成功的信息作为依据。
　　当一条转移指令第一次被执行时，它还没有转移历史的记录，即"转移历史表"还是空白的。可以有两种做法，一种是在"转移历史表"中预置转移历史信息。例如，可以预置历史上转移都成功；那么，第一次执行这条转移指令时，必然预测为转移成功。另一种方法是根据指令本身的偏移字段的符号来预测转移的方向；如果偏移字段的符号是负的，则预测转移成功，否则预测转移不成功。当偏移字段的符号是负时，表示要向后转移，通常是转移到一个循环程序的开始；因此，转移成功的概率比较大。
　　采用在指令Cache中记录转移历史信息的方法，其优点是不必专门设置转移缓冲栈，所记录的转移历史信息比较少。它的缺点是需要有专门的指令Cache和专门的指令Cache控制逻辑。DEC公司的Alpha 21064超标量超流水线处理机就采用了这种转移预测方法，在它的一级指令Cache中有一个专门的"转移历史表"字段。