1、2014.2.17计算机系统结构1第第5 5章章 指令级并行硬件方法（指令级并行硬件方法（P111P111）（指令级，多发射或乱序执行，动态调度）指令级，多发射或乱序执行，动态调度）本章学习由硬件（即流水线控制器）实现的指令级并行方法，本章学习由硬件（即流水线控制器）实现的指令级并行方法，主要内容是流水线的多指令控制技术，目的是让处理机中同时流动主要内容是流水线的多指令控制技术，目的是让处理机中同时流动更多的指令，减少各种原因造成的停顿，以缩短程序执行时间。更多的指令，减少各种原因造成的停顿，以缩短程序执行时间。5.1 5.1 指令级并行的概念（重点）指令级并行的概念（重点）5.2 5.2 相
2、关与指令级并行相关与指令级并行5.3 5.3 指令的动态调度指令的动态调度5.4 5.4 动态分支预测技术（重点）动态分支预测技术（重点）5.5 5.5 多指令流出技术（重点）多指令流出技术（重点）2014.2.17计算机系统结构2从执行程序的角度来看，并行性等级从低到高可分为：从执行程序的角度来看，并行性等级从低到高可分为：指令内部并行：单条指令中各微操作之间的并行。指令内部并行：单条指令中各微操作之间的并行。指令级并行：并行执行两条或两条以上的指令。指令级并行：并行执行两条或两条以上的指令。线程级并行：并行执行两个或两个以上的线程。通常是以一个进程线程级并行：并行执行两个或两个以上的线程。
3、通常是以一个进程内派生的多个线程为调度单位。内派生的多个线程为调度单位。任务级或过程级并行：并行执行两个或两个以上的过程或任务（程任务级或过程级并行：并行执行两个或两个以上的过程或任务（程序段）。以子程序或进程为调度单元。序段）。以子程序或进程为调度单元。作业或程序级并行：并行执行两个或两个以上的作业或程序。作业或程序级并行：并行执行两个或两个以上的作业或程序。并行性等级的划分（并行性等级的划分（P23P23，1.5.11.5.1节）节）2014.2.17计算机系统结构3指令级并行的英文缩写是指令级并行的英文缩写是ILP（Instruction-Level Parallelism）开发开发IL
4、P的途径有两种：的途径有两种：q 资源重复，重复设置多个处理部件，让它们同时执行相邻或相近的资源重复，重复设置多个处理部件，让它们同时执行相邻或相近的多条指令；多条指令；q 采用流水线技术，使指令重叠并行执行。采用流水线技术，使指令重叠并行执行。(1)狭义指令级并行狭义指令级并行 超标量超标量SuperScalar（设备重复）设备重复）超长指令字超长指令字Very Long Instruction Word（简称简称VLIW）(2)广义指令级并行广义指令级并行 流水线流水线Pipeline（设备细分）设备细分）超级流水线超级流水线Super Pipeline(3)线程级并行线程级并行 超线程超
5、线程Hyper-Threading（简称简称HT）(4)任务线程任务线程 多核处理机多核处理机Multicore5.1 5.1 指令级并行的概念指令级并行的概念2014.2.17计算机系统结构4 静态调度（软件方法）：在程序执行前，在编译过程中对目标指令静态调度（软件方法）：在程序执行前，在编译过程中对目标指令序列进行优化，避免将来由于相关和冲突造成的停顿。主要手段是将序列进行优化，避免将来由于相关和冲突造成的停顿。主要手段是将冲突指令错开启动时间、变量换名等。冲突指令错开启动时间、变量换名等。动态调度（硬件方法）：在程序执行中，由专门硬件预测将要发生动态调度（硬件方法）：在程序执行中，由专门
6、硬件预测将要发生的冲突、控制指令在流水线中的流动，避免停顿。的冲突、控制指令在流水线中的流动，避免停顿。2.流水线处理机的实际流水线处理机的实际CPI=理想流水线的理想流水线的CPI加上各类停顿的时钟周期加上各类停顿的时钟周期数：数：CPI流水线流水线=CPI理想理想+停顿停顿结构冲突结构冲突+停顿停顿数据冲突数据冲突+停顿停顿控制冲突控制冲突 CPI理想理想是衡量流水线最高性能的一个指标。本式表明降低实际是衡量流水线最高性能的一个指标。本式表明降低实际CPI有许有许多途径。多途径。换一个角度，有时从换一个角度，有时从CPICPI的倒数看问题会有新思路，的倒数看问题会有新思路，IPCIPC（I
7、nstructions Per Instructions Per CycleCycle）是每个时钟周期完成的指令条数。是每个时钟周期完成的指令条数。在不能缩短单条指令周期数的情况下，在每个时钟周期里启动更多的指令（在不能缩短单条指令周期数的情况下，在每个时钟周期里启动更多的指令（提高提高IPCIPC），），同样可以提高处理机的性能。这就是同样可以提高处理机的性能。这就是ILPILP的基本思想。的基本思想。1.1.开发开发ILPILP的方法分类的方法分类2014.2.17计算机系统结构5 基本程序块：一串连续的代码除了入口和出口以外，没有其他的分基本程序块：一串连续的代码除了入口和出口以外，没有
8、其他的分支指令和转入点支指令和转入点。程序平均每程序平均每47条指令就会有一个分支。条指令就会有一个分支。4.循环级并行：使一个循环中的不同循环体并行执行。循环级并行：使一个循环中的不同循环体并行执行。开发循环的不同叠代之间存在的并行性（最常见、最基本思路）开发循环的不同叠代之间存在的并行性（最常见、最基本思路）这是指令级并行研究的重点之一这是指令级并行研究的重点之一5.最基本的开发循环级并行的技术最基本的开发循环级并行的技术 循环展开（循环展开（loop unrolling）技术技术 采用向量指令和向量数据表示采用向量指令和向量数据表示3.3.基本程序块基本程序块2014.2.17计算机系统
9、结构6多发射技术（多发射技术（Multiple Issue）：）：同时启动多条指令。同时启动多条指令。为什么要多发射？在传统流水线上，要减少为什么要多发射？在传统流水线上，要减少CPU时间，可以减少时间，可以减少CPI或者或者Cycle。CPI的下限是的下限是1，减少，减少Cycle碰到了碰到了“4G墙墙”（指（指Intel公司开发公司开发4GHz P4计划失败，因为功耗正比于主频计划失败，因为功耗正比于主频3次方），工程师们无奈又回头来次方），工程师们无奈又回头来打打CPI的主意，想使的主意，想使CPI低于低于1，即在一个时钟周期内流出多条指令。，即在一个时钟周期内流出多条指令。狭义的多指令
10、流出技术（同时启动）包括超标量狭义的多指令流出技术（同时启动）包括超标量(Superscalar)和超长和超长指令字指令字(VLIW)，广义的多指令流出技术（分时启动）还包括超流水线广义的多指令流出技术（分时启动）还包括超流水线(Superpipeline)等。等。超标量采用多条流水线的多发射技术，每个时钟周期流出的指令数不超标量采用多条流水线的多发射技术，每个时钟周期流出的指令数不定，既可以使用编译器静态调度，也可以使用硬件动态调度。定，既可以使用编译器静态调度，也可以使用硬件动态调度。由于管理乱由于管理乱序流动中指令相关问题的硬件复杂度非常大，所以目前超标量序流动中指令相关问题的硬件复杂度
11、非常大，所以目前超标量CPU的的ILP没有超过没有超过8的。的。采用单发射技术的传统处理机又被称为采用单发射技术的传统处理机又被称为“标量处理机标量处理机”。5.5 5.5 多指令流出技术（又称多发射技术，多指令流出技术（又称多发射技术，P141P141）2014.2.17计算机系统结构7超长指令字超长指令字CPU采用长指令单发射，多个执行部件同时执行小指令的采用长指令单发射，多个执行部件同时执行小指令的方法，每个时钟周期流出的小指令数是限定的。在编译过程中，由编译程方法，每个时钟周期流出的小指令数是限定的。在编译过程中，由编译程序来判断实际指令之间的相关关系，进行静态调度，把抽取序来判断实际
12、指令之间的相关关系，进行静态调度，把抽取ILP的复杂工的复杂工作转移给编译器，而执行指令的硬件则大大简化，也比较规则，有利于低作转移给编译器，而执行指令的硬件则大大简化，也比较规则，有利于低功耗设计。功耗设计。超流水线则是将每个功能部件进一步流水化，使得一个功能部件在一超流水线则是将每个功能部件进一步流水化，使得一个功能部件在一拍中可以分时处理多条指令。拍中可以分时处理多条指令。5.5 5.5 多指令流出技术（续多指令流出技术（续）2014.2.17计算机系统结构85.5.0 超标量技术：一个时钟节拍内超标量技术：一个时钟节拍内同时同时发射多条指令（发射多条指令（P142第第1段）。段）。时空
13、图时空图 指令999988887777666655554444333322221111123456节拍“超标量超标量”的前身是的前身是“多操作部件技术多操作部件技术”。它是通过它是通过“设备并联设备并联”技术技术扩充的单流水线，被扩充的部件通常是运算部件、访存部件等扩充的单流水线，被扩充的部件通常是运算部件、访存部件等“瓶颈瓶颈”部件。部件。2014.2.17计算机系统结构95.5.3 超长指令字技术超长指令字技术VLIW（P147，P163）把多条无相关关系的常规指令打包在一个超长的指令字中，让它们同时把多条无相关关系的常规指令打包在一个超长的指令字中，让它们同时被处理，分别控制多个功能部件
14、并行工作的技术。被处理，分别控制多个功能部件并行工作的技术。每个操作放在一个槽（每个操作放在一个槽（slot）内。内。这种技术的实质，是把超标量技术中的相关性识别任务，由这种技术的实质，是把超标量技术中的相关性识别任务，由CPU硬件转硬件转移给程序员或编译程序去实现。移给程序员或编译程序去实现。指令 1 指令 2.指令 n 2014.2.17计算机系统结构105.5.5 超流水技术：一个时钟节拍内超流水技术：一个时钟节拍内分时分时发射多条指令（发射多条指令（P149）时空图时空图 指令999988887777666655554444333322221111123456节拍2014.2.17计算
15、机系统结构11附：超线程技术附：超线程技术HT通俗的理解就是将一颗具有超线程功能的通俗的理解就是将一颗具有超线程功能的“实体实体”处理器虚拟成两个处理器虚拟成两个“逻辑逻辑”处理器，让多个应用程序或单一应用程序的多个线程，能够同时在同处理器，让多个应用程序或单一应用程序的多个线程，能够同时在同一颗处理器上执行。一颗处理器上执行。超线程运行模式下，超线程运行模式下，CPU中核心资源的利用率可提高中核心资源的利用率可提高3040%，也就是，也就是说在同样时间里可多执行说在同样时间里可多执行3040%的指令，其性能可以与含双处理器的系统的指令，其性能可以与含双处理器的系统相媲美，但具有低得多的价格。
16、相媲美，但具有低得多的价格。为了同时执行多个线程，使用超线程技术的新一代为了同时执行多个线程，使用超线程技术的新一代P4 HT处理器需要增加处理器需要增加一个逻辑处理器单元。因此面积比以往的一个逻辑处理器单元。因此面积比以往的P4增大了增大了5%。而其余部分如。而其余部分如ALU（整数运算单元）、整数运算单元）、FPU（浮点运算单元）、浮点运算单元）、L2 Cache（二级缓存）则保持不二级缓存）则保持不变，这些部分是被分享的。变，这些部分是被分享的。虽然采用超线程技术能同时执行两个线程，但是当两个线程争夺同一资虽然采用超线程技术能同时执行两个线程，但是当两个线程争夺同一资源时，其中一个要被阻
17、塞，这时性能就不如两个真正的源时，其中一个要被阻塞，这时性能就不如两个真正的CPU。含有超线程技术的含有超线程技术的CPU需要主板（包括芯片组和需要主板（包括芯片组和BIOS）、）、软件（包括操软件（包括操作系统和应用软件，如作系统和应用软件，如XP）支持，才能比较理想地发挥该项技术的优势。支持，才能比较理想地发挥该项技术的优势。超线程是一种过渡技术，不久就被多核心技术取代。超线程是一种过渡技术，不久就被多核心技术取代。2014.2.17计算机系统结构12对于多指令流出的处理机，分支等待造成的性能下降比单流出机器更对于多指令流出的处理机，分支等待造成的性能下降比单流出机器更为显著为显著每停一拍
18、要减少几条指令，所以需要采取更复杂的解决办法。每停一拍要减少几条指令，所以需要采取更复杂的解决办法。第第3 3章介绍了避免在分支（包括无条件跳转）指令后面空等待的几种章介绍了避免在分支（包括无条件跳转）指令后面空等待的几种方法。方法。其中其中“在在IDID周期完成判断并计算目标地址周期完成判断并计算目标地址”的方法把分支等待周期由的方法把分支等待周期由3 3个减少到个减少到1 1个，但是再要消除这个，但是再要消除这1 1个等待周期就很难了。有的处理机做这个等待周期就很难了。有的处理机做这两件事需要的周期数还不止两件事需要的周期数还不止1 1个。个。从上文调换不相关指令到从上文调换不相关指令到“
19、延迟槽延迟槽”执行的办法固然可以避免这段时执行的办法固然可以避免这段时间的空等待，但是找不到不相关指令就不能用。间的空等待，但是找不到不相关指令就不能用。为了利用这种等待周期，还有一个办法是为了利用这种等待周期，还有一个办法是“猜测猜测”，不等，不等“判跳判跳”完完成就开始取下条指令，取完之后成就开始取下条指令，取完之后“判跳判跳”结果也出来了，如果证明结果也出来了，如果证明“猜对猜对”就继续执行这条指令，就继续执行这条指令，“猜错猜错”就报废它。就报废它。为了容易实现，一个为了容易实现，一个CPUCPU在设计时就把在设计时就把“猜猜”的方向设定了，即总是的方向设定了，即总是猜分支失败（或者总
20、是猜分支成功），这种猜法的猜分支失败（或者总是猜分支成功），这种猜法的“猜对率猜对率”没有保障。没有保障。5.4 5.4 动态分支预测技术（动态分支预测技术（P133P133）2014.2.17计算机系统结构13现在讨论的现在讨论的“动态分支预测技术动态分支预测技术”就是对每条分支指令完成之后的真就是对每条分支指令完成之后的真实方向进行记录，下次再回到这条指令时就往上次的同一方向猜，猜对的实方向进行记录，下次再回到这条指令时就往上次的同一方向猜，猜对的可能性就增大了。万一有的指令是一会儿总是分支失败，一会儿又总是分可能性就增大了。万一有的指令是一会儿总是分支失败，一会儿又总是分支成功（动态变化
21、），那也可以在猜错后及时修改记录，以后就按新的方支成功（动态变化），那也可以在猜错后及时修改记录，以后就按新的方向猜。向猜。“分支开销分支开销”指指“猜对猜对”、“猜错猜错”两种情况下流水线分别等待的时两种情况下流水线分别等待的时间（周期数）。显然，间（周期数）。显然，“猜错猜错”时的开销更大，否则时的开销更大，否则“猜猜”就没有意义了就没有意义了。5.4 5.4 动态分支预测技术（续）动态分支预测技术（续）i-1 i i+1 i+2 p+1 p+2 猜测执行路径 实际执行路径 分支指令 得到分支结果 2014.2.17计算机系统结构14 分支历史表的英文缩写是分支历史表的英文缩写是BHT（B
22、ranch History Table）(1)1位位BHT方法方法表中给最近遇到的每条分支指令分配表中给最近遇到的每条分支指令分配1个个bit的记录单元，的记录单元，0表示上次分支表示上次分支不成功，不成功，1表示上次分支成功。表示上次分支成功。BHT表可以设在指令表可以设在指令Cache中，也可以用一个专门的中，也可以用一个专门的RAM来实现。查表来实现。查表方法是相联比较。表的容量决定了能为多少个方法是相联比较。表的容量决定了能为多少个“最近用到最近用到”的分支指令记录的分支指令记录历史信息。装满之后可以按历史信息。装满之后可以按“先进先出先进先出”或或“最近最少使用最近最少使用”策略进行
23、替换策略进行替换。5.4.1 5.4.1 分支历史表分支历史表 BHT BHT 方法（方法（P134P134）分分支支指指令令地地址址 分分支支方方向向（0 失失败败/1 成成功功）xxxxxxxx 0 xxxxxxxx 1.xxxxxxxx 0 11111111 无无意意义义 2014.2.17计算机系统结构15(2)2位位BHT方法方法有的分支指令会有有的分支指令会有“临时性换向临时性换向”，比如一段循环程序末尾的，比如一段循环程序末尾的“返回返回指令指令”可能在可能在n-1次分支成功后跟次分支成功后跟1次分支失败，但是下一次再执行这段循次分支失败，但是下一次再执行这段循环程序，环程序，“
24、返回指令返回指令”又应该按分支成功猜测。为了避免又应该按分支成功猜测。为了避免“1位位BHT方法方法”被这种偶然变化所被这种偶然变化所“欺骗欺骗”，可以使用，可以使用2bit信息记录，只有连续信息记录，只有连续2次次“猜错猜错”才会才会“改口改口”猜另一方向。具体算法见下图。猜另一方向。具体算法见下图。5.4.1 5.4.1 分支历史表分支历史表 BHT BHT 方法（续）方法（续）预预测测分分支支：成成功功 预预测测分分支支：不不成成功功 00 01 分分支支成成功功 分分支支不不成成功功 分分支支成成功功 分分支支不不成成功功 10 11 分分支支成成功功 分分支支不不成成功功 分分支支成
25、成功功 分分支支不不成成功功 2014.2.17计算机系统结构16分支目标缓冲器分支目标缓冲器的英文缩写是的英文缩写是BTB（Branch-Target Buffer），），也称分也称分支目标支目标Cache（ranch-Target Cache）。）。上面介绍的上面介绍的BHT表只保存了分支指令地址和成功转移的方向，没有保表只保存了分支指令地址和成功转移的方向，没有保存成功转移的目标地址，即只猜存成功转移的目标地址，即只猜“是否转移是否转移”，不猜，不猜“转到哪里转到哪里”，在转，在转移成功情况下即使移成功情况下即使“猜对了猜对了”也需要另花时间计算目标地址，这对于判断也需要另花时间计算目标
26、地址，这对于判断分支方向和计算目标地址同时进行的机器来说起不到节省时间的作用。分支方向和计算目标地址同时进行的机器来说起不到节省时间的作用。分支目标缓冲器分支目标缓冲器BTB表里面增加了成功转移的目标地址，如果表里面增加了成功转移的目标地址，如果“猜猜”本次转移成功就可以立即用它取指，不等待目标地址的计算结果，而本次转移成功就可以立即用它取指，不等待目标地址的计算结果，而“猜猜”本次分支失败则不需要使用目标地址。所以本次分支失败则不需要使用目标地址。所以BTB表只保存成功的分支指表只保存成功的分支指令地址及其目标地址，不保存失败的分支指令。遇到分支指令要令地址及其目标地址，不保存失败的分支指令
27、。遇到分支指令要“猜猜”时时，采用并行比较来搜索，搜到匹配项猜，采用并行比较来搜索，搜到匹配项猜“分支成功分支成功”，没有匹配项猜，没有匹配项猜“分分支失败支失败”，而后者不需要，而后者不需要BTB提供目标地址。提供目标地址。5.4.2 5.4.2 分支目标缓冲器分支目标缓冲器BTBBTB方法方法2014.2.17计算机系统结构17BTBBTB表的结构：表的结构：分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续1 1）BTB 表表 查找字段查找字段 读出字段读出字段 成功转移指令的地址成功转移指令的地址 1 转向的目标地址转向的目标地址 1 成功转移指令的地址成功转移指令的地址 2 转
28、向的目标地址转向的目标地址 2 下条指令地址下条指令地址（送（送PCPC去）去）匹配成功匹配成功信号信号比较器比较器当前指令地址当前指令地址（从（从PCPC来）来）比较器比较器比较器比较器2014.2.17计算机系统结构18BTBBTB预测方法逻辑分支图：预测方法逻辑分支图：分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续2 2）否否（预测错误）（预测错误）是是（预测错误）（预测错误）IDID周期：周期：IFIF周期：周期：是是（预测（预测“转移转移”）否否（预测（预测“不转移不转移”）启动启动BTBBTB表查找成功表查找成功（命中）？（命中）？取当前指令；查找取当前指令；查找BTBB
29、TB表表当前指令译码；取下条指令当前指令译码；取下条指令IDID周期：周期：当前指令译码；取下条指令当前指令译码；取下条指令BTBBTB表添加一条记录，需若干拍；表添加一条记录，需若干拍；重取下条指令，又需重取下条指令，又需1 1拍拍当前指令转移成功？当前指令转移成功？当前指令转移成功？当前指令转移成功？否否（预测正确）（预测正确）是是（预测正确）（预测正确）延迟延迟0 0拍拍延迟若干拍延迟若干拍+1+1延迟延迟0 0拍拍BTBBTB表删减一条记录，需若干拍；表删减一条记录，需若干拍；重取下条指令，又需重取下条指令，又需1 1拍拍延迟若干拍延迟若干拍+1+12014.2.17计算机系统结构19
30、BTBBTB预测机构加入到流水线中：预测机构加入到流水线中：分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续3 3）相对跳转距离相对跳转距离IF/IDIF/IDBTBBTB命中？命中？BTB 表表 源源址址 目目址址 指令指令存储器存储器MUXMUXMUXMUXPCPC4 4NPCNPCIRIR判跳成功？判跳成功？寄存器组寄存器组符号位扩展符号位扩展IFIF段段IDID段段2014.2.17计算机系统结构20现在现在分析采用分析采用BTB预测方法的加速效果，预测方法的加速效果，以以第第3章末尾（章末尾（P90）的改进的改进后的后的MIPS流水线为例流水线为例。在采用在采用BTB预测方法
31、之前，该流水线在预测方法之前，该流水线在ID周期进行分支判断与计算目周期进行分支判断与计算目标地址，到标地址，到EX周期才能取下一条指令，所以每条转移指令之后有周期才能取下一条指令，所以每条转移指令之后有1个周期个周期的固定延迟。的固定延迟。采用采用BTB预测方法之后，不同情况下的延迟周期数是不同的，下面分预测方法之后，不同情况下的延迟周期数是不同的，下面分4种情形讨论。种情形讨论。分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续4 4）2014.2.17计算机系统结构21情形情形1 1：BTBBTB命中，指令命中，指令K K转移转移 延迟延迟=0=0分支目标缓冲器分支目标缓冲器BTB
32、BTB方法（续方法（续5 5）IFIFIDIDEXEXMemMemWBWBIFIFIDIDEXEXMemMemWBWB指令指令K K指令指令L L1.1.指令指令K K取指，取指，PC+4PC+4；2.2.使用指令使用指令K K的地址，的地址，检索检索BTBBTB表，命中，表表，命中，表明指令明指令K K上次转移成功上次转移成功，猜此次仍转移，猜此次仍转移，PCPC指令指令L L的地址的地址1.1.指令指令K K译码、判断转移、译码、判断转移、计算转移目标地址；计算转移目标地址；2.2.判断结果是：转移。所判断结果是：转移。所以以“试取指令试取指令L”L”有效；有效；3.3.不改不改BTBBT
33、B表，猜指令表，猜指令K K下下次仍转移到指令次仍转移到指令L L使用使用PCPC值，试取指值，试取指令令L L（有效）有效）2014.2.17计算机系统结构22情形情形2 2：BTBBTB命中，指令命中，指令K K不转移不转移 延迟延迟=2=2分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续6 6）IFIFIDIDEXEXMemMemWBWBIDIDEXEXMemMemWBWB指令指令K K指令指令L L1.1.指令指令K K取指，取指，PC+4PC+4；2.2.使用指令使用指令K K的地址，的地址，检索检索BTBBTB表，命中，表表，命中，表明指令明指令K K上次转移成功上次转移成
34、功，猜此次仍转移，猜此次仍转移，PCPC指令指令L L的地址的地址1.1.指令指令K K译码、判断转移、译码、判断转移、计算转移目标地址；计算转移目标地址；2.2.判断结果是：不转移。所判断结果是：不转移。所以以“试取指令试取指令L”L”无效，须无效，须报废；报废；3.3.PCPC指令指令L L的地址的地址+4+4使用使用PCPC值，试取值，试取指令指令L L（无效）无效）StrStrIFIF指令指令K+1K+1使用新使用新PCPC值值，改改取指令取指令K+1K+1删除删除BTBBTB表该项，猜表该项，猜指令指令K K下次不转移下次不转移IFIF2014.2.17计算机系统结构23情形情形3
35、3：BTBBTB不命中，指令不命中，指令K K转移转移 延迟延迟=2=2分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续7 7）IFIFIDIDEXEXMemMemWBWBIDIDEXEXMemMemWBWB指令指令K K指令指令K+1K+11.1.指令指令K K取指，取指，PC+4PC+4；2.2.使用指令使用指令K K的地址，的地址，检索检索BTBBTB表，不命中，表，不命中，表明指令表明指令K K上次没有转上次没有转移，猜此次仍不转移移，猜此次仍不转移，不改，不改PCPC1.1.指令指令K K译码、判断转移译码、判断转移、计算转移目标地址；、计算转移目标地址；2.2.判断结果是：
36、转移。判断结果是：转移。所以所以“试取指令试取指令K+1”K+1”无无效，须报废；效，须报废；3.3.PCPC指令指令L L的地址的地址使用使用PCPC值，试取值，试取指令指令K+1K+1（无效）无效）StrStrIFIF指令指令L L使用新使用新PCPC值值，改改取指令取指令L LBTBBTB表增添一项，猜指令表增添一项，猜指令K K下次转移到指令下次转移到指令L LIFIF2014.2.17计算机系统结构24情形情形4 4：BTBBTB不命中，指令不命中，指令K K不转移不转移 延迟延迟=0=0分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续8 8）IFIFIDIDEXEXMemM
37、emWBWBIFIFIDIDEXEXMemMemWBWB指令指令K K指令指令K+1K+11.1.指令指令K K取指，取指，PC+4PC+4；2.2.使用指令使用指令K K的地址，的地址，检索检索BTBBTB表，不命中，表，不命中，表明指令表明指令K K上次没有转上次没有转移，猜此次仍不转移移，猜此次仍不转移，不改，不改PCPC1.1.指令指令K K译码、判断转移、译码、判断转移、计算转移目标地址；计算转移目标地址；2.2.判断结果是：不转移。判断结果是：不转移。所以所以“试取指令试取指令K+1”K+1”有效有效；3.3.不改不改BTBBTB表，猜指令表，猜指令K K下下次仍不转移次仍不转移使
38、用使用PCPC值，试取指值，试取指令令K+1K+1（有效）有效）注意：该情形包括当前指令是转移指令但不成功、当前指令不是转移指令注意：该情形包括当前指令是转移指令但不成功、当前指令不是转移指令两种情况。两种情况。2014.2.17计算机系统结构25小结：小结：可见，与不用可见，与不用BTBBTB的时序相比，情形的时序相比，情形1 1、4 4减少了延迟，而情形减少了延迟，而情形2 2、3 3增增加了延迟。加了延迟。我们可以这样计算：我们可以这样计算：平均转移延迟平均转移延迟=情形情形1 1概率概率0+0+情形情形2 2概率概率2+2+情形情形3 3概率概率2+2+情形情形1 1概率概率0 0如果
39、平均值小于如果平均值小于1 1，则新方法加快了转移指令执行速度，反之则减慢，则新方法加快了转移指令执行速度，反之则减慢了速度。了速度。分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续9 9）名名称称 BTB 命命中中情情况况 预预测测 指指令令判判跳跳结结果果 延延迟迟周周期期 情情形形 1 命命中中 成成功功 成成功功 0 情情形形 2 命命中中 成成功功 不不成成功功 2 情情形形 3 不不命命中中 成成功功 2 情情形形 4 不不命命中中 不不成成功功 0 2014.2.17计算机系统结构26采用采用BTB预测方法后的预测方法后的CPI计算公式：计算公式：平均平均CPI=CPI=
40、理想理想CPI+CPI+平均延迟周期数平均延迟周期数由于平均由于平均CPICPI针对所有指令，所以还要把非转移指令也考虑进去，如下图针对所有指令，所以还要把非转移指令也考虑进去，如下图分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续1010）所有指令所有指令转移指令转移指令非转移指令（非转移指令（BTBBTB必不命中，本次必不转移）必不命中，本次必不转移）BTBBTB命中命中BTBBTB不命中不命中本次不转移本次不转移 BTBBTB不命中，不转移：不命中，不转移：0 0拍拍本次转移本次转移 BTBBTB命中，转移：命中，转移：0 0拍拍本次不转移本次不转移 BTBBTB命中，不转移：命
41、中，不转移：若干拍若干拍+1+1本次转移本次转移 BTBBTB不命中，转移：不命中，转移：若干拍若干拍+1+12014.2.17计算机系统结构27例例5.6 5.6 设程序中转移指令占设程序中转移指令占20%20%，50%50%可以在可以在BTBBTB命中，命中的指令本次转命中，命中的指令本次转移概率为移概率为90%90%，未命中的指令本次转移概率为，未命中的指令本次转移概率为60%60%，判断转移并计算地址的，判断转移并计算地址的开销是开销是2 2，修改，修改BTBBTB的开销是的开销是1 1，非转移指令的，非转移指令的CPI=1CPI=1。求平均求平均CPICPI。解：解：分支目标缓冲器分
42、支目标缓冲器BTBBTB方法（续方法（续1111）所有指令所有指令转移指令转移指令非转移指令（非转移指令（BTBBTB必不命中，本次必不转移）必不命中，本次必不转移）BTBBTB命中命中BTBBTB不命中不命中本次不转移本次不转移 BTBBTB不命中，不转移：不命中，不转移：0 0拍拍本次转移本次转移 BTBBTB命中，转移：命中，转移：0 0拍拍本次不转移本次不转移 BTBBTB命中，不转移：命中，不转移：2+12+1拍拍本次转移本次转移 BTBBTB不命中，转移：不命中，转移：2+12+1拍拍20%20%80%80%50%50%50%50%90%90%10%10%60%60%40%40%平
43、均平均CPI=1+20%CPI=1+20%50%50%(90%(90%0+10%0+10%3)+3)+50%+50%(60%(60%3+40%3+40%0)0)=1.21=1.212014.2.17计算机系统结构28如果不采用如果不采用BTBBTB预测方法，每条转移指令无论是否成功，都有预测方法，每条转移指令无论是否成功，都有2 2个周期个周期的固定延迟。的固定延迟。平均平均CPI=1+20%CPI=1+20%2=1.402=1.40可见，采用可见，采用BTBBTB预测方法有可能缩短平均预测方法有可能缩短平均CPICPI。分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续1212）201
44、4.2.17计算机系统结构295.85.8题假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。题假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为假设分支预测错误的开销为4 4个时钟周期，缓冲不命中的开销为个时钟周期，缓冲不命中的开销为3 3个时钟周个时钟周期。假设：命中率为期。假设：命中率为90%90%，预测精度为，预测精度为90%90%，分支频率为，分支频率为15%15%，没有分支的，没有分支的基本基本CPICPI为为1 1。(1)(1)求程序执行的求程序执行的CPICPI。(2)(2)相对于采用固定的相对于采用固定的2 2个时钟周期延迟的分支处理，采用
45、哪种方法能使程个时钟周期延迟的分支处理，采用哪种方法能使程序执行速度更快？序执行速度更快？分析：分析：分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续1313）所有指令所有指令转移指令转移指令非转移指令（非转移指令（BTBBTB必不命中，本次必不转移）必不命中，本次必不转移）BTBBTB命中命中BTBBTB不命中不命中本次不转移本次不转移 0 0拍拍本次转移本次转移 BTBBTB命中，转移：命中，转移：0 0拍拍本次不转移本次不转移 BTBBTB命中，不转移：命中，不转移：4 4拍拍本次转移本次转移 15%15%85%85%90%90%10%10%90%90%10%10%平均：平均：3
46、 3拍拍2014.2.17计算机系统结构305.95.9题假设分支目标缓冲的命中率为题假设分支目标缓冲的命中率为90%90%，程序中无条件转移指令的比例，程序中无条件转移指令的比例为为5%5%，没有无条件转移指令的程序，没有无条件转移指令的程序CPICPI值为值为1 1。假设分支目标缓冲中包含分。假设分支目标缓冲中包含分支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPICPI值为值为多少？假设原来的多少？假设原来的CPI=1.1CPI=1.1。分析：本题只考虑无条件转移指令，所以取指后分析：本题只考虑无条件转移指令，所以取指后
47、100%100%会转移，会转移，BTBBTB命中开命中开销销=0=0拍，所缺的条件是不命中开销。再看，拍，所缺的条件是不命中开销。再看，“原来的原来的CPICPI”指使用指使用BTBBTB方法方法前的平均前的平均CPICPI，是是1.11.1，理想，理想CPI=1CPI=1，由此可以解出原来的转移开销。使用由此可以解出原来的转移开销。使用BTBBTB方法后的不命中开销比它多方法后的不命中开销比它多1 1拍。拍。分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续1414）所有指令所有指令转移指令转移指令非转移指令（非转移指令（BTBBTB必不命中，必不转移）必不命中，必不转移）0 0拍拍B
48、TBBTB命中（命中（100%100%必转移）必转移）0 0拍拍BTBBTB不命中（不命中（100%100%必转移）必转移）?拍拍5%5%95%95%90%90%10%10%2014.2.17计算机系统结构31思考题：思考题：5.85.8题：题：BTB“BTB“命中率为命中率为90%”90%”意味着什么？实际上有没有可能达到？意味着什么？实际上有没有可能达到？参考观点：参考观点：BTBBTB表中存放最近一次执行中转移成功的转移指令地址，它的表中存放最近一次执行中转移成功的转移指令地址，它的命中率指程序中包含的全部转移指令有百分之多少已经存入。显然，命中率指程序中包含的全部转移指令有百分之多少已
49、经存入。显然，“条条件转移指令命中率为件转移指令命中率为90%”90%”的情形只能是的情形只能是90%90%以上条件转移指令被执行过后以上条件转移指令被执行过后才可能出现，即程序运行的后期。我们要计算程序运行全程的平均才可能出现，即程序运行的后期。我们要计算程序运行全程的平均CPICPI，应该引用应该引用BTBBTB的平均命中率，通常应该在的平均命中率，通常应该在50%50%左右。左右。一些特殊程序中，一些特殊程序中，BTBBTB平均命中率也可能达到平均命中率也可能达到90%90%，比如高次数循环。，比如高次数循环。该题的设计者为了证明该题的设计者为了证明“BTBBTB方法能使程序执行速度更快
50、方法能使程序执行速度更快”，设定了，设定了特殊情况下的已知条件。特殊情况下的已知条件。5.95.9题：根据题：根据BTBBTB方法原理，方法原理，BTBBTB不命中开销不命中开销=指令本身的转移开销指令本身的转移开销+BTBBTB表修改开销（表修改开销（1 1拍），但是习题指导书中的题解没有加这拍），但是习题指导书中的题解没有加这1 1拍。拍。参考观点：该题解应该修正。参考观点：该题解应该修正。分支目标缓冲器分支目标缓冲器BTBBTB方法（续方法（续1515）2014.2.17计算机系统结构32各次作业应交的内容各次作业应交的内容作业作业6 6（第（第6 6次课）次课）5.115.11，5.8
