控制相关的动态解决技术ppt课件

1、1284.3 控制相关的动态处理技术 处置器一个时钟周期流出多条指令遭到以下两处置器一个时钟周期流出多条指令遭到以下两 个要素的限制：个要素的限制： 流出流出n n条指令的处置器中，遇到分支指令的条指令的处置器中，遇到分支指令的 速度也快了速度也快了n n倍；倍； 根据根据AmdahlAmdahl定律可知，随着机器定律可知，随着机器CPICPI的降低，的降低， 控制相关对性能的影响越来越大。控制相关对性能的影响越来越大。第四章 指令级并行228本节着重于：本节着重于： 经过硬件技术，动态地进展分支处置，对程经过硬件技术，动态地进展分支处置，对程序运转时的分支行为进展预测，提早对分支操作做序运转

2、时的分支行为进展预测，提早对分支操作做出反响，加快分支处置的速度。出反响，加快分支处置的速度。 分支的最终延迟取决于流水线的构造、预测的分支的最终延迟取决于流水线的构造、预测的方法和预测错误后恢复所采取的战略。方法和预测错误后恢复所采取的战略。 4.3 控制相关的动态处理技术3284.3.1 分支预测缓冲 动态分支预测必需处理两个问题：动态分支预测必需处理两个问题： 如何记录一个分支操作的历史。如何记录一个分支操作的历史。 决议预测的走向。决议预测的走向。 记录分支历史的方法有以下几种：记录分支历史的方法有以下几种： 1 1仅仅记录最近一次或最近几次的分支历仅仅记录最近一次或最近几次的分支历史

3、；史； 2 2记录分支胜利的目的地址；记录分支胜利的目的地址； 3 3记录分支历史和分支目的地址，相当于记录分支历史和分支目的地址，相当于前前 面两种方式的结合；面两种方式的结合； 4 4记录分支目的地址的一条或假设干条指记录分支目的地址的一条或假设干条指令。令。 4.3 控制相关的动态处理技术428分支预测缓冲技术分支预测缓冲技术Branch-Prediction BufferBranch-Prediction Buffer或者或者Branch History TableBranch History Table，简写为，简写为BTBBTB或者或者BHTBHT： 目前广泛运用的最简单的动态分支

4、预测技术。目前广泛运用的最简单的动态分支预测技术。 运用一片存储区域，记录最近一次或几次分支特运用一片存储区域，记录最近一次或几次分支特征的历史。征的历史。 1. 只需只需1个预测位的分支预测缓冲个预测位的分支预测缓冲 索引：分支指令地址的低位。索引：分支指令地址的低位。 存储区：存储区：1 1位的分支历史记录位，又称为位的分支历史记录位，又称为 预测位，记录该指令最近一次预测位，记录该指令最近一次 分支能否胜利。分支能否胜利。4.3 控制相关的动态处理技术528形状转换图形状转换图 “0 0记录分支不胜利记录分支不胜利 “1 1记录分支胜利记录分支胜利 1 0 分支不成功 分支成功 分支不成

5、功 分支成功 图图4.9 4.9 只需只需1 1个预测位的分支预测缓冲形状转换图个预测位的分支预测缓冲形状转换图 4.3 控制相关的动态处理技术6282. 2. 分支预测缓冲技术包括两个步骤分支预测缓冲技术包括两个步骤 分支预测分支预测 假设当前缓冲记录的预测位为假设当前缓冲记录的预测位为“1 1，那么，那么预预 测分为胜利；假设预测位为测分为胜利；假设预测位为“0 0，那么预测，那么预测分支分支为不胜利。为不胜利。预测位修正预测位修正 假设当前分支胜利，那么预测位置为假设当前分支胜利，那么预测位置为“1 1； 假设当前分支不胜利，预测位置为假设当前分支不胜利，预测位置为“0 0。 3.3.分

6、支预测错误时，预测位就被修正，并且需分支预测错误时，预测位就被修正，并且需 要恢复现场，程序从分支指令处重新执行。要恢复现场，程序从分支指令处重新执行。 4.3 控制相关的动态处理技术728 i-1 i i+1 i+2 p+1 p+2 猜测执行路径 实际执行路径 分支指令 得到分支结果 图图4.10 4.10 分支预测执行不胜利和重新执行过程分支预测执行不胜利和重新执行过程 4.3 控制相关的动态处理技术828例例4.6 4.6 一个循环共循环一个循环共循环1010次，它将分支胜利次，它将分支胜利9 9次，次， 1 1次不胜利。假设此分支的预测位一直在次不胜利。假设此分支的预测位一直在缓冲区中

7、。那么分支预测的准确性是多少？缓冲区中。那么分支预测的准确性是多少？ 解解 这种固定的预测将会在第一次和最后一次这种固定的预测将会在第一次和最后一次 循环中出现预测错误。循环中出现预测错误。 第一次预测错误是源于上次程序的执行，第一次预测错误是源于上次程序的执行， 由于上一次程序最后一次分支是不胜利的。由于上一次程序最后一次分支是不胜利的。 最后一次预测错误是不可防止的，由于前最后一次预测错误是不可防止的，由于前 面的分支总是胜利，共九次。面的分支总是胜利，共九次。 因此，虽然分支胜利的比例率是因此，虽然分支胜利的比例率是90%90%， 但分支预测的准确性为但分支预测的准确性为80%80%两次

8、不正确，两次不正确， 8 8次确。次确。 4.3 控制相关的动态处理技术9284.14.1位预测机制的缺陷位预测机制的缺陷 只需预测出错，往往是延续两次而不是一次。只需预测出错，往往是延续两次而不是一次。5.5.处理方法处理方法 采用两个预测位的预测机制。采用两个预测位的预测机制。 在两个预测位的分支预测中，更改对分支的在两个预测位的分支预测中，更改对分支的预测必需有两次延续预测错误。预测必需有两次延续预测错误。 两位分支预测的形状转换图两位分支预测的形状转换图4.3 控制相关的动态处理技术1028 分支预测： 不成功 分支预测： 成功 11 10 分支不成功 分支成功 分支不成功 分支成功

9、01 00 分支不成功 分支成功 分支不成功 分支成功 图图4.11 4.11 具有两个分支预测位的分支预测缓冲形状转换机制具有两个分支预测位的分支预测缓冲形状转换机制 4.3 控制相关的动态处理技术11286. n6. n位分支预测缓冲位分支预测缓冲采用采用n n位计数器，那么计数器的值在位计数器，那么计数器的值在0 0到到2n-12n-1之间：之间： 当计数器的值大于或等于最大值的一半当计数器的值大于或等于最大值的一半2n-12n-1时，那么预测下一次分支胜利；时，那么预测下一次分支胜利； 否那么预测下一次分支不胜利。否那么预测下一次分支不胜利。预测位的修正和两位预测时一样：预测位的修正和

10、两位预测时一样： 当分支胜利时计数器的值加当分支胜利时计数器的值加1 1，不胜利时减，不胜利时减1 1。研讨阐明：研讨阐明： n n位分支预测的性能和两位分支预测差不多，位分支预测的性能和两位分支预测差不多，因此大多数处置器都只采用两位分支预测。因此大多数处置器都只采用两位分支预测。4.3 控制相关的动态处理技术12287.7.对于真实的运用程序，两位的分支预测的准对于真实的运用程序，两位的分支预测的准确率可到达多少呢？确率可到达多少呢？ SPEC89SPEC89规范程序的测试：规范程序的测试： 在运用在运用40964096个记录项的缓冲区时，分支个记录项的缓冲区时，分支 预测准确率可到达预测

11、准确率可到达99%99%到到82%82%。 运用无穷多历史记录项的分支预测缓冲，运用无穷多历史记录项的分支预测缓冲， 只需少量程序的分支预测准确率仅仅比只需少量程序的分支预测准确率仅仅比40964096 个记录项提高个记录项提高1%1%，多数程序的预测精度是相，多数程序的预测精度是相 同的。同的。 因此，对于因此，对于SPEC89SPEC89运用环境而言，运用环境而言，4K4K的的 缓冲区是恰当的。缓冲区是恰当的。8.8.上述分支预测机制对于改良后的上述分支预测机制对于改良后的DLXDLX流水线没流水线没有协助。有协助。 4.3 控制相关的动态处理技术13284.3.2 分支目的缓冲 目的：将

12、分支的开销降为零。目的：将分支的开销降为零。方法：分支目的缓冲方法：分支目的缓冲 将分支胜利的分支指令的地址和它的分支目将分支胜利的分支指令的地址和它的分支目的地址都放到一个缓冲区中保管起来，缓冲区的地址都放到一个缓冲区中保管起来，缓冲区以分支指令的地址作为标示；取指令阶段，一以分支指令的地址作为标示；取指令阶段，一切指令地址都与保管的标示作比较，一旦一样，切指令地址都与保管的标示作比较，一旦一样，我们就以为本指令是分支指令，且以为它转移我们就以为本指令是分支指令，且以为它转移胜利，并且它的分支目的下一条指令地址胜利，并且它的分支目的下一条指令地址就是保管在缓冲区中的分支目的地址。就是保管在缓

13、冲区中的分支目的地址。 这个缓冲区就是分支目的缓冲区这个缓冲区就是分支目的缓冲区Branch-Branch-Target BufferTarget Buffer，简记为，简记为BTBBTB，或者，或者Branch-Branch-Target CacheTarget Cache。 4.3 控制相关的动态处理技术1. 1. 分支目的缓冲构造和任务过程分支目的缓冲构造和任务过程 N 命中？ 当前 PC 地址标示 分支目标 PC 分支目标指令 查找、比较 分支目标缓冲 没有命中，则认为本指令不是分支，按普通指令执行 Y 命中，则认为本指令是分支，且分支成功，以分支目标缓冲中分支目标 PC 作为下一条指

14、令地址 图图4.12 4.12 分支目的缓冲的构造和任务过程分支目的缓冲的构造和任务过程 2. 2. 在流水线的各个阶段中，具有分支目的缓冲的任务在流水线的各个阶段中，具有分支目的缓冲的任务 分配如图分配如图4.134.13。 当前 PC 值送存储器和 BTB BTB 中存在？ 成功分支指令？ 当前分支成功？ 以分支目标 PC 值送存储器 否 是 否 普通指令 是 是 否 预测成功，后续指令无延迟执行 预测错误，清除取来的指令并从分支的另外一个目标取指令，删除BTB 中对应项 将当前指令PC 值和分支目标PC 送入 BTB 中作为一个新项 取指令 指令译码 指令执行 问题：处理预测错误或不命中

15、的延迟。问题：处理预测错误或不命中的延迟。 16283. 3. 采用采用BTBBTB技术时指令在各种情况下的延迟技术时指令在各种情况下的延迟 指令在BTB中？是是不是不是预测结果胜利胜利实践的动作胜利不胜利胜利不胜利延迟周期0220表表4.3 4.3 采用采用BTBBTB技术时指令在各种情况下的延迟技术时指令在各种情况下的延迟 4.3 控制相关的动态处理技术1728例例4.7 4.7 按表按表4.34.3计算分支转移总的延迟，根据下面的假计算分支转移总的延迟，根据下面的假 设，计算分支目的缓冲的性能。设，计算分支目的缓冲的性能。 1 1对于对于BTBBTB中的指令，预测准确率中的指令，预测准确

16、率90%90% 2 2缓冲区命中率缓冲区命中率90%90% 3 3不在不在BTBBTB中分支转移胜利的比例为中分支转移胜利的比例为60% 60% 解解 根据表根据表4.34.3的分类，性能计算包括的分类，性能计算包括4 4个部分：个部分： 1 1在在BTBBTB中，预测胜利，实践胜利，此时的中，预测胜利，实践胜利，此时的 延迟为延迟为0 0。 2 2在在BTBBTB中，预测胜利，实践不胜利，此时中，预测胜利，实践不胜利，此时 的延迟为：的延迟为： 4.3 控制相关的动态处理技术1828 BTB BTB命中率命中率 预测错误率预测错误率 2 2 = 90% = 90% 10% 10% 2 2 =

17、 0.18 = 0.18时钟周期时钟周期3 3不在不在BTBBTB中，实践胜利，此时的延迟为：中，实践胜利，此时的延迟为：1-BTB1-BTB命中率命中率 不在不在BTBBTB中分支转移胜利中分支转移胜利率率 2 2 = 10% = 10% 60% 60% 2 2 = 0.12 = 0.12时钟周期时钟周期4 4不在不在BTBBTB中，实践不胜利，此时的延迟为中，实践不胜利，此时的延迟为0 0。4.3 控制相关的动态处理技术19284. 4. 对分支预测机制的一种改良对分支预测机制的一种改良 在缓冲区中不仅存入目的地址，而且还存入一在缓冲区中不仅存入目的地址，而且还存入一 个或多个目的指令。个

18、或多个目的指令。 有两种潜在的益处：有两种潜在的益处： 在延续取指令之前，可以较长时间的访问缓冲在延续取指令之前，可以较长时间的访问缓冲区，这时的分支目的缓冲区较大。区，这时的分支目的缓冲区较大。对目的指令进展缓冲，构成称为分支目的指令对目的指令进展缓冲，构成称为分支目的指令缓冲缓冲branch foldingbranch folding的构造，它可使无条的构造，它可使无条件分支的延迟到达零，甚至有的条件分支也可件分支的延迟到达零，甚至有的条件分支也可到达零延迟到达零延迟 。4.3 控制相关的动态处理技术20284.3.3 基于硬件的前瞻执行 前瞻前瞻SpeculationSpeculatio

19、n的技术方法：的技术方法： 它允许在处置器还未判别指令能否能执行它允许在处置器还未判别指令能否能执行之前就提早执行，以抑制控制相关。之前就提早执行，以抑制控制相关。 在大多数指令前瞻正确的前提下，前瞻就在大多数指令前瞻正确的前提下，前瞻就可以有效地加快分支处置的速度。可以有效地加快分支处置的速度。 1.1.基于硬件的前瞻执行结合了三种思想：基于硬件的前瞻执行结合了三种思想： 1 1采用动态的分支预测技术来选择后续执采用动态的分支预测技术来选择后续执 行语句；行语句；4.3 控制相关的动态处理技术2128 2 2在控制相关消除之前指令前瞻执行；在控制相关消除之前指令前瞻执行； 3 3对根本块采用

20、动态调度。对根本块采用动态调度。 2.2.基于硬件的前瞻是动态地根据数据相关性来选择基于硬件的前瞻是动态地根据数据相关性来选择指令和指令的执行时间。指令和指令的执行时间。 本质：数据流驱动运转本质：数据流驱动运转data-flow executiondata-flow execution 只需操作数有效，指令就可以执行。只需操作数有效，指令就可以执行。3.3.指令确实认指令确实认 前瞻执行的指令产生的结果要不断到指令处前瞻执行的指令产生的结果要不断到指令处于非前瞻执行形状时，才干确定为最终结果，才于非前瞻执行形状时，才干确定为最终结果，才允许最终写到存放器或存储器中去。允许最终写到存放器或存储

21、器中去。 4.3 控制相关的动态处理技术22284.4.实现前瞻的关键思想：实现前瞻的关键思想： 允许指令乱序执行，但必需顺序确认。允许指令乱序执行，但必需顺序确认。5.5.再定序缓冲再定序缓冲reorder bufferreorder buffer，简记为，简记为ROBROB 保管那些执行终了但未经确认的指令及其结保管那些执行终了但未经确认的指令及其结果。在指令执行终了和确认之间这段时间里，由果。在指令执行终了和确认之间这段时间里，由 再定序缓冲提供一切其他指令需求的作为操作数再定序缓冲提供一切其他指令需求的作为操作数的数据。再定序缓冲区还可以取代取的数据。再定序缓冲区还可以取代取loadl

22、oad缓缓 冲区。冲区。 4.3 控制相关的动态处理技术2328再定序缓冲的每个项包含三个域：再定序缓冲的每个项包含三个域： 1 1指令的类型指令的类型 指令类型包括能否是分支尚无结果、指令类型包括能否是分支尚无结果、 存操作目的地址为存储器或存放器操作存操作目的地址为存储器或存放器操作 ALUALU操作或目的地址是存放器的取操作。操作或目的地址是存放器的取操作。 2 2目的地址目的地址 目的地址域给出结果应写入的目的存放目的地址域给出结果应写入的目的存放 器号对于取操作和器号对于取操作和ALUALU指令或存储器的指令或存储器的地地 址存操作。址存操作。 3 3值域值域 值域用来保管指令前瞻执

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