控制相关的动态解决技术

1、128秦杰 郑丽萍 张庆辉4.3 控制相关的动态解决技术 处理器一个时钟周期流出多条指令受到以下两处理器一个时钟周期流出多条指令受到以下两 个因素的限制：个因素的限制： 流出流出n n条条指令的处理器中，遇到分支指令指令的处理器中，遇到分支指令的的 速度也快了速度也快了n n倍；倍； 根据根据AmdahlAmdahl定律可知，随着机器定律可知，随着机器CPICPI的降的降低，低， 控制相关对性能的影响越来越大。控制相关对性能的影响越来越大。第四章 指令级并行228秦杰 郑丽萍 张庆辉本节着重于：本节着重于： 通过硬件技术，动态地进行分支处理，对程通过硬件技术，动态地进行分支处理，对程序运行时的

2、分支行为进行预测，提前对分支操作做序运行时的分支行为进行预测，提前对分支操作做出反应，加快分支处理的速度。出反应，加快分支处理的速度。 分支的最终延迟分支的最终延迟取决于流水线的结构、预测的取决于流水线的结构、预测的方法和预测错误后恢复所采取的策略。方法和预测错误后恢复所采取的策略。 4.3 控制相关的动态解决技术328秦杰 郑丽萍 张庆辉4.3.1 分支预测缓冲 动态分支预测必须解决动态分支预测必须解决两个问题两个问题： 如何记录一个分支操作的历史。如何记录一个分支操作的历史。 决定预测的走向。决定预测的走向。 记录分支历史的方法有以下几种：记录分支历史的方法有以下几种： （1 1）仅仅记录

3、最近一次或最近几次的分支历史；）仅仅记录最近一次或最近几次的分支历史； （2 2）记录分支成功的目标地址；）记录分支成功的目标地址； （3 3）记录分支历史和分支目标地址，相当于前）记录分支历史和分支目标地址，相当于前 面两种方式的结合；面两种方式的结合； （4 4）记录分支目标地址的一条或若干条指令。）记录分支目标地址的一条或若干条指令。 4.3 控制相关的动态解决技术428秦杰 郑丽萍 张庆辉分支预测缓冲技术分支预测缓冲技术（Branch-Prediction BufferBranch-Prediction Buffer或者或者Branch History TableBranch Hist

4、ory Table，简写为，简写为BTBBTB或者或者BHTBHT）：）： 目前广泛使用的最简单的动态分支预测技术。目前广泛使用的最简单的动态分支预测技术。 使用一片存储区域，记录最近一次或几次分支特使用一片存储区域，记录最近一次或几次分支特征的历史。征的历史。 1. 只有只有1 1个预测位个预测位的分支预测缓冲的分支预测缓冲 索引索引：分支指令地址的低位。：分支指令地址的低位。 存储区存储区：1 1位位的分支历史记录位，又称为的分支历史记录位，又称为 预测位，记录该指令最近一次预测位，记录该指令最近一次 分支是否成功。分支是否成功。4.3 控制相关的动态解决技术528秦杰 郑丽萍 张庆辉状态

5、转换图状态转换图 “0”“0”记录分支不成功记录分支不成功 “1”1”记录分支成功记录分支成功 1 0 分支不成功 分支成功 分支不成功 分支成功 图图4.9 4.9 只有只有1 1个预测位的分支预测缓冲状态转换图个预测位的分支预测缓冲状态转换图 4.3 控制相关的动态解决技术628秦杰 郑丽萍 张庆辉2. 2. 分支预测缓冲技术包括两个步骤分支预测缓冲技术包括两个步骤 分支预测分支预测 如果当前缓冲记录的预测位为如果当前缓冲记录的预测位为“1”1”，则预，则预 测分为成功；如果预测位为测分为成功；如果预测位为“0”0”，则预测分支，则预测分支为不成功。为不成功。预测位修改预测位修改 如果当前

6、分支成功，则预测位置为如果当前分支成功，则预测位置为“1”1”； 如果当前分支不成功，预测位置为如果当前分支不成功，预测位置为“0”0”。 3.3.分支预测错误时，预测位就被修改，并且需分支预测错误时，预测位就被修改，并且需 要恢复现场，程序从分支指令处重新执行要恢复现场，程序从分支指令处重新执行。 4.3 控制相关的动态解决技术728秦杰 郑丽萍 张庆辉 i-1 i i+1 i+2 p+1 p+2 猜测执行路径 实际执行路径 分支指令 得到分支结果 图图4.10 4.10 分支预测执行不成功和重新执行过程分支预测执行不成功和重新执行过程 4.3 控制相关的动态解决技术828秦杰 郑丽萍 张庆

7、辉例例4.64.6 一个循环共循环一个循环共循环1010次，它将分支成功次，它将分支成功9 9次，次， 1 1次不成功。假设此分支的预测位始终在次不成功。假设此分支的预测位始终在缓冲区中。那么分支预测的准确性是多少？缓冲区中。那么分支预测的准确性是多少？ 解解 这种固定的预测将会在第一次和最后一次这种固定的预测将会在第一次和最后一次 循环中出现预测错误。循环中出现预测错误。 第一次预测错误是源于上次程序的执行，第一次预测错误是源于上次程序的执行， 因为上一次程序最后一次分支是不成功的。因为上一次程序最后一次分支是不成功的。 最后一次预测错误是不可避免的，因为前最后一次预测错误是不可避免的，因为

8、前 面的分支总是成功，共面的分支总是成功，共九九次。次。 因此，尽管分支成功的比例率是因此，尽管分支成功的比例率是90%90%， 但分支预测的准确性为但分支预测的准确性为80%80%（两两次不正确，次不正确， 8 8次确）。次确）。 4.3 控制相关的动态解决技术928秦杰 郑丽萍 张庆辉4.4.1 1位预测机制的位预测机制的缺点缺点 只要预测出错，往往是连续两次而不是一次。只要预测出错，往往是连续两次而不是一次。5.5.解决方法解决方法 采用采用两个预测位的预测机制两个预测位的预测机制。 在两个预测位的分支预测中，更改对分支的在两个预测位的分支预测中，更改对分支的预测必须有两次连续预测错误。

9、预测必须有两次连续预测错误。 两位分支预测的状态转换图两位分支预测的状态转换图4.3 控制相关的动态解决技术1028秦杰 郑丽萍 张庆辉 分支预测： 不成功 分支预测： 成功 11 10 分支不成功 分支成功 分支不成功 分支成功 01 00 分支不成功 分支成功 分支不成功 分支成功 图图4.11 4.11 具有两个分支预测位的分支预测缓冲状态转换机制具有两个分支预测位的分支预测缓冲状态转换机制 4.3 控制相关的动态解决技术1128秦杰 郑丽萍 张庆辉6. 6. n n位位分支预测缓冲分支预测缓冲采用采用n n位位计数器，则计数器的值在计数器，则计数器的值在0 0到到2 2n n-1-1之

10、间：之间： 当计数器的值大于或等于最大值的一半（当计数器的值大于或等于最大值的一半（2 2n-1n-1）时，则预测下一次分支成功；时，则预测下一次分支成功； 否则预测下一次分支不成功。否则预测下一次分支不成功。预测位的修改和两位预测时相同：预测位的修改和两位预测时相同： 当分支成功时计数器的值当分支成功时计数器的值加加1 1，不成功时，不成功时减减1 1。研究表明：研究表明： n n位位分支预测的性能和两位分支预测差不多，分支预测的性能和两位分支预测差不多，因而大多数处理器都只采用两位分支预测。因而大多数处理器都只采用两位分支预测。4.3 控制相关的动态解决技术1228秦杰 郑丽萍 张庆辉7.

11、7.对于真实的应用程序，两位的分支预测的准对于真实的应用程序，两位的分支预测的准确率可达到多少呢？确率可达到多少呢？ SPEC89SPEC89标准程序的测试：标准程序的测试： 在使用在使用40964096个记录项的缓冲区时，分支个记录项的缓冲区时，分支 预测准确率可达到预测准确率可达到99%99%到到82%82%。 使用无穷多历史记录项的分支预测缓冲，使用无穷多历史记录项的分支预测缓冲， 只有少量程序的分支预测准确率仅仅比只有少量程序的分支预测准确率仅仅比40964096 个记录项提高个记录项提高1%1%，多数程序的预测精度是相，多数程序的预测精度是相 同的。同的。 因此，对于因此，对于SPE

12、C89SPEC89应用环境而言，应用环境而言，4K4K的的 缓冲区是恰当的。缓冲区是恰当的。8.8.上述分支预测机制对于改进后的上述分支预测机制对于改进后的DLXDLX流水线没流水线没有帮助。有帮助。 4.3 控制相关的动态解决技术1328秦杰 郑丽萍 张庆辉4.3.2 分支目标缓冲 目标：目标：将分支的开销降为零。将分支的开销降为零。方法：方法：分支目标缓冲分支目标缓冲 将分支成功的分支指令的地址和它的分支目将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标示；取指令阶段，所以分支指令的地址作为标示；取

13、指令阶段，所有指令地址都与保存的标示作比较，一旦相同，有指令地址都与保存的标示作比较，一旦相同，我们就认为本指令是分支指令，且认为它转移我们就认为本指令是分支指令，且认为它转移成功，并且它的分支目标（下一条指令）地址成功，并且它的分支目标（下一条指令）地址就是保存在缓冲区中的分支目标地址。就是保存在缓冲区中的分支目标地址。 这个缓冲区就是这个缓冲区就是分支目标缓冲区分支目标缓冲区（Branch-Branch-Target BufferTarget Buffer，简记为，简记为BTBBTB，或者，或者Branch-Branch-Target CacheTarget Cache）。）。 4.3 控

14、制相关的动态解决技术1. 1. 分支目标缓冲结构和工作过程分支目标缓冲结构和工作过程 N 命中？ 当前 PC 地址标示 分支目标 PC 分支目标指令 查找、比较 分支目标缓冲 没有命中，则认为本指令不是分支，按普通指令执行 Y 命中，则认为本指令是分支，且分支成功，以分支目标缓冲中分支目标 PC 作为下一条指令地址 图图4.12 4.12 分支目标缓冲的结构和工作过程分支目标缓冲的结构和工作过程 2. 2. 在流水线的各个阶段中，具有分支目标缓冲的工作在流水线的各个阶段中，具有分支目标缓冲的工作 分配如图分配如图4.134.13。 当前 PC 值送存储器和 BTB BTB 中存在？ 成功分支指

15、令？ 当前分支成功？ 以分支目标 PC 值送存储器 否 是 否 普通指令 是 是 否 预测成功，后续指令无延迟执行 预测错误，清除取来的指令并从分支的另外一个目标取指令，删除BTB 中对应项 将当前指令PC 值和分支目标PC 送入 BTB 中作为一个新项 取指令 指令译码 指令执行 问题：问题：解决预测错误或不命中的延迟。解决预测错误或不命中的延迟。 1628秦杰 郑丽萍 张庆辉3. 3. 采用采用BTBBTB技术时指令在各种情况下的延迟技术时指令在各种情况下的延迟 指令在BTB中？是是不是不是预测结果成功成功实际的动作成功不成功成功不成功延迟周期0220表表4.3 4.3 采用采用BTBBT

16、B技术时指令在各种情况下的延迟技术时指令在各种情况下的延迟 4.3 控制相关的动态解决技术1728秦杰 郑丽萍 张庆辉例例4.74.7 按按表表4.34.3计算分支转移总的延迟，根据下面的假计算分支转移总的延迟，根据下面的假 设，计算分支目标缓冲的性能。设，计算分支目标缓冲的性能。 （1 1）对于）对于BTBBTB中的指令，预测准确率中的指令，预测准确率90%90% （2 2）缓冲区命中率）缓冲区命中率90%90% （3 3）不在）不在BTBBTB中分支转移成功的比例为中分支转移成功的比例为60%60% 解解 根据根据表表4.34.3的分类，性能计算包括的分类，性能计算包括4 4个个部分：部分

17、： （1 1）在）在BTBBTB中，预测成功，实际成功，此时的中，预测成功，实际成功，此时的 延迟为延迟为0 0。 （2 2）在）在BTBBTB中，预测成功，实际不成功，此时中，预测成功，实际不成功，此时 的延迟为：的延迟为： 4.3 控制相关的动态解决技术1828秦杰 郑丽萍 张庆辉 BTBBTB命中率命中率 预测错误率预测错误率 2 2 = 90% = 90% 10% 10% 2 2 = 0.18 = 0.18（时钟周期）（时钟周期）（3 3）不在）不在BTBBTB中，实际成功，此时的延迟为：中，实际成功，此时的延迟为：（1-BTB1-BTB命中率）命中率） 不在不在BTBBTB中分支转移

18、成功率中分支转移成功率 2 2 = 10% = 10% 60% 60% 2 2 = 0.12 = 0.12（时钟周期）（时钟周期）（4 4）不在）不在BTBBTB中，实际不成功，此时的延迟为中，实际不成功，此时的延迟为0 0。4.3 控制相关的动态解决技术1928秦杰 郑丽萍 张庆辉4. 4. 对分支预测机制的一种改进对分支预测机制的一种改进 在缓冲区中不仅存入目的地址，而且还存入一在缓冲区中不仅存入目的地址，而且还存入一 个或多个目标指令。个或多个目标指令。 有两种潜在的有两种潜在的好处好处： 在连续取指令之前，可以较长时间的访问缓冲在连续取指令之前，可以较长时间的访问缓冲区，这时的分支目的

19、缓冲区较大。区，这时的分支目的缓冲区较大。对目的指令进行缓冲，构成称为对目的指令进行缓冲，构成称为分支目标指令分支目标指令缓冲缓冲（branch foldingbranch folding）的结构，它可使无条）的结构，它可使无条件分支的延迟达到零，甚至有的条件分支也可件分支的延迟达到零，甚至有的条件分支也可达到零延迟达到零延迟 。4.3 控制相关的动态解决技术2028秦杰 郑丽萍 张庆辉4.3.3 基于硬件的前瞻执行 前瞻（前瞻（SpeculationSpeculation）的技术方法）的技术方法： 它允许在处理器还未判断指令是否能执行它允许在处理器还未判断指令是否能执行之前就提前执行，以克服

20、控制相关。之前就提前执行，以克服控制相关。 在大多数指令前瞻正确的前提下，前瞻就在大多数指令前瞻正确的前提下，前瞻就可以有效地加快分支处理的速度。可以有效地加快分支处理的速度。 1.1.基于硬件的前瞻执行结合了基于硬件的前瞻执行结合了三种思想三种思想： （1 1）采用动态的分支预测技术来选择后续执）采用动态的分支预测技术来选择后续执 行语句；行语句；4.3 控制相关的动态解决技术2128秦杰 郑丽萍 张庆辉 （2 2）在控制相关消除之前指令前瞻执行；）在控制相关消除之前指令前瞻执行； （3 3）对基本块采用动态调度。）对基本块采用动态调度。 2.2.基于硬件的前瞻是动态地根据数据相关性来选择基

21、于硬件的前瞻是动态地根据数据相关性来选择指令和指令的执行时间。指令和指令的执行时间。 实质：实质：数据流驱动运行数据流驱动运行（data-flow executiondata-flow execution） 只要操作数有效，指令就可以执行。只要操作数有效，指令就可以执行。3.3.指令的确认指令的确认 前瞻执行的指令产生的结果要一直到指令处前瞻执行的指令产生的结果要一直到指令处于非前瞻执行状态时，才能确定为最终结果，才于非前瞻执行状态时，才能确定为最终结果，才允许最终写到寄存器或存储器中去。允许最终写到寄存器或存储器中去。 4.3 控制相关的动态解决技术2228秦杰 郑丽萍 张庆辉4.4.实现前

22、瞻的实现前瞻的关键思想关键思想： 允许指令乱序执行，但必须顺序确认。允许指令乱序执行，但必须顺序确认。5.5.再定序缓冲（再定序缓冲（reorder bufferreorder buffer，简记为，简记为ROBROB） 保存那些执行完毕但未经确认的指令及其结保存那些执行完毕但未经确认的指令及其结果。在指令执行完毕和确认之间这段时间里，由果。在指令执行完毕和确认之间这段时间里，由 再定序缓冲提供所有其他指令需要的作为操作数再定序缓冲提供所有其他指令需要的作为操作数的数据。再定序缓冲区还可以取代取（的数据。再定序缓冲区还可以取代取（loadload）缓）缓 冲区。冲区。 4.3 控制相关的动态解

23、决技术2328秦杰 郑丽萍 张庆辉再定序缓冲的每个项包含再定序缓冲的每个项包含三个域三个域： （1 1）指令的类型）指令的类型 指令类型包括是否是分支（尚无结果）、指令类型包括是否是分支（尚无结果）、 存操作（目的地址为存储器）或寄存器操作存操作（目的地址为存储器）或寄存器操作 （ALUALU操作或目的地址是寄存器的取操作）。操作或目的地址是寄存器的取操作）。 （2 2）目的地址）目的地址 目的地址域给出结果应写入的目的寄存目的地址域给出结果应写入的目的寄存 器号（对于取操作和器号（对于取操作和ALUALU指令）或存储器的地指令）或存储器的地 址（存操作）。址（存操作）。 （3 3）值域）值域

24、 值域用来保存指令前瞻执行的结果，直值域用来保存指令前瞻执行的结果，直 到指令得到确认。到指令得到确认。 4.3 控制相关的动态解决技术 使用再定序缓冲的处理部件的硬件结构使用再定序缓冲的处理部件的硬件结构 浮点 操作 队列 再定序缓冲 浮点寄存器组 FP 加法器 FP 乘法器 公共数据总线 从存储器来 (取的结果) ） 从指令部件来 保留站 去存储器 (地址/数据) 操作总线 操作数总线 图图4.14 4.14 采用采用TomasuloTomasulo算法并支持前瞻执行的算法并支持前瞻执行的DLXDLX浮点部件的结构浮点部件的结构 2528秦杰 郑丽萍 张庆辉例例4.84.8 假设浮点功能单元的延迟为加法是假设浮点功能单元的延迟为加法是2 2个个时钟周时钟周 期，乘法是期，乘法是1010个个时钟周期，除法时钟周期，除法4040个个时钟周时钟周 期。给出下面的代码段当指令期。给出下面的代码段当指令MULTDMULTD要确认要确认 时的状态。时的状态。 LDLDF6,3